(SFB) Combinatorics Afternoon Workshop (PDF)

The (SFB) Combinatorics Afternoon Workshop will take place on 6 June 2025 (Friday) in the afternoon at the seminar room STEG050 (AE06) on the ground floor (EG) of the Mathematics Building located at Steyrergasse 30, A-8010 Graz, on the Neue Technik Campus of TU Graz.


Program

  • 13:00-13:50   Michael Krivelevich  Percolation through isoperimetry
  • 14:00-14:30   Coffee break
  • 14:30-15:20   Sahar Diskin  TBA
  • 15:30-16:20   Michael Anastos  TBA
  • 16:30-17:00   Discussions
  • 18:00      Joint Dinner

Title and Abstract


Michael Krivelevich (Tel Aviv University):  Percolation through isoperimetry

Let G be a d-regular graph of growing degree on n vertices, and form a random subgraph G_p of G by retaining each edge of G independently with probability p=p(d). Which conditions on G suffice to observe a phase transition at p=1/d similar to that in the binomial random graph G(d+1,p), or, say, in a random subgraph of the binary hypercube Q^d?
We argue that in the supercritical regime p=(1+ε)/d, ε>0 being a small constant, postulating that every vertex subset S of G of at most n/2 vertices has its edge boundary at least C|S|, for some large enough constant C=C(ε)>0, suffices to guarantee the likely appearance of the giant component in G_p. Moreover, its asymptotic order is equal to that in the random graph G(n,(1+ε)/n), and all other components are typically much smaller.
We further give examples demonstrating the tightness of this result in several key senses.
A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.



Sahar Diskin (Tel Aviv University):  TBA


Michael Anastos (IST Austria):  TBA



(SFB) Combinatorics Afternoon Workshop is an associated event of the SFB "Discrete random structures: enumeration and scaling limits". It is supported in part by Austrian Science Fund (FWF) [10.55776/F1002] and [10.55776/DOC183].