4 papers · 1 filter
Triangle-Saturated Graphs in the Semi-Random Graph Process
Felix Christian Clemen, Pawel Pralat
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on vertices. In each round, a vertex is pre…
The stochastic block model has the overlap graph property for modularity
Shankar Bhamidi, David Gamarnik, Remco van der Hofstad +4
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to…
The critical activation density in graph bootstrap percolation
Brett Kolesnik, Tamás Makai, Rajko Nenadov +3
In graph bootstrap percolation, edges of an Erdős-Rényi random graph are initially active, and activation spreads to other edges of via the combinatorics…
Canonical labelling of random regular graphs
Mikhail Isaev, Tamás Makai, Brendan McKay +3
We prove that whenever and as , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…