The characteristic polynomial of sunflowers
Changjiang Bu 1 , Lixiang Chen 2 , Ge Lin · 2025
Read The characteristic polynomial of sunflowers by Changjiang Bu 1 , Lixiang Chen 2 , Ge Lin (2025) 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-2506-17628.txt.
Introduction
Changjiang Bu, Lixiang Chen, and Ge Lin study the characteristic polynomial of sunflowers, a special family of uniform hypergraphs. A sunflower is a hypergraph whose edges all intersect in exactly the same shared set of vertices. The authors determine the eigenvalues of these structures and work out their spectral moments. From those results they derive an explicit formula for the characteristic polynomial. The result gives spectral graph theory a closed-form handle on a structured hypergraph family.
Catalog record
| CREATOR | Changjiang Bu 1 , Lixiang Chen 2 , Ge Lin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-17628
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The characteristic polynomial of sunflowers Changjiang Bu 1 , Lixiang Chen 2 , Ge Lin Abstract A uniform hypergraph is called a sunflower if all of its hyperedges intersect in the same set of vertices. In this paper, we determine the eigenvalues and spectral moments of a sunflower, thereby obtaining an explicit formula for its characteristic polynomial. Keywords: Characteristic polynomial, Spectral moment, Hypergraph, Sunflower AMS classification(2020): 05C50, 05C65 1 Introduction In spectral hypergraph theory, determining the characteristic polynomial of a hypergraph is a fundamental problem, which is equivalent to determining all eigenvalues and their multiplicities. The characteristic polynomial of a uniform hypergraph is the resultant of a system of homogeneous multi-linear equations qi2005eigenvalues . The resultant both determines whether such a system has non-trivial solutions and provides a way to express those solutions explicitly cox2005using , which is studied and applied in various fields like algebraic geometry and number theory. However, computing the resultant (and thus, the characteristic polynomial of a hypergraph) is NP-hard in general hillar2013most . To the best of our knowledge, there are currently three tools for computing the characteristic polynomial of a hypergraph. The first one is a resultant formula given in the elimination theory macaulay1902some , which expresses the resultant as a quotient of two determinants. Li, Su, and Fallat express the characteristic polynomials of a uniform hypertree in terms of the matching polynomials of its subhypertrees in this way li2024hypertree . The second one is the Poisson formula, which may provide an inductive computational method jouanolou1991formalisme . It is applied to derive the characteristic polynomials of some concrete hypergraphs, including hyperstars bao2020combinatorial , hyperpaths chen2021reduction , and 3 -uniform complete hypergraphs zheng2021complete . The third tool is the so-called generalized trace or spectral moment, which is defined by Morozov and Shakirov morozov2011analogue . Clark and Cooper establish a hypergraph analogue of the Harary–Sachs Theorem clark2021harary . Shao, Qi, and Hu shao2015some obtain a useful expression for the trace of general tensors. Using the formula of Shao et al., Chen, van Dam, and Bu derive an explicit expression for the characteristic polynomial of power hypergraphs chen2024spectra . A hypergraph is called linear if every pair of hyperedges intersects in at most one vertex. So far, most hypergraphs whose characteristic polynomials are explicitly known are linear. A uniform hypergraph is called a sunflower if all of its hyperedges intersect in the same set of vertices, called its seeds. Let \mathcal{S}(k,s,p) denote a k -uniform sunflower with s seeds and p petals. When s\geq 2 , the sunflowers \mathcal{S}(k,s,p) form a family of non-linear hypergraphs. The characteristic polynomial of a sunflower is first studied by Cooper and Dutle, who provide the characteristic polynomial of a 3 -uniform hyperstar \mathcal{S}(3,1,p) cooper2015computing . Bao, Fan, Wang, and Zhu later generalize the result to \mathcal{S}(k,1,p) for general k bao2020combinatorial . In this paper, we further extend the result to the more general case \mathcal{S}(k,s,p) (see Theorem 3.7 ), by determining its eigenvalues (see Theorem 3.1 ) and spectral moments (see Theorem 3.6 ). 2 Preliminaries In this section, we introduce some basic notation and auxiliary lemmas on the eigenvalues and spectral moments of hypergraphs. A hypergraph H=(V,E) is called k - uniform if each edge of H contains exactly k vertices. For a k -uniform hypergraph H with V=[n]:=\{1,\ldots,n\} , its adjacency tensor A_{H}=(a_{i_{1}i_{2}\cdots i_{k}}) is a k -order n -dimensional tensor cooper2012spectra , where a_{i_{1}i_{2}\cdots i_{k}}=\begin{cases}\frac{1}{(k-1)!}&\text{if $\{i_{1},i_{2},\ldots,i_{k}\}\in E$},\\ 0&\text{otherwise}.\end{cases} For a vector \mathbf{x}=(x_{1},\ldots,x_{n})^{\top}\in\mathbb{C}^{n} and S\subseteq V , let \mathbf{x}^{S}=\prod_{s\in S}x_{s} . In particular, we set \mathbf{x}^{\emptyset}=1 . Let E_{H}(v) denote the set of hyperedges of H containing the vertex v . For some \lambda\in\mathbb{C} , if there exists a non-zero vector \mathbf{x} such that for each i\in[n] , \displaystyle\lambda x_{i}^{k-1}=\sum_{i_{2},\ldots,i_{k}=1}^{n}a_{ii_{2}\cdots i_{k}}x_{i_{2}}\cdots x_{i_{k}}, or equivalently, for each v\in V , \displaystyle\lambda x_{v}^{k-1}=\sum_{e\in E_{H}(v)}\mathbf{x}^{e\setminus\{v\}}, (1) then \lambda is called an eigenvalue of H and \mathbf{x} is an eigenvector of H corresponding to \lambda ( lim2005singular ; qi2005eigenvalues ). The characteristic polynomial \phi_{H}(\lambda) of H is defined as the resultant of the polynomial system \{\lambda x_{v}^{k-1}-\sum_{e\in E_{H}(v)}\mathbf{x}^{e\setminus\{v\}}:v\in V\} qi2005eigenvalues . The sum of d -th powers of all eigenvalues of a uniform hypergraph H is called the d -th order spectral moment of H , denoted by \mathrm{S}_{d}(H) . It is known that the d -th order spectral moment of a graph is equal to the d -th order trace of the adjacency matrix cvetkovic1980spectra . Similar to the case of graphs, the d -th order spectral moment \mathrm{S}_{d}(H) is equal to the d -th order trace of the adjacency tensor A_{H} hu2013determinants . In order to describe the formula for the spectral moments of a hypergraph (see Lemma 2.1 ), we introduce some related notation. For a k -uniform hypergraph H with V=[n] and a k -tuple iv_{1}v_{2}\cdots v_{k-1}\in[n]^{k} , we interpret it as a rooted hyperedge of H with root i if \{i,v_{1},v_{2},\ldots,v_{k-1}\}\in E . When no confusion arises, we use iv_{1}v_{2}\cdots v_{k-1} to represent the hyperedge \{i,v_{1},v_{2},\ldots,v_{k-1}\} rooted at i . Let \mathcal{F}_{d}=\{(i_{1}\alpha_{1},\ldots,i_{d}\alpha_{d}):1\leq i_{1}\leq\cdots\leq i_{d}\leq n,\alpha_{1},\ldots,\alpha_{d}\in[n]^{k-1},i_{j}\alpha_{j}\in E\} . Let f=(i_{1}\alpha_{1},\ldots,i_{d}\alpha_{d})\in\mathcal{F}_{d} , where i_{j}\alpha_{j}\in[n]^{k} and j=1,\ldots,d . It implies that f consists of d rooted hyperedges. Construct a k -uniform hypergraph H_{f} such that V(H_{f})=\bigcup_{j=1}^{d}i_{j}\alpha_{j} and E(H_{f})=\bigcup_{j=1}^{d}\{i_{j}\alpha_{j}\} . Obviously, H_{f} is a subhypergraph of H . For i_{j}\alpha_{j}=i_{j}v_{1}\cdots v_{k-1} , let \theta(i_{j}\alpha_{j})=\{(i_{j},v_{1}),\ldots,(i_{j},v_{k-1})\} be the set of arcs from i_{j} to v_{1},\ldots,v_{k-1} , where (v_{1},v_{2}) denotes an arc from vertex v_{1} to vertex v_{2} . Construct a multi-digraph D_{f} such that V(D_{f})=\bigcup_{j=1}^{d}i_{j}\alpha_{j} and E(D_{f})=\bigcup_{j=1}^{d}\theta(i_{j}\alpha_{j}) . Consider next a set of representatives of isomorphic such connected subhypergraphs \displaystyle\mathcal{H}_{d}=\{\widehat{H}:\mbox{$H_{f}\cong\widehat{H}$ and $D_{f}$ is Eulerian for some $f\in\mathcal{F}_{d}$}\}. For \widehat{H}\in\mathcal{H}_{d} , let \mathcal{F}_{d}(\widehat{H})=\{f\in\mathcal{F}_{d}:H_{f}\cong\widehat{H}\} . Denote the number of subhypergraphs of H which are isomorphic to \widehat{H} by N_{H}(\widehat{H}) . Let the set of representatives of isomorphic Eulerian multi-digraphs \mathfrak{D}_{d}(\widehat{H})=\{D:\mbox{$D_{f}\cong D$ is Eulerian for some $f\in\mathcal{F}_{d}(\widehat{H})$}\}. Lemma 2.1 . chen2024spectra The d -th order spectral moment of a k -uniform hypergraph H is \displaystyle\mathrm{S}_{d}(H)=(k-1)^{n-1}\sum_{\widehat{H}\in\mathcal{H}_{d}}c_{d}(\widehat{H})N_{H}(\widehat{H}). The d -th order spectral moment coefficient of the subhypergraph \widehat{H} is \displaystyle c_{d}(\widehat{H})=d(k-1)((k-1)!)^{-d}\sum_{D\in\mathfrak{D}_{d}(\widehat{H})}\frac{|\{f:\mbox{$f\in\mathcal{F}_{d}(\widehat{H})$ and $D_{f}\cong D$}\}|t(D)}{\prod_{v\in V(D)}\mathrm{deg}^{+}(v)}, where \mathrm{deg}^{+}(v) is the out-degree of v\in V(D) and t(D) is the number of spanning trees of D . 3 Spectra of a sunflower 3.1 The eigenvalues of a sunflower For a sunflower \mathcal{S}=\mathcal{S}(k,s,p) , denote by S the set of seed vertices, and let P_{i} be the set of vertices on the i -th petal of \mathcal{S} for each i\in[p] . Let (\lambda,\mathbf{x}) be an eigenpair of \mathcal{S} . From ( 1 ), for each v\in S , we have that \displaystyle\lambda x_{v}^{k-1}=\sum_{i=1}^{p}\mathbf{x}^{S\setminus\{v\}}\mathbf{x}^{P_{i}}, (2) and for each i\in[p] and each u\in P_{i} , we have that \displaystyle\lambda x_{u}^{k-1}=\mathbf{x}^{S}\mathbf{x}^{P_{i}\setminus\{u\}}. (3) For k=2 , it is known that the star graph \mathcal{S}(2,1,p) have the spectrum \{[\sqrt{p}]^{1},[-\sqrt{p}]^{1},[0]^{p-1}\} (exponents indicate multiplicity) cvetkovic1980spectra . For k\geq 3 , we first determine all the eigenvalues of \mathcal{S}(k,s,p) as follows. Theorem 3.1 . For k\geq 3 , let \mathcal{S}=\mathcal{S}(k,s,p) be a k -uniform sunflower with s seeds and p petals. Denote \Xi^{p}=\{(\xi_{i})\in\mathbb{C}^{p}:\mbox{$\xi_{i}^{s+1}-\xi_{i}=0$ for all $i\in[p]$}\} and \Xi^{p}_{0}=\{\xi\in\Xi^{p}:\mbox{$|\mathrm{supp}(\xi)|=0$ or $p$}\} . Let \mathbf{e}_{p} denote the p -dimensional all-ones column vector. Then the complex number \lambda is an eigenvalue of \mathcal{S} if and only if (a) \prod_{\xi\in\Xi^{p}}(\lambda^{k}-(\mathbf{e}_{p}^{\top}\xi)^{s})=0 , when s<k-1 ; (b)