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
393
questions
0
votes
0
answers
5
views
Bound the $\infty$-norm of the eigenvector of the second minimum eigenvalue of normalized Laplacian from below
I meet the above problem while reading a paper. The problem can be stated as below.
Consider an undirected graph $G$. Let $\mathbf{v}$ be a vector such that $\mathbf{D}^{1/2}\mathbf{v}$ is the ...
3
votes
1
answer
169
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
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
1
answer
135
views
Invertibility of message passing with invertible parametrization
Consider the message passing framework defined by, $$f(\boldsymbol{x}_i)= \boldsymbol{x}_i + \sum_{j \neq i} (\boldsymbol{x}_i -\boldsymbol{x}_j) g(\|\boldsymbol{x}_i -\boldsymbol{x}_j\|^2),$$ for $i=...
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_{\...
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 ...
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 $\...
0
votes
1
answer
65
views
Number of bi-directional (or symmetric edges) [closed]
I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
5
votes
3
answers
2k
views
Effect of different graph operations on spectrum of graph laplacian?
The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this ...
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 ...
1
vote
0
answers
77
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
0
votes
1
answer
107
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
2
votes
1
answer
234
views
Do balls in expander graphs have small expansion?
Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$?
My intuition is that $B_r$ will ...
1
vote
0
answers
89
views
Max-cut from Laplacian
(This question seems like very standard material for those well-versed in the subject. I thought I would get a quick answer from Math stackexchange, but to no avail.)
Given a weighted graph with $n$ ...
5
votes
2
answers
182
views
Can we calculate the spectral radius of the universal cover for specific graphs?
Background
For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. 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 $...
1
vote
0
answers
44
views
Bounds on the spectral radius of a perturbed directed graph
Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
1
vote
0
answers
51
views
Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph
Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
8
votes
1
answer
207
views
Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?
The Heawood graph is a $3$-regular graph on $14$ vertices. Its (adjacency) spectrum is $\{ (3)^1, (\sqrt{2})^6, (-\sqrt{2})^6, (-3)^1 \}$. So, $3/7 \approx 42.8\%$ of its eigenvalues equal $\sqrt{2}$.
...
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
1
answer
2k
views
Eigenvalues of directed Laplacian matrix $L$ and $DL$, where $D$ is a diagonal matrix with positive entries
I have a weighted Laplacian matrix $L$ of a strongly connected directed graph and a diagonal matrix $D$ with positive entries. Since the graph is directed, $L$ is non-symmetric real. Further, since ...
18
votes
7
answers
3k
views
Spectral properties of Cayley graphs
Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good ...
2
votes
0
answers
318
views
Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?
In Bobkov and Tetali - Modified Log-Sobolev Inequalities, Mixing and Hypercontractivity (extended version Modified Logarithmic Sobolev Inequalities in Discrete Settings), at the beginning of section 3,...
1
vote
0
answers
33
views
Tightness of the bounding the operator norm of graph by average degree from below
Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue
$\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
3
votes
1
answer
105
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
7
votes
1
answer
303
views
Diameter bound for graphs: spectral and random walk versions
This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
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 ...
0
votes
0
answers
31
views
Resolvent estimates for Laplacians on directed graphs
Let us consider a directed and weighted graph $G$ with $N = |G|$ nodes. Denote the corresponding (weighted) adjacency matrix by $W \in \mathbb{R}^{N\times N}_{\geq 0}$ and let $D$ be the diagonal in-...
0
votes
0
answers
62
views
On eigenvalues of signed complete graphs
From Akbari et al. -1 as well as Akbari et al. -2, we have that the eigenvalues of a signed complete graph $K_n$ with the negative edges forming an induced graph $H$ with order $k$ has the ...
0
votes
0
answers
71
views
When is the sum of matrices (circulant + [super upper triangular]) not diagonalizable?
By the circulant matrix $C \in M_n(\mathbb{R})$, we mean that
$$ C = \left[\begin{array}{c|c|c|c} e_n & e_1 & \cdots & e_{n-1} \end{array}\right] $$
where $e_1,\dots,e_n$ are the standard ...
2
votes
1
answer
122
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
1
vote
1
answer
118
views
Directed graph whose adjacency matrix admits only 0 as eigenvalue
Let $G$ be a directed graph and let $P_i$
be its vertices. Let $A$
be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$
if and only if there is a directed edge from $P_i$
to $P_j$, ($a_{i,...
8
votes
3
answers
7k
views
Spectrum of an adjacency matrix
The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
0
votes
2
answers
565
views
Estimating the shift in the $\lambda_{\max}$ of a matrix under a diagonal perturbation
Given a matrix $A$ and a diagonal matrix $D$, how can we estimate $\lambda_{\max}(A+D) - \lambda_{\max}(A)$? Feel free to make other assumptions about the matrices that they are all symmetric and have ...
6
votes
1
answer
387
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
0
votes
1
answer
104
views
Two fractionally isomorphic graphs but only one having eigenvalue zero
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) with adjacency matrices $A_G$ and $A_H$, respectively, such that
$G$ and $H$ are ...
4
votes
1
answer
86
views
Strongly/distance regular graphs over $\mathbb{Z}_2^n$ with the same parameters
I am wondering if there is a known example of a pair of non-isomorphic graphs $G$ and $H$ that are both Cayley graphs for $\mathbb{Z}_2^n$ (for some $n$) and are both distance regular and have the ...
0
votes
0
answers
31
views
Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices
Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...
0
votes
0
answers
122
views
On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph
Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
1
vote
0
answers
58
views
What do you call this class of matrices with a unique positive eigenvalue associated to a graph?
I am looking for the name of a class of symmetric matrices $M\in\Bbb R^{n\times n}$ that I can associate to a (finite simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and that have the following ...
25
votes
3
answers
1k
views
Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?
30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain ...
39
votes
6
answers
4k
views
Is the Laplacian on a manifold the limit of graph Laplacians?
Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so ...
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 ...
0
votes
0
answers
52
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
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 ...
1
vote
1
answer
381
views
Vertex degree on random graphs
Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$,
where $G_{n,p}$ is a graph with $n$ vertices and the ...
1
vote
1
answer
123
views
Eigenvalues of directed graph with one outward edge for each vertex
I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
0
votes
1
answer
122
views
Entropy of eigenvectors of (traceless) laplacian of a bipartite graph
This problem is motivated by the edge states that sometimes appear (and sometimes not) at the level of Huckel hamiltonians for $\pi$-conjugated benzenoid hydrocarbons. If this sentence is cryptic, ...
0
votes
1
answer
191
views
Series analyzed in Lubotzky–Phillips–Sarnak "Ramanujan Graphs"
In the LPS paper "Ramanujan graphs" the adjacency matrix of $X^{p,q}$, for simplicity say that $p,q\equiv1\mod{4}$ and $\left(\frac{p}{q}\right)=1$ (so, nonbipartite) and $n=\lvert X^{p,q}\...
3
votes
1
answer
269
views
Relation between spectra of a Cayley graph of a group and irreducible characters of that group
I know the following fact:
If $G$ is an abelian group and $S\subset G$ be a subset of G such that $1\notin G$ and $S=S^{-1}$ and we draw an edge between $g$ and $h$ if and only if $hg^{-1}\in S$,then ...