18 papers
Universality in random graphs via optimal linking systems: trees and beyond
Asaf Cohen Antonir, Lyuben Lichev, Maksim Zhukovskii
We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant such that, with high p…
Diameter and mixing time of the giant component in the percolated hypercube
Michael Anastos, Sahar Diskin, Lyuben Lichev +1
We consider bond percolation on the -dimensional binary hypercube with for fixed . We prove that the typical diameter of the giant component is of order $Î(d…
The Mihail-Vazirani conjecture and strong edge-expansion in random polytopes
Micha Christoph, Sahar Diskin, Lyuben Lichev +1
We study the edge-expansion of the graph of a random polytope , defined as the convex hull of a random subset of the points in where every point is retaine…
On the depth of depth-weighted trees
Lyuben Lichev, Amitai Linker, Bas Lodewijks +1
The depth-weighted tree DWT() with weight function is a dynamic random tree grown from a root where vertices arrive consecutively and ever…
Explosive appearance of cores and bootstrap percolation on lattices
Ivailo Hartarsky, Lyuben Lichev
Consider the process where the vertices of a square -dimensional torus appear consecutively in a random order. We show that typically the size of the -core of the corresp…
Sharp thresholds, hitting times and the power of choice for random geometric graphs
Dawid Ignasiak, Lyuben Lichev
We consider a random geometric graph process where random points are embedded consecutively in the -dimensional unit torus , and every two points…