In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters d1≤d2, there exists a coupling of G(n,d1) and G(n,d2) satisfying that G(n,d1)⊆G(n,d2) with high probability, confirming a conjecture of Ga...
Lawrence Hollom, Lyuben Lichev, Adva Mond et al.· The Annals of Applied Probab...· 0 citations
We show that, for some absolute constants $c_1,c_2>0$, every $(n,d,\lambda)$-graph with $\lambda\le c_1 d$ contains an induced cycle of length at least $c_2n\log(d/\lambda)/d$. This is best possible up to the values of $c_1,c_2$. Our techniques include a multi-scale algorithmic analysis, an adapted depth-first explorat...
Sahar Diskin, Lyuben Lichev, Michael Krivelevich et al.· 1 citation
We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant $C>1$ such that, with high probability, for every fixed constant $\Delta$, the binomial random graph $G(n,C\ln n/n)$ contains every $n$-vertex tree with maximum degree...
Asaf Cohen Antonir, Lyuben Lichev, M. Zhukovskii· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
