pith. sign in

arxiv: 2605.21208 · v1 · pith:O4PTHAPCnew · submitted 2026-05-20 · 🧮 math.CO

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

Haixiang Zhang , Mengyu Cao , Mei Lu This is my paper

Pith reviewed 2026-05-21 03:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords k-uniform hypergraphmatching numberdegree sequencedegree thresholdhypergraph matchingOre-degree
0
0 comments X

The pith

If the (2sk+1)th largest degree exceeds binom(n-1,k-1) minus binom(n-s,k-1), then a k-uniform hypergraph on n > 2sk vertices has a matching of size at least s.

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

The paper links the ordered vertex degrees of a k-uniform hypergraph to the size of its largest matching. For k at least 2, s at least 2 and n larger than 2sk, a lower bound on the (2sk+1)th degree forces the existence of s pairwise disjoint edges. The result generalizes earlier degree-matching theorems and improves the vertex-count requirement in a related Ore-degree conjecture from quadratic to linear in sk. When the lower bound on n is relaxed, the same matching guarantee holds for the (k+2s-2)th degree and that position is shown to be optimal.

Core claim

For integers k greater than or equal to 2, s greater than or equal to 2 and n greater than 2sk, if the (2sk+1)th largest degree d_{2sk+1} satisfies d_{2sk+1} greater than binom(n-1,k-1) minus binom(n-s,k-1), then the k-uniform hypergraph contains a matching of size at least s. Relaxing the condition on n yields the identical conclusion when the bound is placed on the (k+2s-2)th degree instead, and this index is optimal.

What carries the argument

The non-increasing degree sequence d1 greater than or equal to d2 greater than or equal to ... greater than or equal to dn, with the threshold applied specifically at position 2sk+1 (or k+2s-2 in the relaxed case) to guarantee enough high-degree vertices remain after removing the vertices of a potential small matching.

If this is right

  • The hypergraph must contain a matching of size at least s whenever the stated degree condition holds.
  • The same matching conclusion holds for the (k+2s-2)th degree once the lower bound on n is dropped.
  • The index k+2s-2 is the smallest possible position that works in the relaxed-n regime.
  • The Ore-degree condition of Balogh, Palmer and Raeisi implies a matching of size s already when n is at least 3sk.

Where Pith is reading between the lines

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

  • The same style of degree threshold may control other global properties such as covering number or Hamiltonicity in uniform hypergraphs.
  • Because only one term in the sorted degree list needs to be checked, the condition offers a fast certificate for the existence of a large matching.
  • The optimality statement implies that explicit constructions exist in which the degree sequence drops just below the threshold precisely at position k+2s-2 and the matching size is exactly s-1.

Load-bearing premise

The hypergraph must be exactly k-uniform on a vertex set whose size exceeds 2sk, which is required for the counting arguments that turn the degree threshold into a matching guarantee.

What would settle it

A single counterexample consisting of a k-uniform hypergraph on n greater than 2sk vertices whose (2sk+1)th degree meets or exceeds the stated binomial threshold yet whose largest matching has size strictly less than s.

read the original abstract

We study the connection between the degree sequence of a $k$-uniform hypergraph and the size of its largest matching. Let $\mathcal{F}$ be a $k$-uniform hypergraph on $n$ vertices and let $d_1 \ge d_2 \ge \dots \ge d_n$ be the vertex degrees arranged in non-increasing order. For integers $k\ge 2$, $s\ge 2$ and $n > 2sk$, we prove that if the $(2sk+1)$-th largest degree satisfies $d_{2sk+1} > \binom{n-1}{k-1} - \binom{n-s}{k-1},$ then $\mathcal{F}$ contains a matching of size at least $s$. This can be viewed as a generalization of theorems by Lu, Guo, and Jiang (2023) and Huang and Rao (2026). Moreover, by relaxing the range of $n$, we obtain the same bound for the $(k+2s-2)$-th largest degree vertex. Note that the number $k+2s-2$ is optimal. For a $k$-set of vertices $S \subseteq [n]$, the degree of $S$ is defined as $\mathrm{deg}(S) = \sum_{v \in S} \mathrm{deg}(v)$, and the minimum of $\mathrm{deg}(S)$ over all non-edge $k$-subsets $S \notin E(\mathcal{F})$ of $V(\mathcal{F})$ is the Ore-degree of $\mathcal{F}$, denoted by $\sigma_k(\mathcal{F})$. Balogh, Palmer and Raeisi proved: for $s \ge 2$ and $n \ge 3k^2(s-1)$, if $\sigma_k(\mathcal{F}) > k\left(\binom{n-1}{k-1} - \binom{n-s}{k-1}\right),$ then $\mathcal{F}$ contains a matching of size $s$. They also conjectured that the result holds when $n > sk$. As a corollary, we prove that the bound on $n$ can be taken to be linear in $sk$ ($ n \geq 3sk $).

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 / 2 minor

Summary. The paper establishes a degree-sequence condition guaranteeing a matching of size s in a k-uniform hypergraph F on n vertices: for k≥2, s≥2 and n>2sk, if the (2sk+1)-th largest degree satisfies d_{2sk+1} > binom(n-1,k-1) - binom(n-s,k-1), then the matching number is at least s. This generalizes results of Lu-Guo-Jiang (2023) and Huang-Rao (2026). By relaxing the vertex count, the authors obtain the same conclusion for the (k+2s-2)-th largest degree and prove that this index is optimal. As a corollary they improve the range in the Balogh-Palmer-Raeisi Ore-degree theorem from n≥3k²(s-1) to the linear bound n≥3sk.

Significance. If the counting arguments hold, the result supplies a clean, explicit degree threshold that forces large matchings and improves the quantitative range for the related Ore-degree conjecture. The optimality statement for the index k+2s-2 and the linear improvement in the corollary are concrete advances over the cited literature.

minor comments (2)
  1. The abstract states the main theorem for n>2sk but the corollary relaxes to n≥3sk; a brief sentence clarifying why the stricter linear bound suffices for the Ore-degree version would help readers.
  2. The optimality claim for the index k+2s-2 is asserted but the extremal construction is not exhibited in the abstract; adding a one-sentence description or reference to the construction in the introduction would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of our manuscript, including the accurate summary of our main results and the recommendation for minor revision. We are pleased that the significance of the degree-sequence condition, the optimality of the index k+2s-2, and the improved linear bound in the corollary are recognized.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes a direct combinatorial theorem linking the (2sk+1)-th degree in a k-uniform hypergraph to the existence of a matching of size s, for n > 2sk, via explicit binomial comparisons and counting arguments that rely on the stated range restriction to ensure strict inequalities. The result is presented as a generalization of external prior theorems, with a corollary improving the Ore-degree bound to n ≥ 3sk; neither the main proof nor the corollary reduces to self-definitional loops, fitted parameters called predictions, or load-bearing self-citations whose validity depends on the current paper. The derivation remains self-contained against the combinatorial hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard counting with binomial coefficients and basic matching definitions; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Binomial coefficient identities and non-increasing degree ordering are valid for any finite set.
    Used to express the degree threshold and to index the (2sk+1)th position.

pith-pipeline@v0.9.0 · 5953 in / 1282 out tokens · 43179 ms · 2026-05-21T03:18:39.280880+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.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 2 internal anchors

  1. [1]

    Alon and R

    N. Alon and R. B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1–22, 1987

    work page 1987

  2. [2]

    Bollobas, D

    B. Bollobas, D. Daykin, and P. Erdos. Sets of independent edges of a hypergraph. Quart. J. Math. Oxford Ser., 27:25–32, 1976

    work page 1976

  3. [3]

    P. Erd˝ os. A problem on independent r-tuples.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 8(93-95):2, 1965

    work page 1965

  4. [4]

    Erd˝ os and R

    P. Erd˝ os and R. Rado. Intersection theorems for systems of sets.Journal of the London Mathematical Society, 1(1):85–90, 1960

    work page 1960

  5. [5]

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

    work page 1961

  6. [6]

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

    work page 2013

  7. [7]

    Frankl and Z

    P. Frankl and Z. F˝ uredi. Forbidding just one intersection.Journal of Combinatorial Theory, Series A, 39(2):160–176, 1985

    work page 1985

  8. [8]

    Frankl and Z

    P. Frankl and Z. F˝ uredi. Exact solution of some Tur´ an-type problems.Journal of Combinatorial Theory, Series A, 45(2):226–262, 1987. 16

    work page 1987

  9. [9]

    Frankl and A

    P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022

    work page 2022

  10. [10]

    Frankl, T

    P. Frankl, T. Luczak, and K. Mieczkowska. On matchings in hypergraphs.Electron. J. Combin., 19(2):Paper 42, 5, 2012

    work page 2012

  11. [11]

    Frankl and J

    P. Frankl and J. Wang. On the largest degrees in intersecting hypergraphs.arXiv preprint arXiv:2511.15508, 2025

    work page arXiv 2025

  12. [12]

    Huang, P

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

    work page 2012

  13. [13]

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

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

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  14. [14]

    Huang and Y

    H. Huang and Y. Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.Journal of Combinatorial Theory, Series A, 150:233– 247, 2017

    work page 2017

  15. [15]

    Matchings in hypergraphs via Ore-degree conditions

    C. Palmer, J. Balogh and G. Raeisi. Matchings in hypergraphs via ore-degree conditions. arXiv, 2603.06415, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  16. [16]

    Erd˝ os, M

    P. Erd˝ os, M. Deza and P. Frankl. Intersection properties of systems of finite sets. Proceedings of the London Mathematical Society, 36(3):369–384, 1978

    work page 1978

  17. [17]

    H. Lu, M. Guo and Y. Jiang. Improved bound on vertex degree version of Erd˝ os matching conjecture.J. Graph Theory, 104(3):485–498, 2023

    work page 2023

  18. [18]

    Omidi and G

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

    work page 2024

  19. [19]

    K. Wu, R. Alweiss, S. Lovett and J. Zhang. Improved bounds for the sunflower lemma. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 624–630, 2020. 17

    work page 2020