Research Fields of the Combinatorics Group

Random Discrete Structures

Random discrete structures have been extensively studied during the last few decades and have become one of the central themes of contemporary mathematics. The most important and popular example of random discrete structures is random graphs. Since the seminal work of Erdős and Rényi on the standard random graph, various random graph models are introduced and studied. The intense study of random graphs and random graph processes has brought together different fields such as discrete mathematics, probability theory, theoretical computer science and statistical physics. Our research is centered around phase transitions in random graphs and random graph processes with constraints.

  • Keywords: random graphs, random hypergraphs, random graph processes, random graphs with constraints, probabilistic graph theory, phase transitions
  • Group members working on this area: Oliver Cooley, Nicola Del Giudice, Chris Dowden, Mihyun Kang, Michael Moßhammer, Philipp Sprüssel, Julian Zalla

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. The members of the institute 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: graphs on surfaces, minor-closed classes, singularity analysis, structural graph theory
  • Group members working on this area: Chris Dowden, Wenjie Fang, Mihyun Kang, Michael Moßhammer, Philipp Sprüssel

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