Positive co-degree densities and jumps

• Published in: arXiv.org 2024-12
• Main Authors: Balogh, József, Halfpap, Anastasia, Lidický, Bernard, Palmer, Cory
• Format: Article
• Language: English
• Subjects: Graphs
• ISSN: 2331-8422

The minimum positive co-degree of a nonempty \(r\)-graph \(H\), denoted by \(\delta_{r-1}^+(H)\), is the largest integer \(k\) such that for every \((r-1)\)-set \(S \subset V(H)\), if \(S\) is contained in a hyperedge of \(H\), then \(S\) is contained in at least \(k\) hyperedges of \(H\). Given a family \(\mathcal{F}\) of \(r\)-graphs, the positive co-degree Turán function \(\mathrm{co^+ex}(n,\mathcal{F})\) is the maximum of \(\delta_{r-1}^+(H)\) over all \(n\)-vertex \(r\)-graphs \(H\) containing no member of \(\mathcal{F}\). The positive co-degree density of \(\mathcal{F}\) is \(\gamma^+(\mathcal{F}) = \underset{n \rightarrow \infty}{\lim} \frac{\mathrm{co^+ex}(n,\mathcal{F})}{n}.\) While the existence of \(\gamma^+(\mathcal{F})\) is proved for all families \(\mathcal{F}\), only few positive co-degree densities are known exactly. For a fixed \(r \geq 2\), we call \(\alpha \in [0,1]\) an achievable value if there exists a family of \(r\)-graphs \(\mathcal{F}\) with \(\gamma^+(\mathcal{F}) = \alpha\), and call \(\alpha\) a jump if for some \(\delta > 0\), there is no family \(\mathcal{F}\) with \(\gamma^+(\mathcal{F}) \in (\alpha, \alpha + \delta)\). Halfpap, Lemons, and Palmer showed that every \(\alpha \in [0, \frac{1}{r})\) is a jump. We extend this result by showing that every \(\alpha \in [0, \frac{2}{2r -1})\) is a jump. We also show that for \(r = 3\), the set of achievable values is infinite, more precisely, \(\frac{k-2}{2k-3}\) for every \(k \geq 4\) is achievable. Finally, we determine two additional achievable values for \(r=3\) using flag algebra calculations.