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
394
questions
1
vote
0
answers
48
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
216
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 previously ...
2
votes
2
answers
107
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
482
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
177
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 ...
1
vote
1
answer
1k
views
largest adjacency eigenvalue of line graphs
It is well-known that the largest eigenvalue $\lambda_{\max}$ of the adjacency matrix of a graph $G$ lies between the average and the maximal degree of $G$. Another known lower estimate is due to Dvo\...
12
votes
1
answer
497
views
Spectrum of induced subgraphs of Paley graph
Let $G_q$ be a Paley graph on $q$ vertices, where $q=1 \text{ (mod 4)}$, i.e., the vertices of $G_q$ are the elements of the finite field $\mathbb{F}_q$, and there is an edge between vertices $a,b \in ...
5
votes
1
answer
1k
views
Intuition on Kronecker Product of a Transition Matrix
Let $T$ be a $N\times N$ transition matrix for a markov chain with $N$ states. Thus $T_{ij}$ is the probability of transition from state $i$ to state $j$ (and thus rows summing to one). Now consider ...
3
votes
0
answers
91
views
Analogues of relative property $(\tau)$ for Schreier graphs
Suppose I have an expanding family of Schreier graphs $Z_n=\text{Sch}(G_n,S_n,X_n)$ of groups $G_n=\underbrace{G\wr\ldots\wr G}_{\text{$n$ times}}$ acting on sets $S_n=S^n$ by generating sets $X_n$, ...
1
vote
1
answer
240
views
Jordan blocks of directed graphs
Let $G$ be a (possibly weighted) directed graph with $n$ vertices and let $P$ be its transition matrix. That is, $P = D^{-1}A$ where $A$ is the graph's adjacency matrix and $D$ is a diagonal matrix ...
3
votes
1
answer
79
views
A graph spectra graph problem?
I was wondering how to relate the spectra of the Zig-Zag product of two graphs in term of the factors...someone can help me?
4
votes
1
answer
165
views
A graph spectra problem?
The composition $G=G_1[G_2]$ of graphs $G_1$ and $G_2$ with disjoint point sets $V_1$ and $V_2$ and edge sets $X_1$ and $X_2$ is the graph with point vertex $V_1×V_2$ and $u=(u_1,u_2)$ adjacent with $...
4
votes
0
answers
656
views
Counting loops in degree: 1 or 2?
Here's what seems to be an annoying technicality when dealing with loops in graphs.
In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex $v$ ...
5
votes
2
answers
181
views
colored graph characteristic polynomial
This was asked previously on stackexchange and it was suggested to bring it here where more specialists could see it.
Given the adjacency matrix $\mathbf{A}$ for a simple connected graph, the ...
1
vote
0
answers
69
views
spectrum of some product of 2 graphs? [closed]
Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be 2 graphs:
Union of 2 graphs $G_1 \cup G_2=(V_1 \cup V_2,E_1 \cup E_2)$;
Composition of 2 graphs $G_1[G_2]$;
Sum(join) of 2 graphs by $G_1+G_2=(V(G_1)\cup ...
6
votes
1
answer
668
views
Connection between PageRank and Fiedler vector
This question is on graph clustering. In its simplest form, the eigenvector corresponding to the second smallest eigenvalue of the normalized Laplacian of a graph provides a relaxed solution to the ...
7
votes
1
answer
299
views
Does an expander remain an expander after removing few vertices and edges?
Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices.
Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
1
vote
1
answer
216
views
best known bounds for spectral radius [closed]
There are many bounds for the spectral radius of graphs in terms of no. of vertices, maximum degree, chromatic number etc. I wish to know till date what are the best lower and upper bound for the ...
1
vote
0
answers
166
views
Largest eigenvalue of signed graph
Let us consider a graph where edges can have weight 1 or -1, such a graph is called signed graph. In a signed graph, a cycle is called balanced cycle when product of weights on its edges is positive ...
1
vote
1
answer
449
views
Spectrum of adjacency matrix of block graph
Let us consider a graph $G$ having $m$ number of complete sub-graphs $K_{n_1},K_{n_2},...,K_{n_m}$ which have size $n_1,n_2,...,n_m$ respectively. Further $\forall i$, one vertex of $K_{n_i}$ is ...
5
votes
2
answers
958
views
Lower bound for smallest eigenvalue of symmetric doubly-stochastic Metropolis-Hasting transition matrix
For my master's thesis research, I stumbled upon a question concerning the Metropolis-Hasting transition matrix $W$.
Context $\quad$
Let me start with some context. I consider connected undirected ...
7
votes
4
answers
1k
views
Minimum negative eigenvalue of zero-one matrices
The following question must have been answered decades ago.
For $n$ fixed, what is the most negative eigenvalue among all trace zero zero-one matrices (that is, all entries are either zero or one, ...
4
votes
1
answer
405
views
Behaviour of eigenspaces of adjacency matrices after a single change to the graph
Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...
4
votes
1
answer
2k
views
Size of connected components of a graph via its spectrum
I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is:
Is there a way to understand the size of each connected ...
4
votes
1
answer
4k
views
exact definition of Fiedler vector
For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...
1
vote
2
answers
392
views
Spectral radius of a non-negative matrix after moving and replicating an element
Let $A$ be a non-negative square matrix and its spectral radius (i.e., it's largest eigenvalue) be $\rho(A)$. I need to do the following operation to $A$ and compare the resulting spectral radii.
...
3
votes
1
answer
144
views
An algebraic graph theory problem?
Let we consider cayley graph $G=cayley(Z_2^n,S)$ which S is a subset of $Z_2^n$. If we consider a set of spectrum for this graph which satisfies all relations for cayley graph like $\sum_i \lambda_i^2=...
3
votes
3
answers
241
views
Graphs cospectral with Cayley graphs
Let $G$ be a Cayley graph, and $H$ a graph cospectral with $G$. Must $H$ be a Cayley graph? Does a counterexample exist? If $G$ is a circulant graph, does a counterexample exist?
3
votes
1
answer
259
views
Spectra of undirected $d$-regular graphs
Let $G$ be a undirected $d$-regular graph, that is, a graph whose all vertices have the same degree $d$. It is known that the eigenvalues $\sigma_i$, $i=1,\cdots,n$, of the adjacency matrix are real ...
5
votes
1
answer
693
views
Graph spectra and topology
This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.
To give an ...
2
votes
1
answer
306
views
Spectrum of Laplacian matrix of an infinite tree graph
I'm having difficulty understanding a fact stated in a research paper I'm reading. Namely, let $T$ be a tree with all nodes of degree $4$ (ie, the root has $4$ daughter nodes and all other nodes have $...
2
votes
1
answer
142
views
Spectral radius of perturbed bipartite graphs
I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually, I'm not exactly looking into bipartite but my ...
14
votes
1
answer
2k
views
Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?
In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
2
votes
1
answer
160
views
Do product distributions (or graph products) eventually cluster as more products are taken?
Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
5
votes
2
answers
806
views
Database of adjacency matrices on cospectral non-isomorphic graph pairs
Is there a repository of cospectral non-isomorphic graphs available somewhere?
I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
1
vote
2
answers
282
views
Laplacian spectrum and size of a graph
Does the Laplacian spectrum of a graph give information on the size of the graph?
For example, is it possible that I have two disconnected graphs $G$ and $H$ with the following features:
1) $G$ and $...
7
votes
1
answer
402
views
Sum of the absolute eigenvalues of A>=B
Kindly help me to prove/disprove the following statement.
Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ (...
6
votes
1
answer
506
views
Eigenvalue inequality for regular graphs
I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...
5
votes
1
answer
126
views
recovering information about a group from the spectrum of its Cayley graph
Suppose you have a finite group and you consider its Cayley graph with respect to some fixed generating set of nonidentity elements closed under inversion. Are there any results known to the effect ...
9
votes
1
answer
253
views
Expansion in strongly regular graphs
Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
1
vote
1
answer
743
views
Strongly connected graph and the eigenvalues of the laplacian matrix
Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. Reformulation of this definition: $G$ is strongly connected iff for any ...
7
votes
3
answers
3k
views
Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian
The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)?
To make the question as self-contained as ...
2
votes
0
answers
298
views
Maps between graphs defined through laplacian operations
Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at ...
2
votes
2
answers
333
views
Application of cospectral graphs
Cospectral graphs are graphs having same eigenvalues. Constructions of cospectral graph is an interesting question in graph theory. Now a days we use graph theory in different brunches of Sciences and ...
1
vote
0
answers
228
views
Lp norm estimates for the inverse of the Laplacian on a graph
I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} \|...
0
votes
2
answers
566
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 ...
4
votes
0
answers
124
views
An inequality from the "Interlacing-1" paper
This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...
3
votes
0
answers
41
views
About the partial expectation polynomials in the Interlacing-I paper and perfect matchings
I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf
In the use of these ...
4
votes
1
answer
649
views
Embedding graphs into hyperbolic spaces
Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...
0
votes
0
answers
160
views
$l_{\infty}$ norms of matrix perturbations
Say $B$ is a real symmetric matrix of dimension $n$ and $A$ is another real symmetric matrix of the same dimension.
What needs to be the bounds on (which?) norm of $B$ to ensure that $\lambda_{max}(...