Combinatorics Seminar
When: Sunday, November 16, 10am
Where: Schreiber 309
Speaker: Asaf Ferber, ETH Zurich
Title: Robust hamiltonicity of random directed graphs
Abstract:
In his seminal paper from 1952 Dirac showed that the complete graph
on n>2 vertices remains Hamiltonian even if we allow an adversary
to remove n/2 edges touching each vertex.
In 1960 Ghouila-Houri obtained an analogue statement for digraphs
by showing that every directed graph on n>2 vertices with minimum
in- and out-degree at least n/2 contains a directed Hamilton
cycle. Both statements quantify the robustness of complete graphs
(digraphs) with respect to the property of containing a Hamilton
cycle.
A natural way to generalize such results to arbitrary graphs
(digraphs) is using the notion of local resilience. The local
resilience of a graph (digraph) G with respect to a property
P is the maximum number r such that G has the property P even
if we allow an adversary to remove an r-fraction of
(in- and out-going) edges touching every vertex. The theorems
of Dirac and Ghouila-Houri state that the local resilience
of the complete graph and digraph with respect to Hamiltonicity
is 1/2. Recently, this statements have been generalized to
random settings. Lee and Sudakov (2012) proved that the local
resilience of a random graph with edge probability p>>\log n/n
with respect to Hamiltonicity is around 1/2. For random directed
graphs, Hefetz, Steger and Sudakov (2014+) proved an analogous
statement, but only for edge probability p>>n^{-1/2}\log n.
In this talk we significantly improve their result by extending
it for p=\log^8 n/n, which is optimal up to the polylogarithmic
factor.
This is a joint work: Rajko Nenadov, Andreas Noever, Ueli Peter
and Nemanja Skorić.