Questions tagged [spectral-graph-theory]
Questions related to the spectrum of graphs, defined using one of the possible variants of the discrete Laplace operator or Laplacian matrix. See https://en.wikipedia.org/wiki/Discrete_Laplace_operator
130
questions with no upvoted or accepted answers
13
votes
0
answers
1k
views
A new lower bound for the chromatic number of a graph?
Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
11
votes
0
answers
549
views
Ramanujan Digraphs?
In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...
10
votes
0
answers
216
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
10
votes
1
answer
548
views
Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?
Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and $\...
8
votes
0
answers
306
views
Explicit constructions of Ramanujan graphs
I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
8
votes
0
answers
122
views
Conceptual explanation for the gap in the spectrum of biregular trees
Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval
$$[-2\sqrt{q}, 2\sqrt{q}].$$
The reason for this ...
8
votes
0
answers
391
views
Bounding eigenvalues by taking high powers of matrices: history?
Let $A$ be real symmetric matrix. It is a well-known observation that we can bound any eigenvalue $\lambda$ of $A$ by using the fact that
$$\lambda^{2 k} \leq \textrm{Tr} A^{2 k}$$
for any $k\geq 1$. ...
8
votes
0
answers
432
views
Is there a version of Weyl's law for graph Laplacians?
Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
7
votes
0
answers
193
views
Surprising symmetry in the Ramanujan bound
The condition for a connected $(q+1)$-regular graph to be Ramanujan is that every nonzero eigenvalue $\lambda$ of the graph Laplacian satisfy
$$q+1-2\sqrt{q}\le \lambda\le q+1+2\sqrt{q}.$$
With a ...
7
votes
0
answers
302
views
When can the Cheeger constant be well-approximated by ``Hamming balls''?
Given a graph G, the Cheeger constant is defined by
$$
\DeclareMathOperator{\Vol}{Vol}
h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}.
$$
Here, $\Vol S$ is the sum of ...
5
votes
0
answers
115
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
5
votes
0
answers
177
views
(How) does the spectral gap of the $n\times n$ Rubik's cube close with $n$?
Consider the spectrum of the adjacency matrix $A$ of the Cayley graph of the standard, 3x3x3 Rubik's cube generated with the usual quarter-turn and half-turn twists of each face (the Singmaster ...
5
votes
0
answers
110
views
Closed paths, closed trails and traces
Let $A$ be the adjacency matrix of a (non-oriented) graph $\Gamma$. Then $\textrm{Tr} A^k$ equals both the sum $\sum_i \lambda_i^k$ of $k$th powers of eigenvalues of $A$, on the one hand, and the ...
5
votes
0
answers
267
views
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...
5
votes
0
answers
361
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
5
votes
0
answers
258
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
4
votes
0
answers
132
views
Derivative of characteristic polynomial of a graph and derivative of characteristic polynomial of a vertex-deleted subgraph have a common root
Let $G$ be a simple graph and $G-i$ be one of its vertex-deleted subgraphs. Let $\phi(G,x)$ and $\phi(G-i,x)$ be the characteristic polynomials of $G$ and of $G-i$ respectively, with respect to their ...
4
votes
0
answers
157
views
Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?
This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...
4
votes
0
answers
151
views
Relation between two conjectures on reconstruction of graphs
In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...
4
votes
0
answers
474
views
Laplace spectra of "half" grid graph
Let $G=(E,V)$ be a simple graph. The graph Laplacian is given by $$ L= D-A,$$
where $D$ is the degree matrix (diagonal matrix with entries corresponding to the degree of the vertex) and $A$ the ...
4
votes
0
answers
139
views
algebraic connectivity of a tree
Suppose that $T$ is a tree with $n$ vertices and $L$ is the Laplacian matrix of $T$ and $0=\mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ are laplacian eigenvalues.
I think the multiplicity of $\mu_2$ can ...
4
votes
0
answers
651
views
Counting loops in degree: 1 or 2?
Here's what seems to be an annoying technicality when dealing with loops in graphs.
In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex $v$ ...
4
votes
0
answers
124
views
An inequality from the "Interlacing-1" paper
This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...
4
votes
0
answers
589
views
The Bilu-Linial conjecture and Ramanujan graphs
The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...
4
votes
0
answers
181
views
Relaxation = absorption?
Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
3
votes
0
answers
61
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
3
votes
0
answers
64
views
Clique number and spectrum of a graph
In the Wikipedia article on Grassmann graph it is stated that in this graph:
$$\omega=1-\frac{\lambda_{max}}{\lambda_{min}}$$
where $\omega$ is the clique number of the graph, and $\lambda_{max}$ and $...
3
votes
0
answers
182
views
Spectral norm and "operator norm" for hypergraphs
Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
3
votes
0
answers
250
views
Eigenvalue bounds and triple (and quadruple, etc.) products
Very basic and somewhat open-ended question:
Let $A$ be a symmetric operator on functions $f:X\to \mathbb{R}$, where $X$ is a finite
set. Assume that the $L^2\to L^2$ norm of $A$ is $\leq \epsilon$, i....
3
votes
0
answers
141
views
Chromatic number of regular graphs using spectra
There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
3
votes
0
answers
141
views
How related are Fourier transforms on finite groups and Fourier transforms on graphs?
Here are two generalizations of the notion of a Fourier transform. I am also aware of the Pontryagin Duality generalization for locally compact abelian groups, though I am personally more concerned ...
3
votes
0
answers
823
views
Principal eigenvector of non-negative symmetric block matrix is approximated by a linear combination of the principal eigenvectors of the blocks
Let $
M \in \mathbb{R}^{n \times n} =
\begin{bmatrix}
A & B \\
B^T & C
\end{bmatrix}
$ for some nonnegative $A \in \mathbb{R}^{k \times k}, B \in \mathbb{R}^{k \times n-k}, C \in \mathbb{R}^{n-...
3
votes
0
answers
234
views
Does the zeta regularized Laplacian determinant measure the volume of some parameter space? How many "spanning trees" on a manifold?
Let $(M,g)$ be a Riemannian manifold, with Laplacian $\Delta$. If $\lambda_i$ are the nonzero eigenvalues of $\Delta$, we can define the zeta function $\zeta(s) = \Sigma \lambda_i^{-s}$. By analytic ...
3
votes
0
answers
116
views
The algebraic connectivity of graphs with large isoperimetric number
Let $G = (V,E)$ be an undirected graph with maximum degree $\Delta$.
The isoperimetric number of $G$, denoted $i(G)$, is defined by
$$i(G) = \min_{|S| \leq |V|/2} \frac{e(S,\bar{S})}{|S|},$$
where $e(...
3
votes
0
answers
91
views
Analogues of relative property $(\tau)$ for Schreier graphs
Suppose I have an expanding family of Schreier graphs $Z_n=\text{Sch}(G_n,S_n,X_n)$ of groups $G_n=\underbrace{G\wr\ldots\wr G}_{\text{$n$ times}}$ acting on sets $S_n=S^n$ by generating sets $X_n$, ...
3
votes
0
answers
41
views
About the partial expectation polynomials in the Interlacing-I paper and perfect matchings
I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf
In the use of these ...
3
votes
0
answers
253
views
About the small set expansion conjecture
Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \...
3
votes
0
answers
233
views
Must distinct tree eigenvalues be relatively far apart?
How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ?
For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
3
votes
0
answers
799
views
A problem on graph theory and complex numbers!
Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that
$$
||z_1||=\ldots = |...
3
votes
0
answers
127
views
Effect of removing a Hamiltonian cycle on the Laplacian spectrum
Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...
3
votes
0
answers
155
views
inverse M-matrix times mixed-sign vector
Recently a colleague and I came across this unusual phenomenon.
Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable (so,...
2
votes
0
answers
38
views
Given a low-rank symmetric positive semidefinite matrix and a basis of its nullspace, is there a fast way to get the nonzero eigenvalues?
I have a (possibly dense) $k\times k$ real matrix $L = AA^T + B^T B$, a type of combinatorial Laplacian (self-adjoint, symmetric, positive semidefinite) of rank $(k-n)$ and possibly repeated nonzero ...
2
votes
0
answers
72
views
Bound on the magnitude of the entries of the Laplacian pseudo-inverse
Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
2
votes
0
answers
39
views
Regularize a graph while embedding the spectrum of adjacency matrix
Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
2
votes
0
answers
118
views
Graph Laplacians, Riemannian manifolds, and object collisions
To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
2
votes
0
answers
303
views
Spectral norm bound for lower triangular matrix
Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
2
votes
0
answers
113
views
Formulas to determine the value of graph energy with addition or deletion of edges
If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...
2
votes
0
answers
158
views
Closed geodesics and eigenvalues in a non-regular graph
Let $\Gamma$ be an undirected graph the degree of whose $n$ vertices is $\leq D$ without necessarily being constant. Say we have bounds of type $\leq \gamma^{2 k}$ for the number of closed geodesics ...
2
votes
0
answers
180
views
The rank of a Laplacian-type matrix
Suppose that $M$ is an integer, symmetric matrix of order $n>2$ with the positive integers $K_1,\dotsc,K_n$ on its main diagonal, and with all the off-diagonal elements equal to $0$ or $1$ so that ...
2
votes
0
answers
191
views
Expansion of random subgraphs of a bi-regular bipartite graph
Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...