7 papers
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 power of choice for Boolean functions
Nicolas Fraiman, Lyuben Lichev, Dieter Mitsche
In this paper we consider a variant of the well-known Achlioptas process for graphs adapted to monotone Boolean functions. Fix a number of choices and a sequence o…
On the Boxicity of Kneser Graphs and Complements of Line Graphs
Marco Caoduro, Lyuben Lichev
An axis-parallel -dimensional box is a cartesian product where is a closed sub-interval of the real line. For a graph , t…
The giant component after percolation of product graphs
Lyuben Lichev
In this paper we show the existence of a sharp threshold for the appearance of a giant component after percolation of Cartesian products of graphs under assumptions on their maximu…
A note on the Erdős-Szekeres theorem in two dimensions
Lyuben Lichev
Burkill and Mirsky, and Kalmanson, prove independently that, for every , there is a sequence of vectors in , which does not contain a subsequ…
On the Decycling Number of -regular Random Graphs
Lyuben Lichev, Dieter Mitsche
The decycling number of a graph is the smallest number of vertices which can be removed from so that the resulting graph has no cycles. Bau, Wormald and Zhou conject…