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
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
codegree
0 references
jump constant
0 references
hypergraph
0 references
extremal problem
0 references
0 references