**0**

votes

**0**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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 ...