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

50 papers

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.PR2026

On the depth of depth-weighted trees

Lyuben Lichev, Amitai Linker, Bas Lodewijks +1

The depth-weighted tree DWT( $f$ ) with weight function $f : {0, 1, 2, \dots} \to (0, \infty)$ is a dynamic random tree grown from a root $r$ where vertices arrive consecutively and ever…

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.PR2025

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 $d$ -dimensional binary hypercube with $p = c / d$ for fixed $c > 1$ . We prove that the typical diameter of the giant component $L_{1}$ is of order $Θ(d)…

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.OC2024

Zero-sum Random Games on Directed Graphs

Luc Attia, Lyuben Lichev, Dieter Mitsche +2

This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players. Starting from…

math.PR2023

Brownian snails with removal die out in one dimension

Ivailo Hartarsky, Lyuben Lichev

Brownian snails with removal is a spatial epidemic model defined as follows. Initially, a homogeneous Poisson process of susceptible particles on $R^{d}$ with intensity $λ > 0$ …

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…

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

On the depth of depth-weighted trees

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

Diameter and mixing time of the giant component in the percolated hypercube

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

Zero-sum Random Games on Directed Graphs

Brownian snails with removal die out in one dimension

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

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$