کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651897 1632582 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cycles and matchings in randomly perturbed digraphs and hypergraphs
ترجمه فارسی عنوان
چرخه ها و ماتریس ها در دیفرانسیل های تصادفی و هیج گراف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 181-187