Research Seminar in Discrete Mathematics and Algebra (DMA)

Current semester:

• 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.

Previous semesters

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).