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.PRShow all

14 papers · 1 filter

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

Label propagation on binomial random graphs

Marcos Kiwi, Lyuben Lichev, Dieter Mitsche +1

We study the behavior of a label propagation algorithm (LPA) on the Erdős-Rényi random graph $G (n, p)$ . Initially, given a network, each vertex starts with a random label…

math.PR2023

Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime

Lyuben Lichev

Fix a graph $G$ in which every edge is colored in some of $k \geq 2$ colors. Two vertices $u$ and $v$ are CA-connected if $u$ and $v$ may be connected using any subset of $k - 1$ col…

math.PR2022★ 2 cited

Lower bound on the running time of Pop-Stack Sorting on a random permutation

Lyuben Lichev

Pop-Stack Sorting is an algorithm that takes a permutation as an input and sorts its elements. It consists of several steps. At one step, the algorithm reads the permutation it has…

math.PR2022★ 2 cited

Color-avoiding percolation on the Erdős-Rényi random graph

Lyuben Lichev, Bruno Schapira

We consider a recently introduced model of color-avoiding percolation defined as follows. Every edge in a graph $G$ is colored in some of $k \geq 2$ colors. Two vertices $u$ and $v$ …

math.PR2022

Dynamic random graphs with vertex removal

Josep Díaz, Lyuben Lichev, Bas Lodewijks

We introduce and analyse a Dynamic Random Graph with Vertex Removal (DRGVR) defined as follows. At every step, with probability $p > 1/2$ a new vertex is introduced, and with proba…

math.PR2022

On the first and second largest components in the percolated Random Geometric Graph

Lyuben Lichev, Bas Lodewijks, Dieter Mitsche +1

The percolated random geometric graph $G_{n} (λ, p)$ has vertex set given by a Poisson Point Process in the square $[0, n]^{2}$ , and every pair of vertices at distance at most 1 i…

math.PR2022

Percolation on dense random graphs with given degrees

Lyuben Lichev, Dieter Mitsche, Guillem Perarnau

In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a…

math.PR2021★ 1 cited

New results for the random nearest neighbor tree

Lyuben Lichev, Dieter Mitsche

In this paper, we study the online nearest neighbor random tree in dimension $d \in N$ (called $d$ -NN tree for short) defined as follows. We fix the torus $T_{n}^{d}$ of…

math.PR2020

On the minimum bisection of random $3$ -regular graphs

Lyuben Lichev, Dieter Mitsche

In this paper we give new bounds on the bisection width of random 3-regular graphs on $n$ vertices. The main contribution is a new lower bound of $0.103295 n$ based on a first momen…

math.PR2020★ 4 cited

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

Lyuben Lichev, Dieter Mitsche

The modularity of a graph is a parameter that measures its community structure; the higher its value (between $0$ and $1$ ), the more clustered the graph is. In this paper we show t…

math.PR2020

On the Decycling Number of $4$ -regular Random Graphs

Lyuben Lichev, Dieter Mitsche

The decycling number $ϕ (G)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resulting graph has no cycles. Bau, Wormald and Zhou conject…

On the depth of depth-weighted trees

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

Brownian snails with removal die out in one dimension

Label propagation on binomial random graphs

Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime

Lower bound on the running time of Pop-Stack Sorting on a random permutation

Color-avoiding percolation on the Erdős-Rényi random graph

Dynamic random graphs with vertex removal

On the first and second largest components in the percolated Random Geometric Graph

Percolation on dense random graphs with given degrees

New results for the random nearest neighbor tree

On the minimum bisection of random 3-regular graphs

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

On the Decycling Number of 4-regular Random Graphs

On the minimum bisection of random $3$ -regular graphs

On the Decycling Number of $4$ -regular Random Graphs