Positive co-degree densities and jumps

Balogh, József; Halfpap, Anastasia; Lidický, Bernard; Palmer, Cory

doi:10.5802/igt.16

Balogh, József ¹; Halfpap, Anastasia ²; Lidický, Bernard ³; Palmer, Cory ⁴

¹Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61801 (USA)
²School of Science and Mathematics, Truman State University, Kirksville, MO 63501 (USA)
³Department of Mathematics, Iowa State University, Ames, IA 50011 (USA)
⁴Department of Mathematical Sciences, University of Montana, Missoula, MT 59812 (USA)

Innovations in Graph Theory, Volume 3 (2026), pp. 1-36

Abstract

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}^+\mathrm{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}^+\mathrm{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 \ge 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 [27] 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 \ge 4$ is achievable. Finally, we determine two additional achievable values for $r=3$ using flag algebra calculations.

Received: 2024-12-11
Accepted: 2025-12-01
Published online: 2026-01-15

DOI: 10.5802/igt.16

Classification: 05C35, 05C65
Keywords: positive co-degree, hypergraph, Turán, jump, flag algebras

Author's affiliations:

Balogh, József ¹ ; Halfpap, Anastasia ² ; Lidický, Bernard ³ ; Palmer, Cory ⁴

¹ Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61801 (USA)
² School of Science and Mathematics, Truman State University, Kirksville, MO 63501 (USA)
³ Department of Mathematics, Iowa State University, Ames, IA 50011 (USA)
⁴ Department of Mathematical Sciences, University of Montana, Missoula, MT 59812 (USA)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{IGT_2026__3__1_0,
     author = {Balogh, J\'ozsef and Halfpap, Anastasia and Lidick\'y, Bernard and Palmer, Cory},
     title = {Positive co-degree densities and jumps},
     journal = {Innovations in Graph Theory},
     pages = {1--36},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.16},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.16/}
}

TY  - JOUR
AU  - Balogh, József
AU  - Halfpap, Anastasia
AU  - Lidický, Bernard
AU  - Palmer, Cory
TI  - Positive co-degree densities and jumps
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 1
EP  - 36
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.16/
DO  - 10.5802/igt.16
LA  - en
ID  - IGT_2026__3__1_0
ER  -

%0 Journal Article
%A Balogh, József
%A Halfpap, Anastasia
%A Lidický, Bernard
%A Palmer, Cory
%T Positive co-degree densities and jumps
%J Innovations in Graph Theory
%D 2026
%P 1-36
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.16/
%R 10.5802/igt.16
%G en
%F IGT_2026__3__1_0

Balogh, József; Halfpap, Anastasia; Lidický, Bernard; Palmer, Cory. Positive co-degree densities and jumps. Innovations in Graph Theory, Volume 3 (2026), pp. 1-36. doi: 10.5802/igt.16

References
Cited by

[1] Avart, Christian; Rödl, Vojtěch; Schacht, Mathias Every monotone 3-graph property is testable, SIAM J. Discrete Math., Volume 21 (2007) no. 1, pp. 73-92 | DOI | MR | Zbl

[2] Baber, Rahil Turán densities of hypercubes (2012) | arXiv | Zbl

[3] Baber, Rahil; Talbot, John Hypergraphs do jump, Comb. Probab. Comput., Volume 20 (2011) no. 2, pp. 161-171 | DOI | MR | Zbl

[4] Balogh, József The Turán density of triple systems is not principal, J. Comb. Theory, Ser. A, Volume 100 (2002) no. 1, pp. 176-180 | DOI | Zbl | MR

[5] Balogh, József; Clemen, Felix Christian; Lidický, Bernard Hypergraph Turán problems in $ℓ_{2}$ -norm, Surveys in combinatorics 2022 (London Mathematical Society Lecture Note Series), Volume 481, Cambridge University Press, 2022, pp. 21-63 | DOI | MR | Zbl

[6] Balogh, Jozsef; Lemons, Nathan; Palmer, Cory Maximum size intersecting families of bounded minimum positive co-degree, SIAM J. Discrete Math., Volume 35 (2021) no. 3, pp. 1525-1535 | DOI | MR | Zbl

[7] Balogh, József; Luo, Haoran Turán Density of Long Tight Cycle Minus One Hyperedge, Combinatorica, Volume 44 (2024) no. 5, pp. 949-976 | DOI | Zbl | MR

[8] Bodnár, Levente; León, Jared; Liu, Xizhi; Pikhurko, Oleg The Turán density of short tight cycles (2025) | arXiv

[9] Bodnár, Levente; León, Jared; Liu, Xizhi; Pikhurko, Oleg The Turán density of the tight 5-cycle minus one edge (2025) | arXiv

[10] Bollobás, Béla Three-graphs without two triples whose symmetric difference is contained in a third, Discrete Math., Volume 8 (1974), pp. 21-24 | DOI | MR | Zbl

[11] Bollobás, Béla; Leader, Imre; Malvenuto, Claudia Daisies and other Turán problems, Comb. Probab. Comput., Volume 20 (2011) no. 5, pp. 743-747 | DOI | MR | Zbl

[12] Conlon, David; Fox, Jacob Graph removal lemmas, Surveys in combinatorics 2013 (London Mathematical Society Lecture Note Series), Volume 409, Cambridge University Press, 2013, pp. 1-49 | MR | Zbl

[13] Czygrinow, Andrzej; Nagle, Brendan A note on codegree problems for hypergraphs, Bull. Inst. Comb. Appl., Volume 32 (2001), pp. 63-69 | MR | Zbl

[14] De Caen, Dominique; Füredi, Zoltán The maximum size of 3-uniform hypergraphs not containing a Fano plane, J. Comb. Theory, Ser. B, Volume 78 (2000) no. 2, pp. 274-276 | DOI | MR | Zbl

[15] Ding, Laihao; Liu, Hong; Wang, Shuaichao; Yang, Haotian Vanishing codegree Turán density implies vanishing uniform Turán density (2023) | arXiv | Zbl

[16] Ellis, David; Ivan, Maria-Romina; Leader, Imre Turán densities for daisies and hypercubes, Bull. Lond. Math. Soc., Volume 56 (2024) no. 12, pp. 3838-3853 | DOI | MR | Zbl

[17] Erdős, Pál; Simonovits, Miklós A limit theorem in graph theory, Stud. Sci. Math. Hung., Volume 1 (1966), pp. 51-57 | MR | Zbl

[18] Erdős, Pál; Stone, Arthur H. On the structure of linear graphs, Bull. Am. Math. Soc., Volume 52 (1946), pp. 1087-1091 | DOI | MR | Zbl

[19] Falgas-Ravry, Victor; Marchant, Edward; Pikhurko, Oleg; Vaughan, Emil The codegree threshold for 3-graphs with independent neighborhoods, SIAM J. Discrete Math., Volume 29 (2015) no. 3, pp. 1504-1539 | DOI | MR | Zbl

[20] Falgas-Ravry, Victor; Pikhurko, Oleg; Vaughan, Emil; Volec, Jan The codegree threshold of $K_{4}^{-}$ , J. Lond. Math. Soc. (2), Volume 107 (2023) no. 5, pp. 1660-1691 | DOI | MR | Zbl

[21] Falgas-Ravry, Victor; Vaughan, Emil Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs, Comb. Probab. Comput., Volume 22 (2013) no. 1, pp. 21-54 | DOI | Zbl | MR

[22] Frankl, Peter; Füredi, Zoltán A new generalization of the Erdős-Ko-Rado theorem, Combinatorica, Volume 3 (1983) no. 3-4, pp. 341-349 | DOI | MR | Zbl

[23] Frankl, Peter; Füredi, Zoltán An exact result for $3$ -graphs, Discrete Math., Volume 50 (1984) no. 2-3, pp. 323-328 | DOI | MR | Zbl

[24] Frankl, Peter; Rödl, Vojtěch Hypergraphs do not jump, Combinatorica, Volume 4 (1984) no. 2-3, pp. 149-159 | DOI | MR | Zbl

[25] Füredi, Zoltán; Pikhurko, Oleg; Simonovits, Miklós The Turán density of the hypergraph ${a b c, a d e, b d e, c d e}$ , Electron. J. Comb., Volume 10 (2003), Paper no. 18, 7 pages | DOI | MR | Zbl

[26] Halfpap, Anastasia personal communication

[27] Halfpap, Anastasia; Lemons, Nathan; Palmer, Cory Positive co-degree density of hypergraphs (2024) | arXiv

[28] Halfpap, Anastasia; Magnan, Van Positive co-degree thresholds for spanning structures (2024) | arXiv | Zbl

[29] Kamčev, Nina; Letzter, Shoham; Pokrovskiy, Alexey The Turán Density of Tight Cycles in Three-Uniform Hypergraphs, Int. Math. Res. Not., Volume 2024 (2023) no. 6, pp. 4804-4841 | DOI | Zbl | MR

[30] Keevash, Peter Hypergraph Turán problems, Surveys in combinatorics 2011 (London Mathematical Society Lecture Note Series), Volume 392, Cambridge University Press, 2011, pp. 83-139 | MR | DOI | Zbl

[31] Lidický, Bernard; Mattes, Connor; Pfender, Florian The Hypergraph Turán Densities of Tight Cycles Minus an Edge (2024) | arXiv | Zbl

[32] Ma, Jie On codegree Turán density of the 3-uniform tight cycle $C_{11}$ (2024) | arXiv | Zbl

[33] Mubayi, Dhruv The co-degree density of the Fano plane, J. Comb. Theory, Ser. B, Volume 95 (2005) no. 2, pp. 333-337 | DOI | MR | Zbl

[34] Mubayi, Dhruv; Rödl, Vojtěch On the Turán number of triple systems, J. Comb. Theory, Ser. A, Volume 100 (2002) no. 1, pp. 136-152 | DOI | MR | Zbl

[35] Mubayi, Dhruv; Zhao, Yi Co-degree density of hypergraphs, J. Comb. Theory, Ser. A, Volume 114 (2007) no. 6, pp. 1118-1132 | DOI | MR | Zbl

[36] Nagle, Brendan Turán related problems for hypergraphs, Congr. Numerantium, Volume 136 (1999), pp. 119-127 Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999) | MR | Zbl

[37] Piga, Simón; Sales, Marcelo; Schülke, Bjarne The codegree Turán density of tight cycles minus one edge, Comb. Probab. Comput., Volume 32 (2023) no. 6, pp. 881-884 | DOI | MR | Zbl

[38] Piga, Simón; Sanhueza-Matamala, Nicolás; Schacht, Mathias The codegree Turán density of $3$ -uniform tight cycles (2024) | arXiv | Zbl

[39] Piga, Simón; Schülke, Bjarne Hypergraphs with arbitrarily small codegree Turán density (2023) | arXiv | Zbl

[40] Pikhurko, Oleg On the limit of the positive $ℓ$ -degree Turán problem, Electron. J. Comb., Volume 30 (2023) no. 3, Paper no. 3.25, 15 pages | DOI | MR | Zbl

[41] Razborov, Alexander A. Flag algebras, J. Symb. Log., Volume 72 (2007) no. 4, pp. 1239-1282 | DOI | MR | Zbl

[42] Rödl, Vojtěch; Schacht, Mathias Generalizations of the removal lemma, Combinatorica, Volume 29 (2009) no. 4, pp. 467-501 | DOI | MR | Zbl

[43] Sós, Vera T. Remarks on the connection of graph theory, finite geometry and block designs, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II, Accad. Naz. Lincei, Rome, 1976, pp. 223-233 | MR | Zbl

[44] Turán, Paul Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 6 (1961), pp. 417-423 | DOI | MR

[45] Vaughan, Emil Flagmatic (http://lidicky.name/flagmatic/flagmatic.html)

[46] Volec, Jan personal communication, 2023

[47] Wu, Zhuo Positive co-degree Turán number for $C_{5}$ and $C_{5}^{-}$ , J. Graph Theory, Volume 109 (2025) no. 1, pp. 25-30 | DOI | MR | Zbl

Cited by Sources:

BROWSE ISSUES

About the journal

Editorial Board

Submit a paper

Journal Statistics