BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Critical core percolation on random graphs - Alice Contat (Univers
 ity of Paris-Saclay)
DTSTART:20231121T140000Z
DTEND:20231121T150000Z
UID:TALK208384@talks.cam.ac.uk
CONTACT:Jason Miller
DESCRIPTION: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 i
 s optimal as long as $c < \\mathrm{e}$. We will present the proof of a phy
 sics 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\na
 lgorithm and the $k$-core algorithm. \nBased on a joint work with Nicolas 
 Curien and Thomas Budzinski.
LOCATION:MR12
END:VEVENT
END:VCALENDAR