Lyuben Lichev

activity

20202026

most citedOn the modularity of 3-regular random graphs and random graphs with given degree sequences

4 citations · 21 across the 45 of their papers we have counts for

collaborators

Showing math.COShow all

35 papers · 1 filter

math.CO2026

Long induced cycles in pseudorandom graphs

Sahar Diskin, Lyuben Lichev, Michael Krivelevich +1

We show that, for some absolute constants $c_{1}, c_{2} > 0$ , every $(n, d, λ)$ -graph with $λ \leq c_{1} d$ contains an induced cycle of length at least $c_{2} n lo g (d / λ) / d$ . This is best possible…

math.CO2026

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 $C > 1$ such that, with high p…

math.CO2026

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

Micha Christoph, Sahar Diskin, Lyuben Lichev +1

We study the edge-expansion of the graph of a random $0/1$ polytope $P_{p}^{d}$ , defined as the convex hull of a random subset of the points in ${0, 1}^{d}$ where every point is retaine…

math.CO2025

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 $(X_{i})_{i \geq 1}$ are embedded consecutively in the $d$ -dimensional unit torus $T^{d}$ , and every two points…

math.CO2025

Approximate Itai-Zehavi conjecture for random graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +2

A famous conjecture by Itai and Zehavi states that, for every $d$ -vertex-connected graph $G$ and every vertex $r$ in $G$ , there are $d$ spanning trees of $G$ such that, for every v…

math.CO2025

Cycle lengths in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q_{p}^{d}$ be the random subgraph of the $d$ -dimensional binary hypercube obtained after edge-percolation with probability $p$ . It was shown recently by the authors that, for ever…

math.CO2025

Monotonicity and decompositions of random regular graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +2

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 parameter…

math.CO2025

Spanning trees of bounded degree in random geometric graphs

Michael Anastos, Sahar Diskin, Dawid Ignasiak +2

We determine the sharp threshold for the containment of all $n$ -vertex trees of bounded degree in random geometric graphs with $n$ vertices. This provides a geometric counterpart o…

math.CO2025

Nearly spanning cycle in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q^{d}$ be the $d$ -dimensional binary hypercube. We form a random subgraph $Q_{p}^{d} \subseteq Q^{d}$ by retaining each edge of $Q^{d}$ independently with probability $p$ . We show that,…

math.CO2025

Universality of the matching number in percolated regular graphs

Sahar Diskin, Mihyun Kang, Lyuben Lichev

Fix a sequence of $d$ -regular graphs $(G_{d})_{d \in N}$ and denote by $G_{d, p}$ the graph obtained from $G_{d}$ after edge-percolation with probability $p = c / d$ , for a constant…

math.CO2025

Colouring random Hasse diagrams and box-Delaunay graphs

Zhihan Jin, Matthew Kwan, Lyuben Lichev

Fix $d \geq 2$ and consider a uniformly random set $P$ of $n$ points in $[0, 1]^{d}$ . Let $G$ be the Hasse diagram of $P$ (with respect to the coordinatewise partial order), or alterna…

math.CO2025

Explosive appearance of cores and bootstrap percolation on lattices

Ivailo Hartarsky, Lyuben Lichev

Consider the process where the $n$ vertices of a square $2$ -dimensional torus appear consecutively in a random order. We show that typically the size of the $3$ -core of the corresp…

math.CO2024

A note on high-dimensional discrepancy of subtrees

Lawrence Hollom, Lyuben Lichev, Adva Mond +1

For a tree $T$ and a function $f : E (T) \to S^{d}$ , the imbalance of a subtree $T^{'} \subseteq T$ is given by $∣ \sum_{e \in E (T^{'})} f (e) ∣$ . The $d$ -dimensional discrepancy o…

math.CO2024

Discrepancies of spanning trees in dense graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +1

We address several related problems on combinatorial discrepancy of trees in a setting introduced by Erdős, Füredi, Loebl and Sós. Given a fixed tree $T$ on $n$ vertices and an edg…

math.CO2024

Vertex-separating path systems in random graphs

Lyuben Lichev, Nicolás Sanhueza-Matamala

A set $V$ is said to be separated by subsets $V_{1}, \dots, V_{k}$ if, for every pair of distinct elements of $V$ , there is a set $V_{i}$ that contains exactly one of them. Imposing struc…

math.CO2024

On the local resilience of random geometric graphs with respect to connectivity and long cycles

Alberto Espuny Díaz, Lyuben Lichev, Alexandra Wesolek

Given an increasing graph property $P$ , a graph $G$ is $α$ -resilient with respect to $P$ if, for every spanning subgraph $H \subseteq G$ where each vertex keeps…

math.CO2024

On the $(k + 2, k)$ -problem of Brown, Erdős and Sós for $k = 5, 6, 7$

Stefan Glock, Jaehoon Kim, Lyuben Lichev +2

Let $f^{(r)} (n; s, k)$ denote the maximum number of edges in an $n$ -vertex $r$ -uniform hypergraph containing no subgraph with $k$ edges and at most $s$ vertices. Brown, Erdős and Sós…

math.CO2023★ 2 cited

Local dimer dynamics in higher dimensions

Ivailo Hartarsky, Lyuben Lichev, Fabio Toninelli

We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes $[n]^{d}$ . These consist of successively switching the dimers along alternating cycles of prescr…

math.CO2023

Sharp threshold for embedding balanced spanning trees in random geometric graphs

Alberto Espuny Díaz, Lyuben Lichev, Dieter Mitsche +1

A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of…

math.CO2023

Large monochromatic components in colorings of complete hypergraphs

Lyuben Lichev, Sammy Luo

Gyárfás famously showed that in every $r$ -coloring of the edges of the complete graph $K_{n}$ , there is a monochromatic connected component with at least $\frac{n}{r - 1}$ vertices. A…

math.CO2022

On the $(6, 4)$ -problem of Brown, Erdős and Sós

Stefan Glock, Felix Joos, Jaehoon Kim +3

Let $f^{(r)} (n; s, k)$ be the maximum number of edges of an $r$ -uniform hypergraph on $n$ vertices not containing a subgraph with $k$ edges and at most $s$ vertices. In 1973, Brown,…

math.CO2022★ 3 cited

The maximal running time of hypergraph bootstrap percolation

Ivailo Hartarsky, Lyuben Lichev

We show that for every $r \geq 3$ , the maximal running time of the $K_{r + 1}^{r}$ -bootstrap percolation in the complete $r$ -uniform hypergraph on $n$ vertices $K_{n}^{r}$ is $Θ (n^{r})$ . Thi…

math.CO2022

$d$ -connectivity of the random graph with restricted budget

Lyuben Lichev

In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph $K_{n}$ are ordered uniformly…

math.CO2022

Conflict-free hypergraph matchings

Stefan Glock, Felix Joos, Jaehoon Kim +2

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph $H$ with small maximum codegree has an almost-perfect matching…

Long induced cycles in pseudorandom graphs

Universality in random graphs via optimal linking systems: trees and beyond

The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes

Sharp thresholds, hitting times and the power of choice for random geometric graphs

Approximate Itai-Zehavi conjecture for random graphs

Cycle lengths in the percolated hypercube

Monotonicity and decompositions of random regular graphs

Spanning trees of bounded degree in random geometric graphs

Nearly spanning cycle in the percolated hypercube

Universality of the matching number in percolated regular graphs

Colouring random Hasse diagrams and box-Delaunay graphs

Explosive appearance of cores and bootstrap percolation on lattices

A note on high-dimensional discrepancy of subtrees

Discrepancies of spanning trees in dense graphs

Vertex-separating path systems in random graphs

On the local resilience of random geometric graphs with respect to connectivity and long cycles

On the (k+2,k)-problem of Brown, Erdős and Sós for k=5,6,7

Local dimer dynamics in higher dimensions

Sharp threshold for embedding balanced spanning trees in random geometric graphs

Large monochromatic components in colorings of complete hypergraphs

On the (6,4)-problem of Brown, Erdős and Sós

The maximal running time of hypergraph bootstrap percolation

d-connectivity of the random graph with restricted budget

Conflict-free hypergraph matchings

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

On the $(k + 2, k)$ -problem of Brown, Erdős and Sós for $k = 5, 6, 7$

On the $(6, 4)$ -problem of Brown, Erdős and Sós

$d$ -connectivity of the random graph with restricted budget