کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651897 | 1632582 | 2015 | 7 صفحه PDF | دانلود رایگان |
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. This builds on a sizeable existing body of research. 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 Szemerédi'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.
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 181-187