Spectral characterizations of local structures of graphs and hypergraphs Journal:
Jiang Zhou, Changjiang Bu · 2025
Read Spectral characterizations of local structures of graphs and hypergraphs Journal: by Jiang Zhou, Changjiang Bu (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-2512-00896.txt.
Introduction
Jiang Zhou and Changjiang Bu study the spectra of graphs and hypergraphs in a 2025 math paper. A graph's spectrum is a set of numbers from its connection matrix that summarize its structure. The largest of them, the spectral radius, is especially telling.
The authors link the spectral radius to local structures, the small patterns sitting inside a graph. They show that when a certain ratio of spectral values is large, particular local subgraphs or subhypergraphs must appear. They also bound the local vector chromatic number using tensor eigenvalues. Such results let one number reveal what small shapes a network must contain.
Catalog record
| CREATOR | Jiang Zhou, Changjiang Bu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectral characterizations of local structures of graphs and hypergraphs Journal: Jiang Zhou, Changjiang Bu Abstract In this paper, we give the relationship between spectral radius and local structures of graphs and hypergraphs. Our work shows that certain local subgraphs (subhypergraphs) must occur when the spectral radius ratio is large. We also give spectral bounds on the local vector chromatic number in terms of tensor eigenvalues of graphs. 1 Introduction A hypergraph H is called r - uniform if each edge of H contains exactly r distinct vertices. Let V(H) and E(H) denote the vertex set and the edge set of H , respectively. The 2-section graph of a hypergraph H , denoted by H^{(2)} , is the graph on the vertex set V(H) , and \{u,v\}\in E(H^{(2)}) if and only if there exists e\in E(H) such that \{u,v\}\subseteq e . A hypergraph H_{0} is called a subhypergraph of H if V(H_{0})\subseteq V(H) and E(H_{0})\subseteq E(H) . The adjacency tensor Cooper of an r -uniform hypergraph H , denoted by \mathcal{A}_{H}=(a_{i_{1}i_{2}\cdots i_{r}}) , is an r -order |V(H)| -dimension tensor with entries \displaystyle a_{i_{1}i_{2}\cdots i_{r}}=\begin{cases}\frac{1}{(k-1)!}~~~~~~~\mbox{if}~\{i_{1},i_{2},\ldots,i_{r}\}\in E(H),\\ 0~~~~~~~~~~~~~\mbox{otherwise}.\end{cases} The spectral radius of H , denoted by \rho(H) , is defined as the spectral radius of \mathcal{A}_{H} . Clearly, for a graph ( 2 -uniform hypergraph) G , \rho(G) is the spectral radius of the adjacency matrix of G . Let \beta(H)=\frac{\rho(H)}{\rho(H^{(2)})} denote the spectral radius ratio of H . If a vertex subset C of a graph G induces a complete graph, then C is called a clique in G . A clique with r vertices is called an r -clique. Let C_{r}(G) denote the set of r -cliques in G . The r -clique tensor Liu of G , denoted by \mathcal{A}_{r}(G)=(a_{i_{1}i_{2}\cdots i_{r}}) , is an r -order |V(G)| -dimension tensor with entries \displaystyle a_{i_{1}i_{2}\cdots i_{r}}=\begin{cases}\frac{1}{(t-1)!},&\{i_{1},\ldots,i_{r}\}\in C_{t}(G).\\ 0,&\textup{otherwise}.\end{cases} The spectral radius of \mathcal{A}_{r}(G) is called the r -clique spectral radius of G , denoted by \rho_{r}(G) . Let \gamma_{r}(G)=\frac{\rho_{r}(G)}{\rho_{2}(H)} , where H is the subgraph of G obtained by deleting all edges that are not containing in an r -clique. Actually, \mathcal{A}_{r}(G) equals to the adjacency tensor of an r -uniform hypergraph H_{r} with vertex set V(H_{r})=V(G) and edge set E(H)=\{i_{1}\cdots i_{r}:\{i_{1},\ldots,i_{r}\}\in C_{r}(G)\} . Recent years, the research on tensor eigenvalues of graphs and hypergraphs have received extensive attention ChenBu , Clark , GaoChang , Liu_2024 , YuPeng . The spectral extremal problems of graph and hypergraphs have been an active topic in spectral graph theory. From the research on spectral extremal problems, it is easy to see that certain subgraphs (subhypergraphs) must occur when the spectral radius or the number of edges is large enough. We will consider a localized problem: Are there some spectral conditions to guarantee the existence of certain local subgraphs (subhypergraphs) in the open neighborhood of some vertex? The Lovász theta function Lovasz \vartheta(G) is a powerful tool for studying the independence number and Shannon capacity of graphs. The Schrijver theta function Schrijver \vartheta^{\prime}(G) is a smaller upper bound for the independence number \alpha(G) , that is, \alpha(G)\leq\vartheta^{\prime}(G)\leq\vartheta(G) . Based on vector coloring, the vector chromatic number \chi_{v}(G) was introduced in Karger , and it is known Balla that \chi_{v}(G)=\vartheta^{\prime}(\overline{G})\leq\chi(G) , where \overline{G} is the complement of G , \chi(G) denotes the chromatic number of G . An eigenvalue bound on \chi_{v}(G) was given in Bilu . We will investigate spectral bounds on the vector chromatic number in local induced graphs. This paper is organized as follows. In Section 2, some definitions, notations and auxiliary lemmas are introduced. In Sections 3 and 4, we give the relationship between spectral radius and local structures of graphs and hypergraphs. We show that certain subgraphs (subhypergraphs) must occur in the open neighborhood of some vertex when \gamma_{r}(G) ( \beta(H) ) is large enough. In Section 5, we give spectral lower bounds on the local vector chromatic number in terms of tensor eigenvalues of graphs, which are also spectral lower bounds on the local chromatic number introduced by Erdős et al. ErdosFuredi . 2 Preliminaries An m -order n -dimension complex tensor \mathcal{A}=(a_{i_{1}\cdots i_{m}}) is a multidimensional array with n^{m} entries, where i_{j}=1,2,...,n , j=1,2,...,m . For a vector x=(x_{1},\ldots,x_{n})^{\top}\in\mathbb{C}^{n} , let \mathcal{A}x^{m-1} denote a vector in \mathbb{C}^{n} whose i -th component is \sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots i_{m}}x_{i_{2}}\cdots x_{i_{m}} (see Qi ). If there exist \lambda\in\mathbb{C} and nonzero vector x=(x_{1},\ldots,x_{n})^{\top}\in\mathbb{C}^{n} satisfying \displaystyle\mathcal{A}x^{m-1}=\lambda x^{[m-1]}, then \lambda is called an eigenvalue of \mathcal{A} , and x is called an eigenvector of \mathcal{A} corresponding to \lambda , where x^{[m-1]}=(x_{1}^{m-1},\ldots,x_{n}^{m-1})^{\top} . The largest modulus of all eigenvalues of \mathcal{A} is called the spectral radius of \mathcal{A} , denoted by \rho(\mathcal{A}) . When \mathcal{A} is a nonnegative tensor, \rho(\mathcal{A}) is an eigenvalue of \mathcal{A} , and there exists a nonnegative eigenvector associated with \rho(\mathcal{A}) . Let \mathbb{R}_{+}^{n} denote the set of n -dimensional nonnegative real vectors. A tensor is called symmetric if its entries are invariant under any permutation of their indices. Lemma 2.1 . Qi2013 Suppose that \mathcal{A}=(a_{i_{1}\cdots i_{m}}) is an order m dimension n symmetric nonnegative tensor, with m\geq 2 . Then the spectral radius of \mathcal{A} is equal to \displaystyle\max\left\{\mathcal{A}x^{m}:\sum_{i=1}^{n}x_{i}^{m}=1,x=(x_{1},\ldots,x_{n})^{\top}\in\mathbb{R}_{+}^{n}\right\}, where \mathcal{A}x^{m}=x^{\top}(\mathcal{A}x^{m-1})=\sum_{i_{1},\ldots,i_{m}=1}^{n}a_{i_{1}\cdots i_{m}}x_{i_{1}}\cdots x_{i_{m}} . Lemma 2.2 . [ YY , Theorem 5.3] Let \mathcal{A} be an m -order n -dimension nonnegative tensor. Then \displaystyle\rho(\mathcal{A})=\max_{0\neq x\in\mathbb{R}_{+}^{n}}\min_{x_{i}>0}\frac{(\mathcal{A}x^{m-1})_{i}}{x_{i}^{m-1}}. For an n -vertex r -uniform hypergraph H , by Lemma 2.1 , we know that \rho(H)=\max\left\{\mathcal{A}_{H}x^{r}=r\sum_{i_{1}\cdots i_{r}\in E(H)}x_{i_{1}}\cdots x_{i_{1}}:\sum_{i\in V(H)}x_{i}^{r}=1,x\in\mathbb{R}_{+}^{n}\right\}. (2.1) For a vertex u of H , the degree of u is the number of edges containing u in H . Let \Delta(H) denote the maximum degree of H . Lemma 2.3 . [ Cooper , Theorem 3.8] Let H be an n -vertex r -uniform hypergraph. Then \displaystyle\frac{r|E(H)|}{n}\leq\rho(H)\leq\Delta(H). Let K_{r+1}^{+} denote the r -uniform hypergraph obtained from K_{r+1} by enlarging each edge of K_{r+1} with r-2 new vertices such that distinct edges of K_{r+1} are enlarged by distinct vertices. An r -uniform hypergraph is called linear if every two edges have at most one common vertex. Lemma 2.4 . [ GaoChang , Theorem 1.1] Let H be a K_{r+1}^{+} -free r -uniform linear hypergraph with n vertices. Then \rho(H)\leq\frac{n}{r} when n is sufficiently large. Lemma 2.5 . Liu For a graph G on n vertices, we have \displaystyle|C_{r}(G)|\leq\frac{n}{r}\rho_{r}(G). The clique number of a graph G , denoted by \omega(G) , is the size of the maximum clique in G . Lemma 2.6 . LiuBu Let G be an n -vertex graph. For any positive integer t\leq\omega(G) , we have \max\left\{\sum_{\{i_{1},\ldots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}:\sum_{i=1}^{n}x_{i}=1,x\in\mathbb{R}^{n}_{+}\right\}={\omega(G)\choose t}\omega(G)^{-t}. An orthonormal representation of an n -vertex graph G is a set \{u_{1},\ldots,u_{n}\} of unit real vectors such that u_{i}^{\top}u_{j}=0 if i and j are two nonadjacent vertices in G . For an orthonormal representation f=\{u_{1},\ldots,u_{n}\} of a graph G , its Gram matrix M_{f} is the positive semidefinite matrix such that (M_{f})_{ij}=u_{i}^{\top}u_{j} . The orthonormal representation f is called nonnegative if u_{i}^{\top}u_{j}\geq 0 for any i,j\in V(G) . The following spectral characterization of the Schrijver theta function \vartheta^{\prime}(G) follows from the equation (A.6) in Acin . Lemma 2.7 . Acin For any graph G , \vartheta^{\prime}(G) is the maximum, over all nonnegative orthonormal representations f of the complement graph \overline{G} , of