Előző hónap Előző nap Következő nap Következő hónap
Év szerint Hónap szerint Ugrás a hónaphoz

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

 iCal fájl letöltése
Péntek, 14. Február 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).
Hely : Kalmár Intézet, Árpád tér, szemináriumi szoba

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013