## Research Grants of the Combinatorics Group

### Sparse random combinatorial structures

Probabilistic combinatorics is a mathematical discipline concerned with the study of random combinatorial structures such as random graphs, networks or matrices. Such random structures play a pivotal role in randomised constructions in computer science and other areas of application. Over the past two decades probabilistic combinatorics has received impulses from statistical physics, where a heuristic method called the "Cavity Method" has been developed to put forward intriguing conjectures on numerous long-standing problems. The aim of this project is to provide a rigorous mathematical basis for the techniques upon which the cavity method is based. The focus will be on sparse random combinatorial structures. Specifically, the project concentrates on three prominent, closely related challenges: random combinatorial matrices and random equations over discrete algebraic structures; weighted matchings on sparse random graphs; Hamilton cycles in sparse random graphs.

- Grant DOI: 10.55776/I6502
- Supported by Austrian Science Fund (FWF), Grant no. I6502, 14.10.2023-13.10.2026
- Combinatorics group members in this project:
- Mihyun Kang (PI)
- Vincent Pfenninger (postdoc)

- Members at the partner institution TU Dortmund:
- Amin Coja-Oghlan (PI)
- Pavel Zakharov (PhD student)

- Project website

### Supercritical behaviour in random subgraph models

Percolation, or random subgraphs, is a mathematical model originally studied in the context of statistical physics, where they model the flow of a liquid or gas through a lattice like medium whose channels are randomly blocked. For many of these models, as the density of the random subgraph increases, there is a threshold at which its likely structure changes dramatically. Below this threshold all the components are small, whereas above this threshold many of these small component coalesce and a unique large component appears. In this supercritical regime, whilst the random subgraph is still quite sparse and disconnected, its largest component displays many interesting structural properties which you would expect to appear only for much denser graphs. This project aims to investigate the structural properties of these supercritical random subgraphs, and in particular their largest components, in a range of percolation models.

- Grant DOI: 10.55776/P36131
- Supported by Austrian Science Fund (FWF), Grant no. P36131, 01.01.2023-31.12.2025
- Group members in this project:
- Mauricio Collares
- Joshua Erde (PI)

- Project website

### Doctoral program (DK) "Discrete Mathematics"

The Combinatorics Group takes actively part in the Doctoral Program (DK) "Discrete Mathematics", which offers an advanced PhD training and research program.

- Grant DOI: 10.55776/W1230
- Supported by Austrian Science Fund (FWF), Grant no. W1230, 2015-2024
- Current group members in this project:
- Joshua Erde (DK associated scientist since 2022)
- Anna Geisler (Associated DK doctoral student since March 2023)
- Mihyun Kang (PI of Project 15)
- Philipp Sprüssel (DK Mentor)
- Dominik Schmid (Associated DK doctoral student since May 2022)

- Former group members in this project:
- Oliver Cooley (DK Mentor)
- Nicola Del Giudice (DK doctoral student from September 2016 to June 2020)
- Title of PhD thesis: Random hypergraphs and random simplicial complexes
- Rigorosum: on 19 June 2020
- Reviewers: Mihyun Kang (TU Graz), Tomasz Luczak (Adam Mickiewicz University), Tobias Müller (University of Groningen)
- Examiners: Tomasz Luczak, Tobias Müller
- Tuan Anh Do (DK doctoral student from October 2019 to April 2023)
- Title of PhD thesis: Structural properties of sparse random graph models
- Rigorosum: on 28 April 2023
- Reviewers: Michael Krivelevich (Tel Aviv University), Mihyun Kang (TU Graz), Will Perkins (Georgia Tech)
- Examiners: Michael Krivelevich, Will Perkins
- Christoph Koch (Associated DK doctoral student from April 2012 to December 2016)
- Title of PhD thesis: Phase transition phenomena in random graphs and hypergraphs
- Rigorosum: on 25 November 2016
- Reviewers: Mihyun Kang (TU Graz), Michael Krivelevich (Tel Aviv University), Angelika Steger (ETH Zürich)
- Examiners: Angelika Steger, Wolfgang Woess
- Michael Missthan (DK doctoral student from October 2019 to September 2022)
- Title of PhD thesis: Global and local properties of random planar graphs
- Rigorosum: on 6 May 2022
- Reviewers: Michael Drmota (TU Wien), Mihyun Kang (TU Graz), Konstantinos Pangiotou (LMU Munich)
- Examiners: Michael Drmota, Konstantinos Pangiotuo
- Michael Moßhammer (Associated DK doctoral student from October 2013 to June 2018)
- Title of PhD thesis: Phase transitions and structural properties of random graphs on surfaces
- Rigorosum: on 4 May 2018
- Reviewers: Michael Drmota (TU Wien), Mihyun Kang (TU Graz), Colin McDiarmid (University of Oxford)
- Examiners: Michael Drmota, Mihyun Kang
- Julian Zalla (Associated DK doctoral student from May 2018 to Setember 2022)
- Title of PhD thesis: High-order structures in random hypergraphs
- Rigorosum: on 20 May 2022
- Reviewers: Julia Böttcher (LSE), Mihyun Kang (TU Graz), Yury Person (TU Ilmenau)
- Examiners: Julia Böttcher, Yury Person
- Project webbsite

## Research Grants - completed

### Random graphs: cores, colourings and contagion

The aim of this collaborative project, which is hosted jointly at Goethe University Frankfurt in Germany and at TU Graz in Austria, is to advance the rigorous mathematical understanding of random graphs with the assistance of novel mathematical tools originating, for example, from enumerative combinatorics or the recent theory of graph limits. Specific problems that we intend to study include the graph colouring problem on random graphs, strongly connected sub-structures of random graphs called cores and the contagion of cascading events. For example, graph colouring has been a core topic of mathematics since the famous four colour problem posed by Gutherie in 1852. Cores have applications, for example, in coding theory, and contagion is a key topic in the study of complex social or artificial networks.

- Austrian-German DACH-Project
- Supported by Austrian Science Fund (FWF) and German Research Foundation (DFG)
- Support period by FWF: 01.09.2018-30.06.2022
- Combinatorics group members in this project:
- Oliver Cooley
- Mihyun Kang (PI)

- Members at the partner institution Goethe University Frankfurt:
- Amin Coja-Oghlan (PI)
- Jean Bernoulli Ravelomanana

- Project website

### Random recursive structures of small diameters

Austrian-Taiwanese Joint Project FWF-MOST 2015

- Supported by Austrian Science Fund (FWF), Grant no. I2309-N35, March 2016- August 2020
- Group members in this project:
- Mihyun Kang (Co-PI)
- Wenjie Fang

- Members at partner institution TU Wien:
- Bernhard Gittenberger (PI)
- Michael Drmota (Co-PI)

- Members at partner institutions in Taiwan:
- Michael Fuchs (PI)
- Hsien-Kuei Hwang (Co-PI)
- Young-Nan Yeh (Co-PI)

### Asymptotic properties of graphs on a surface

Since the foundation of the theory of random graphs by Erdős and Rényi five decades ago, various random graphs have been introduced and studied. One example is random graphs on a surface, in particular random planar graphs. Graphs on a 2-dimensional surface and related objects (e.g. planar graphs, triangulations) have been among the most studied objects in graph theory, enumerative combinatorics, discrete probability theory, and statistical physics. The main objectives of this project are to study the asymptotic properties and limit behaviour of random graphs on a surface (e.g. evolution, phase transition, critical behaviour, component size distribution) and to investigate enumerative and algorithmic aspects of unlabelled graphs on a surface (e.g. connectivity, symmetry, decomposition, random generation).

- Supported by Austrian Science Fund (FWF), Grant no. P27290, 01.06.2015-30.06.2019
- Group members in this project:
- Oliver Cooley
- Chris Dowden
- Wenjie Fang
- Mihyun Kang (PI)
- Michael Moßhammer
- Philipp Sprüssel (Co-PI)

- Project website

### Phase transitions and critical phenomena in random graphs

Random graph models that this project focuses on are random graph processes and random hypergraphs. The constraints imposed on these random graph models (in particular random graph processes) lead to difficulties in the analysis of their asymptotic behaviour, due to the long-term and/or global dependence between edges. To overcome these difficulties, new approaches have to be found. The main objective of this project is to advance analytic and probabilistic approaches and to apply them to analyse asymptotic behaviour of such complex random graph models. The scientific program of this project consists of two main themes, which are closely related in that both themes deal with phase transitions and critical phenomena.

- Supported by Austrian Science Fund (FWF), Grant no. P26826, 01.05.2014-31.12.2017
- Group members in this project:
- Oliver Cooley
- Chris Dowden
- Mihyun Kang (PI)
- Christoph Koch
- Tamas Makai

- Project website

### Random graphs defined geometrically

OeAD Scientific & Technological Agreement with Slovenia 2016-2017

- Supported by Austrian Agency for International Cooperation in Education and Research (OeAD), Grant no. SI 12/2016, 01.01.2016-31.12.2017
- Group members in this project: Oliver Cooley, Mihyun Kang (PI), Michael Moßhammer, Philipp Sprüssel
- Members at partner institution in Slovenia : Sergio Cabello (PI), David Gajser, Sandi Klavzar, Bojan Mohar

### Phase transitions in random graphs and random graph processes

The objectives of this project are to study the phase transitions in random graphs and random graph processes with constraints such as degree distribution, forbidden substructures, genus. The phase transition is a phenomenon observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, including Potts models, graph colourings and satisfiability problem. The phase transition observed in the plethora of different random graph models refers to a phenomenon that there is a critical value of edge density such that adding a small number of edges around the critical value results in a dramatic change in the size of the largest components. It is our aim to further develop and apply new analytic approaches combined with counting and probabilistic methods, e.g. singularity analysis, differential equations method, to the study of the phase transitions in random graphs and random graph processes.

- Supported by German Research Foundation (DFG), Grant no. KA 2748/3-1, 01.10.2011-30.11.2014
- Group members in this project: Mihyun Kang (PI), Tamas Makai, Angélica Pachón