4 citations · 21 across the 45 of their papers we have counts for
10 papers · 1 filter
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…
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 is colored in some of colors. Two vertices and …
On the -problem of Brown, Erdős and Sós
Stefan Glock, Felix Joos, Jaehoon Kim +3
Let be the maximum number of edges of an -uniform hypergraph on vertices not containing a subgraph with edges and at most vertices. In 1973, Brown,…
The maximal running time of hypergraph bootstrap percolation
Ivailo Hartarsky, Lyuben Lichev
We show that for every , the maximal running time of the -bootstrap percolation in the complete -uniform hypergraph on vertices is . Thi…
-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 are ordered uniformly…
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 a new vertex is introduced, and with proba…
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 with small maximum codegree has an almost-perfect matching…
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 has vertex set given by a Poisson Point Process in the square , and every pair of vertices at distance at most 1 i…
The semi-random tree process
Sofiya Burova, Lyuben Lichev
The online semi-random graph process is a one-player game which starts with the empty graph on vertices. At every round, a player (called Builder) is presented with a vertex $v…
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…