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

-3
votes
0answers
29 views

eigenvalues of cycle and its complement [on hold]

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2cos (2\pi/n) $, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=?$ Is it ...
0
votes
2answers
90 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
86 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 ...
1
vote
0answers
29 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
110 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
39 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
78 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
69 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
60 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
69 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
58 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
219 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
89 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
134 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
164 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
102 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
0answers
39 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
1answer
186 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
119 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
162 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
94 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
180 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
102 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
293 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
343 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
0answers
111 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
0answers
45 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
2answers
144 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
0answers
58 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
0answers
63 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
1answer
115 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
1answer
103 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
2answers
210 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
0answers
75 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
1answer
66 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
1answer
163 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
0answers
193 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
1answer
141 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
1answer
87 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
3answers
976 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
0answers
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
0answers
62 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
1answer
276 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
2answers
175 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
4answers
365 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
3answers
426 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
0answers
127 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
2answers
145 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
0answers
77 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
0answers
192 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 ...