pith. sign in

arxiv: 2604.13726 · v1 · submitted 2026-04-15 · 🧮 math.CO

A local spectral condition for perfect matchings in 3-graphs

Huiqiu Lin , Hongliang Lu , Feihong Yuan , Xiaonan Zhao This is my paper

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

classification 🧮 math.CO
keywords 3-uniform hypergraphsperfect matchingsspectral radiuslink graphsfractional matchingshypergraph matching
0
0 comments X

The pith

If the spectral radius of every link graph exceeds (2/3 + γ)n in a large 3-uniform hypergraph, then it has a perfect matching.

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

The paper proves a sufficient condition for perfect matchings in 3-uniform hypergraphs. For n large and divisible by 3, if the spectral radius of the link graph of every vertex is strictly larger than (2/3 + γ)n, the hypergraph contains a perfect matching. This spectral threshold is asymptotically tight and improves on earlier minimum-degree requirements by measuring the density of edges through each vertex via the largest eigenvalue of its link. The authors also give a tight spectral bound that guarantees a fractional matching of any given size s + 1 when n is at least 3s + 3.

Core claim

If ρ(N_H(v)) > (2/3 + γ)n for all v ∈ V(H), where 0 < γ < 1 and n is sufficiently large with n ≡ 0 mod 3, then the 3-uniform hypergraph H admits a perfect matching; the bound is asymptotically tight. A similar tight spectral bound guarantees a fractional matching of size s + 1 when n ≥ 3s + 3.

What carries the argument

The spectral radius ρ(N_H(v)) of the link graph N_H(v), the 2-uniform graph whose edges are the pairs that together with v form a triple in H.

If this is right

  • Such a hypergraph can be partitioned into n/3 vertex-disjoint edges.
  • The same local spectral test yields a tight guarantee for the existence of a large fractional matching of any prescribed size.
  • The 2/3 threshold cannot be replaced by any smaller constant without losing the conclusion for some sequences of hypergraphs.
  • The condition supplies a spectral strengthening of the known minimum codegree thresholds for perfect matchings in 3-graphs.

Where Pith is reading between the lines

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

  • The bound may be useful for algorithmic verification since computing spectral radii of the link graphs is a standard linear-algebra task.
  • The same local spectral test could plausibly extend to other matching problems such as Hamilton cycles in hypergraphs.
  • The requirement that the inequality hold for every vertex suggests that a single weak link can destroy the global matching property.

Load-bearing premise

The spectral-radius inequality must hold simultaneously for the link graph of every single vertex, and n must be sufficiently large.

What would settle it

A 3-uniform hypergraph on n vertices (n large, divisible by 3) in which at least one link graph has spectral radius at most (2/3 + γ)n yet no perfect matching exists.

read the original abstract

Let $\gamma$ be a constant such that $0 < \gamma < 1$, and let $n$ be a sufficiently large integer. Consider a $3$-uniform hypergraph $H$ on $n$ vertices. In 2013, K\"{u}hn, Osthus, and Treglown, along with Khan independently, proved that for large enough $n$ with $n\equiv 0\pmod{3}$, if $\delta_1(H)\geq\binom{2n/3}{2}$, then $H$ admits a perfect matching. For any vertex $v\in V(H)$, we define $N_H(v)$ as the $2$-graph with vertex set $V(H)\setminus\{v\}$ and edge set $E(N_H(v)) = \{e\subseteq V(H)\setminus\{v\}: e\cup \{v\}\in E(H)\}$. In this paper, we show that if $\rho(N_H(v)) > (2/3+\gamma)n$ for all $v\in V(H)$, where $\rho(N_H(v))$ denotes the spectral radius of $N_H(v)$, then $H$ has a perfect matching. This bound is asymptotically tight. Furthermore, for integer $s$ satisfying $n\geq 3s+3$, we establish that if \[ \rho(N_H(v))>\frac{1}{2}(s-1+\sqrt{(s-1)^2+4s(n-s-1)})\] holds for every $v\in V(H),$ then $H$ admits a fractional matching of size $s+1$. Notably, this second spectral bound is tight.

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

Summary. The paper proves that a 3-uniform hypergraph H on n vertices (n large, n ≡ 0 mod 3) admits a perfect matching whenever the spectral radius ρ(N_H(v)) of every link graph exceeds (2/3 + γ)n for fixed γ > 0. The bound is asymptotically tight via the standard extremal construction with parts of size 2n/3 − 1 and n/3 + 1. A second result gives an explicit spectral-radius threshold on the link graphs that guarantees a fractional matching of size s + 1; this threshold is also tight.

Significance. The results supply local spectral sufficient conditions that imply the known minimum 1-degree condition of Kühn–Osthus–Treglown/Khan (2013) for perfect matchings and an analogous algebraic condition for fractional matchings. Because the proofs reduce to the elementary inequality e(G) ≥ ρ(G)^2/2 together with the existing combinatorial theorem, the paper offers a clean spectral translation that may be useful when only spectral data are available.

minor comments (3)
  1. §1, after the definition of N_H(v): explicitly recall the inequality e(G) ≥ ρ(G)^2/2 (with equality conditions) and verify that ρ > (2/3 + γ)n forces e(N_H(v)) > binom(2n/3, 2) for all sufficiently large n; a short calculation would make the reduction to the 2013 theorem completely self-contained.
  2. The fractional-matching threshold is stated as the largest eigenvalue of the extremal link graph; adding a one-sentence description of that graph (or the quadratic equation it satisfies) would clarify why the given closed-form expression is tight.
  3. Notation: the paper uses both δ_1(H) and the link-graph edge count; a single sentence equating the minimum-degree hypothesis to min_v |E(N_H(v))| ≥ binom(2n/3, 2) would help readers who are not already familiar with the 2013 result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results, for recognizing the connection to the Kühn–Osthus–Treglown/Khan minimum-degree theorem, and for recommending acceptance.

Circularity Check

0 steps flagged

No significant circularity; derivation uses external theorem and standard inequalities

full rationale

The central result reduces the given spectral-radius hypothesis on each link graph N_H(v) to the minimum 1-degree condition δ_1(H) ≥ binom(2n/3,2) by invoking the elementary inequality relating ρ(G) to e(G) for the 2-graph G = N_H(v). This degree condition is then fed into the 2013 theorem of Kühn-Osthus-Treglown (and the independent result of Khan), whose authors are distinct from the present paper. The fractional-matching statement likewise follows from direct algebraic comparison with the extremal link graphs and is verified tight by an explicit construction; neither step is self-referential, fitted by construction, nor dependent on a load-bearing self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard linear-algebra facts about the adjacency matrix and spectral radius of graphs, plus the asymptotic regime for large n; no new entities or fitted constants beyond the arbitrary positive γ are introduced.

axioms (2)
  • standard math Perron-Frobenius theorem and basic properties of the spectral radius for nonnegative symmetric matrices
    Implicitly required to interpret ρ(N_H(v)) as a well-defined measure of the link graph.
  • domain assumption The 2013 theorem of Kühn-Osthus-Treglown and Khan that δ1(H) ≥ binom(2n/3,2) implies a perfect matching
    Provides the context and comparison point for the new spectral condition.

pith-pipeline@v0.9.0 · 5614 in / 1226 out tokens · 61888 ms · 2026-05-10T13:07:26.118229+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Aharoni, R

    R. Aharoni, R. Holzman, and Z. Jiang. Rainbow fractional matchings. Combinatorica, 39(6):1191–1202, 2019

    work page 2019

  2. [2]

    N. Alon, P. Frankl, H. Huang, V. R¨ odl, A. Ruci´ nski, and B. Sudakov. Large matchings in uniform hypergraphs and the conjectures of Erd˝ os and Samuels.J. Combin. Theory Ser. A, 119(6):1200–1215, 2012

    work page 2012

  3. [3]

    N. Alon, H. Huang, and B. Sudakov. Nonnegative k-sums, fractional covers, and probability of small deviations.J. Combin. Theory Ser. B, 102(3):784–796, 2012

    work page 2012

  4. [4]

    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

  5. [5]

    L. Feng, G. Yu, and X. Zhang. Spectral radius of graphs with given matching number.Linear Algebra Appl., 422(1):133–138, 2007

    work page 2007

  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]

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

    work page 2017

  8. [8]

    Frankl and A

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

    work page 2022

  9. [9]

    Frankl, T

    P. Frankl, T. Luczak, and K. Mieczkowska. On matchings in hyper- graphs.Electron. J. Combin., pages P42–P42, 2012

    work page 2012

  10. [10]

    Frankl and V

    P. Frankl and V. R¨ odl. Near perfect coverings in graphs and hyper- graphs.European J. Combin., 6(4):317–326, 1985

    work page 1985

  11. [11]

    H` an, Y

    H. H` an, Y. Person, and M. Schacht. On perfect matchings in uni- form hypergraphs with large minimum vertex degree.SIAM J. Discrete Math., 23(2):732–748, 2009

    work page 2009

  12. [12]

    Y. Hong, J. Shu, and K. Fang. A sharp upper bound of the spectral radius of graphs.J. Combin. Theory Ser. B, 81(2):177–183, 2001

    work page 2001

  13. [13]

    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. 15

    work page 2012

  14. [14]

    R. Karp. Reducibility among combinatorial problems. In50 Years of Integer Programming 1958-2008: from the Early Years to the State-of- the-Art, pages 219–241. Springer, 2009

    work page 1958

  15. [15]

    I. Khan. Perfect matchings in 3-uniform hypergraphs with large vertex degree.SIAM J. Discrete Math., 27(2):1021–1039, 2013

    work page 2013

  16. [16]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Treglown. Matchings in 3-uniform hyper- graphs.J. Combin. Theory Ser. B, 103(2):291–305, 2013

    work page 2013

  17. [17]

    NIKIFOROV

    V. NIKIFOROV. Some inequalities for the largest eigenvalue of a graph. Combin. Probab. Comput., 11(2):179–189, 2002

    work page 2002

  18. [18]

    Nikiforov

    V. Nikiforov. Eigenvalue problems of Nordhaus–Gaddum type.Discrete Math., 307(6):774–780, 2007

    work page 2007

  19. [19]

    R. Stanley. A bound on the spectral radius of graphs with e edges. Linear Algebra Appl., 87:267–269, 1987

    work page 1987

  20. [20]

    T. Terpai. Proof of a conjecture of V. Nikiforov.Combinatorica, 31(6):739–754, 2011. 16

    work page 2011