The spectral-graph-theory tag has no wiki summary.

**31**

votes

**5**answers

2k views

### Is the Laplacian on a manifold the limit of graph Laplacians?

Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so ...

**15**

votes

**8**answers

4k views

### The first eigenvalue of a graph - what does it reflect?

A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the ...

**15**

votes

**2**answers

802 views

### Groups with a rational generating function for the word problem

This question comes more from curiosity than a specific research problem. Let G be a group and S a finite symmetric generating set. By the WP(G,S) I mean the set of all words in the free monoid on S ...

**14**

votes

**1**answer

597 views

### Convexity of spectral radius of Markov operators, Random walks on non-amenable groups

Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$.
Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication.
Question
Under which conditions can we show that ...

**12**

votes

**3**answers

290 views

### How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...

**11**

votes

**1**answer

266 views

### Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, ...

**10**

votes

**0**answers

241 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

**0**answers

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

**9**

votes

**1**answer

313 views

### Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a ...

**8**

votes

**3**answers

385 views

### Classes of graphs for which isospectrum implies isomorphism ?

The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same ...

**8**

votes

**1**answer

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

**8**

votes

**0**answers

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

**7**

votes

**3**answers

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

**7**

votes

**2**answers

279 views

### Small eigenvalues and spectral clustering

Let $L$ be the discrete Laplacian associated to an undirected graph. It is well-known that the spectral gap of $L$, i.e. the smallest nonzero eigenvalue, is a measure of how well connected the graph ...

**7**

votes

**1**answer

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

**7**

votes

**3**answers

558 views

### Eigenfunctions of random graphs

Consider a random $d$-regular graph on $n$ vertices. What can be said about its nontrivial (i.e. orthogonal to the constant) eigenfunctions? For example, I'm interested whether there are "nodal ...

**7**

votes

**1**answer

302 views

### normalized laplacian spectrum of trees

Is it known for which class of graphs the normalized laplacian has only simple eigenvalues (i.e., with multiplicity one)? In particular, are there trees (or perhaps a specific class of trees) whose ...

**7**

votes

**1**answer

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

**7**

votes

**1**answer

420 views

### Diophantine elements in SU(2)

Following notions from [1], call a set of elements $g_1, \dots, g_k \in G = SU(2)$ Diophantine if it satisfies the following property: there exists a constant $D$ such that for every word $W_m$ of ...

**6**

votes

**3**answers

1k views

### Random bipartite graphs

Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I ...

**6**

votes

**3**answers

566 views

### Generalization or Improvement of Cheeger inequality on Graphs

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $A$ denote the adjacency matrix of $G$ and $D$ denote the diagonal matrix such that $D_{i,i}$ equals to the degree $d_i$ ...

**6**

votes

**2**answers

684 views

### Spectrum of the Laplacian on G(n, p) and G(n, M)

A random graph in $G(n, p)$ model is a graph on $n$ vertices in which for each of the $n\choose{2}$ edges we independently flip a coin, then take the edge with probability $p$ or remove it with $1 - ...

**5**

votes

**1**answer

230 views

### Dimension of Specht Modules $S^\lambda$

In the study of representation theory of $S_n$, we know that the irreducible characters of $\chi_\lambda$ of $S_n$ are indexed by partitions $\lambda \vdash n$. There are several methods in ...

**5**

votes

**3**answers

421 views

### Bounds on maximal eigenvalue of a k-regular graph

Given a k-regular graph $G$ (every vertex is of degree k), one defines its Laplace operator as
$L(G)=D-A=kI-A$, where $I$ is identity matrix and $A$ adjacency matrix of $G$.
Let $\lambda_{1}\leq ...

**5**

votes

**2**answers

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

**5**

votes

**2**answers

251 views

### Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of ...

**5**

votes

**1**answer

269 views

### Second eigenvalue of suspension of a graph

Suppose I have some $d$-regular graph $G$. Let $\lambda = \max\{\lambda_2(G), |\lambda_n(G)|\}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of ...

**5**

votes

**1**answer

370 views

### Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

This question is motivated by a talk I went to earlier today.
Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.
Let $$\lambda_1\geq \lambda_2 \geq\dots \geq ...

**5**

votes

**2**answers

331 views

### cospectral graphs

The simple connected graph $G$ has $n$ vertices and we have:
1) $|E(G)|\geq \frac{n(n-1)}{3}$
2) we have the spectrum and degree sequence of $G$
3) $Spectrum(G)=Spectrum(H)$
Is $G \cong H$?

**5**

votes

**1**answer

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

**5**

votes

**2**answers

159 views

### Reflexive (hyperbolic) graphs

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$?
By "effective" I mean something ...

**5**

votes

**0**answers

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

**5**

votes

**0**answers

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

**4**

votes

**1**answer

525 views

### How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...

**4**

votes

**3**answers

620 views

### Spectral radius of a proper subgraph

I came across a Chinese reference in the paper "On the spectral radius of trees with ﬁxed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...

**4**

votes

**3**answers

261 views

### Operation on Isospectral graphs

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that obtain by binary operation between $G$ and $H$?
For example,in special case, is ...

**4**

votes

**1**answer

213 views

### What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...

**4**

votes

**0**answers

107 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

**1**answer

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

**4**

votes

**0**answers

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

**4**

votes

**1**answer

262 views

### Graphs which are “distance-regular” with respect to a vertex (but not distance-regular)

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all ...

**3**

votes

**2**answers

722 views

### Complex Eigenvalues of Directed Graphs

I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined ...

**3**

votes

**2**answers

424 views

### spectrum of an adjacency matrix

The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...

**3**

votes

**1**answer

182 views

### Estimation of DS graph growth

We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum.
Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ ...

**3**

votes

**1**answer

109 views

### The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...

**3**

votes

**2**answers

299 views

### signing a strongly regular graph

Let $A$ be the adjacency matrix of a strongly regular graph. When is it possible to sign $A$ (i.e. replace some of the +1 entries by -1) so that the resulting matrix has exactly two eigenvalues?
I ...

**3**

votes

**1**answer

248 views

### Eigenvectors of asymmetric graphs

Let $G$ be an asymmetric connected graph. Then is it always the case that at least one of the eigenvectors of its adjacency matrix $A$ consists entirely of distinct entries?
Thanks!

**3**

votes

**2**answers

199 views

### are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

Two graphs are isospectral if the combinatorial Laplacian on them has the same spectrum, equivalently, the adjacency matrix has the same the set of eigenvalues (including multiplicities). Two graphs ...

**3**

votes

**1**answer

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

**3**

votes

**2**answers

96 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:
$$
...