9 papers
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 critical activation density in graph bootstrap percolation
Brett Kolesnik, Tamás Makai, Tamás Makai +6
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…
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…
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…
Multilayer Artificial Benchmark for Community Detection (mABCD)
Åukasz KraiÅski, MichaÅ Czuba, Piotr Bródka +3
One of the most persistent challenges in network science is the development of various synthetic graph models to support subsequent analyses. Among the most notable frameworks addr…
Direct Paths in the Temporal Hypercube
Austin Eide, Martijn Gösgens, PaweÅ PraÅat
We consider the -dimensional random temporal hypercube, i.e., the -dimensional hypercube graph with its edges endowed with i.i.d. continuous random weights. We say that a ver…