pith. sign in

arxiv: 2310.09379 · v4 · submitted 2023-10-13 · 🧮 math.CO

Some exact and asymptotic results for hypergraph Tur\'an problems in ell₂-norm

George Brooks , William Linz This is my paper

Pith reviewed 2026-05-24 06:34 UTC · model grok-4.3

classification 🧮 math.CO
keywords Erdős-Ko-Rado theoremcodegree squared sumhypergraph Turán problemsintersecting familiesErdős matching conjecturepaths and cyclesℓ2-norm
0
0 comments X

The pith

Intersecting k-uniform families have codegree squared sum at most that of the star for n at least 2k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an Erdős-Ko-Rado type result measured by the codegree squared sum rather than family size. For any intersecting family F of k-subsets of an n-element set with n at least 2k, co₂(F) is at most binom(n-1,k-1) times (1 plus (n-k+1) times (k-1)), with equality only for the star when n exceeds 2k. The proof relies on Bey's inequality applied to the codegree vector. The same tool yields a general upper bound on the codegree squared extremal number exco₂(n,F) for arbitrary forbidden families F. Additional exact or asymptotic determinations are given for matchings, t-intersecting families at large n, and minimal or linear paths and cycles.

Core claim

If F subset binom([n],k) is intersecting and n ≥ 2k, then co₂(F) ≤ binom(n-1,k-1)(1+(n-k+1)(k-1)), with equality only for the star when n > 2k. The authors also establish analogous results for the Erdős matching conjecture and t-intersecting families in the large n regime, as well as exact values for the codegree squared extremal number of minimal and linear 3-paths and 3-cycles and asymptotic values for s-paths and s-cycles when s ≥ 4.

What carries the argument

Bey's inequality applied directly to the codegree vector, which bounds the squared sum of codegrees for any k-uniform hypergraph.

If this is right

  • The codegree squared extremal number exco₂(n, intersecting family) equals the value for the star when n ≥ 2k.
  • Analogous bounds hold for the Erdős matching conjecture and t-intersecting families when n is sufficiently large.
  • Exact values are obtained for exco₂(n, minimal 3-path), exco₂(n, linear 3-path), exco₂(n, minimal 3-cycle) and exco₂(n, linear 3-cycle).
  • Asymptotic determinations are obtained for exco₂(n, minimal s-path), exco₂(n, linear s-path), exco₂(n, minimal s-cycle) and exco₂(n, linear s-cycle) when s ≥ 4.
  • Graph Turán-type problems in the ℓ₂-norm admit exact or asymptotic results via spectral extremal graph theory and Hofmeister's inequality.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method may yield stability versions that classify near-extremal families in this norm.
  • Similar bounds could be sought for other ℓ_p-norms on the codegree vector.
  • The graph results suggest that spectral methods for forbidden subgraphs translate directly into ℓ₂-norm Turán bounds for ordinary graphs.

Load-bearing premise

Bey's inequality applies directly to the codegree vector of an arbitrary k-uniform hypergraph without additional structural assumptions on the support of the codegrees.

What would settle it

An intersecting k-uniform hypergraph on n=2k+1 vertices whose codegree squared sum exceeds the stated bound.

read the original abstract

For a $k$-uniform hypergraph $\mathcal{H}$, the \emph{codegree squared sum} $\text{co}_2(\mathcal{H})$ is the square of the $\ell_2$-norm of the codegree vector of $\mathcal{H}$, and for a family $\mathscr{F}$ of $k$-uniform hypergraphs, the codegree squared extremal number $\text{exco}_2(n, \mathscr{F})$ is the maximum codegree squared sum of a hypergraph on $n$ vertices which does not contain any hypergraph in $\mathscr{F}$. Balogh, Clemen and Lidick\'y recently introduced the codegree squared extremal number and determined it for a number of $3$-uniform hypergraphs, including the complete graphs $K_4^3$ and $K_5^3$. In this paper, we give a number of exact or asymptotic results for hypergraph Tur\'an problems in the $\ell_2$-norm, including the first exact results for arbitrary $k$. Namely, we prove a version of the classical Erd\H{o}s-Ko-Rado theorem for the codegree squared extremal number: if $\mathcal{F} \subset \binom{[n]}{k}$ is intersecting and $n\ge 2k$, then \[\text{co}_2(\mathcal{F}) \le \binom{n-1}{k-1}(1+(n-k+1)(k-1)),\] with equality only for the star for $n > 2k$. Our main tool is an inequality of Bey, which also gives a general upper bound on $\text{exco}_2(n, \mathscr{F})$. We also prove versions of the Erd\H{o}s Matching Conjecture and the $t$-intersecting Erd\H{o}s-Ko-Rado theorem for the codegree squared extremal number for large $n$, determine the exact codegree squared extremal number of minimal and linear $3$-paths and $3$-cycles, and determine asymptotically the codegree squared extremal number of minimal and linear $s$-paths and $s$-cycles for $s\ge 4$. Lastly, we derive a number of exact or asymptotic results for graph Tur\'an-type problems in the $\ell_2$-norm from spectral extremal results for certain forbidden subgraph problems and the well-known Hofmeister's inequality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves several exact and asymptotic results on the codegree squared extremal number exco₂(n, ℱ) for k-uniform hypergraphs. The central result is an EKR-type theorem: for an intersecting k-uniform family F on [n] with n ≥ 2k, co₂(F) ≤ binom(n-1,k-1)(1+(n-k+1)(k-1)), with equality only for the star when n > 2k. It also gives large-n versions of the Erdős Matching Conjecture and t-intersecting EKR, exact values for minimal/linear 3-paths and 3-cycles, asymptotics for s-paths/cycles with s ≥ 4, a general upper bound via Bey's inequality, and some graph ℓ₂-Turán results derived from spectral extremal theorems and Hofmeister's inequality.

Significance. If the derivations hold, the work supplies the first exact results for arbitrary k in the codegree squared norm and extends several classical hypergraph Turán theorems to this setting. A strength is the parameter-free derivation of the general upper bound from Bey's inequality and the exact determination of exco₂ for several small forbidden configurations without additional assumptions.

major comments (1)
  1. [Proof of Theorem 1.1] Proof of Theorem 1.1 (EKR-type statement): Bey's inequality is applied directly to the codegree vector d of an arbitrary intersecting k-uniform family F. The manuscript does not verify or cite that d satisfies the precise hypotheses of Bey's inequality (typically non-negativity together with a support condition such as being a down-set or having nested support under the partial order). If intersecting families can produce codegree vectors outside this domain, the bound is not established for all such F.
minor comments (2)
  1. [§3] §3, statement of the general bound: the dependence on the forbidden family ℱ is stated only asymptotically; an explicit statement of the resulting upper bound in terms of the parameters of Bey's inequality would improve readability.
  2. [Introduction] Notation: the codegree vector is introduced without an explicit definition of its indexing set in the opening paragraphs; adding a sentence clarifying that the vector is indexed by (k-1)-subsets would remove ambiguity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this point about the hypotheses of Bey's inequality. We address the comment below.

read point-by-point responses

  1. Referee: Proof of Theorem 1.1 (EKR-type statement): Bey's inequality is applied directly to the codegree vector d of an arbitrary intersecting k-uniform family F. The manuscript does not verify or cite that d satisfies the precise hypotheses of Bey's inequality (typically non-negativity together with a support condition such as being a down-set or having nested support under the partial order). If intersecting families can produce codegree vectors outside this domain, the bound is not established for all such F.

    Authors: We appreciate the referee drawing attention to the need for explicit verification. The codegree vector d is non-negative by definition for any hypergraph. We will revise the manuscript to include a short paragraph that (i) cites the precise statement of Bey's inequality from the reference, (ii) confirms that d satisfies non-negativity, and (iii) verifies the support condition holds for codegree vectors of arbitrary intersecting families (the intersecting property does not remove any (k-1)-sets from the domain, and the vector remains defined over the full collection of (k-1)-subsets). This addition will make the application fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity; bounds derived from external Bey inequality

full rationale

The paper's central EKR-type result for co_2(F) on intersecting families is obtained by direct application of Bey's inequality (an external result) to the codegree vector of an arbitrary intersecting k-uniform family. The abstract explicitly states the main tool is 'an inequality of Bey' and gives the bound without any fitted parameters, self-definitional constructions, or load-bearing self-citations. No step reduces the claimed inequality to the paper's own inputs by construction; the derivation chain remains self-contained against the cited external inequality and classical theorems. The equality case for the star is verified separately but does not create a circular loop.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard combinatorial definitions and one external inequality; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Bey's inequality holds for the codegree vector of any k-uniform hypergraph
    Invoked to obtain the general upper bound and the EKR-type statement.

pith-pipeline@v0.9.0 · 5986 in / 1290 out tokens · 20162 ms · 2026-05-24T06:34:12.094457+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Counting sunflowers in hypergraphs with bounded matching number and Erd\H{o}s Matching Conjecture in the $(t,k)$-norm

    math.CO 2026-04 conditional novelty 8.0

    The maximum number of S_{r-1,k}^r copies in an r-uniform hypergraph with matching number at most ν is independent of k and equals the number in the extremal construction given by the Erdős Matching Conjecture; this im...

  2. Counting sunflowers with restricted matching number

    math.CO 2026-04 unverdicted novelty 5.0

    For large n the maximum ℓ_p-norm and maximum number of S_{k,l}^{k-1} sunflowers are determined exactly for any k-uniform family with matching number s.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · cited by 2 Pith papers

  1. [1]

    Ahlswede, N

    R. Ahlswede, N. Cai, A counterexample to Kleitman ’s conjecture concerning an ed ge- isoperimetric problem, Comb. Probab. Comp., 8.4 (1999), 301–305

    work page 1999

  2. [2]

    Ahlswede, G.O.H

    R. Ahlswede, G.O.H. Katona, Graphs with maximal number of pairs of adjacent edges , Acta Math Acad. Sci Hungar., 32 (1978), 97–120

    work page 1978

  3. [3]

    Ahlswede, L

    R. Ahlswede, L. Khachatrian, The Complete Nontrivial-Intersection Theorem for Sys- tems of Finite Sets , J. Combin Theory, Series A, 76 (1996), 21–38

    work page 1996

  4. [4]

    Balogh, F.C

    J. Balogh, F.C. Clemen, B. Lidick´ y, Hypergraph Tur´ an Problems inℓ2-norm, Surveys in Combinatorics 2022, 21–63, London Math. Soc. Lecture Note Se r., 481, Cambridge University Press (2022)

    work page 2022

  5. [5]

    Balogh, F.C

    J. Balogh, F.C. Clemen, B. Lidick´ y, Solving Tur´ an ’s Tetrahedron Problem for the ℓ2- norm, J. London Math. Soc. 106 (2022), no. 1, 60–84

    work page 2022

  6. [6]

    Balogh, W

    J. Balogh, W. Linz, Short proofs of three results about intersecting systems , Comb. The- ory, 4 (2024), no. 1, Paper No. 4, 15pp

    work page 2024

  7. [7]

    Bey, An upper bound on the sum of squares of degrees in a hypergraph , Discrete Math

    C. Bey, An upper bound on the sum of squares of degrees in a hypergraph , Discrete Math. 269 (2003), 259–263

    work page 2003

  8. [8]

    Bey, Remarks on an Edge Isoperimetric Problem , in General theory of information transfer and combinatorics, Lecture Notes in Computer Science, 4123, Springer, (2006), 971–978

    C. Bey, Remarks on an Edge Isoperimetric Problem , in General theory of information transfer and combinatorics, Lecture Notes in Computer Science, 4123, Springer, (2006), 971–978

    work page 2006

  9. [9]

    Byrne, D

    J. Byrne, D. N. Desai, M. Tait, A general theorem in spectral extremal graph theory , preprint available at arXiv:2401.07266

    work page arXiv

  10. [10]

    Y. Caro, R. Yuster, A Tur´ an type problem concerning the powers of the degrees of a graph, Electron. J. Combin. 7 #R47 (2000)

    work page 2000

  11. [11]

    Y. Caro, R. Yuster, A Tur´ an type problem concerning the powers of the degrees of a graph(revised), available at arXiv:0401398

    work page

  12. [12]

    de Caen, Extension of a theorem of Moon and Moser on complete subgraph s, Ars Combin., 16 (1983), 5–10

    D. de Caen, Extension of a theorem of Moon and Moser on complete subgraph s, Ars Combin., 16 (1983), 5–10

    work page 1983

  13. [13]

    de Caen, An upper bound on the sum of squares of degrees in a graph , Discrete Math

    D. de Caen, An upper bound on the sum of squares of degrees in a graph , Discrete Math. 185 (1998), 245–248

    work page 1998

  14. [14]

    de Caen and Z

    D. de Caen and Z. F¨ uredi, The maximum size of 3-uniform hypergraphs not containing a Fano plane , J. Combin. Theory, Ser. B, 78 (2000), 274–276. 23

    work page 2000

  15. [15]

    Chv´ atal, An extremal set-intersection theorem , J

    V. Chv´ atal, An extremal set-intersection theorem , J. London Math. Soc., 9 (1974), 355–359

    work page 1974

  16. [16]

    Cioab˘ a, D

    S. Cioab˘ a, D. N. Desai, M. Tait, The spectral even cycle problem , preprint available at arXiv:2005.00990

    work page arXiv 2005

  17. [17]

    Cioab˘ a, D

    S. Cioab˘ a, D. N. Desai, M. Tait, A spectral version of the Erd˝ os-S´ os theorem, 37, no. 3, (2023)

    work page 2023

  18. [18]

    Cs´ ak´ any and J

    R. Cs´ ak´ any and J. Kahn, A homological approach to two problems on finite sets , J. Algebraic Combin., 9 (1999), 141–149

    work page 1999

  19. [19]

    Currier, On the d-cluster generalization of Erd˝ os-Ko-Rado, J

    G. Currier, On the d-cluster generalization of Erd˝ os-Ko-Rado, J. Combin. Theory, Ser. A 182, (2021)

    work page 2021

  20. [20]

    Currier, New results on simplex-clusters in set systems , Combinatorica, 41 (2021), 495–506

    G. Currier, New results on simplex-clusters in set systems , Combinatorica, 41 (2021), 495–506

    work page 2021

  21. [21]

    S. Das, W. Gan, B. Sudakov, The minimum number of disjoint pairs in set systems and related problems, Combinatorica 36, no. 6, (2015), 623–660

    work page 2015

  22. [22]

    Erd˝ os,On extremal problems of graphs and generalized graphs , Israel J

    P. Erd˝ os,On extremal problems of graphs and generalized graphs , Israel J. Math., 2(3) (1964), 183–190

    work page 1964

  23. [23]

    Erd˝ os,A problem on independent r-tuples, Ann

    P. Erd˝ os,A problem on independent r-tuples, Ann. Univ. Sci. Budapest 8 (1965), 93–95

    work page 1965

  24. [24]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets , Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320

    work page 1961

  25. [25]

    Erd˝ os, L

    P. Erd˝ os, L. P´ osa,On the maximal number of disjoint circuits of a graph , Publ. Math. Debrecen, 9 (1962), 3–12

    work page 1962

  26. [26]

    Frankl, Improved bounds for Erd˝ os’ matching conjecture, J

    P. Frankl, Improved bounds for Erd˝ os’ matching conjecture, J. Comb. Theory, Ser. A, 120 (2013), 1068–1072

    work page 2013

  27. [27]

    Frankl, On intersecting families of finite sets , J

    P. Frankl, On intersecting families of finite sets , J. Comb. Theory, Ser. A, 24 (1978), 146–161

    work page 1978

  28. [28]

    Frankl, Sperner families satisfying an additional condition , J

    P. Frankl, Sperner families satisfying an additional condition , J. Comb. Theory, Ser. A 20 (1976), 1–11

    work page 1976

  29. [29]

    Frankl and Z

    P. Frankl and Z. F¨ uredi,Exact solution of some Tur´ an-type problems, J. Comb. Theory, Ser. A 45 (1987), 226–262

    work page 1987

  30. [30]

    Frankl and A

    P. Frankl and A. Kupavskii, The Erd˝ os matching conjecture and concentration inequal- ities, J. Comb. Theory, Ser. B 157 (2022), 366–400. 24

    work page 2022

  31. [31]

    Frankl and A

    P. Frankl and A. Kupavskii, Families with no s pairwise disjoint sets , J. London Math. Soc. 95 (2017), N3, 875–894

    work page 2017

  32. [32]

    F¨ uredi and T

    Z. F¨ uredi and T. Jiang, Hypergraph Tur´ an numbers of linear cycles. J. Comb. Theory, Ser. A, 123 (2014) , 252–270

    work page 2014

  33. [33]

    F¨ uredi, T

    Z. F¨ uredi, T. Jiang and R. Seiver, Exact solution of the hypergraph Tur´ an problem for k-uniform linear paths , Combinatorica, 34 (2014), 299–322

    work page 2014

  34. [34]

    Gerbner, On degree powers and counting stars in F -free graphs , available at arXiv:2401.04894

    D. Gerbner, On degree powers and counting stars in F -free graphs , available at arXiv:2401.04894

    work page arXiv

  35. [35]

    R. L. Graham and N. J. A Sloane, Lower bounds for constant weight codes , IEEE Trans. Inform. Theory, 26, no. 1 (1980), 37–43

    work page 1980

  36. [36]

    Gruslys, S

    V. Gruslys, S. Letzter, and N. Morrison, Lagrangians of hypergraphs II: When colex is best, Israel J. Math., 242, no. 2, (2021), 637–662

    work page 2021

  37. [37]

    L. H. Harper, Global methods for combinatorial isoperimetric problems , Cambridge Uni- versity Press (2004)

    work page 2004

  38. [38]

    L. H. Harper, On a problem of Kleitman and West , Disc. Math. 93 (1991), 169–182

    work page 1991

  39. [39]

    A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets , Quarterly Journal of Mathematics, 18 (1967), no. 1, 369–384

    work page 1967

  40. [40]

    Hofmeister, Spectral radius and degree sequence , Math

    M. Hofmeister, Spectral radius and degree sequence , Math. Nachr., 139 (1988), 37–44

    work page 1988

  41. [41]

    Keevash, Hypergraph Tur´ an problems, Surveys in Combinatorics 2011, 83–139, Lon- don Math

    P. Keevash, Hypergraph Tur´ an problems, Surveys in Combinatorics 2011, 83–139, Lon- don Math. Soc. Lecture Note Ser., 392, Cambridge University Press (2011)

    work page 2011

  42. [42]

    Keevash and D

    P. Keevash and D. Mubayi, Set systems without a simplex or cluster , Combinatorica 30 (2010), 175–200

    work page 2010

  43. [43]

    Kostochka, D

    A. Kostochka, D. Mubayi and J. Verstra¨ ete, Tur´ an problems and shadows I: Paths and cycles, J. Comb. Theory, Ser. A, 129 (2105), 57–79

    work page

  44. [44]

    Lifshitz, On set systems without a simplex-cluster and the junta metho d, J

    N. Lifshitz, On set systems without a simplex-cluster and the junta metho d, J. Combin. Theory, Ser. A 170 (2020)

    work page 2020

  45. [45]

    Liu and M

    R. Liu and M. Zhai, A spectral Erd˝ os-P´ osa Theorem, (2022), preprint available at arXiv:2208.02988

    work page arXiv 2022

  46. [46]

    Mubayi, Erd˝ os-Ko-Rado for three sets, J

    D. Mubayi, Erd˝ os-Ko-Rado for three sets, J. Comb. Theory, Ser. A, 113 (2006), 547– 550

    work page 2006

  47. [47]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete, Minimal paths and cycles in set-systems , Eur. J. Comb. 28 (2007), 1681–1693. 25

    work page 2007

  48. [48]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete, Proof of a conjecture of Erd˝ os on triangles in set-systems, Combinatorica 25, no. 5 (2005), 599–614

    work page 2005

  49. [49]

    Nikiforov, Bounds on graph eigenvalues II , Lin Alg

    V. Nikiforov, Bounds on graph eigenvalues II , Lin Alg. Appl. 427 (2007), 183–189

    work page 2007

  50. [50]

    Nikiforov, Degree powers in graphs with a forbidden even cycle , Elect

    V. Nikiforov, Degree powers in graphs with a forbidden even cycle , Elect. J. Combina- torics, 16 (2009), #R107

    work page 2009

  51. [51]

    Nikiforov, Some inequalities for the largest eigenvalue of a graph , Comb

    V. Nikiforov, Some inequalities for the largest eigenvalue of a graph , Comb. Probab. Comput. 11 (2002), 179–189

    work page 2002

  52. [52]

    Nikiforov, The spectral radius of graphs without paths and cycles of spe cified length , Lin Alg

    V. Nikiforov, The spectral radius of graphs without paths and cycles of spe cified length , Lin Alg. Appl. 432, no. 2 (2010), 2243–2256

    work page 2010

  53. [53]

    O’Neill and J

    J. O’Neill and J. Verstra¨ ete,Non-trivial d-wise intersecting families , J. Combin. Theory, Series A 178 (2021), Paper 105369, 12pp

    work page 2021

  54. [54]

    Polcyn and A

    J. Polcyn and A. Ruci´ nski,A hierarchy of maximal triple intersecting systems , Opuscula Math., 37 (4) (2017)

    work page 2017

  55. [55]

    Tait, The Colin de Verdi´ ere parameter, excluded minors and the sp ectral radius, J

    M. Tait, The Colin de Verdi´ ere parameter, excluded minors and the sp ectral radius, J. Combin. Theory, Ser. A 166 (2019), 42–58

    work page 2019

  56. [56]

    M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory, J. Combin Theory Series B, 126 (2017), 137–161

    work page 2017

  57. [57]

    Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Sci- ence, 7, nos

    S. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Sci- ence, 7, nos. 1–3 (2011), 1–336

    work page 2011

  58. [58]

    Wilson, The exact bound in the Erd˝ os-Ko-Rado theorem, Combinatorica, 4, (1984), 247–257

    R.M. Wilson, The exact bound in the Erd˝ os-Ko-Rado theorem, Combinatorica, 4, (1984), 247–257

    work page 1984

  59. [59]

    Zhai and H

    M. Zhai and H. Lin, Spectral extrema of Ks,t-minor-free graphs - On a conjecture of M. Tait, J. Combin Theory Ser. B, 157 (2022), 184–215. 26

    work page 2022