Previous month Previous day Next day Next month
See by year See by month Jump to month

Frank Mousset, ETH: Packing rainbow Hamilton cycles in random colorings of G(n,p)

 Download as iCal file
Friday, 14. February 2014, 10:30 - 12:00
Abstract: Denote by G(n,p,c) the model of random graphs G ~ G(n,p) in which every edge is randomly assigned one of c colors. Much research has concentrated on the existence of rainbow Hamilton cycles (i.e., Ham. cycles whose edges have distinct colors) in a graph G ~ G(n,p,c). In the end, it was shown by Frieze and Loh that for p = (1+o(1)) (log n)/n and c = (1+o(1)) n, such a graph G a.a.s. contains a rainbow Hamilton cycle. Recently, we started considering a packing variant of this problem: under what conditions can one embed into G(n,p,c) many edge-disjoint rainbow Hamilton cycles? As a first step, I will present a simple technique that we used to prove that there is a constant C>0 such that for p >> (log n)/n, a graph G ~ G(n,p,Cn) a.a.s. contains np/C edge-disjoint rainbow Hamilton cycles. Joint work with Asaf Ferber (ETH) and Gal Kronenberg (TAU).
Location : Kalmár Intézet, Árpád tér, szemináriumi szoba

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013