History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Co-degree density of hypergraphs. (English)
J. Comb. Theory, Ser. A 114, No. 6, 1118-1132 (2007).
For sets $S$ of $r-1$ vertices of an $r$-graph $H$, ${\Cal C}(H)$ is the minimum number of vertices $v$ such that $S\cup\{v\}$ is an edge of $H$. For a family $\Cal F$ of $r$-graphs, the co-degree Turán number co-ex$(n,{\Cal F})$ is the maximum of ${\Cal C}(H)$ among all $H$ containing no member of $\Cal F$ as a subhypergraph. The co-degree density of $\Cal F$ is $γ({\Cal F})=\limsup_{n\to\infty}\frac{\text{co-ex}(n,\Cal F)}{n}$; $Γ_r=\{γ({\Cal F}):{\Cal F}$ is a family of $r$-graphs\}. Observing that the Erdős-Simonovits-Stone theorem for ordinary graphs can be interpreted in terms of the minimum degree of vertices, the authors investigate one possible interpretation of the Erdős “jumping constant" conjecture for hypergraphs [{\it W. G. Brown, P. Erdős} and {\it M. Simonovits}, Trans. Am. Math. Soc. 292, 421-449 (1985; Zbl 0607.05040)] in terms of co-degrees. For an integer $r\ge2$, a real number $α$ such that $0\leα<1$ is a $γ$-jump for $r$ if there exists $δ=δ(α)>0$ such that, for every (infinite or finite) family $\Cal F$ of $r$ graphs, $γ({\Cal F})\notin(α,α+δ)$. Theorem 1.6. Fix $r\ge3$. Then no $α\in[0,1)$ is a $γ$-jump. In particular, $Γ_r$ is dense in $[0,1)$. Conjecture 1.7. Fix $r\ge3$. For every $0\leα<1$ there exists an infinite family $\Cal F$ of $r$-graphs such that $γ({\Cal F})=α$, but, for all finite families ${\Cal F}^\prime\subset{\Cal F}$, $γ({\Cal F}^\prime)>α$. Theorem 1.8. Fix $r\ge3$. Then there is a finite family ${\Cal F}$ of $r$-graphs such that $0<γ({\Cal F})<\min_{F\in{\Cal F}}γ(F)$. Open problems are discussed in \S5.
William G. Brown (Montréal)
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!