Return to Question

added 38 characters in body

Source Link

edited Mar 8, 2015 at 20:32

1.9k
12
20

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/

Can someone explain what is the argument there which seems to conclude that for arbitrary $d-$regular graphs on $n$ vertices with their second highest adjacency eigenvalue $\lambda_2(A) \leq \alpha d$ it should follow that $d = O(log (n))$. How!? (Isn't some such a thing true only for Abelian Cayley graphs?)

The only part of that thrid bullet point is that I can understand is its last-but-two line - as to how it follows from the ``Expander Mixing Lemma" that for all $S \subset V$$S \subseteq V$ we have $\frac{E(S,S)}{\vert S \vert } \leq d(\alpha + \frac{\vert S \vert }{n})$. This just comes from setting the two sets equal to $S$ in the EML.

But how is the above the same as $\frac{E(S,\bar{S})}{\vert S \vert } \geq d((1-\alpha) - \frac{\vert S \vert }{n})$ ?
But $S$ has at least $\frac{E(S,\bar{S}) }{d}$ neighbours? Why? Isn't every edge in $E(S,\bar{S})$ corresponding to a neighbour of $S$ by definition?
From the above how does it follow that $\vert B(x,r+1)\vert \geq (1+\epsilon)\vert B(x,r)\vert$ where $\vert B(x,r) \vert \leq \frac{n}{2}$ and $\epsilon = \frac{1}{2} - \alpha$? (where $\vert B(x,r) \vert$ is the size of the set of elements who are at a distance of $r$ from $x$)
From the above it apparently follows that $\vert B(x,r)\vert >\frac{n}{2}$ for every $x$ and some $r \leq O(log (n))$?

And how is the last statement above the same as saying that the graph has diameter $O(log(n))$?

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/

Can someone explain what is the argument there which seems to conclude that for arbitrary $d-$regular graphs on $n$ vertices with their second highest adjacency eigenvalue $\lambda_2(A) \leq \alpha d$ it should follow that $d = O(log (n))$. How!? (Isn't some such a thing true only for Abelian Cayley graphs?)

The only part of that thrid bullet point is that I can understand is its last-but-two line - as to how it follows from the ``Expander Mixing Lemma" that for all $S \subset V$ we have $\frac{E(S,S)}{\vert S \vert } \leq d(\alpha + \frac{\vert S \vert }{n})$. This just comes from setting the two sets equal to $S$ in the EML.

But how is the above the same as $\frac{E(S,\bar{S})}{\vert S \vert } \geq d((1-\alpha) - \frac{\vert S \vert }{n})$ ?
But $S$ has at least $\frac{E(S,\bar{S}) }{d}$ neighbours? Why? Isn't every edge in $E(S,\bar{S})$ corresponding to a neighbour of $S$ by definition?
From the above how does it follow that $\vert B(x,r+1)\vert \geq (1+\epsilon)\vert B(x,r)\vert$ where $\vert B(x,r) \vert \leq \frac{n}{2}$? (where $\vert B(x,r) \vert$ is the size of the set of elements who are at a distance of $r$ from $x$)
From the above it apparently follows that $\vert B(x,r)\vert >\frac{n}{2}$ for every $x$ and some $r \leq O(log (n))$?

And how is the last statement above the same as saying that the graph has diameter $O(log(n))$?

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/

Can someone explain what is the argument there which seems to conclude that for arbitrary $d-$regular graphs on $n$ vertices with their second highest adjacency eigenvalue $\lambda_2(A) \leq \alpha d$ it should follow that $d = O(log (n))$. How!? (Isn't some such a thing true only for Abelian Cayley graphs?)

The only part of that thrid bullet point is that I can understand is its last-but-two line - as to how it follows from the ``Expander Mixing Lemma" that for all $S \subseteq V$ we have $\frac{E(S,S)}{\vert S \vert } \leq d(\alpha + \frac{\vert S \vert }{n})$. This just comes from setting the two sets equal to $S$ in the EML.

But how is the above the same as $\frac{E(S,\bar{S})}{\vert S \vert } \geq d((1-\alpha) - \frac{\vert S \vert }{n})$ ?
But $S$ has at least $\frac{E(S,\bar{S}) }{d}$ neighbours? Why? Isn't every edge in $E(S,\bar{S})$ corresponding to a neighbour of $S$ by definition?
From the above how does it follow that $\vert B(x,r+1)\vert \geq (1+\epsilon)\vert B(x,r)\vert$ where $\vert B(x,r) \vert \leq \frac{n}{2}$ and $\epsilon = \frac{1}{2} - \alpha$? (where $\vert B(x,r) \vert$ is the size of the set of elements who are at a distance of $r$ from $x$)
From the above it apparently follows that $\vert B(x,r)\vert >\frac{n}{2}$ for every $x$ and some $r \leq O(log (n))$?

And how is the last statement above the same as saying that the graph has diameter $O(log(n))$?

Source Link

asked Mar 8, 2015 at 20:22

user6818

1.9k
12
20

A particular argument in the review on expanders by Hoory-Linial-Wigderson

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/

Can someone explain what is the argument there which seems to conclude that for arbitrary $d-$regular graphs on $n$ vertices with their second highest adjacency eigenvalue $\lambda_2(A) \leq \alpha d$ it should follow that $d = O(log (n))$. How!? (Isn't some such a thing true only for Abelian Cayley graphs?)

But how is the above the same as $\frac{E(S,\bar{S})}{\vert S \vert } \geq d((1-\alpha) - \frac{\vert S \vert }{n})$ ?
But $S$ has at least $\frac{E(S,\bar{S}) }{d}$ neighbours? Why? Isn't every edge in $E(S,\bar{S})$ corresponding to a neighbour of $S$ by definition?
From the above how does it follow that $\vert B(x,r+1)\vert \geq (1+\epsilon)\vert B(x,r)\vert$ where $\vert B(x,r) \vert \leq \frac{n}{2}$? (where $\vert B(x,r) \vert$ is the size of the set of elements who are at a distance of $r$ from $x$)
From the above it apparently follows that $\vert B(x,r)\vert >\frac{n}{2}$ for every $x$ and some $r \leq O(log (n))$?

And how is the last statement above the same as saying that the graph has diameter $O(log(n))$?