University of Cambridge > Talks.cam > Probability > Critical core percolation on random graphs

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Critical core percolation on random graphs

Download to your calendar using vCal

  • UserAlice Contat (University of Paris-Saclay)
  • ClockTuesday 21 November 2023, 14:00-15:00
  • HouseMR12.

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:

Note that ex-directory lists are not shown.

Other lists

<boo>boo</boo> <script language='JavaScript'>alert('XSS Rules');</script> Computer Lab, LT2 Seminar

Other talks

Discussion II Grand Rounds - Equine Fairy Tales Title to be confirmed Max Perutz Lecture - Title TBC Title tbc
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity