**33**

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

6k 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

848 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

**3**answers

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

**14**

votes

**1**answer

647 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

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

**12**

votes

**3**answers

321 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

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

**11**

votes

**1**answer

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

**11**

votes

**0**answers

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

**11**

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

**9**

votes

**3**answers

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

**9**

votes

**3**answers

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

**9**

votes

**1**answer

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

**9**

votes

**1**answer

356 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

496 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

732 views

### When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, ...

**8**

votes

**1**answer

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

**8**

votes

**1**answer

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

**8**

votes

**1**answer

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

**7**

votes

**3**answers

464 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

**3**answers

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

**7**

votes

**2**answers

437 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

**2**answers

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

**7**

votes

**2**answers

409 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$?

**7**

votes

**1**answer

433 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

**2**answers

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

**7**

votes

**1**answer

446 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

**1**answer

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

**6**

votes

**3**answers

644 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

**1**answer

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

**6**

votes

**4**answers

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**0**answers

211 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

**1**answer

369 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

486 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

510 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

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

**5**

votes

**1**answer

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

**5**

votes

**3**answers

310 views

### Operation on Isospectral graphs

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that are obtained by applying a binary operation to $G$ and $H$?
For example, to take one ...

**5**

votes

**1**answer

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

**5**

votes

**2**answers

271 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

299 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

240 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

190 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

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

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