Packing, Covering and Counting Hamilton cycles in random digraphs

Combinatorics Seminar
Event time: 
Thursday, February 19, 2015 - 11:00am to 12:00pm
215 LOM
Asaf Ferber
Speaker affiliation: 
Event description: 

A random directed graph (digraph) is obtained by adding each arc (that is, an ordered pair) with probability $p$, independently at random. A Hamilton cycle in a digraph is a cycle passes through all the vertices, where all the arcs are oriented to the same direction. The problem of finding Hamilton cycles in digraphs is well studied and is known to be hard. One of the main reasons for that, is that there is no general tool for finding Hamilton cycles in digraphs, as the so called Posa rotation-extension technique for the undirected analogue.

A recent breakthrough was obtained by Ferber, Nenadov, Noever, Peter and Skoric, by showing that in a random digraph, w.h.p. one can find a Hamilton cycle even after an adversary deletes roughly half of the in- and out- edges touching each vertex. Based on this result, together with a nice coupling argument due to McDiarmid, we present a general method to attack the problems of packing, covering and counting Hamilton cycles in random digraphs, for every edge-probability $p polylog(n)/n$. Our results are approximately optimal with respect to all the parameters.

This is a joint work with
Gal Kronenberg and Eoin Long from Tel Aviv University.