55
votes

Accepted

### What are good mathematical models for spider webs?

In response to the second question (which I interpret as asking for math models of spider webs as they appear in Nature): There exist several distinct types of spider webs. The most common type, the ...

41
votes

Accepted

### Intuitively, what does a graph Laplacian represent?

How to understand the Graph Laplacian (3-steps recipe for the impatients)
read the answer here by Muni Pydi. This is essentially a concentrate of a comprehensive article, which is very nice and well-...

27
votes

Accepted

### Factorization of the characteristic polynomial of the adjacency matrix of a graph

Expanding on Richard's comment: let me rename your graph to $S$ and consider the adjacency matrix $A$ abstractly as a linear operator acting on the free vector space $\mathbb{C}[S]$ on (the vertices ...

20
votes

### What are good mathematical models for spider webs?

In topology there is the notion of an infinite spider's web in the (complex) plane $\mathbb C$ that was introduced in 2010 https://arxiv.org/pdf/1009.5081.pdf.
A set $E\subseteq \mathbb C$ is an ...

18
votes

### Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

Johnson graphs do not cause difficulty to existing programs. Actually they are rather easy; nauty can handle them up to tens of millions of vertices, and so can other programs such as Traces and Bliss....

17
votes

### Intuitively, what does a graph Laplacian represent?

This is just a long comment, adding to the excellent answers above.
There is a great article from László Lovász "Discrete and Continuous:
Two sides of the same?", written around 2000 (https:/...

17
votes

### What are good mathematical models for spider webs?

So, I promised I would come up with some answer, but looks like there is already a great deal in the great answers above.
Anyway, I find it impossible to resist the temptation, especially because I ...

16
votes

Accepted

### What happens to eigenvalues when edges are removed?

The smallest eigenvalue can go up or down when an edge is removed.
For "down": $G=K_n$ for $n\ge 3$.
For "up": Take $K_n$ for $n\ge 1$ and append a new vertex attached to a single vertex of the ...

15
votes

Accepted

### Eigenvalues of the complement of a graph

Edit (bis). There are two answers, depending on whether loops about vertices are allowed or not. In addition, the case of regular graphs is completely described.
If loops are allowed
The relation ...

14
votes

### Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?

Perhaps I can contribute to the history part the question, since I was quite close to the Institut Fourier at that time and was very interested in their work (I am a physicist). Grenoble now has ...

14
votes

### Intuitively, what does a graph Laplacian represent?

This is not really about the connection with graph theory, a topic I am rather ignorant of, but rather the connection to continuum notions, all of which I learned from this paper.
Consider a ...

12
votes

### Algebraic properties of graph of chess pieces

The clique complex of the complement of the rook's graph is sometimes called a chessboard complex. It has some remarkable algebraic properties. For example, its Laplacian eigenvalues are all ...

12
votes

### Intuitively, what does a graph Laplacian represent?

I wrote a blog post a while ago* on different ways of interpreting the graph laplacian from the perspectives of functional analysis, probability, statistics, differential equations, and topology, and ...

12
votes

Accepted

### Is there Matrix-Tree theorem for counting the bases of a connected matroid?

A broader class of matroids for which you have a Matrix Tree theorem are the regular matroids (those representable over every field): see, e.g., https://arxiv.org/abs/1404.3876.
EDIT: Let me actually ...

11
votes

### What are good mathematical models for spider webs?

A biologist friend told me about this question on MathOverflow, so I wanted to contribute a useful link to a related article that appeared in NATURE.
Published: 01 February 2012
Nonlinear material ...

10
votes

### Sum of the absolute eigenvalues of A>=B

The claim is false.
In particular, we have $A=kee^T-kI$, so that $\lambda(A)=((n-1)k,-k,\ldots,-k)$, so that $\|A\|_* = 2(n-1)k$.
Now generate a random matrix $B$ such that $B_{ii}=0$, $B_{ij}=B_{ji}...

10
votes

### regular graphs with the smallest eigenvalue -2?

Connected regular graphs with smallest eigenvalue at least $−2$ are either a line graph, a cocktail party graph, or the number of vertices is at most 28.
P. J. Cameron, J. M. Goethals, J. J. Seidel ...

10
votes

Accepted

### When does a row standardized adjacency matrix have a real spectrum?

If the adjacency matrix is $A,$ the "row-standardized" matrix is $DA$, where $D$ is a diagonal matrix all of whose diagonal entries are positive, so has a positive diagonal square root $D^{1/2}$. Now, ...

10
votes

### Factorization of the characteristic polynomial of the adjacency matrix of a graph

In a comment I said that large eigenspaces of the adjacency matrix may point to large symmetry or regularity in the graph.
For example, let me explain why highly symmetric graphs have large ...

9
votes

### Spectrum of orthogonality graph (2)

If $G$ is a Cayley graph for $\mathbb{Z}_2^n$ with connection set $C \subseteq \mathbb{Z}_2^n \setminus \{0\}$, then for each element $a \in \mathbb{Z}_2^n$ there is an eigenvector $v$ given by
$$v_x =...

9
votes

Accepted

### Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant

Kaluza and Tancer have actually proved $\mu(G)\leq\sigma(G)$ in 2019: See their proof in the preprint "Even maps, the Colin de Verdière number, and representations of
graphs" on arxiv. Here ...

8
votes

Accepted

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

Yes, see this paper by Ram Murty. The basic point is that the sum of squares of the eigenvalues is the trace of the square of the adjacency matrix, which is equal to $d n.$

8
votes

### Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

If you take an infinite regular tree of degree $d$ and fix one vertex $v$, then the number of closed walks of length $2k$ (there are none of odd length) starting at $v$ grows like $4^k(d-1)^k$ as $k\...

8
votes

Accepted

### graph signal processing

"I am looking for some simple concrete examples of the ways in which
real problems go through graph signal processing and how graph Fourier
transforms are obtained."
• A concrete example of a ...

8
votes

Accepted

### Are there graphs with irrational eigenvalues which are all $>1$?

Yes, the graph with adjacency matrix
...

8
votes

### Suggestion for framing a course in Representation theory + Spectral graph theory

Update
I have since uploaded a preprint discussing this connection. This is probably not it‘s final form, but since I claimed writing on this some years ago, it is more than time to finally mention it ...

Community wiki

8
votes

### Intuitively, what does a graph Laplacian represent?

Here is another interpretation of the Laplacian (for this answer I use the notation of this answer to a similar post, in particular $\nabla$ is the [graph] gradient and $\nabla^*$ is its adjoint (i.e. ...

8
votes

Accepted

### Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?

Here's a table containing the Colin de Verdière numbers:
...

8
votes

### Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?

This is a limited partial answer to the question ruling out the case where the graph is regular and has four distinct eigenvalues, so the spectrum is $\{k, (\sqrt{2})^a, (-\sqrt{2})^a, -k\}$.
van Dam'...

7
votes

Accepted

### exact definition of Fiedler vector

The concept of a Fiedler vector is defined for graphs that consist of one single connected component. Since the number of zero eigenvalues counts the number of connected components, the second largest ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

spectral-graph-theory × 384graph-theory × 258

co.combinatorics × 87

linear-algebra × 79

eigenvalues × 54

sp.spectral-theory × 46

matrices × 34

reference-request × 27

expander-graphs × 20

random-graphs × 19

laplacian × 19

fa.functional-analysis × 16

pr.probability × 15

eigenvector × 14

algebraic-graph-theory × 14

gr.group-theory × 10

nt.number-theory × 8

rt.representation-theory × 8

random-matrices × 8

markov-chains × 8

extremal-graph-theory × 8

adjacency-matrices × 8

polynomials × 7

random-walks × 7

trees × 7