Research Fields of the Combinatorics Group

Random Graphs

Since the seminal work of Erdős and Rényi on the classical random graph, various random graph models are introduced and studied. The intense study of random graphs and high dimensional analogues has brought together different fields such as discrete mathematics, probability theory, theoretical computer science and statistical physics. Our research is centered around the global and local structure of random graphs, especially their phase transitions.

  • Keywords: random graphs, random hypergraphs, random simplicial complexes, random graphs on surfaces, probabilistic graph theory, probabilistic combinatorics
  • Current group members working on this area: Joshua Erde, Mihyun Kang, Mauricio Collares, Anna Geisler, Vincent Pfenninger, Dominik Schmid, Philipp Sprüssel, Julian Zalla
  • Former group members: Oliver Cooley, Nicola Del Giudice, Tuan anh Do, Chris Dowden, Christoph Koch, Tamas Makai, Michael Missethan, Michael Moßhammer, Angelica Pachon

Structural, Enumerative, and Algorithmic Aspects of Graphs

Classes of graphs that have attracted much attention during recent years are graphs with constraints, such as the class of graphs on surfaces, minor-closed classes and the class of graphs with forbidden subgraphs. We investigate enumerative, algorithmic, and structural aspects of such graph classes. In view of recent results on asymptotic enumeration (and random generation) of graphs with contraints, an essential step is constructive decompositions of graphs into smaller building-blocks. Such decompositions can be interpreted as functional operations of generating functions which encode the enumerative information of graphs. Singularity analysis can then be applied to extract asymptotic behaviour of the number of graphs.

  • Keywords: planar graphs, graphs on surfaces, triangulations, minor-closed classes, structural graph theory, enumerative combinatorics, analytic combinatorics
  • Current group members working on this area: Joshua Erde, Mihyun Kang, Philipp Sprüssel
  • Former group members: Chris Dowden, Wenjie Fang, Michael Missethan, Michael MoƟhammer

Analysis of Algorithms

The aim of “Analysis of Algorithms” is to precisely analyse various algorithms in an asymptotic and probabilistic sense. Apart from the average behaviour for large values of the parameter, limiting distributions of quantities describing the algorithms are also of interest. Specifically, we focus on the design and the analysis of algorithms for efficient generation of combinatorial structures, e.g. Boltzmann Sampler.

  • Keywords: analysis of algorithms, Boltzmann sampler
  • Group members working on this area: Mihyun Kang, Philipp Sprüssel