<p>The <a href="http://mathworld.wolfram.com/Hoffman-SingletonTheorem.html">Hoffman–Singleton theorem</a>.</p>

CC BY-SA 2.5
2011-02-23T23:57:30.287Z
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.
mhum
CC BY-SA 2.5
2011-02-23T16:01:38.320Z
2011-02-23T18:15:21.870Z
2011-02-23T18:15:21.870Z
Colin McQuillan
<p>I think that the <a href="http://en.wikipedia.org/wiki/Friendship_theorem#Friendship_theorem">friendship theorem</a> (see also <a href="http://www.jstor.org/stable/2695332">Huneke's paper</a>) 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.</p>

<p>(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.)</p>

CC BY-SA 2.5
2011-02-24T23:39:41.083Z
2011-02-24T23:39:41.083Z
Timothy Chow
<p>How about this result on quantum computing.</p>

<p><a href="http://www.computer.org/portal/web/csdl/abs/proceedings/focs/2004/2228/00/22280032abs.htm">Mario Szegedy. Quantum Speed-Up of Markov Chain Based Algorithms. In FOCS'04.</a></p>

<p>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.</p>

CC BY-SA 2.5
2011-02-25T00:26:06.710Z
2011-02-25T01:55:22.057Z
2011-02-25T01:55:22.057Z
Marcos Villagra
<p>Let $L_G$ be the <a href="http://en.wikipedia.org/wiki/Laplacian_matrix">Laplacian matrix</a> 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, <a href="http://arxiv.org/PS_cache/arxiv/pdf/0808/0808.0163v3.pdf">Batson et al.</a> show how to construct these sparisifiers using $O(n/\epsilon^2)$ edges.  </p>

<p>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.</p>

CC BY-SA 3.0
2011-05-05T19:16:02.177Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-05-05T20:10:28.470Z
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.
Aaron Roth
CC BY-SA 3.0
2011-05-05T22:10:04.950Z
Sure - but one can imagine getting these sparsifiers another way.  But, yes, this might not be the best example...
Lev Reyzin
CC BY-SA 3.0
2011-05-05T18:24:08.753Z
2011-05-06T01:36:17.953Z
2011-05-06T01:36:17.953Z
Lev Reyzin
<p>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.</p>

<p>However, I'm curious about a statement that popped up in several sources (for instance <a href="http://www.sgt.pep.ufrj.br/index.php">over there</a>), 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. </p>

<p>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?</p>

CC BY-SA 2.5
2011-02-23T16:18:41.893Z
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.
Dave Clarke
CC BY-SA 2.5
2011-02-23T17:15:32.163Z
@Dave I did a rollback
Suresh Venkat
CC BY-SA 2.5
2011-02-24T23:57:00.933Z
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.
Timothy Chow
CC BY-SA 2.5
2011-02-25T06:49:58.300Z
@Timothy Chow: Thanks, I'll try to get my hands on it.
Anthony Labarre
CC BY-SA 2.5
2011-02-25T07:45:16.523Z
@TimothyChow: You should make this an answer, I think.
Suresh Venkat
CC BY-SA 2.5
2011-02-25T16:28:56.243Z
@Suresh: I thought about it, but as it stands it's not really an answer to the question as stated---at least, not until I do the work of digging further explicit examples out of the chapter myself, which I'm too lazy to do.  :-)  It's just a suggestion to Anthony.
Timothy Chow
CC BY-SA 3.0
2011-05-06T13:48:24.353Z
I remember having heard that the Graham-Pollak theorem (stating that $K_n$ cannot be decomposed into $n-2$ edge-disjoint complete bipartite graphs) is such a result. However a quick research in google leads to this preprint (http://arxiv.org/abs/1007.1553), which seems to give a combinatorial proof of this result.
Florent Foucaud
<graph-theory><co.combinatorics><proofs><spectral-graph-theory>
Proofs obtained only through spectral graph theory
Anthony Labarre
# Proofs obtained only through spectral graph theory

(Asked by: username_0 on 2011-02-23)

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](http://www.sgt.pep.ufrj.br/index.php)), 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?

**Tags:** graph-theory, co.combinatorics, proofs, spectral-graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: @Dave I did a rollback  
> **username_3**: 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.  
> **username_0**: @username_3: Thanks, I'll try to get my hands on it.  
> **username_2**: @TimothyChow: You should make this an answer, I think.  
> **username_3**: @Suresh: I thought about it, but as it stands it's not really an answer to the question as stated---at least, not until I do the work of digging further explicit examples out of the chapter myself, which I'm too lazy to do.  :-)  It's just a suggestion to Anthony.  
> **username_4**: I remember having heard that the Graham-Pollak theorem (stating that $K_n$ cannot be decomposed into $n-2$ edge-disjoint complete bipartite graphs) is such a result. However a quick research in google leads to this preprint (http://arxiv.org/abs/1007.1553), which seems to give a combinatorial proof of this result.  

---

## 4 answers

### Answer by username_5 on 2011-02-23. Score: 14

The [Hoffman–Singleton theorem](http://mathworld.wolfram.com/Hoffman-SingletonTheorem.html).

> **Comments:**
> **username_6**: 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.  

---

### Answer by username_3 on 2011-02-24. Score: 9

I think that the [friendship theorem](http://en.wikipedia.org/wiki/Friendship_theorem#Friendship_theorem) (see also [Huneke's paper](http://www.jstor.org/stable/2695332)) 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.)


---

### Answer by username_7 on 2011-02-25. Score: 9

How about this result on quantum computing.

[Mario Szegedy. Quantum Speed-Up of Markov Chain Based Algorithms. In FOCS'04.](http://www.computer.org/portal/web/csdl/abs/proceedings/focs/2004/2228/00/22280032abs.htm)

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.


---

### Answer by username_8 on 2011-05-05. Score: 8

Let $L\_G$ be the [Laplacian matrix](http://en.wikipedia.org/wiki/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.](http://arxiv.org/PS_cache/arxiv/pdf/0808/0808.0163v3.pdf) 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.

> **Comments:**
> **username_2**: 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.  
> **username_9**: 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.  
> **username_8**: Sure - but one can imagine getting these sparsifiers another way.  But, yes, this might not be the best example...  

---

