# Tag Info

## Hot answers tagged spectral-graph-theory

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 ...
• 172k
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-...
• 7,487
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 ...
• 114k

### 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 ...
• 2,921

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

### 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:/...
• 6,757

### 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 ...
• 7,487
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 ...
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 ...
• 50.5k

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

### 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 ...
• 241

### 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 ...
• 76.9k

### 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 ...
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 ...
• 21.5k

### 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 ...
• 111

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 ...
• 172k
Accepted

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

Yes, the graph with adjacency matrix ...
• 9,272

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

### 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. ...
• 4,342
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: ...
• 9,272

### 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'...
• 11.7k