Critical core percolation on random graphs

Add to your list(s) Download to your calendar using vCal

• Alice Contat (University of Paris-Saclay)
• Tuesday 21 November 2023, 14:00-15:00
• MR12.

If you have a question about this talk, please contact Jason Miller.

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.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.