کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656589 1343445 2007 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Co-degree density of hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Co-degree density of hypergraphs
چکیده انگلیسی

For an r-graph H  , let C(H)=minSd(S)C(H)=minSd(S), where the minimum is taken over all (r−1)(r−1)-sets of vertices of H  , and d(S)d(S) is the number of vertices v   such that S∪{v}S∪{v} is an edge of H  . Given a family FF of r  -graphs, the co-degree Turán number co-ex(n,F) is the maximum of C(H)C(H) among all r-graphs H   which contain no member of FF as a subhypergraph. Define the co-degree density of a family FF to beγ(F)=lim supn→∞co-ex(n,F)n. When r⩾3r⩾3, non-zero values of γ(F) are known for very few finite r  -graphs families FF. Nevertheless, our main result implies that the possible values of γ(F) form a dense set in [0,1)[0,1). The corresponding problem in terms of the classical Turán density is an old question of Erdős (the jump constant conjecture), which was partially answered by Frankl and Rödl [P. Frankl, V. Rödl, Hypergraphs do not jump, Combinatorica 4 (2–3) (1984) 149–159]. We also prove the existence, by explicit construction, of finite FF satisfying 0<γ(F)

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 114, Issue 6, August 2007, Pages 1118–1132
نویسندگان
, ,