pith. sign in

arxiv: 2605.14882 · v1 · pith:2KW3YUD7new · submitted 2026-05-14 · 🧮 math.CO

Perturbation of the largest matching root of hypergraphs

Jiang-Chao Wan , Yi Wang This is my paper

Pith reviewed 2026-06-30 20:25 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C6505C31
keywords k-graphsmatching polynomiallargest matching rootshifting operationk-cactiErdős–Ko–Radohypergraph matching
0
0 comments X

The pith

Shifting does not decrease the largest matching root of k-graphs and identifies the maximizers among k-cacti.

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

The paper proves that the Erdős–Ko–Rado shifting operation on k-uniform hypergraphs never lowers the largest real root of the matching polynomial. The authors apply this monotonicity to characterize exactly which k-cacti and linear k-cacti attain the maximum value of the root when the number of edges and cycles is fixed. A k-cactus is a hypergraph in which any two cycles intersect in at most one vertex. The result extends Csikvári’s theorem that the Kelmans transformation is monotone for the matching root of ordinary graphs. The largest matching root bounds the size of a maximum matching and controls the growth of the number of matchings of all sizes.

Core claim

The largest matching root of a k-graph is the largest real root of its matching polynomial and equals the maximum modulus of all its zeros. The Erdős–Ko–Rado shifting operation does not decrease this root. Consequently, among all k-cacti with a prescribed number of edges and cycles, the maximum root is attained precisely by the k-graphs that are stable under shifting; the authors classify these stable members as certain linear k-cacti.

What carries the argument

The Erdős–Ko–Rado shifting operation, a local edge-replacement that increases the intersection size with a fixed vertex set while preserving uniformity and the counts of edges and cycles.

If this is right

  • The largest matching root is non-decreasing under the shifting operation for every k-graph.
  • The k-cacti that maximize the root are exactly those that admit no further shift.
  • The maximizers are certain linear k-cacti whose structure is completely determined by the given numbers of edges and cycles.
  • The same monotonicity supplies a proof technique that extends the graph case of Csikvári to hypergraphs.

Where Pith is reading between the lines

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

  • If monotonicity under shifting extends to other local operations, the same method could resolve extremal problems for matching roots in arbitrary hypergraphs rather than only cacti.
  • Analogous arguments might bound roots of other hypergraph invariants such as the chromatic or independence polynomials.
  • Direct computation of the matching polynomial on small linear k-cacti would give an independent check of which members achieve the claimed maximum.

Load-bearing premise

Repeated shifts can reach every extremal member while staying inside the class of k-cacti that have exactly the given numbers of edges and cycles.

What would settle it

An explicit k-cactus with fixed edges and cycles on which a single shift strictly decreases the largest matching root would falsify the monotonicity claim.

Figures

Figures reproduced from arXiv: 2605.14882 by Jiang-Chao Wan, Yi Wang.

Figure 1
Figure 1. Figure 1: The structures of H (k) m,t and L (k) m,t. We are now ready to state the main result of this paper. Theorem 1.1. Let k ≥ 3 (resp. k ≥ 2), m ≥ 1, and t ≥ 0 be integers. Let H (k) m,t (resp. L (k) m,t) be the k-graph illustrated in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: for an example. u v u v G H [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
read the original abstract

The largest matching root of a $k$-graph is the largest real root of its matching polynomial, which is equal to the maximum modulus of all the zeros of the matching polynomial. In this paper, we investigate the perturbation of the largest matching root of $k$-graphs. We determine all $k$-graphs whose largest matching root attains the maximum among all $k$-cacti and linear $k$-cacti with a given number of cycles and edges, where a $k$-cactus is a $k$-graph in which every two distinct cycles have at most one vertex in common. To achieve this, we prove that the celebrated shifting operation of $k$-graphs, introduced by Erd\H{o}s, Ko and Rado, does not decrease the largest matching root. This result extends a classical result by Csikv\'ari (Electron. J. Combin. {\bf 18} (2011) $\#$P182) stating that the Kelmans transformation does not decrease the largest matching root of graphs.

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

2 major / 1 minor

Summary. The manuscript proves that the Erdős–Ko–Rado shifting operation on k-uniform hypergraphs does not decrease the largest real root of the matching polynomial (equivalently, the maximum modulus of its zeros). It extends Csikvári's 2011 result on the Kelmans transformation for graphs and applies the inequality to identify all k-cacti and linear k-cacti with a fixed number of cycles and edges that attain the maximum possible largest matching root.

Significance. If the shifting inequality is established and the operation can be shown to remain inside the k-cactus class, the result supplies a perturbation tool for matching polynomials of hypergraphs and yields explicit extremal structures among cacti, extending classical EKR-type methods to a new setting. The absence of free parameters or fitted quantities in the stated claim is a strength.

major comments (2)
  1. [application to k-cacti (after the shifting theorem)] The extremal claim for k-cacti requires that any member of the class can be transformed into the asserted maximizer by a sequence of shifts that remain inside the class (preserving both the property that any two cycles intersect in at most one vertex and the exact numbers of cycles and edges). No lemma or argument verifying this preservation appears in the abstract or the claim description; without it the reachability step is unsupported and the identification of the extremal members cannot be completed.
  2. [proof of the shifting inequality] The central shifting inequality is asserted to hold for general k-graphs, yet the manuscript provides neither the full derivation nor the key lemmas that would allow verification that the operation is well-defined on the matching polynomial and that the root comparison is strict or non-strict as claimed.
minor comments (1)
  1. [preliminaries] Notation for the matching polynomial and its roots should be introduced once with a clear reference to the definition used in Csikvári's paper for easy comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the paper accordingly to strengthen the arguments.

read point-by-point responses

  1. Referee: [application to k-cacti (after the shifting theorem)] The extremal claim for k-cacti requires that any member of the class can be transformed into the asserted maximizer by a sequence of shifts that remain inside the class (preserving both the property that any two cycles intersect in at most one vertex and the exact numbers of cycles and edges). No lemma or argument verifying this preservation appears in the abstract or the claim description; without it the reachability step is unsupported and the identification of the extremal members cannot be completed.

    Authors: We agree that an explicit verification is required to ensure shifts remain within the k-cactus class while preserving the number of cycles and edges. The original manuscript implicitly relied on the fact that shifting preserves uniformity and edge count but did not detail the cycle-intersection property. We will add a new lemma proving that the Erdős–Ko–Rado shift on a k-cactus produces another k-cactus with identical cycle and edge counts, thereby justifying the reachability argument for the extremal structures. revision: yes

  2. Referee: [proof of the shifting inequality] The central shifting inequality is asserted to hold for general k-graphs, yet the manuscript provides neither the full derivation nor the key lemmas that would allow verification that the operation is well-defined on the matching polynomial and that the root comparison is strict or non-strict as claimed.

    Authors: Section 3 of the manuscript contains the proof of the shifting inequality, including the definition of the matching polynomial and the comparison of its largest real root under the operation. To address the concern about completeness, we will expand this section with additional intermediate steps and lemmas that explicitly confirm the operation is well-defined on the polynomial and establish the non-strict inequality, extending the approach of Csikvári while making the derivation fully verifiable. revision: yes

Circularity Check

0 steps flagged

No circularity: direct proof of monotonicity under explicit operation

full rationale

The central claim is a combinatorial proof that the EKR shifting operation on k-graphs is non-decreasing for the largest matching root (extending Csikvári's Kelmans result on graphs). No parameters are fitted to data and then relabeled as predictions; no self-citation chain is invoked to justify a uniqueness theorem or ansatz; the cactus reachability step is an explicit assumption about the operation's preservation properties rather than a definitional reduction. The derivation is self-contained against the external benchmark of the matching polynomial definition and the cited prior result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of the matching polynomial for hypergraphs and the combinatorial definition of k-cacti; no new entities or fitted constants are introduced.

axioms (2)
  • domain assumption The matching polynomial of a k-graph is well-defined and its largest real root equals the maximum modulus of all its zeros.
    Invoked in the first sentence of the abstract to equate the two characterizations of the largest matching root.
  • domain assumption The shifting operation of Erdős–Ko–Rado is well-defined on k-graphs.
    Central to the proof announced in the abstract.

pith-pipeline@v0.9.1-grok · 5703 in / 1405 out tokens · 29915 ms · 2026-06-30T20:25:59.705251+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

30 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Brown, C

    J. Brown, C. Colbourn, J. Devitt, Network transformations and bounding network reliability,Networks 23(1993), 1–17

    1993

  2. [2]

    Cooper and A

    J. Cooper and A. Dutle, Spectra of uniform hypergraphs,Linear Algebra Appl.436(2012), 3268–3292

    2012

  3. [3]

    Csikv´ ari, On a conjecture of V

    P. Csikv´ ari, On a conjecture of V. Nikiforov,Discrete Math.309(13) (2009), 4522–4526

    2009

  4. [4]

    Csikv´ ari, Applications of the Kelmans transformation: extremality of the threshold graphs,Electron

    P. Csikv´ ari, Applications of the Kelmans transformation: extremality of the threshold graphs,Electron. J. Combin.18(2011), #P182

    2011

  5. [5]

    X. Chen, X. Li, H. Lian, Solution to a conjecture on the maximum skew-spectral radius of odd-cycle graphs,Electron. J. Combin.22(1) (2015), #P1.71

    2015

  6. [6]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, and R. Rado, Intersection theorems for systems of finite sets,The Quarterly Journal of Mathematics12(2)(1961), 313–320

    1961

  7. [7]

    Frankl, The shifting techniques in extremal set theory, in: Surveys in Combinatorics,Lond

    P. Frankl, The shifting techniques in extremal set theory, in: Surveys in Combinatorics,Lond. Math. Soc. Lect. Note Ser.123(1987), 81–110

    1987

  8. [8]

    Friedland, S

    S. Friedland, S. Gaubert, L. Han, Perron–Frobenius theorem for nonnegative multilinear forms and extensions,Linear Algebra Appl.438(2013) 738–749

    2013

  9. [9]

    Godsil, Matchings and walks in graphs,J

    C.D. Godsil, Matchings and walks in graphs,J. Graph Theory5(1981), 285–297

    1981

  10. [10]

    Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993

    C.D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993

    1993

  11. [11]

    Heilmann and E.H

    O.J. Heilmann and E.H. Lieb, Monomers and dimers,Phys. Rev. Lett.24(1970), 1412–1414

    1970

  12. [12]

    Heilmann and E.H

    O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems,Comm. Math. Phys.25(1972), 190–232

    1972

  13. [13]

    Kahn and J

    J. Kahn and J. H. Kim, Random matchings in regular graphs,Combinatorica18(1998), 201–226

    1998

  14. [14]

    Kelmans, On graphs with randomly deleted edges,Acta

    A.K. Kelmans, On graphs with randomly deleted edges,Acta. Math. Acad. Sci. Hung.37(1981), 77–88

    1981

  15. [15]

    Lee, Random matchings in linear hypergraphs, available at arXiv:2406.06421v2

    H. Lee, Random matchings in linear hypergraphs, available at arXiv:2406.06421v2

    work page arXiv

  16. [16]

    H. Li, J. Shao, L. Qi, The extremal spectral radii ofk-uniform supertrees,J. Comb. Optim.32(2016), 741–764. 16 JIANG-CHAO W AN 1, YI W ANG 2

    2016

  17. [17]

    L. Lim, Singular values and eigenvalues of tensors: a variational approach, in: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, vol. 1, CAMSAP’05, pages 129–132, 2005

    2005

  18. [18]

    W. Liu, Q. Guo, Y. Zhang, L. Feng, I. Gutman, Further results on the largest matching root of unicyclic graphs,Discrete Appl. Math.221(2017), 82–88

    2017

  19. [19]

    Lov´ asz and J

    L. Lov´ asz and J. Pelik´ an, On the eigenvalues of trees,Period. Math. Hungar.3(1973), 175-182

    1973

  20. [20]

    Qi, Eigenvalues of a real supersymmetric tensor,J

    L. Qi, Eigenvalues of a real supersymmetric tensor,J. Symbolic Comput.40(6) (2005), 1302–1324

    2005

  21. [21]

    Satyanarayana, L

    A. Satyanarayana, L. Schoppman, C.L. Suffel, A reliability-improving graph transformation with appli- cations to network reliability,Networks22(1992), 209–216

    1992

  22. [22]

    L. Su, L. Kang, H. Li, and E. Shan, The matching polynomials and spectral radii of uniform supertrees, Electron. J. Combin.25(4) (2018), #P4.13

    2018

  23. [23]

    J. Wan, Y. Wang, Y. Fan, A hypergraph Heilmann–Lieb theorem,Proc. Amer. Math. Soc.,154(4) 2026, 1479–1493

    2026

  24. [24]

    Y. Yang, Q. Yang, Further results for Perron–Frobenius theorem for nonnegative tensors,SIAM J. Matrix Anal. Appl.31(5) (2010), 2517–2530

    2010

  25. [25]

    Y. Yang, Q. Yang, On some properties of nonnegative weakly irreducible tensors, arXiv: 1111.0713v2

    work page internal anchor Pith review Pith/arXiv arXiv

  26. [26]

    Zhang, G

    H. Zhang, G. Chen, and G. Yu, On the largest matching roots of graphs with a given number of pendent vertices,Discrete Appl. Math.255(2019), 339–344

    2019

  27. [27]

    Zhang, R

    H. Zhang, R. Lin, G. Yu, The largest matching root of unicyclic graphs,Inform. Process. Lett.113 (2013), 804–806

    2013

  28. [28]

    Zhang, L

    W. Zhang, L. Kang, E. Shan, and Y. Bai, The spectra of uniform hypertrees,Linear Algebra Appl.533 (2017), 84–94

    2017

  29. [29]

    School of Mathematics and Statistics, Hefei University, Hefei 230601, Anhui, China,

  30. [30]

    School of Mathematical Sciences, Anhui University, Hefei 230601, Anhui, China Email address:wanjc@stu.ahu.edu.cn, wangy@ahu.edu.cn