Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 24, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Matthew Kwan
We consider several situations where "typical" structures have certain spanning substructures (in particular, Hamilton cycles), but where worst-case extremal examples do not. In these situations we show that the extremal examples are "fragile" in that after a modest random perturbation our desired substructures will typically appear.
Our first theorem is that adding linearly many random edges to a dense k-uniform hypergraph typically ensures the existence of a perfect matching or a loose Hamilton cycle. We outline the proof of this theorem, which involves a nonstandard application of Szemeredi's regularity lemma to "beat the union bound"; this might be of independent interest. Our next theorem is that digraphs with certain strong expansion properties are pancyclic. This implies that adding a linear number of random edges typically makes a dense digraph pancyclic. Our final theorem is that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.
This is joint work with Michael Krivelevich and Benny Sudakov.
Automatic MiSe System Software Version 1.4803M | admin login