Article ID Journal Published Year Pages File Type
4656589 Journal of Combinatorial Theory, Series A 2007 15 Pages PDF
Abstract

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)

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,