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
375
questions
0
votes
0
answers
44
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 ...
- 3,774
2
votes
1
answer
99
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=\...
- 3,774
1
vote
1
answer
57
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,...
- 3,774
6
votes
1
answer
297
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 ...
- 3,774
0
votes
1
answer
92
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 ...
- 493
4
votes
1
answer
76
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 ...
- 2,064
0
votes
0
answers
22
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
107
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$ ...
- 61
5
votes
1
answer
96
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 ...
- 11k
1
vote
0
answers
44
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 ...
- 11.4k
5
votes
0
answers
129
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 ...
- 2,113
0
votes
0
answers
43
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 ...
- 199
8
votes
0
answers
170
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 ...
- 235
0
votes
0
answers
26
views
Nilpotent parts of graph Laplacians
Let $W$ be the adjacency matrix of a directed graph. Let us denote by $D$ the associated in-degree matrix, whose diagonal entries are given by $D_{ii} = \sum_j W_{ij}$. The associated Laplacian
$$ L =...
- 83
0
votes
1
answer
219
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 ...
- 11
1
vote
1
answer
87
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 ...
- 283
0
votes
1
answer
80
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, ...
- 251
0
votes
1
answer
170
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}\...
- 455
0
votes
0
answers
44
views
State-of-the-art for approximating the Cheeger constant (for graphs)
What is the state-of-the-art algorithm for approximating the Cheeger constant, given a regular graph? Ideally, such an algorithm would run in polynomial time (in the size of the graph, and could be ...
- 455
0
votes
0
answers
28
views
upper band for the eigenvalue-distance from an eigenvalue regarding its eigenvector extension, in the adjacency matrix of a local graph?
Background: Suppose we have a system in which an electron can hop locally on this lattice. Here locally means that the electron can hop up to a short distance. We can make an energy spectrum that ...
- 101
2
votes
1
answer
191
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 ...
- 131
0
votes
0
answers
118
views
Non-backtracking operator and spectra
Let $A$ be the adjacency operator of a symmetric graph $\Gamma$. (It may be weighted and/or non-regular, but, to keep it simple, let us say it is unweighted and regular of degree $d$.) We want to ...
- 18.6k
0
votes
0
answers
70
views
Reference request: Spectral gap for cubic random graphs
I gather the following is well known:
Fact: There exists some $\epsilon>0$ such that with probability approaching $1$ as $n\to\infty$, a random cubic (i.e. $3$-regular) graph on $n$ vertices has ...
- 51
7
votes
0
answers
175
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 ...
- 2,402
7
votes
0
answers
98
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 ...
- 2,402
0
votes
0
answers
65
views
Vertex percolation on bipartite graphs
This is essentially a repost of this math overflow post since it didn't get any reception.
Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with ...
- 1
1
vote
0
answers
69
views
Graph energy and spectral radius
Suppose $G$ is a simple graph of order $n$ with eigenvalues $\lambda_1\geq \cdots\geq \lambda_n$. I've encountered the quantity $L=\big\vert |\lambda_1|-|\lambda_2|-\cdots-|\lambda_n|\big\vert$. Note ...
- 171
2
votes
1
answer
75
views
Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two
Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...
- 511
4
votes
0
answers
86
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 ...
- 327
1
vote
0
answers
54
views
Angles between edges of a geometric graph and graph invariants
Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...
- 532
0
votes
0
answers
98
views
Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?
Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
- 511
0
votes
0
answers
45
views
Variation in eigenvalues of adjacency matrices of regular graphs
What is known about the range of spectra of regular graphs? That is, I wish to know the largest intervals in which the minimum and maximum eigenvalues of a graph lie. For example, it is known that the ...
- 1,823
4
votes
1
answer
144
views
Explicit constructions of regular graphs with very sparse induced subgraphs
Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
2
votes
2
answers
131
views
Ramanujan graphs from varieties over finite fields
Let $G$ be a $d$-regular graph. Let $d= \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d $ be the eigenvalues of the adjacency matrix of $G$, and set $\lambda = \max (|\lambda_2| , |\lambda_n|) $...
- 7,605
0
votes
1
answer
120
views
Is there a notion of "rapid" expansion for graphs?
I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for.
Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described ...
- 939
2
votes
1
answer
82
views
Are the eigenvalues of the 1D lattice with random weights known?
Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...
- 169
4
votes
0
answers
141
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 ...
- 150
0
votes
0
answers
159
views
compare two graphs with different number of nodes
Is there a distance measure between two graphs with different number of nodes?
To be specific, let $W_1$ and $W_2$ be their adjacency matrices respectively. When the two graphs have the same number of ...
- 205
1
vote
0
answers
97
views
Do I need to find a maximum matching to get the matching number of a graph?
Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum ...
- 11
2
votes
0
answers
226
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 ...
- 13.3k
1
vote
0
answers
139
views
What is a good algorithm to measure similarity between isomorphic graphs with different node labels?
I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...
- 141
1
vote
1
answer
258
views
Trace minimization for generalized eigenvalue problem
In [1], it is shown in theorem 1.2 that for symmetric $n \times n$ matrices $A$, $B$, we have
$$
\min_{Y \in Y^*} \text{tr}(Y^TAY) =
\text{tr}(X^TAX) =
\sum_{i=1}^p \lambda_i,
$$
with
$$
\text{
$X^...
- 21
2
votes
1
answer
142
views
Minimal Laplacian spread of a graph
Laplacian spread of a graph is the difference among the largest and the second smallest Laplacian eigenvalue of the graph. Is there any result or conjecture that discusses about the graphs having ...
8
votes
0
answers
389
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$. ...
- 18.6k
0
votes
0
answers
85
views
Incidence matrix of a planar graph
Are there any special properties for the incidence matrix when a graph is planar?
- 75
1
vote
1
answer
117
views
Incidence matrix in a graph, meaning of $B^TB$
If $B\in\mathbb{R}^{n\times e}$ is the incidence matrix corresponding to a graph with $n$ vertices and $e$ edges, we know that $BB^T\in\mathbb{R}^{n\times n}$ is the graph Laplacian matrix.
I am ...
- 75
5
votes
1
answer
374
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 130
2
votes
1
answer
162
views
The complexity of expansion ratio (Cheeger constant) of a graph
Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...
- 620
6
votes
1
answer
279
views
Determinant of walk matrix for a skew-symmetric matrix of even order
Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...
- 437
7
votes
1
answer
762
views
Strategies for bounding the spectral norm of a tensor?
Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by
$$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$
(...
- 18.6k