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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
8