pith. sign in

arxiv: 2603.06415 · v2 · submitted 2026-03-06 · 🧮 math.CO

Matchings in hypergraphs via Ore-degree conditions

J\'ozsef Balogh , Cory Palmer , Ghaffar Raeisi This is my paper

Pith reviewed 2026-05-15 15:10 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph matchingsOre-degreeintersecting familiesuniform hypergraphsdegree conditionsmatching theoremsdisjoint edges
0
0 comments X

The pith

Ore-degree sums over non-edges bound intersecting hypergraphs and force large matchings when exceeded.

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

The paper proves that any intersecting r-uniform hypergraph on n vertices with n at least 2r+2 has Ore-degree at most r times the binomial coefficient binom(n-2, r-2), and equality holds only for the complete 1-star. For r at least 3 and n at least 4r squared, non-trivial intersecting hypergraphs satisfy a strictly smaller upper bound. When the Ore-degree exceeds r times the difference binom(n-1, r-1) minus binom(n-s, r-1) and n is at least 3r squared times (s-1), the hypergraph must contain s pairwise disjoint edges. These degree-sum thresholds matter because they translate local non-edge information into global guarantees on the size of a matching.

Core claim

For an r-uniform hypergraph H on n vertices the Ore-degree σ_r(H) is the minimum, over all non-edges S, of the sum of the degrees of the vertices in S. The paper shows that if H is intersecting and n ≥ 2r+2 then σ_r(H) ≤ r binom(n-2, r-2), with equality if and only if H is a 1-star. For r ≥ 3 and n ≥ 4r² any non-trivial intersecting H satisfies the stricter bound σ_r(H) ≤ r (binom(n-2, r-2) − binom(n-r-2, r-2)). Finally, if σ_r(H) > r (binom(n-1, r-1) − binom(n-s, r-1)) and n ≥ 3r²(s-1), then H contains s pairwise disjoint edges.

What carries the argument

The Ore-degree σ_r(H), the minimum sum of vertex degrees taken over all non-edge r-sets, which serves as a single-number proxy that controls the existence of matchings.

If this is right

  • Any intersecting r-uniform hypergraph on sufficiently many vertices is forced to have Ore-degree no larger than that of the 1-star.
  • Non-trivial intersecting families on large vertex sets must have strictly smaller Ore-degree than the star extremal example.
  • Crossing the stated Ore-degree threshold immediately produces a matching of any prescribed size s.
  • The star constructions achieve the bound, showing that the numerical thresholds are tight.

Where Pith is reading between the lines

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

  • The same Ore-degree threshold might be used to obtain stability versions that describe the structure of near-extremal hypergraphs.
  • These conditions could be checked in polynomial time by computing all vertex degrees and then scanning non-edges, offering an algorithmic route to large matchings.
  • Similar summed-degree conditions may extend to non-uniform hypergraphs or to weighted versions where edges carry capacities.

Load-bearing premise

The hypergraph is exactly r-uniform and the vertex count n meets the stated lower bounds in terms of r and s.

What would settle it

An explicit r-uniform hypergraph on n = 3r²(s-1) vertices whose Ore-degree exceeds r (binom(n-1, r-1) − binom(n-s, r-1)) yet contains no set of s pairwise disjoint edges.

read the original abstract

Let $\mathcal{H} \subseteq \binom{[n]}{r}$ be an $r$-uniform hypergraph on vertex set $[n] = \{1,2,\dots, n\}$. For an $r$-set of vertices $S \subseteq [n]$, the \emph{degree} of $S$ is defined as $\textrm{deg}(S)=\sum_{v \in S}\textrm{deg}(v)$ and the minimum of $\textrm{deg}(S)$ over all non-edge $r$-subsets $S \not \in E(\mathcal{H})$ of $V({\cal H})$ is the {\it Ore-degree} of ${\cal H}$, denoted by ${\sigma_r}({\cal H})$. We prove several Ore-degree results about existence of matchings in hypergraphs: (1) For $n\geq 2r+2$, if ${\cal H}$ is an intersecting $r$-uniform hypergraph on $n$ vertices, then $\sigma_r({\cal H})\leq r{n-2 \choose r-2}$, and there is equality only when ${\cal H}$ is a $1$-star. (2) For $r\geq 3$ and $n\geq 4r^2$, if is a non-trivial intersecting $r$-uniform hypergraph on $n$ vertices, then $\sigma_r({\cal H})\leq r\left({n-2 \choose r-2}-{n-r-2 \choose r-2}\right)$. (3) For $s\geq 2$ and $n\geq 3r^2(s-1)$, if ${\cal H}$ is an $r$-uniform hypergraph on $n$ vertices and $\sigma_r({\cal H})>r\left({n-1 \choose r-1}-{n-s \choose r-1}\right)$, then ${\cal H}$ contains $s$ pairwise disjoint edges.

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

0 major / 1 minor

Summary. The manuscript proves three Ore-degree theorems for matchings in r-uniform hypergraphs on n vertices. For n ≥ 2r+2, any intersecting H satisfies σ_r(H) ≤ r binom(n-2,r-2) with equality only for the 1-star. For r ≥ 3 and n ≥ 4r², non-trivial intersecting H obeys the stricter bound σ_r(H) ≤ r(binom(n-2,r-2) - binom(n-r-2,r-2)). For s ≥ 2 and n ≥ 3r²(s-1), the condition σ_r(H) > r(binom(n-1,r-1) - binom(n-s,r-1)) forces H to contain s pairwise disjoint edges.

Significance. If the proofs are correct, the results supply tight, explicit Ore-type bounds that extend classical graph matching theorems to hypergraphs while characterizing extremal intersecting families. The equality case for the 1-star and the quantitative improvement for non-trivial intersecting hypergraphs are concrete advances in extremal set theory.

minor comments (1)
  1. Abstract, theorem (2): the sentence begins 'if is a non-trivial' and is missing the subject H; this is a typographical omission that should be corrected for readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. We appreciate the recognition that the results provide tight Ore-type bounds extending classical matching theorems to hypergraphs, along with the characterization of extremal intersecting families. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives Ore-degree bounds for matchings in r-uniform hypergraphs via standard double counting and extremal set theory on intersecting families. All three theorems follow directly from the given degree definitions, the intersecting property, and the stated lower bounds on n in terms of r and s. No steps reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations; the equality case for the 1-star is immediately verifiable from the Ore-degree definition itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard mathematical axioms from set theory and combinatorics with no free parameters fitted to data and no invented entities postulated.

axioms (1)
  • standard math Standard definitions and properties of r-uniform hypergraphs, degrees, and intersecting families
    Invoked throughout the statements of the three results.

pith-pipeline@v0.9.0 · 5659 in / 1175 out tokens · 52518 ms · 2026-05-15T15:10:17.980668+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 1 Pith paper

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

  1. On degree bounds of $k$-uniform hypergraphs with bounded matching number

    math.CO 2026-05 unverdicted novelty 6.0

    The authors establish a degree-sequence condition guaranteeing a matching of size s in k-uniform hypergraphs and relax the n requirement for an Ore-degree matching theorem to n at least 3sk.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Bar´ at, G

    J. Bar´ at, G. N. S´ ark¨ ozy, Partitioning 2-edge-colored Ore-type graphs by monochromatic cycles,J. Graph Theory 81(4) (2016), 317–328

    work page 2016

  2. [2]

    Bollob´ as, D

    B. Bollob´ as, D. E. Daykin, P. Erd˝ os, Sets of independent edges of a hypergraph,Q. J. Math. Oxf. Ser.27(105) (1976), 25–32

    work page 1976

  3. [3]

    Erd˝ os, A problem on independentr-tuples,Ann

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

    work page 1965

  4. [4]

    Erd˝ os, T

    P. Erd˝ os, T. Gallai, On the minimal number of vertices representing the edges of a graph,Publ. Math. Inst. Hung. Acad. Sci.6(1961), 181–203. 14

    work page 1961

  5. [5]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, R. Rado, Intersection Theorems for Systems of Finite Sets,Quart. J. Math.12(1) (1961), 313–320

    work page 1961

  6. [6]

    R. J. Faudree, R. J. Gould, A. V. Kostochka, L. Lesniak, I. Schiermeyer, A. Saito, Degree conditions fork-ordered Hamiltonian graphs,J. Graph Theory42(2003), 199–210

    work page 2003

  7. [7]

    Ferrara, R

    M. Ferrara, R. Gould, M. Jacobson, F. Pfender, J. Powell, T. Whalen, New Ore-type conditions forH-linked graphs,J. Graph Theory71(2012), 69–77

    work page 2012

  8. [8]

    Frankl, Erd˝ os–Ko–Rado theorem with conditions on the maximal degree,J

    P. Frankl, Erd˝ os–Ko–Rado theorem with conditions on the maximal degree,J. Combin. Theory A46(1987), 252–263

    work page 1987

  9. [9]

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

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

    work page 2013

  10. [10]

    Frankl, On the maximum number of edges in a hypergraph with a given matching number,Discrete Appl

    P. Frankl, On the maximum number of edges in a hypergraph with a given matching number,Discrete Appl. Math.216(2017), 562–581

    work page 2017

  11. [11]

    Frankl, R

    P. Frankl, R. L. Graham, Old and new proofs of the Erd˝ os–Ko–Rado theorem,Sichuan Daxue Xuebao26(1989), 112–122

    work page 1989

  12. [12]

    Frankl, J

    P. Frankl, J. Han, H. Hao, Z. Yi, A degree version of the Hilton–Milner theorem,J. Combin. Theory Ser. A155 (2018), 493–502

    work page 2018

  13. [13]

    Frankl, A

    P. Frankl, A. Kupavskii, A size-sensitive inequality for cross-intersecting families.European J. Combin.62(2017), 263–271

    work page 2017

  14. [14]

    Frankl, V

    P. Frankl, V. R¨ odl, A. Ruci´ nski, On the maximum number of edges in a triple system not containing a disjoint family of a given size,Combin. Probab. Comput.21(2012), 141–148

    work page 2012

  15. [15]

    Frankl, N

    P. Frankl, N. Tokushige, A note on Huang–Zhao theorem on intersecting families with large minimum degree, Discrete Math.340(5) (2017), 1098–1103

    work page 2017

  16. [16]

    Frankl and J

    P. Frankl, J. Wang, On the Largest Degrees in Intersecting Hypergraphs, arXiv:2511.15508

    work page arXiv

  17. [17]

    J. Han, Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family,Proc. Amer. Math. Soc.145(1) (2017), 73–87

    work page 2017

  18. [18]

    Hilton, E

    A. Hilton, E. Milner, Some intersection theorems for systems of finite sets,Q. J. Math. Oxf. Ser.18(2) (1967), 369–384

    work page 1967

  19. [19]

    Huang, P

    H. Huang, P. Loh, B. Sudakov, The size of a hypergraph and its matching number,Combin. Probab. Comput. 21(2012), 442–450

    work page 2012

  20. [20]

    Huang, Y

    H. Huang, Y. Zhao, Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching,J. Combin. Theory Ser. A150(2017), 233–247

    work page 2017

  21. [21]

    Huang, T

    H. Huang, T. Li, G. Wang, Rainbow matchings in properly-colored hypergraphs,Electron. J. Combin.26(1) (2019),#P1.4

    work page 2019

  22. [22]

    On the $\ell$-th largest degree of an intersecting family

    H. Huang, R. Rao, On theℓ-th largest degree of an intersecting family, arXiv:2602.01692

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    Ihringer, A

    F. Ihringer, A. Kupavskii, Regular intersecting families,Discrete Appl. Math.270(2019), 142–152

    work page 2019

  24. [24]

    H. A. Kierstead, A.V. Kostochka, An Ore-type theorem on equitable coloring,J. Combin. Theory Ser. B98(1) (2008), 226–234

    work page 2008

  25. [25]

    H. A. Kierstead, A. V. Kostochka, Ore-type versions of Brooks theorem,J. Combin. Theory Ser. B99(2) (2009), 298–305

    work page 2009

  26. [26]

    Kupavskii, Degree versions of theorems on intersecting families via stability,J

    A. Kupavskii, Degree versions of theorems on intersecting families via stability,J. Combin. Theory Ser. A168 (2019), 272–287

    work page 2019

  27. [27]

    Luczak, K

    T. Luczak, K. Mieczkowska, On Erd˝ os extremal problem on matchings in hypergraphs,J. Combin. Theory Ser. A124(2014), 178–194

    work page 2014

  28. [28]

    G. R. Omidi, G. Raeisi, Ramsey-Tur´ an type results for matchings in edge colored graphs,Discrete Math.347 (3) (2024), 113785

    work page 2024

  29. [29]

    Ore, Note on Hamilton circuits,Am

    O. Ore, Note on Hamilton circuits,Am. Math. Mon.67(1960), 55

    work page 1960

  30. [30]

    Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem,J

    L. Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem,J. Combin. Theory Ser. A43(1986), 85–90

    work page 1986

  31. [31]

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

    work page 1984

  32. [32]

    B. Wu, R. Xiong, H. Rong, A note on the maximum product-size of non-trivial crosst-intersecting families, Discrete Math.347(2) (2024), 113783. 15

    work page 2024