Research Seminar in Discrete Mathematics and Algebra (DMA)

Current semester

• 5.11. Manuel Bodirsky (Dresden) : TBA
• 12.11. Will Turner : Temporal graphs
• 19.11. public holiday
• 7.1. Tim Planken : TBA
• 21.1. Andreas Thom (Dresden) : TBA
• 28.1. Sandra Albrechtsen (Leipzig) : TBA

Regular events

• SEG Workshop on Combinatorics, Graph Theory and Algorithms

Previous semesters

Summer Semester 2025

• 25.6. Romain Bourneuf (Bordeaux and Lyon): A Dense Neighborhood Lemma with Applications to Domination and Chromatic Number

  Abstract: In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of R^N such that for each point v in V the ball B(v,1) intersects V on at least delta*|V| points, then for every epsilon>0, the points of V can be covered with f(delta,epsilon) balls B(v,1+epsilon) with v in V.
  DNL applies to many other settings. In its strongest form, it provides an epsilon-clustering with size exponential in 1/epsilon, which amounts to a Regularity Lemma with 0/1 densities of some trigraph.
  I will discuss the notion of VC-dimension, and explain how to generalize it to trigraphs to obtain statements such as DNL. I will then discuss some applications of DNL to the chromatic number of dense triangle-free graphs, and to winning sets in elections.
  This is based on joint work with Pierre Charbit and Stéphan Thomassé.

• 18.6. Matthew Kroeker: Unavoidable flats in matroids representable over a finite field

  Abstract: For a positive integer k and finite field F, we prove that every simple F-representable matroid with sufficiently high rank has a rank-k flat which either is independent, or is a projective or affine geometry over a subfield of F. As a corollary, we obtain the following Ramsey theorem: given an F-representable matroid of sufficiently high rank and any 2-colouring of its points, there is a monochromatic rank-k flat. This is joint work with Jim Geelen and Peter Nelson.

• 13.6. at 15:45 in PRÜ-1104 Matthias Hamann (Hamburg): Grid minors in transitive graphs

  Abstract: In this talk, I will discuss strengethings of Halins result from 1965 that every graph with a thick end contains the half-grid as a minor. First, we will show that quasi-transitive, locally finite graphs contain the full-grid as a minor if and only if they are not quasi-isometric to a tree. Then, we will look at coarse variants for this, that is, we look at notions of minors that stay visible when looking at the large-scale geometry of the graph. For this, we define asymptotic and diverging minors and show that the above equivalence stays valid if we ask the cycle space of the graph to be generated by cycles of bounded length. It follows that all locally finite Cayley graphs of finitely presented groups that are not virtually free contain the full-grid as an asymptotic and as a diverging minor. As a byproduct of our proof, we will obtain a coarse variant of Halin's theorem for locally finite graphs satisfying the above mentioned condition on the cycle space but that need not be quasi-transitive.

  This is based on joint works with Agelos Georgakopoulos and with Sandra Albrechtsen.

• 13.6. at 14:30 in PRÜ-1104 Florian Hörsch (CISPA Helmholtz Center for Information Security, Germany): Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

  

• 11.6. Slawomir Solecki (Cornell): Simplicial complexes, stellar moves, projective amalgamation, and set theory

  Abstract: The talk will explore connections between stellar moves on simplicial complexes (these are fundamental operations of combinatorial topology), amalgamation classes (these classes of structures extensively studied in combinatorics), and projective Fra{\"i}ss{\'e} limits (this is a model theoretic construction with topological applications). We will also touch on relations between these topics and topological dynamics.
  The technical core of the talk will consist of identifying a class of simplicial maps that arise from the stellar moves of welding and subdividing. We call these maps weld-division maps. Our main theorem asserts that the category of weld-division maps fulfills the projective amalgamation property. As we will explain, the method of proof of the amalgamation theorem is new. It is not geometric or topological, but rather it consists of combinatorial calculations performed on finite sequences of finite sets. Set theoretic nature of the entries of the sequences is crucial to the arguments.

• 4.6. no seminar.
• 28.5. Waltraud Lederle (Dresden): Conservative actions and boomerang subgroups

  Abstract: In previous work, together with Yair Glasner, I introduced boomerang subgroups of countable groups. We prove that in many lattices, like in SL_n(Z), every boomerang subgroup is finite and central or has finite index; generalizing the Margulis Normal Subgroup theorem and providing a deterministic generalization of the Stuck-Zimmer rigidity theorem for these lattices. But few examples of boomerang subgroups are known and it seems not easy to construct them. In this talk, I will give not a concrete, but a generic construction using measurable full groups and conservative actions. Based on joint work with Yair Glasner and Tobias Hartnick.

• 21.5. Olga Varghese (Münster) : Automatic continuity

Abstract: The automatic continuity problem asks the following question: Given two topological groups $L$ and $G$ and an algebraic morphism $\varphi\colon L\to G$, can we find conditions on the groups $L$ and $G$ ensuring that $\varphi$ is continuous? In this talk we will give an introduction to this problem focusing on the case where $L$ is a locally compact Hausdorff group and $G$ is a geometric group.
• 14.5. Martin Winter (TU Berlin and MPL Leipzig): Adjoint degrees and scissors congruence for polytopes

  Abstract: Hilbert's Third Problem asks whether for any two (3-dimensional) polytopes there is a way to cut the first one into finitely many pieces and rearrange them to obtain the second one (that is, we ask whether the polytopes are "scissors congruent"). Its resolution by Max Dehn (with a negative answer) marks the beginning of valuation theory, which to this day provides often one of the most elegant approaches to problems in the geometric theory of polytopes. In this talk we take a look at a particular valuation of recent interest - the canonical form - and we shall explore what it can teach us about scissors congruence for polytopes. It will turn out that the degree of the the so-called adjoint polynomial is a fundamental parameter in this context. We investigate the polytope classes defined by their adjoint degrees. This is joined work with Tom Baumbach, Ansgar Freyer and Julian Weigert

• 7.5. Tangle Workshop

• 30.4. Maja Pech (University of Novi Sad): Characterizing XY-homogeneity
  
  
Abstract: The notion of homomorphism homogeneity was introduced in 2002 by Cameron and Nešetril. A relational structure U is called homomorphism homogeneous if every local homomorphism of U can be extended to an endomorphism of U. The notion of XY-homogeneity introduced in 2014 by Lockett and Truss generalizes the notion of homomorphism homogeneity. A relational structure U is called XY-homogeneous if every homomorphism of type X between finite substructures of U can be extended to an endomorphism of U of type Y. Here X and Y refer to certain standard classes of morphisms such as homomorphisms, monomorphisms, endomorphisms, etc. In this talk we use a notion of morphism classes X and Y that goes beyond the classification by Lockett and Truss. Our main results are two Fraisse-type theorems for XY-homogeneous structures, that extend and generalize the results by Coleman, Evans and Gray.


• 23.4. at 15:30 Benjamin Moore (IST): Flow Critical graphs

Abstract: A graph is flow critical if it does not have a nowhere zero 3 flow but identifying every pair of vertices results in a graph with a nowhere zero 3 flow. The Lovaaz Thomassen Wu Zhang theorem implies no 6 edge connected graph is flow critical. We give a very technical generalization of this theorem, which in particular implies every flow critical graph with at most one vertex of degree bigger than 7 has at most 3v(G) -5 edges. This is joint work with Arnbjorg Soffıa Arnadottir Zdenek Dvoraak , Bernard Lidicky , Benjamin Moore Evelyne Smith-Roberge and Robert Samal
• 16.4. Andrew Paul Moorhead (TU Dresden): Higher dimensional generalized quasiorders
  
  
Abstract: We are interested in clones on a finite set, where a (concrete) clone is a set of operations on some finite base set which is closed under composition and also contains all projection operations for every possible number of arguments. Clones have wide applications in mathematics, especially to algebra, the study of relational structures, and computational complexity theory (the so-called constraint satisfaction problem). Since clones have a wide scope of applicability, one correctly expects that their structure is complicated. Early in the 20th century, Post famously classified all of the clones on a two element set and provided a complete picture of their lattice order under containment. A detailed understanding of clones on finite sets with cardinality bigger than two remains a distant dream, since we know that in all other cases there are continuum many and the structure of this continuum is quite complicated. Many of the deeper insights into clone theory are obtained via a Galois connection relating operations to sets of invariant relations. The fundamental concept which mediates this Galois connection is that of preservation. A classical result of Maltsev states that an equivalence relation is preserved by an operation if and only if it is preserved by all basic translations of the operation, which are unary operations obtained by substituting all variables but one for a constant. Hence, we ask the question: for which relations is it sufficient to check preservation by higher arity analogues of these basic translations? Building on independent work of each of the authors, we develop the general framework of Higher Dimensional Generalized Quasiorders in which the classical result of Maltsev can be viewed as a (1)-dimensional example.


• 9.4. Roman Schaut (Hamburg): Displaying prescribed sets of ends by linked tree-decompositions
  
  
Abstract: Given a set of ends $\Psi$ in some graph that can be displayed by a tree-decomposition of finite adhesion, we give the construction of a linked, tight and componential tree-decomposition of finite adhesion that displays $\Psi$.

Winter Semester 2024/2025

• 23.10.2024 Various speakers: Open problems workshop.
  
  
• 30.10.2024 Will J. Turner : matroid reconstruction
  
  
• 6.11.2024 Olga Varghese (Düsseldorf) : Automatic continuity
  
  
Abstract: The automatic continuity problem asks the following question: Given two topological groups $L$ and $G$ and an algebraic morphism $\varphi\colon L\to G$, can we find conditions on the groups $L$ and $G$ ensuring that $\varphi$ is continuous? In this talk we will give an introduction to this problem focusing on the case where $L$ is a locally compact Hausdorff group and $G$ is a geometric group.


• 13.11.2024 Tim Planken : linear time algorithms in graph connectivity
  
  
• 20.11.2024 No seminar (public holiday)
  
  
• 27.11.2024 Paula Kahl, Martin Schneider : Thompson's group F and the notorious amenability question
  
  
• 3.12.2024 SEG Workshop (organised by Christoph Brause), starting at Tuesday, 3pm in Pr-1103 Programme
  
  
• 11.12.2024 No seminar
  
  
Abstract: TBA


• 15.1.2025 Joseph Devine : New angry theorems
  
  
• 22.1.2025 Paul Knappe (Hamburg) Locally chordal graphs
  
  
Abstract: A locally chordal graph is, locally at each vertex, composed of cliques glued along a tree. We show that every such graph $G$ can be decomposed into cliques arranged in the form of a large-girth graph, ensuring that $G$ is, locally at each vertex, composed of cliques glued along a tree.


• 29.1.2025 Aleksandra Kwiatkowska (Münster) : Two-sorted ultrametric spaces via the Fraïssé construction
  
  
Abstract: I will start with an overview and applications of the Fraïssé theory. In the second part of the talk I will discuss a particular two-sorted ultrametric space obtained via such a construction as well as its automorphism group. The talk will be based on a joint work in progress with Bartoš, Kubiś, and Malicki.


• 5.2.2025 Žaneta Semanišinová (Dresden) : Valued Constraints over Infinite Domains
  
  
Abstract: Valued constraint satisfaction problems (VCSPs) provide a framework for many optimization problems. A VCSP is parameterized by a valued structure (template), which consists of a domain and cost functions, each of them defined on finite tuples of elements from the domain. The input to the VCSP consists of a finite set of variables, a finite sum of cost functions applied to these variables, and a threshold u, and the task is to decide whether there exists an assignment to the variables so that the sum of the costs is at most u. VCSPs with finite templates are well-understood and exhibit a complexity dichotomy: each of them is in P or NP-complete. However, many important optimization problems, such as min correlation clustering or the minimum feedback arc set problem cannot be modelled as VCSPs over a finite template. In this talk, we give an introduction to the theory of infinite-domain VCSPs. We then present a complexity classification of VCSPs of all valued structures over the domain Q that are preserved by all order-preserving permutations. Finally, we sketch how resilience problems from database theory can be viewed as VCSPs and present some complexity classification results that this connection yields. This talk is based on joint work with M. Bodirsky, É. Bonnet and C. Lutz.

Summer Semester 2024

• 10.7.2024 Various speakers: Workshop on sofic graphs.
  
  
• 3.7.2024 Will J. Turner: Local Separators of Cayley Graphs: Proof Strategy.
  Abstract: Stallings' Theorem (1971) states that a finitely-generated group splits over a finite subgroup if its Cayley graphs have more than one end. In 2010, Bernhard Krön gave a short proof of Stallings' Theorem using separators of graphs. In this project, we move towards a finite version of Stallings' Theorem using local separators. We show that a finitely-generated group (with bounded nilpotency), having a certain local separator in one of its Cayley graphs, is necessarily cyclic, dihedral or decomposes as a direct product of a cycle and an involution. In particular, we assume the existence of a d-local cutvertex or a d-local 2-separator, for d bounded below in terms of the group's nilpotency. A r-local cutvertex u in a graph is a vertex which disconnects the subgraph induced on a ball of diameter d centred at u. A d-local 2-separator is defined so that it works in a similarly intuitive way.
  
  
• 5.6.2024 Paula Kahl: Introduction to amenability and related properties of groups.
  Abstract: Introduced by Gromov in the late 1990s, the notion of a sofic group turned out to be very fruitful. Within a short period of time several long-standing group-theoretic conjectures, such as Gottschalk's surjunctivity conjecture or Kaplansky's direct finiteness conjecture (both still open for arbitrary groups), were proved for sofic groups. This suggests to think of soficity as a strong property only few groups satisfy. However, until now, there is not a single group known to be non-sofic. Starting from the older and stronger notion of amenability, the talk provides an introduction to soficity, hyperlinearity and the Haagerup property, as well as the relations between them. In particular we are going to prove that amenability implies soficity.
  
  
• 22.5.2024 Will J. Turner: Local Separators of Cayley Graphs: Towards a Stallings-Type Theorem for Finite Groups.
  Abstract: Stallings' Theorem (1971) states that a finitely-generated group splits over a finite subgroup if its Cayley graphs have more than one end. In 2010, Bernhard Krön gave a short proof of Stallings' Theorem using separators of graphs. In this project, we move towards a finite version of Stallings' Theorem using local separators. We show that a finitely-generated group (with bounded nilpotency), having a certain local separator in one of its Cayley graphs, is necessarily cyclic, dihedral or decomposes as a direct product of a cycle and an involution. In particular, we assume the existence of a d-local cutvertex or a d-local 2-separator, for d bounded below in terms of the group's nilpotency. A r-local cutvertex u in a graph is a vertex which disconnects the subgraph induced on a ball of diameter d centred at u. A d-local 2-separator is defined so that it works in a similarly intuitive way.
  
  
• 15.5.2024 Tim Planken: Colouring d-dimensional triangulations.
  Abstract: We consider d-dimensional triangulations and show structural equivalences for (d+1)-colourability and (d+2)-colourability of the vertices of such triangulations. In particular, we show that a d-dimensional triangulation admits a proper (d+1)-colouring if and only if every (d-2)-cell is incident with an even number of (d-1)-cells. Moreover, a d-dimensional triangulation C admits a proper (d+2)-colouring if and only if there exists a triangulation C' that contains C such that for every (d-2)-cell in C', the number of incident (d-1)-cells is divisible by three.
  
  
• 8.5.2024 Josefin Bernhard: Automatic continuity of topological groups.
  Abstract: Many concrete groups come equipped with a non-trivial compatible topology. In some natural examples of topological groups, the topology is determined already by the algebraic structure. Such situation is closely linked with the automatic continuity property: a topological group is said to have automatic continuity if every homomorphism from it into any separable topological group is continuous. In the talk, examples and applications of this phenomenon will be given and we will discuss methods of proving this property for a given group.
  
  
• 29.4.2024 Arkady Leiderman (Ben-Gurion, Israel): Embedding the free topological group F(X^n) into F(X).