28
$\begingroup$

I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.

However, I'm curious about a statement that popped up in several sources (for instance over there), which says in essence that some results in graph theory have been proved using spectrum-based techniques only, and that so far, no proof that bypasses those techniques is known.

Unless I skipped that, I don't recall seeing such an example in the literature I've read so far. Do any of you know of examples of such results?

|cite|improve this question
$\endgroup$
  • $\begingroup$ The title of the question suggests that you are asking for proofs that are only obtainable using spectral graph theory, but you are asking for proofs that have up to now only been obtained by spectral graph theory. These are two totally different questions. So as it stands, the title is misleading, which is why I changed it. $\endgroup$ – Dave Clarke Feb 23 '11 at 16:18
  • $\begingroup$ @Dave I did a rollback $\endgroup$ – Suresh Venkat Feb 23 '11 at 17:15
  • 5
    $\begingroup$ Chapter 7 of Spectra of Graphs by Cvetković, Doob, and Sachs gives plenty of examples of theorems whose statements make no explicit mention of spectra but that are provable using spectral techniques. My guess is that many of these have no known non-spectral proof, though you'd have to verify this on a case-by-case basis. Certainly in many cases the simplest or most natural proof uses spectra. $\endgroup$ – Timothy Chow Feb 24 '11 at 23:57
  • $\begingroup$ @Timothy Chow: Thanks, I'll try to get my hands on it. $\endgroup$ – Anthony Labarre Feb 25 '11 at 6:49
  • $\begingroup$ @TimothyChow: You should make this an answer, I think. $\endgroup$ – Suresh Venkat Feb 25 '11 at 7:45
12
$\begingroup$

The Hoffman–Singleton theorem.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hoffman-Singleton was my first thought, too. But, I don't know if any non-spectral proofs exist and if they don't if it's because they're too difficult or because no one has tried. The standard proof is pretty neat and concise, so I don't know offhand what the motivation would be to get a non-spectral proof. $\endgroup$ – mhum Feb 23 '11 at 23:57
9
$\begingroup$

How about this result on quantum computing.

Mario Szegedy. Quantum Speed-Up of Markov Chain Based Algorithms. In FOCS'04.

He extends Markov chains to quantum Markov chains, and shows that the quantum hitting time is upper bounded by the square root of the classical hitting time. He does this by relating the singular vectors of the classical Markov chain to the singular vectors of the quantum Markov chain. Before this paper, there wasn't any known relation between random and quantum walks. I cannot imagine how to do the same using non-spectral techniques.

|cite|improve this answer
$\endgroup$
8
$\begingroup$

I think that the friendship theorem (see also Huneke's paper) is a good example even though strictly speaking there now exist proofs of the friendship theorem that avoid eigenvalues. The proofs that avoid eigenvalues entirely are a lot messier than the spectral proof.

(The friendship theorem states that if in a room of people, every pair of people has exactly one common friend, then there is someone who knows everyone else.)

|cite|improve this answer
$\endgroup$
8
$\begingroup$

Let $L_G$ be the Laplacian matrix of an undirected weighted graph $G = (V,E,w)$. A sparsifier of a graph $G$ is a graph $H$ such that for every $x \in R^V$ the following holds: $$ x^T L_H x (1-\epsilon) \le x^T L_G x \le x^T L_H x (1+\epsilon).$$ Using spectral methods, Batson et al. show how to construct these sparisifiers using $O(n/\epsilon^2)$ edges.

Even though the statement of the theorem is debatably not "inherently spectral," I do not think it is known how one can get this result or a result like it without using spectral techniques.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It's a little debatable as whether the statement is not inherently spectral. In a literal sense, you are right, but the only rationale I can think for why the quadratic form shows up is spectral. $\endgroup$ – Suresh Venkat May 5 '11 at 19:16
  • 1
    $\begingroup$ This is kind of a spectral statement. $F(A) = \{x^TAx: ||x||_2 = 1\}$ is exactly the convex hull of the eigenvalues of A if A is the Laplacian of an undirected graph. The condition is asking for another graph with approximately the same spectrum. But I think it is not even known how to get plain old cut sparsifiers with $O(n/\epsilon^2)$ edges in another way. $\endgroup$ – Aaron Roth May 5 '11 at 20:10
  • $\begingroup$ Sure - but one can imagine getting these sparsifiers another way. But, yes, this might not be the best example... $\endgroup$ – Lev Reyzin♦ May 5 '11 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.