Perturbation of the largest matching root of hypergraphs
Jiang-Chao Wan 1 , Yi Wang 2 · 2026
Read Perturbation of the largest matching root of hypergraphs by Jiang-Chao Wan 1 , Yi Wang 2 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14882.txt.
Introduction
Jiang-Chao Wan and Yi Wang study how the largest matching root of a hypergraph shifts when the graph changes. A hypergraph links groups of vertices at once. Its matching root is the top real root of its matching polynomial. The pair identifies the hypergraphs with the biggest such root among cactus-like families with fixed cycle and edge counts. A key step shows that a classic shifting move never lowers the root. This extends an older result for ordinary graphs.
Catalog record
| CREATOR | Jiang-Chao Wan 1 , Yi Wang 2 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57086 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14882
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Perturbation of the largest matching root of hypergraphs Thanks: Corresponding author. Yi Wang Thanks: Funding. Supported by the National Natural Science Foundation of China (No. 12331012, 12571360) Jiang-Chao Wan 1 , Yi Wang 2 Abstract . The largest matching root of a k 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 k -graphs. We determine all k k -graphs whose largest matching root attains the maximum among all k k -cacti and linear k k -cacti with a given number of cycles and edges, where a k k -cactus is a k 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 k -graphs, introduced by Erdős, Ko and Rado, does not decrease the largest matching root. This result extends a classical result by Csikvári (Electron. J. Combin. 18 (2011) # \# P182) stating that the Kelmans transformation does not decrease the largest matching root of graphs. 1. Introduction The problem of determining the graphs for which the largest matching root achieves the maximum in a given family of graphs can be traced back to the celebrated paper by Lovász and Pelikán [ 19 ] in 1973. They [ 19 ] determined the first two largest spectral radii of trees with a given number of vertices. Since then, many researchers studied the problem of determining the graphs for which the largest matching root achieves the maximum in a given family of graphs, see, e.g. [ 18 , 26 , 27 ] . In this paper, we extend the problem to uniform hypergraphs. Before stating the main results of this paper, we first introduce the necessary background on the matching polynomials of graphs and uniform hypergraphs. 1.1. Background A k -uniform hypergraph (or k -graph for short) \mathcal{H}=(V(\mathcal{H}),E(\mathcal{H})) consists of a vertex set V(\mathcal{H}) and an edge set E(\mathcal{H}) , where each edge e\in E(\mathcal{H}) is a k -element subset of V(\mathcal{H}) . Clearly, 2 -graph are the ordinary graph. A matching in \mathcal{H} is a set of vertex-disjoint edges, and an r -matching is a matching having r edges. To study the spectral radius of the adjacency tensor of k -trees, Su et al. [ 22 ] introduced the matching polynomial of a k -graph \mathcal{H} as follows: (1) \mu(\mathcal{H},x)=\sum_{r\geq 0}(-1)^{r}p(\mathcal{H},r)x^{|V(\mathcal{H})|-kr}, where p(\mathcal{H},r) denotes the number of r -matchings of \mathcal{H} . The case of k=2 in ( 1 ) is the classical matching polynomial of a graph introduced by Heilmann and Lieb [ 11 , 12 ] . We refer the reader to the textbook [ 10 ] for more history on the matching polynomial theory. Denote by \lambda(\mathcal{H}) the maximum modulus of all the zeros of the matching polynomial of a k -graph \mathcal{H} . The Heilmann–Lieb theorem says that the zeros of the matching polynomial of a graph are real and symmetrically distributed about the origin. Thus, \lambda(G) is equal to the largest root of \mu(G,x) for a graph G . However, the case of k\geq 3 seems to be a little more complex since the matching polynomial of a k -graph with k\geq 3 must contain a non-real zero [ 23 ] . Zhang et al. [ 28 ] proved that for a k -tree \mathcal{T} the largest root of \mu(\mathcal{T},x) is equal to the spectral radius of the adjacency tensor of \mathcal{T} . Based on this fact and some properties of the matching polynomial, Su et al. [ 22 ] determined the first \lfloor d/2\rfloor+1 largest spectral radii of the adjacency tensor of k -trees with size m and diameter d . Recently, the authors [ 23 ] established a hypergraph Heilmann–Lieb theorem. In particular, they showed that for a k -graph \mathcal{H} , \lambda(\mathcal{H}) is a simple root of \mu(\mathcal{H},x) , and hence that \lambda(\mathcal{H}) is the largest root of \mu(\mathcal{H},x) (see [ 23 , Theorem 1.2] for details). We simply call \lambda(\mathcal{H}) the largest matching root of \mathcal{H} . A natural question is to determine the k -graphs for which the largest matching root achieves the maximum in a given family of k -graphs. 1.2. Main results Let \mathcal{P}=(v_{0},e_{1},v_{1},\dots,e_{\ell},v_{\ell}) be an alternating sequence of vertices and edges in \mathcal{H} such that e_{1},\ldots,e_{\ell} are pairwise distinct and v_{i-1},v_{i}\in e_{i} for all i=1,\ldots,\ell . The sequence \mathcal{P} is called a path in \mathcal{H} if the vertices v_{0},v_{1},\ldots,v_{\ell} are pairwise distinct, and it is called a cycle in \mathcal{H} if v_{1},\ldots,v_{\ell} are pairwise distinct, \ell\geq 2 , and v_{0}=v_{\ell} . Denote by V(\mathcal{P}) the set \cup_{i=1}^{\ell}e_{i} . A connected k -graph \mathcal{H} is called a k -cactus if every two distinct cycles of \mathcal{H} have at most one vertex in common, that is, |V(\mathcal{C}_{1})\cap V(\mathcal{C}_{2})|\leq 1 for every two distinct cycles \mathcal{C}_{1} and \mathcal{C}_{2} of \mathcal{H} . For integers k\geq 3 (resp. k\geq 2 ), m\geq 1 and t\geq 0 , we denote by \mathfrak{Ca}_{k}(m,t) (resp. \mathfrak{LCa}_{k}(m,t) ) the set of all (resp. linear) k -cacti with m edges and t cycles. Here, a k -graph \mathcal{H} is said to be linear if any two distinct edges of \mathcal{H} intersect at most one vertex. For a given family \mathfrak{F} of k -graphs, a k -graph \mathcal{H}\in\mathfrak{F} is called maximizing in \mathfrak{F} if \lambda(\mathcal{H}) attains the maximum among all k -graphs in \mathfrak{F} . The aim of this paper is to determine all maximizing k -graphs in \mathfrak{Ca}_{k}(m,t) and \mathfrak{LCa}_{k}(m,t) , respectively. m-2t edges \mathcal{H}^{(k)}_{m,t} t cycles of length 2 m-3t edges \mathcal{\mathcal{L}}^{(k)}_{m,t} t cycles of length 3 Figure 1. The structures of \mathcal{H}^{(k)}_{m,t} and \mathcal{\mathcal{L}}^{(k)}_{m,t} . We are now ready to state the main result of this paper. Theorem 1.1 . Let k\geq 3 ( resp. k\geq 2 ) , m\geq 1 , and t\geq 0 be integers. Let \mathcal{H}^{(k)}_{m,t} ( resp. \mathcal{L}^{(k)}_{m,t} ) be the k -graph illustrated in Figure 1 . Then the following statements hold. (a) For (m,t)\neq(3,1) , \mathcal{H}^{(k)}_{m,t} is the unique maximizing k -graph in \mathfrak{Ca}_{k}(m,t) . (b) For (m,t)=(3,1) , \mathcal{H}^{(k)}_{3,1} and \mathcal{L}^{(k)}_{3,1} are all maximizing k -graphs in \mathfrak{Ca}_{k}(m,t) . (c) The k -graph \mathcal{L}^{(k)}_{m,t} is the unique maximizing k -graph in \mathfrak{LCa}_{k}(m,t) . To achieve Theorem 1.1 , we prove that the celebrated shifting operation of k -graphs, introduced by Erdős, Ko and Rado [ 6 ] , does not decrease the largest matching root. 1.3. Main tool: the shifting operation The Kelmans transformation is an important tool in algebraic graph theory, which was introduced by Kelmans [ 14 ] in 1981 to study the extremal problems related to the synthesis of reliable networks. Denote by E_{\mathcal{H}}(v) the set of all edges of the k -graph \mathcal{H} containing v . Given a graph G with two vertices u and v , the Kelmans transformation of G from v to u is the operation that removes all edges between v and N_{G}(v)\setminus(N_{G}(u)\cup\{u\}) and adds all edges between u and N_{G}(v)\setminus(N_{G}(u)\cup\{u\}) . See Figure 2 for an example. u v u v G H Figure 2. An example for Kelmans transformation