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