The tag has no wiki summary.

learn more… | top users | synonyms

32
votes
5answers
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
8answers
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
2answers
806 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
1answer
601 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
3answers
294 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
1answer
267 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
0answers
244 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
221 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
4answers
259 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
1answer
315 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
3answers
388 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
1answer
362 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 ...
8
votes
1answer
110 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
1answer
198 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
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 ...
7
votes
3answers
359 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
2answers
288 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
3answers
563 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
1answer
309 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
1answer
208 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
1answer
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
3answers
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
3answers
575 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
2answers
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 - ...
6
votes
0answers
156 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
1answer
238 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
3answers
424 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
2answers
265 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
2answers
252 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
1answer
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
1answer
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
2answers
333 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
1answer
167 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
2answers
165 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
0answers
160 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
1answer
175 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
1answer
551 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
3answers
629 views

Spectral radius of a proper subgraph

I came across a Chinese reference in the paper "On the spectral radius of trees with fixed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...
4
votes
2answers
340 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 ...
4
votes
3answers
263 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
1answer
216 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
2answers
114 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}$ ...
4
votes
0answers
110 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
1answer
259 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
0answers
130 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
1answer
264 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
2answers
737 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
2answers
447 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
1answer
183 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
1answer
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 ...