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

learn more… | top users | synonyms

0
votes
0answers
7 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 ...
6
votes
4answers
460 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
1answer
93 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 ...
1
vote
1answer
89 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
1answer
180 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
2answers
93 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
1answer
97 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 ...
3
votes
3answers
149 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
1answer
95 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
1answer
218 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 ...
0
votes
0answers
111 views

Ramanujan graphs and stable real polynomials

I have a problem with the lemma 6.5 and the theorems 5.1, 6.6 in the paper of Adam Marcus, Daniel Spielman and Nikhil Srivastava. http://arxiv.org/pdf/1304.4132.pdf I do not understand how they use ...
2
votes
1answer
78 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
1answer
76 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 ...
11
votes
1answer
686 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
1answer
74 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 ...
3
votes
2answers
132 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
2answers
91 views

laplacian spectrum and size of a graph

do Laplacian spectrum of a graph gives us information on the size of a graph? for example, is it possible that I have two disconnected graph G and H with the following feature: 1) G and H have the ...
5
votes
1answer
152 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
1answer
193 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
1answer
80 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
1answer
190 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$ ...
0
votes
0answers
46 views

Is the laplacian spectral radius of a directed grpah a non-decreasing function?

Given a directed graph G and its respective laplacian matrix $L = D-A$ where $A$ is the adjacency matrix ($A_{ij}=1$ if there is a link from $j$ to $i$ and $A_{ij}=0$ otherwise) and D is the diagonal ...
1
vote
1answer
123 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 ...
1
vote
1answer
231 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
0answers
283 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 ...
1
vote
2answers
108 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
0answers
80 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
2answers
132 views

Estimating the shift in the $\lambda_{max}$ of a matrix under a diagonal perturbation

Given a matrix $A$ and a diagonal matrix $D$, what ways do we have to estimate, $\lambda_{max}(A+D) - \lambda_{max}(A)$? (Feel free to make other assumptions about the matrices that they are all ...
4
votes
0answers
104 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
0answers
35 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 ...
2
votes
1answer
168 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
0answers
63 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 ...
1
vote
0answers
163 views

3-regular (cubic) graph with adjacency eigenvalue 1

Suppose $A\in\{0,1\}^{n\times n}$ is the adjacency matrix of a 3-regular (cubic) graph $G=(V,E)$; that is, all $n$ vertices $v\in V$ in the graph have three neighbors. Is there a nice necessary ...
4
votes
2answers
91 views

Integral roots of circulant matrix

When does the circulant matrix have only integral roots? For example: all roots of the adjacency matrix of the complete graph $K_n$ are integer, which its adjacency matrix is circulant, but in case ...
0
votes
2answers
177 views

Connectivity of weighted graph and zero Laplacian eigenvalues

Given an undirected graph $G$, and let $V$ denote its set of vertices and $E$ its set of edges. Suppose that there are no edges connecting the same vertex, and no more than one edge connecting any ...
6
votes
1answer
127 views

Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...
1
vote
0answers
69 views

Interpreting (Fiedler) spectral bisectioning

I would appreciate help on how to interpret the results of spectral bisectioning of a graph. Given a $G=(V,E)$ with size $N$ represented by $Q$ its Laplacian matrix where the eigenvalues are ordered ...
4
votes
3answers
289 views

How networks with high largest eigenvalues are more robust?

In the literature, it is sometimes indicated that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust against link/node removals. ...
0
votes
0answers
108 views

When does the normalized graph Laplacian have eigenvalue 1?

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...
2
votes
1answer
164 views

Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$. But do we have any quantitative ...
1
vote
0answers
178 views

Is there a way to simplify this apparently huge characteristic polynomial calculation?

Say I am given the $0/1$ adjacency matrix of an undirected graph. Also I am given a representation $\rho$ of some group $G$ and an orientation has been arbitrarily chosen along each edge. Let ...
2
votes
2answers
131 views

How does one calculate/estimate/guarantee the girth of a non-Abelian Cayley graph?

This question is in reference to this other question, Can someone point out references (or explain!) which give techniques of being able to prove for any Cayley graph this property of having a girth ...
1
vote
1answer
189 views

About expectation norms on graphs

Let $S \subseteq V$ of a $d-$regular graph $G$ such that $\mu = \frac{\vert S \vert }{\vert V \vert } $. Let $A$ be the adjacency matrix of the graph. Then define the quantity $\phi(S)= ...
-2
votes
1answer
146 views

About structure of the set of perfect matchings of $K_{n,n}$

Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
2
votes
1answer
242 views

About distinct eigenvalues of a graph

if a graph with adjacency matrix $A$ and Laplacian $L$ has $k$ distinct eigenvalues then does this fact naturally help define or prove existence of a polynomial $p$ of degree $k-1$ such that ...
1
vote
1answer
102 views

About the upper bound on the roots of the matching polynomial

Heilman and Lieb had proven that if a graph had $d$ as its maximum vertex degree then the roots of the matching polynomial are bounded from above by $2\sqrt{d-1}$. Is there a modern exposition of ...
3
votes
1answer
189 views

About the second largest adjacency eigenvalue of Abelian Cayley graphs

[Assume all groups are finite] One knows the general statement that the sum of the values of the character function on the generating set is an eigenvalue of a Cayley graph. But the above doesn't ...
0
votes
1answer
113 views

A particular argument in the review on expanders by Hoory-Linial-Wigderson

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Can someone explain what is the argument there which seems to conclude ...
7
votes
2answers
326 views

Constructing Ramanujan graphs from elliptic curves

Is there an exposition which explains how to do this step-by-step? (I see stray references and allusions to such a thing being possible but can't locate anything concretely) Something to do with ...
5
votes
1answer
412 views

When are (Abelian) Cayley graphs also expanders?

I want to ask the question in two parts, (1) Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes ...