**1**

vote

**0**answers

152 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

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

**0**

votes

**0**answers

38 views

### Is there any analytically expressible choice of disjoint perfect matchings?

Consider being given a $d-$regular $(n,n)$-bipartite graph. We know that its edge set decomposes into $d$ disjoint perfect matchings. I want to know if there is a analytic way to pick such a ...

**1**

vote

**1**answer

173 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

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

**0**

votes

**0**answers

110 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

88 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

161 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

91 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

264 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

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

**2**

votes

**0**answers

103 views

### About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...

**0**

votes

**0**answers

41 views

### Weighted eigenvector-entry sums of bipartite graphs

Let $\lambda_m$ denote the $m$-th eigenvalue of the adjacency matrix $A$ of a bipartite graph $G$ of order $N$ and ${\bf v}_m$ the normalized eigenvector corresponding to $\lambda_m$. I am looking for ...

**3**

votes

**2**answers

121 views

### Matching polynomials and Ramanujan graphs

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...

**0**

votes

**0**answers

54 views

### Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges.
In particular ...

**0**

votes

**0**answers

51 views

### About adjacency matrices of $k-$shift lifts of graphs

I am finding the notation of cyclic lifts of graphs to be very confusing.
Lets say one is looking at a cyclic $k-$lift of a $\vert V \vert$ sized graph.
I would like to understand what is the ...

**0**

votes

**1**answer

102 views

### Graph lifts and representation theory

Is there any connection known between the two?
One can naturally define lifts of graphs by groups like $\mathbb{Z}_k$ and hence I wonder if representation theoretic properties can be used to say ...

**0**

votes

**1**answer

94 views

### When is a $2$-lift of a graph connected? [closed]

Let $\ (V\ E)\ $ be a graph, i.e. $\ E\subseteq\binom V2.\ $ A $2$-lift pattern of a graph is a function $\ e:E\rightarrow\{-1\,\ 1\}.\ $ The induced 2-lift is defined as the graph $\ V\times\{-1\,\ ...

**3**

votes

**2**answers

187 views

### Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph without diagonalizing it. The graphs I am interested in are not regular (but ...

**0**

votes

**0**answers

68 views

### Signed Laplacians and Ramanujan graphs

Given a signing/2-lift matrix $A_s$ of a $d-$regular graph one has the relationship that the ``Signed Laplacian" is $L = d + A_s$. This $L$ is still the same size as the base graph. But the lifted ...

**1**

vote

**1**answer

62 views

### Laplacian spectrum of $2-$lifts of graphs

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on ...

**5**

votes

**1**answer

145 views

### How many cospectral graphs available for a given number of nodes?

Two graphs are said to be cospectral if they have same eigenvalues wrt adjacency matrix, Normalised or Signless laplacian matrix. How many graphs has cospectral mates for a given number of nodes? We ...

**3**

votes

**0**answers

160 views

### The Bilu-Linial conjecture and Ramanujan graphs

The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...

**1**

vote

**1**answer

137 views

### Are there good ways of relating a minor to the full determinant?

Say $A$ is a $(n-1)\times (n-1)$ matrix and we augment it by a $n^{th}$ row and a column and get a $n \times n$ matrix $B$. Is there a nice way to relate $det(B)$ and $det(A)$ and the added row and ...

**1**

vote

**1**answer

77 views

### Spectral radius of a time-varying matrix with strictly positive increment of the matrix's entry

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ being the largest eigenvalue of $A(t)$ and $t$ denotes the time. If $A(t)$ changes over time with each time a ...

**11**

votes

**2**answers

752 views

### What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...

**0**

votes

**0**answers

20 views

### Looking to derive bound for modulus of harmonic eigenfunction on weighted graph

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus:
$\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$
and wish to lower ...

**1**

vote

**0**answers

60 views

### Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...

**6**

votes

**1**answer

260 views

### Do perfect matching(s) have signatures in the graph eigenvalues?

If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian?
It would be helpful to ...

**4**

votes

**2**answers

151 views

### Graphs whose degree vectors coincide for all powers of their adjacency matrices

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.
Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...

**9**

votes

**4**answers

327 views

### Are these three different notions of a graph Laplacian?

I seem to see three different things that are being called the Laplacian of a graph,
One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ ...

**7**

votes

**3**answers

410 views

### Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...

**4**

votes

**0**answers

122 views

### minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...

**2**

votes

**2**answers

126 views

### About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?)
I saw these two related discussions,
Roots of matching ...

**2**

votes

**0**answers

72 views

### Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...

**0**

votes

**0**answers

189 views

### A question about Assaf Naor's review in Bourbaki about the Batson-Spielman-Srivastava result

I am referring to this article - http://www.cims.nyu.edu/~naor/homepage%20files/Exp.1033.pdf
If I understand right, the author states that his equations (8) and (9) are equivalent to the equations ...

**3**

votes

**1**answer

191 views

### Meaning of eigenvalue 1 and symmetry in Laplacian spectra of graphs

We often see normalized Laplacian spectra of graphs where density on eigenvalue 1 serves as an axis of symmetry, with particularly high (blue spectra in the figure) or low densities (red spectrum) ...

**0**

votes

**2**answers

115 views

### Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle:
$(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?

**4**

votes

**2**answers

158 views

### eigenvalue estimate of the adjacency matrix

The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem:
$$
...

**5**

votes

**0**answers

168 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**8**

votes

**1**answer

124 views

### Can the graph Laplacian be well approximated by a Laplace-Beltrami operator?

It seems rather well known that given a Laplace-Beltrami operator $\mathcal{L}_{M}$ on a manifold $M$ we can approximate its spectrum by that of a graph Laplacian $L_{G}$ for some $G$ (where $G$ is ...

**4**

votes

**2**answers

166 views

### Largest eigenvalue adjacency matrix-link deletion

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is ...

**8**

votes

**1**answer

228 views

### A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have ...

**5**

votes

**1**answer

182 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**3**

votes

**1**answer

154 views

### Cheeger inequality for the maximal eigenvalue

Let $G = (V,E)$ be an undirected graph and let $L = I - D^{-1/2} A D^{-1/2}$ be its normalized Laplacian matrix. The Cheeger inequality asserts that:
$$\frac{\Phi_G^2}{2} \leq \lambda_2 \leq 2 ...

**2**

votes

**1**answer

101 views

### limiting empirical spectral distribution of the Laplacian matrix on an Erdos-Renyi graph?

Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where ...

**5**

votes

**2**answers

387 views

### Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...

**0**

votes

**0**answers

25 views

### Diffusion maps for non-Markov

Diffusion maps based on the work of Coifman and Lafon use concepts from Markov chains and heat diffusions. Have there been work to extend diffusion maps to non-Markovian or fractional heat ...

**8**

votes

**1**answer

207 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**2**

votes

**1**answer

93 views

### Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices.
Suppose ...