# 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

**6**

votes

**0**answers

112 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 ...

**1**

vote

**0**answers

44 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-...

**1**

vote

**0**answers

54 views

### Expander mixing lemma in combinatoric expanders

There is a well-known relation between combinatoric expansion and the gap between the first and the second largest eigenvalues (Dodziuk 1984)
:
$$ h(G) \le d \sqrt{2 (1 - \alpha)} $$
where
$$h(G) = \...

**1**

vote

**0**answers

74 views

### What is intuitive perception of $T_{\alpha_1} \circ T_{\alpha_2} \circ … \circ T_{\alpha_M} $ in graph domain?

if $G(V,E,W)$ be a weighted graph and $\vert V \vert =N $. for any vertex $i \in \lbrace 1,2,...,,N \rbrace $ define a generalized translation operator $T_i:\mathbb{R}^N \to \mathbb{R}^N $via ...

**10**

votes

**1**answer

270 views

### An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:
Conjecture: If G has ...

**1**

vote

**0**answers

43 views

### Is there a transient graph whose spectral dimension two?

Let $G = (V(G), E(G))$ be an infinite connected simple graph.
Let $((S_n)_n, (P^x)_{x \in V(G)})$ be the simple random walk on $G$.
Let $p_n (x,y) = P^x (S_n = y)$.
A spectral dimension of $G$ is ...

**5**

votes

**1**answer

103 views

### Two graphs with the same number of walks but without a common equitable partition

Consider two undirected graphs $G$ and $H$ of the same order (same number of vertices).
If $G$ and $H$ have a common equitable partition, then it is known (see e.g., Chapter 6 in 1) that these ...

**1**

vote

**0**answers

32 views

### The number of Laplacian eigenvalues of a graph in interval [k,n]

There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$).
I want to know whether there exists any bound ...

**1**

vote

**0**answers

87 views

### U-cospectrality: Cospectral for the universal adjacency matrix

Consider an undirected graphs $G=(V,E)$ and its universal adjacency matrix [1]: $$
U_G(\alpha,\beta,\gamma,\delta)=\alpha A_G + \beta I + \gamma J + \delta D_G,
$$
where $\alpha (\neq 0),\beta,\gamma$ ...

**2**

votes

**1**answer

78 views

### How are characterstic polynomials (resp. Alexander polynomials) distributed amongst adjacency matrices (resp. grid diagrams)?

Fix $n$, and consider the characteristic polynomials for all $C=2^{\frac{n(n-1)}{2}}$ adjacency matrices representing undirected, unweighted graphs on $n$ vertices.
Are the characteristic ...

**2**

votes

**1**answer

85 views

### Local-Global Principle in Graph Spectrum

The question is a bit vague, but any ideas/directions will be appreciated.
Let us fix an $n$-vertex $d$-regular graph $G=(V,E)$. As I understand it, the eigenvalues of the adjacency matrix $A$ of $G$ ...

**2**

votes

**2**answers

104 views

### Discrete approximation of Minkshisundaram-Pleijel zeta function?

I'm looking for some references on the following situation:
$S$ is a Riemannian surface, and $G_n$ is a sequence of metric subgraphs embedded on $S$. Let $\zeta_n$ be the zeta function of the ...

**3**

votes

**0**answers

141 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 ...

**4**

votes

**1**answer

252 views

### What is $e^{- \zeta_{\Delta} '(0)}$ for a $\Delta$ the Laplacian of a manifold?

For a connected, finite graph $G$, let $\lambda_1, \ldots, \lambda_n$ denote the nonzero eigenvalues of the graph Laplacian. We define $\zeta_G = \Sigma_{i = 1}^n \lambda_i^s$.
Then Kirkoffs Matrix-...

**1**

vote

**0**answers

39 views

### $\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph

For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$...

**2**

votes

**1**answer

131 views

### When does a row standardized adjacency matrix have a real spectrum?

A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...

**1**

vote

**0**answers

103 views

### Characterization of k-walk-equivalent graphs

Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$.
Call two graphs $...

**7**

votes

**1**answer

622 views

### graph signal processing

I have read this article
https://arxiv.org/abs/1307.5708
about vertix-frequency analysis on graph.
David IShuman
in this article claims that,"we generalize one of the most important signal ...

**4**

votes

**2**answers

164 views

### How do eigenvalues of combinatorial Laplacian relates to automorphisms in graphs?

Is there a relation between eigenvalues of the graph Laplacian and the automorphism group of a simple graph?
How are the multiplicities of Laplacian eigenvalues related to the order of the ...

**2**

votes

**1**answer

409 views

### Discrete Gaussian free field for a closed manifold

I want to ask if a construction of discrete Gaussian free field has been done for a closed Riemannian manifold. Most of the literature I surveyed either need extra boundary condition and consider ...

**7**

votes

**1**answer

214 views

### Lower bound on the eigenvalues of the Laplacian

I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{...

**5**

votes

**1**answer

109 views

### Inertia of a class of Cayley graphs

Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of ...

**6**

votes

**3**answers

232 views

### Spectrum of orthogonality graph (2)

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...

**3**

votes

**0**answers

211 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

**1**answer

95 views

### Theory of random walks / spectral analysis of non-symmetric Markov chains

I'm reading about markov chains and how to analyze and bound their hitting / mixing times. However many of the useful results seem to require that the analyzed markov chain be symmetric. For reference,...

**4**

votes

**1**answer

110 views

### Distribution of eigenvectors and eigenvalues for random, symmetric matrix

Consider two simple, undirected graphs with adjacency matrices ${\bf A}$ and ${\bf A'}$. Let ${\bf P} = {\bf A'} - {\bf A}$. Thus, ${\bf P}$ is symmetric and always 0 along the diagonal.
Let $f({\bf ...

**4**

votes

**1**answer

184 views

### regular graphs with the smallest eigenvalue -2?

I'm searching for regular graphs with the least eigenvalue -2. Is there any characterization or something that represent all these graphs?also number of vertices is power of n?

**1**

vote

**0**answers

63 views

### Properties of graphs with Hankel-like adjacency matrix

I am having undirected graphs with adjacency matrices which have a regular Hankel-like form, e.g.,
$$A=\begin{pmatrix}0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & (6\times 0 \text{ ...

**1**

vote

**0**answers

57 views

### Relation between the sum of principal minors of different orders

Let $A$ be a symmetric (0,1)-square matrix of order $n$ having the diagonal entries zero. Let $m$ be the nullity of $A$ (number of zero eigenvalues), denoted by $\eta(A)$. Let $A_1$ be the square ...

**1**

vote

**0**answers

43 views

### Relation between nullity of components to its parent graph

Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the ...

**4**

votes

**0**answers

105 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 ...

**2**

votes

**0**answers

59 views

### Nullity of an undirected graph with a pendant edge

Let $G$ be an undirected graph with a vertex $v$ having degree 1. Let $G_1$ be the induced subgraph of $G$ after removing $v$, and $G_2$ be the induced graph of $G$ after removing $v$ along with its ...

**1**

vote

**0**answers

47 views

### Hypercontractive inequality for random walks on sets

Let $k<N$ be natural numbers. In this question we consider graphs whose vertices are size-$k$ subsets of a size-$N$ universe. Consider the following random walk in the graph:
Starting from a set $...

**4**

votes

**1**answer

232 views

### An elementary inequality for graph Laplacians

Let $G$ be an arbitrary graph on $n$ vertices and $\mathcal L$ be its Laplacian.
I need to show that
\begin{equation}\tag{$*$}
\langle \mathcal Lx,\mathcal L(|x|^{p-2}x)\rangle_{\mathbb R^n}\ge 0\...

**2**

votes

**2**answers

117 views

### Questions about interlacing polynomials

If we have a finite set of real-rooted polynomials of the same degree such that any two of them have a common interlacing then does it imply that this set has a common interlacer?
Lemma $4.2$ (top of ...

**6**

votes

**2**answers

208 views

### Generalised Isospectrality of Graphs

Q: Is there a graph matrix-representation (not necessarily an $n \times n$ matrix for an $n$-graph) such that isospectrality implies graph-isomorphism? For instance, would the simple distance-matrix ...

**5**

votes

**1**answer

323 views

### The spectrum of the discrete Laplacian

Consider a connected (we define connected components by defining the set of vertices where every vertex has one neighbour) sublattice $V$ of the square lattice $V \subset\mathbb{Z}^2.$
On this we ...

**1**

vote

**0**answers

146 views

### Difference between largest two eigenvalues of a graph Laplacian

The difference between the smallest eigenvalue and the next-smallest of a graph Laplacian (equivalently, the difference between the largest and next-largest of the random walk Markov chain on the ...

**2**

votes

**3**answers

239 views

### What are the eigenvectors of the graph Laplacian of a Johnson graph J(n,k)?

The spectral properties of Johnson graphs are known. However I also like to know more about their eigenvectors. Are there any results on the eigenvectors of the graph Laplacians of these Johnson ...

**0**

votes

**1**answer

104 views

### The Algebraic Connectivity vs. Isoperimetric Number

Let $d$ be a fixed number. By the Cheeger theory and theory of expanders, the second smallest eigenvalue of the Laplacian for a family of $d$-regular graphs is bounded bellow by a positive constant if ...

**3**

votes

**0**answers

93 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(...

**1**

vote

**0**answers

186 views

### Simple random walk on a discrete torus - the eigensystem, reference

My problem concerns finding a reference in which the formulae for the eigenvalues and the corresponding eigenvectors ($n$ linearly independent eigenvectors!) for the transition matrix of a simple ...

**2**

votes

**0**answers

94 views

### explicit formulae of heat kernel on graphs

I have just discovered this article about heat kernels on graphs. It has been written by a respected theoretical physicist, but seemingly never made it into a peer-reviewed journal. On the other hand, ...

**1**

vote

**0**answers

30 views

### Is $L'L_\text{in}+L_\text{in}'L$ positive semi-definite?

Assume that $A$ is the adjacency matrix of a strongly connected directed graph, that is, $A$ is non-negative and irreducible. Let $$L_\text{in}=D_\text{in}-A',\;L=D_\text{in}-A'+D_\text{out}-A$$ where ...

**1**

vote

**0**answers

56 views

### Cut norm and biclique gap?

Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...

**1**

vote

**0**answers

40 views

### How to define a harmonic coordinates on data graph?

Suppose I knew the Ricci curvature at some point of the Manifold along several directions (the number of directions should be much more than the dimension of the manifold). Can I decompose the Ricci ...

**10**

votes

**0**answers

137 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 ...

**2**

votes

**2**answers

84 views

### Volume doubling implies that the degree is uniformly bounded above?

Let $G=(V,E)$ be a connected graph. Here $V$ is the set of all vertices of $G$, and $E$ is the set of all edges of $G$. Suppose that $G$ is locally finite, i.e., $\sharp\{y\sim x:y \in V \}$ is finite ...

**8**

votes

**3**answers

335 views

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.
Friedman showed that every random $d$-regular graph ...

**2**

votes

**1**answer

107 views

### Connection between graph spectra and graph homomorphisms [closed]

Since there are many properties of graph which can be expressed in terms of both existence of graph homomorphisms and graph spectra I expect there are some papers exploring this connection between ...