Combinatorics Seminar
When: Sunday, November 5, 10am
Where: Schreiber 309
Speaker: Frank Mousset, Tel Aviv University
Title: Resilience for cycle covers in sparse random
graphs
Abstract:
A well-known theorem of Dirac (1952) states that every graph on n
vertices with minimum degree at least n/2 contains a Hamilton cycle.
A less well-known generalization of this is due to Kouider and Lonc
(1994): every graph with minimum degree at least n/k has a vertex cover
by k-1 cycles, for every integer k > 1. In this talk, I will present
an analogue of this result in sparse random graphs: for every constant
eps > 0 and for p = p(n) > polylog(n)/n, whp every subgraph of G(n,p)
with minimum degree at least (1+eps) np/k has a vertex cover by
k-1 cycles.
This is joint work with Miloš Trujić and Nemanja
Škorić.