Critical core percolation on random graphs

Motivated by the desire to construct large independent sets in random graphs, Karp and Sipser modified the usual greedy construction to yield an algorithm that outputs an independent set with a large cardinal. When run on the Erdös-Rényi $G(n,c/n)$ random graph, this algorithm is optimal as long as $c < mathrm{e}$. We will present the proof of a physics conjecture of Bauer and Golinelli (2002) stating that at criticality, the size of the Karp-Sipser core is of order $n^{3/5}$. Along the way we shall highlight the similarities and differences with the usual greedy
algorithm and the $k$-core algorithm.
Based on a joint work with Nicolas Curien and Thomas Budzinski.

• Speaker: Alice Contat (University of Paris-Saclay)
• Tuesday 21 November 2023, 14:00–15:00
• Venue: MR12.
• Series: Probability; organiser: Jason Miller.