![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Alice Contat (University of Paris-Saclay)
Tuesday 21 November 2023, 14:00-15:00
Critical core percolation on random graphs
- 👤 Speaker: Alice Contat (University of Paris-Saclay)
- 📅 Date & Time: Tuesday 21 November 2023, 14:00 - 15:00
- 📍 Venue: MR12
Abstract
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.
Series This talk is part of the Probability series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- CMS Events
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- Hanchen DaDaDash
- Interested Talks
- MR12
- Probability
- School of Physical Sciences
- Statistical Laboratory info aggregator
Note: Ex-directory lists are not shown.