Combinatorics Seminar
When: Sunday, November 1, 10am
Where: Schreiber 309
Speaker: Gal Kronenberg, Tel Aviv University
Title: Packing, Counting and Covering Hamilton cycles in random directed graphs
Abstract:
A Hamilton cycle in a digraph is a cycle passes through all the
vertices, where all the arcs are oriented in the same direction.
The problem of finding Hamilton cycles in directed graphs is well
studied and is known to be hard. One of the main reasons for this,
is that there is no general tool for finding Hamilton cycles in
directed graphs comparable to the so called Posa's rotation-extension
technique for the undirected analogue. Let D(n, p) denote the random
digraph on vertex set [n], obtained by adding each directed edge
independently with probability p. We present a general and a very
simple method, using known results, to attack problems of packing
and counting Hamilton cycles in random directed graphs, for every
edge-probability p > polylog(n)/n. Our results are asymptotically
optimal with respect to all parameters and apply equally well to
the undirected case.
Joint work with Asaf Ferber and Eoin Long.