Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
Sebastian M. Cioabă, Krystal Guo, Chunxu Ji, Mutasim Mim · 2025
Read Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups by Sebastian M. Cioabă, Krystal Guo, Chunxu Ji, Mutasim Mim (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-2508-05871.txt.
Introduction
Sebastian Cioabă, Krystal Guo, Chunxu Ji, and Mutasim Mim ask whether deeper spectra can tell look-alike networks apart. Strongly regular graphs come in families whose members share all basic parameters. Such members always share their ordinary eigenvalues, so that fingerprint fails. The team looks one level up, at the spectra of triangle complexes built from the graphs.
They compute those higher spectra for several classic families, including Hamming and triangular graphs. In many cases the triangle spectrum separates graphs that the ordinary spectrum cannot. Some stubborn pairs still tie, marking the method's limits. A separate result shows that a local common-neighbor condition forces a graph's first cohomology group to vanish. That condition is checked across several families. The work sharpens the tools for distinguishing highly symmetric networks.
Catalog record
| CREATOR | Sebastian M. Cioabă, Krystal Guo, Chunxu Ji, Mutasim Mim |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05871
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups Sebastian M. Cioabă, Krystal Guo, Chunxu Ji, Mutasim Mim Abstract It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). In this paper, we investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this direction, we study the clique complexes of strongly regular graphs, and determine the spectra of the triangle complexes of several families of strongly regular graphs including Hamming graphs and Triangular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. We also prove that if a graph has the property that for any induced cycle, there are four consecutive vertices on the cycle with a common neighbor, then the first cohomology group of the graph is trivial and we apply this result to several families of graphs. Keywords: eigenvalues, Laplacian, simplicial complex, clique complex, strongly regular graphs Mathematics Subject Classifications 2020: 05C50, 05E30, 05E45, 15A18 1 Introduction In the area of spectral characterization of graphs, one of the main goals is determining whether the eigenvalues of a given graph matrix (the adjacency matrix or the Laplacian matrix, for example) characterize the graph, see [ 26 , 27 ] . It is well known that there exist non-isomorphic graphs that are cospectral (have the same eigenvalues). In such cases, it is of interest to determine if the eigenvalues of other graph matrices can distinguish these graphs. In that direction, there has been much interest in exploring the relationship between the spectra of various matrices of graph and graph isomorphism, especially for the class of strongly regular graphs, see [ 3 , 23 ] for example. A graph is strongly regular with parameters (v,k,\lambda,\mu) or a (v,k,\lambda,\mu) -SRG for short, if it has v vertices, is k -regular, any two adjacent vertices have exactly \lambda common neighbors and any two distinct and non-adjacent vertices have exactly \mu common neighbors. We quote below from the preface of the recent monograph [ 9 ] : The topic of strongly regular graphs is an area where statistics, Euclidean geometry, group theory, finite geometry, and extremal combinatorics meet. The subject concerns beautifully regular structures, studied mostly using spectral methods, group theory, geometry and sometimes lattice theory. In general, there is no relation between the eigenvalues of the adjacency matrix and the eigenvalues of the Laplacian matrix of a graph. However, in the case of regular graphs, such a connection between these spectra exists and the eigenvalues of one matrix can be deduced easily from the eigenvalues of the other matrix. Non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same adjacency or Laplacian matrix eigenvalues), see [ 8 , Thm. 9.1.3] . One class of matrices which has been studied are the symmetric powers of graphs. In [ 2 ] , the authors show that the spectra of the symmetric square of strongly regular graphs with the same parameters are equal, while giving computational evidence that higher symmetric powers may be possible graph invariants for strongly regular graphs. In [ 1 , 6 ] , it is shown that there are infinite families of pairs of non-isomorphic graphs with cospectral m -th symmetric powers, for all m , however none of these graphs are strongly regular. Similarly, the spectrum of a matrix related to a quantum walk on a strongly regular graph was proposed in [ 10 , 11 ] and the first strongly regular counterexamples were found in [ 12 ] . In this paper, we study the spectra of the up-Laplacians L_{i}^{\uparrow} and first cohomology groups (see Section 2 for the definitions) of the clique complexes of various classes of strongly regular graphs. These clique complexes are also of interest in topological data analysis, see [ 29 ] . In Section 2 , we present the main definitions and notations. In Section 3 , we determine the spectra of the up-Laplacian L_{1}^{\uparrow} of partial geometries and generalized quadrangles. In Section 4 , we determine the spectra of the up-Laplacian L_{1}^{\uparrow} of Hamming graphs (Section 4.2 ), and most of this section is devoted to determining the L_{1}^{\uparrow} spectra of the Triangular graphs (Theorem 4.3 ). The eigenvalues of the higher dimensional up-Laplacians L_{i}^{\uparrow} of the Triangular graphs are also obtained there. In Section 5 , we show that if a graph has the property that for any induced cycle, there are four consecutive vertices on the cycle with a common neighbor, then the first cohomology group of the graph is trivial and we apply this result to several families of graphs. The focus then shifts to describing our computations of the spectra of the up-Laplacians L_{1}^{\uparrow} of small strongly regular graphs in Section 6 , with examples of cospectral pairs given in Section 6.2 including a pair of strongly regular graphs on 40 vertices. 2 Definitions In this section, we introduce the definitions of simplicial complexes and some of their properties. Our main reference is [ 5 ] . If V is a finite set, then a simplicial complex X on V is a collection of subsets of V such that if F\in X , then any subset of F is also in X . We call such F a face of X , and the dimension of F is defined to be |F|-1 . The set of i -dimensional faces in X is denoted by X_{i} , and conventionally X_{-1}=\{\emptyset\} . Assume we have a global ordering on the ground set V . If F=\{x_{0},x_{1},\dots,x_{i}\} , where x_{0}<x_{1}<\dots<x_{i} , then we define [F:K]=\begin{cases}(-1)^{j},&\text{if }K\subset F\text{ and }F\setminus K=\{x_{j}\},\\ 0,&\text{otherwise. }\end{cases} (1) In this paper, we will consider the clique complex of a graph; the clique complex \mathcal{K}(G) of an undirected graph G is the simplicial complex formed by the subsets of vertices in the cliques of G . Here, the ground set is the vertex set of a graph, equipped with a total ordering. If we restrict to faces of dimension 2 , the triangle complex \mathcal{T}(G) of G is the simplicial complex formed by the subsets of vertices in the triangles of G . Figure 1 shows the clique complex of a graph G (which the complete graph K_{4} with one edge deleted) with the incidences between its faces being decorated by the signing given by ( 1 ). We will use this graph as a running example throughout this section. Figure 1 : A graph G , left , and its clique complex, right . In the clique complex, the lines decorated with dots and dashes connect faces F,K where [F:K]=-1 and the other lines connect faces F,K where [F:K]=1 , where we take the natural ordering of the vertices, 1<2<3<4 . Since we are interested in clique complexes of finite graphs, we will give simplified, finite-dimensional versions of the definitions, for readability. Note that we use \text{Mat}_{U\times W}({\mathbb{F}}) to denote matrices with rows indexed by set U , columns indexed by W and elements in field {\mathbb{F}} . For i\geq 0 , we use the