Co-degree density of hypergraphs (Q2642025)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Co-degree density of hypergraphs
scientific article

    Statements

    Co-degree density of hypergraphs (English)
    0 references
    0 references
    0 references
    20 August 2007
    0 references
    For sets \(S\) of \(r-1\) vertices of an \(r\)-graph \(H\), \({\mathcal C}(H)\) is the minimum number of vertices \(v\) such that \(S\cup\{v\}\) is an edge of \(H\). For a family \(\mathcal F\) of \(r\)-graphs, the co-degree Turán number co-ex\((n,{\mathcal F})\) is the maximum of \({\mathcal C}(H)\) among all \(H\) containing no member of \(\mathcal F\) as a subhypergraph. The co-degree density of \(\mathcal F\) is \(\gamma({\mathcal F})=\limsup_{n\to\infty}\frac{\text{co-ex}(n,\mathcal F)}{n}\); \(\Gamma_r=\{\gamma({\mathcal F}):{\mathcal 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 [\textit{W. G. Brown, P. Erdős} and \textit{M. Simonovits}, Trans. Am. Math. Soc. 292, 421-449 (1985; Zbl 0607.05040)] in terms of co-degrees. For an integer \(r\geq2\), a real number \(\alpha\) such that \(0\leq\alpha<1\) is a \(\gamma\)-jump for \(r\) if there exists \(\delta=\delta(\alpha)>0\) such that, for every (infinite or finite) family \(\mathcal F\) of \(r\) graphs, \(\gamma({\mathcal F})\notin(\alpha,\alpha+\delta)\). Theorem 1.6. Fix \(r\geq3\). Then no \(\alpha\in[0,1)\) is a \(\gamma\)-jump. In particular, \(\Gamma_r\) is dense in \([0,1)\). Conjecture 1.7. Fix \(r\geq3\). For every \(0\leq\alpha<1\) there exists an infinite family \(\mathcal F\) of \(r\)-graphs such that \(\gamma({\mathcal F})=\alpha\), but, for all finite families \({\mathcal F}^\prime\subset{\mathcal F}\), \(\gamma({\mathcal F}^\prime)>\alpha\). Theorem 1.8. Fix \(r\geq3\). Then there is a finite family \({\mathcal F}\) of \(r\)-graphs such that \(0<\gamma({\mathcal F})<\min_{F\in{\mathcal F}}\gamma(F)\). Open problems are discussed in \S5.
    0 references
    0 references
    codegree
    0 references
    jump constant
    0 references
    hypergraph
    0 references
    extremal problem
    0 references
    0 references