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
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 ...
IHitSquirrel's user avatar
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 ...
David Roberson's user avatar
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 ...
user84068's user avatar
  • 169
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 ...
Xiaoyu He's user avatar
  • 1,151
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 ...
user avatar
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\...
Delio Mugnolo's user avatar
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 ...
karakusc's user avatar
  • 171
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 ...
dineshdileep's user avatar
  • 1,371
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$, ...
amakelov's user avatar
  • 987
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 ...
Daniel86's user avatar
  • 215
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?
Vahid's user avatar
  • 31
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 $...
Vahid's user avatar
  • 41
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$ ...
amakelov's user avatar
  • 987
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 ...
JustThinking's user avatar
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 ...
Vahid's user avatar
  • 51
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 ...
Arun's user avatar
  • 171
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 ...
Nalini's user avatar
  • 73
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 ...
Sry's user avatar
  • 135
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 ...
Ranveer Singh's user avatar
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 ...
Ranveer Singh's user avatar
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 ...
Koen's user avatar
  • 51
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, ...
David Handelman's user avatar
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 ...
user91322's user avatar
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 ...
ABIM's user avatar
  • 5,019
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 ...
user3072048's user avatar
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. ...
Val K's user avatar
  • 355
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=...
Reza's user avatar
  • 31
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?
Xueyi Huang's user avatar
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 ...
Daniel Maia's user avatar
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 ...
asdf's user avatar
  • 125
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 $...
robert's user avatar
  • 23
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 ...
Val K's user avatar
  • 355
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 ...
user avatar
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 ...
Christian Chapman's user avatar
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.
Turbo's user avatar
  • 13.7k
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 $...
f.m's user avatar
  • 11
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$ (...
L S B. user255259's user avatar
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 ...
David Roberson's user avatar
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 ...
Rupert's user avatar
  • 2,005
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$ ...
EJI's user avatar
  • 93
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 ...
MarcosDNMaia's user avatar
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 ...
user3275957's user avatar
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 ...
Jake's user avatar
  • 124
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 ...
Supriyo's user avatar
  • 343
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} \|...
ARG's user avatar
  • 4,342
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 ...
InterlacingStudent's user avatar
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 ...
InterlacingStudent's user avatar
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 ...
InterlacingStudent's user avatar
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 ...
Student's user avatar
  • 555
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}(...
user6818's user avatar
  • 1,883

1
4
5
6 7 8