Summer Semester 2024-2025
Abstract: The binomial random graph G(n,p) is formed by retaining every edge of the complete graph K_n independently with probability p. A classical result by Erdős and Rényi from 1960 shows that G(n,p) undergoes a fundamental phase transition in its connected component structure when the expected average degree is around 1 (i.e., around p=1/n). Specifically, for p = (1-\epsilon)/n, where \epsilon > 0 is a constant, all connected components are typically logarithmic in n, whereas for p = (1+\epsilon)/n a unique giant component of linear order emerges, and all other components are of order at most logarithmic in n.
This phenomenon — the typical emergence of a unique giant component surrounded by much smaller components — can be seen in many real world examples, such as disease spread and neural connectivity. Thus, perhaps unsurprisingly, it has been observed in random subgraphs G_p of specific host graphs G, such as the d-dimensional binary hypercube, random d-regular graphs, and pseudo-random (n,d,\lambda)-graphs, though with quite different proofs.
This naturally leads to the question: What assumptions on a d-regular n-vertex graph G suffice for its random subgraph to typically exhibit this phase transition around the critical probability p=1/(d-1)? Furthermore, is there a unified approach that encompasses these classical cases? In this talk, we demonstrate that it suffices for G to have mild global edge expansion and (almost-optimal) expansion of sets of (poly-)logarithmic order in n. This result covers many previously considered concrete setups.
We also discuss the tightness of our sufficient conditions.
No previous knowledge in probabilistic combinatorics is assumed.
Based on joint works with Joshua Erde, Mihyun Kang, and Michael Krivelevich.
Abstract: What do loop erased random walk, critical Ising model, self avoiding walk, critical percolation and UST Peano curves have in common? Come find out.