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 ...
Carlo Beenakker's user avatar
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-...
Mirco A. Mannucci's user avatar
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 ...
Qiaochu Yuan's user avatar
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 ...
D.S. Lipham's user avatar
  • 2,921
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....
Brendan McKay's user avatar
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:/...
Claus's user avatar
  • 6,757
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 ...
Mirco A. Mannucci's user avatar
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 ...
Brendan McKay's user avatar
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 ...
Denis Serre's user avatar
  • 50.5k
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 ...
gwynneth-m.sc.'s user avatar
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 ...
Kai's user avatar
  • 241
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 ...
Timothy Chow's user avatar
  • 76.9k
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 ...
David Childers's user avatar
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 ...
Sam Hopkins's user avatar
  • 21.5k
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 ...
user165663's user avatar
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}...
Suvrit's user avatar
  • 28.3k
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 ...
Carlo Beenakker's user avatar
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, ...
Igor Rivin's user avatar
  • 95.3k
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 ...
M. Winter's user avatar
  • 11.9k
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 =...
David Roberson's user avatar
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 ...
Claus's user avatar
  • 6,757
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.$
Igor Rivin's user avatar
  • 95.3k
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\...
Brendan McKay's user avatar
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 ...
Carlo Beenakker's user avatar
8 votes
Accepted

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

Yes, the graph with adjacency matrix ...
LeechLattice's user avatar
  • 9,272
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 ...
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. ...
ARG's user avatar
  • 4,342
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: ...
LeechLattice's user avatar
  • 9,272
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'...
Gordon Royle's user avatar
  • 11.7k
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 ...
Carlo Beenakker's user avatar

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