کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777122 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Covering and tiling hypergraphs with tight cycles
ترجمه فارسی عنوان
پوشش و کاشی کاری فوق العاده با چرخه های تنگ
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given 3≤k≤s, we say that a k-uniform hypergraph Csk is a tight cycle on s vertices if there is a cyclic ordering of the vertices of Csk such that every k consecutive vertices under this ordering form an edge. We prove that if k≥3 and s≥2k2, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+o(1))n has the property that every vertex is covered by a copy of Csk. Our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime.A perfect Csk-tiling is a spanning collection of vertex-disjoint copies of Csk. When s is divisible by k, the problem of determining the minimum codegree that guarantees a perfect Csk-tiling was solved by a result of Mycroft. We prove that if k≥3 and s≥5k2 is not divisible by k and s divides n, then every k-uniform hypergraph on n vertices with minimum codegree at least (1/2+1/(2s)+o(1))n has a perfect Csk-tiling. Again our result is asymptotically best possible for infinitely many pairs of s and k, e.g. when s and k are coprime with k even.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 561-567
نویسندگان
, , ,