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

5
votes
1answer
278 views

Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas. In the following all graphs are simple and connected. Let $G$ be graph with vertex set ...
5
votes
1answer
287 views

How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
2
votes
1answer
125 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 ...
-1
votes
1answer
242 views

Upper bound on iterations count for power iteration algorithm

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...
10
votes
0answers
259 views

Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
10
votes
0answers
289 views

Ramanujan Digraphs?

In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...
8
votes
0answers
1k views

a new lower bound for the chromatic number of a graph?

Let S+(G) denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph G. Let S-(G) denote the sum of the squares of the negative eigenvalues and q the chromatic ...
6
votes
0answers
161 views

When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by $$ \DeclareMathOperator{\Vol}{Vol} h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}. $$ Here, $\Vol S$ is the sum of ...
5
votes
0answers
163 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 ...
4
votes
0answers
116 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' ...
4
votes
0answers
133 views

Relaxation = absorption?

Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
3
votes
0answers
133 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 ...
3
votes
0answers
145 views

Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ? For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
3
votes
0answers
246 views

A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that $$ ||z_1||=\ldots = ...
3
votes
0answers
114 views

inverse M-matrix times mixed-sign vector

Recently a colleague and I came across this unusual phenomenon. Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable ...
2
votes
0answers
66 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 ...
2
votes
0answers
141 views

If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...
2
votes
0answers
229 views

On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard. Assume we talk only about classes of undirected ...
2
votes
0answers
73 views

Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$). Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$. ...
1
vote
0answers
58 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, ...
1
vote
0answers
73 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
1
vote
0answers
129 views

Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
1
vote
0answers
112 views

Lower bound for the difference between the maximum eigenvalue of a graph with the one of the one-edge-deleted subgraph

I have proposed very recently a question in the following link concerning the title of the current question: Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph ...
1
vote
0answers
90 views

expansion with respect to p-norms for p other than 2

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$. Let $x \in ...
0
votes
0answers
37 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 ...
0
votes
0answers
37 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
39 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
0answers
62 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 ...
0
votes
0answers
17 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 ...
0
votes
0answers
179 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 ...
0
votes
0answers
23 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 ...
0
votes
0answers
96 views

Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
0
votes
0answers
129 views

A graph eigenvalue problem

This is motivated by a graph problem considered by me. For a directed graph $G$ on nodes ${1,\cdots,N}$, denote its graph Laplacian by $L$($l_{ij}=-1$ iff there is an directed edge $j\rightarrow i$ ...