Research Grant ``Supercritical behaviour in random subgraph models''

Summary

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 Info

Supported by Austrian Science Fund (FWF), Grant no. P36131, 01.01.2023-31.12.2025

Team

• Mauricio Collares
• Joshua Erde (PI)

Collaborators and visitors

• Sahar Diskin, Tel Aviv University
• Michael Krievelevich, Tel Aviv University
• Matthew Jensen, King's College London
• Marcelo Campos, Oxford University
• Lyuben Lichev, ISTA
• David Ellis, University of Bristol
• John Sylvester, University of Liverpool

Publications

Articles in Journals

• (N. Bowler, C. Elbracht, J. Erde, J. P. Gollin, K. Heuer, M. Pitz and M. Teegen) Ubiquity of graphs with non-linear end structure, Journal of Graph Theory, Volume 103, Issue 3, 2023 (Journal/arXiv).

• (T. Do, J. Erde, M. Kang and M. Missethan) Component behaviour and excess of random bipartite graphs near the critical point, Electronic Journal of Combinatorics, Volume 30, Issue 3, 2023 (Journal/arXiv).

• (S. Diskin, J. Erde, M. Kang and M. Krivelevich) Percolation on irregular high-dimensional product graphs, Combinatorics, Probability and Computing, 2023 (Journal/arXiv).

• (B. Barber, J. Erde, P. Keevash and A. Roberts) Isoperimetric stability in lattices, Proceedings of the American Mathematical Society, Volume 151, 2023 (Journal/arXiv).

• (M. Campos, M. Collares, G. O. Mota) Counting orientations of random graphs with no directed k-cycles, Random Structures and Algorithms, Volume 64, Issue 3, 2023 (Journal/arXiv).

• (L. Aragão, M. Collares, J. P. Marciano, T. Martins and R. Morris) A lower bound for set-coloring Ramsey numbers, Random Structures and Algorithms, Volume 64, Issue 2, 2024 (Journal/arXiv).

• (T. Do, J. Erde and M. Kang) A note on the width of sparse random graphs, Journal of Graph Theory, Journal of Graph Theory, Volume 106, Issue 2, 2024 (Journal/arXiv).

• (R. Diestel, C. Elbracht, J. Erde and M. Teegen) Duality and tangles of set separations, Journal of Combinatorics, Volume 15, Issue 1, 2024 (Journal/arXiv).

• (S. Diskin, J. Erde, M. Kang and M. Krivelevich) Percolation on irregular high-dimensional product graphs, Combinatorics, Probability and Computing, Volume 33, Issue 3, 2024 (Journal/arXiv).

• (S. Diskin, J. Erde, M. Kang and M. Krivelevich) Isoperimetric inequalities and supercritical percolation on high-dimensional product graphs, Combinatorica, Volume 44, 2024 (Journal/arXiv).

• (N. Bowler, C. Elbracht, J. Erde, J. P. Gollin, K. Heuer, M. Pitz and M. Teegen) Ubiquity of locally finite graphs with extensive tree-decompositions, Combinatorial Theory, Volume 4, Issue 2, 2024 (Journal/arXiv).

• (S. Diskin, J. Erde, M. Kang and M. Krivelevich) Percolation on high-dimensional product graphs, Random Structures and Algorithms, Volume 66, Issue 1, 2025 (Journal/arXiv).

• (L. Aragão, M. Collares, G. Dahia and J. P. Marciano) The diameter of randomly twisted hypercubes, European Journal of Combinatorics, Volume 124, 2025 (Journal/arXiv).

• (M. Collares, S. Diskin, J. Erde and M. Krivelevich) Long cycles in percolated expanders, Electronic Journal of Combinatorics, Volume 32, Issue 1, 2025 (Journal/arXiv).

• (O. Cooley, T. Do, J. Erde and M. Missethan) The emergence of a giant rainbow component, European Journal of Combinatorics, Volume 127, 2025 (Journal/arXiv).

• (J. Erde, F. Lehner, M. Kang, D. Schmid and B. Mohar) Catching a robber on a random k-uniform hypergraph, Canadian Journal of Mathematics, to appear (Journal/arXiv).

• (S. Diskin, J. Erde, M. Kang and M. Krivelevich) Percolation through isoperimetry, Annales de l'Institut Henri Poincaré, to appear (arXiv).

Articles in Peer-Reviewed Conference Proceedings

• (L. Aragão, M. Collares, J. P. Marciano, T. Martins and R. Morris) A lower bound for set-coloring Ramsey numbers, Extended Abstracts EuroComb 2023 2023 (Proceedings).

• (J. Erde, F. Lehner, M. Kang, D. Schmid and B. Mohar) Cop number of random k-uniform hypergraphs, Extended Abstracts EuroComb 2023 2023 (Proceedings).

• (B. Barber, J. Erde, P. Keevash and A. Roberts) Isoperimetric stability in lattices, Extended Abstracts EuroComb 2023 2023 (Proceedings).

last updated in January 2023