Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
3answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
3answers
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
1answer
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 ...