Talk:Expander graph

Various remarks

The final paras here hang by a very tenuous thread from the rest.

Charles Matthews 18:29, 6 Sep 2004 (UTC)

Is the notation $/S$ for the complement of a vertex set standard? It makes my eyes sore to look at $E(S,/S)/|S|$ - Gauge 23:55, 5 Jan 2005 (UTC)

isn't it the second eigenvalue of the admittance matrix rather than adjacency matrix that matters ? --Vastinnocentaims 19:04, 10 August 2005 (UTC)

If M is the adjacency matrix, and A is the admittance/Laplacian matrix, then every eigenvalue λ of M corresponds to an eigenvalue (d-λ) of A, where d is the degree, so they are essentially equivalent concepts. There are also some bounds related to expanders that are expressed not in terms of the 2nd eigenvalue $\lambda _{2}$, but in terms of the 2nd largest eigenvalue magnitude, i.e, $\max\{\lambda _{2},|\lambda _{n}|\}$ ($\lambda _{1}$ is always d, and is always the largest) Blokhead 03:25, 12 October 2005 (UTC)

Spectral expansion section

Hi,

In the spectral expansion section, you mention that lamba = max_{1 <= i <= n}(lambda_1, ..., lambda_{n-1}) but we have lambda_{i+1} >= lambda_i. So is lambda = lambda_1 ? In that case, how is the spectral gap d - lambda_1 different from d - lambda?

Claude-Guy

Directed graph as bipartite

A directed graph can also be interpreted as a balanced bipartite graph (with all edges going from one copy of V to another copy).

I don't understand. 1 cannot be interpreted as 2, I must be missing something, seems like you're making a wholly different graph. MotherFunctor 18:39, 8 August 2006 (UTC)

SL=L

Isn't the Reingold paper from 2004 and not 2008 ? —Preceding unsigned comment added by 24.19.11.255 (talk) 23:01, 19 April 2010 (UTC)

Definition?

This article about expander graphs does not even give a definition of an expander graph.

It defines a lot of things, and gives a lot of properties, but does not define the object described in its title. Or I did not find this definition. --MathsPoetry (talk) 10:09, 19 March 2012 (UTC)

The definition is much too implicit. More or less all graphs are expander graphs; the question is how "expandery" are they. The numbers defined in the article all measure how much of an expander graph a particular graph is. Some results require a particular lower bound on these numbers for the "expander" properties to be useful, but some are more in the context of a family of graphs, and then all that is required is that there exists some lower bound on these numbers ("expander family"). JackSchmidt (talk) 12:01, 19 March 2012 (UTC)

Agreed.

Here is the definition I added to French page: (translating it into English, sorry if that's not correct English)

G is a graph expander by a $\gamma$ ratio when, for each vertices subset $W$ of cardinal $|W|\leq n/2$, $|\partial (W)|\geq \gamma |W|$ is verified. One might notice that $\gamma \leq h(G)$.

I also added examples. I don't give as many details as the English page (by far), but at least people might understand what it is all about. At least I hope so.

Best, --MathsPoetry (talk) 21:09, 19 March 2012 (UTC)

Almost 12 years later, there is still no definition here on the English page! Please, someone fix this. 107.159.247.194 (talk) 20:57, 6 February 2024 (UTC)

d = log | G |

I suppose that d = log | V | or d = log | E | is meant. G itself is (V, E) and does not even have a cardinal.

Same for the other suggestion for the degree that follows : d = | G |^O(1).

Also, the degree is an integer and the logarithm is likely not an integer. So I doubt that's even an equal sign that is meant.

I hope this helps. --MathsPoetry (talk) 14:13, 24 March 2012 (UTC)

Upper bounds for vertex expansion rates

The formulas giving an upper bound for h_out(G) and h_in(G) are not in the paper of Bobkov et. al. -- or I did not find them. This paper is used as a source for those formulas.

What is in Bobkov's paper is the definition of h_out(G) and h_in(G).

Sorry for the bad news, once again. --MathsPoetry (talk) 19:24, 26 March 2012 (UTC)

As remarked in the footnote, it's implied by Theorem 1 of Bobkov et al.. They use a different notation.ylloh (talk) 22:50, 26 March 2012 (UTC)

Wikipedia says:

$h_{\text{out}}(G)\leq ({\sqrt {2(d-\lambda _{2})}}+1)^{2}-1$

$h_{\text{in}}(G)\leq 2\cdot {\sqrt {d-\lambda _{2}}}$

Bobkov' theorem 1 says:

$\lambda _{\infty }\geq {\frac {({\sqrt {1+h_{\text{out}}}}-1)^{2}}{2}}$

$\lambda _{\infty }\geq {\frac {h_{\text{in}}^{2}}{4}}$

This boils down to the same if $\lambda _{\infty }\leq d-\lambda _{2}$, as you pretend. To prove this second assertion, you give a complicated proof in a footnote.

My first problem with that is that deriving the text on the English Wikipedia from Bobkov's paper is not straightforward at all. In fact, what you did exactly matches the definition of "original work".

My second problem is your explanation : noticing that the quantity $\lambda _{\infty }$ they use satisfies $\lambda _{\infty }\leq d-\lambda _{2}$ (they explicitly state this inequality in terms of the second-smallest eigenvalue of the Laplacian, which is equal to $d-\lambda _{2}$ when $\lambda _{2}$ is the second-largest eigenvalue of the adjacency matrix). I understand it but can't see how you can say that (their) $\lambda _{2}$ is the second-smallest eigenvalue of the Laplacian.

Finally, to be able to have something that is really comparable to Cheeger's inequality, we would need a lower bound, which makes me think that this whole work of mixing Cheeger and Bobkov is a bit pointless.

Best --MathsPoetry (talk) 14:57, 27 March 2012 (UTC)

1. Bobkov et al. use the Laplacian instead of the adjacency matrix. All eigenvalues $\lambda$ of the adjacency matrix correspond to eigenvalues $d-\lambda$ of the Laplacian. The $\lambda _{\infty }$ that they consider is some other notion that satisfies $\lambda _{\infty }\leq d-\lambda _{2}$ (where I use $\lambda _{2}$ from the adjacency matrix as in the wikipedia article).
2. The derivations involved consist of streamlining the notation and reordering terms. I expanded the footnote to explain the situation. Verifiability, yes, but verifiable by who? I think verifiability by experts should be enough (which includes you, for which reason the clarification footnote is needed).
3. These inequalities are lower bounds on the spectral gap, just like Cheeger_constant#Cheeger.27s_inequality (in that article, the eigenvalues are again from the Laplacian, so lower bounds on the second-smallest eigenvalue of the Laplacian are lower bounds on the spectral gap). Thus they're Cheeger inequality analogues for the two vertex-expansion notions. I'm sure this is not well-explained in the article and should be expanded, especially history and context. The discussions of the different notions could also be separated, with a first part about edge expansion and spectral expansion, and a second part about other notions of expansions.

ylloh (talk) 16:51, 27 March 2012 (UTC)

See Wikipedia:No_original_research. Even if this reasoning is true, it's original research, and therefore you have to put it onto your web site, but not on Wikipedia. Sorry.

I meant lower bound for the vertex expansion rates h_in and h_out, not for the spectral gap :-). Cheeger's inequality is about a lower bound for h(G), the upper bound is from some othe guy.

No. Cheeger's inequality is an upper bound on h, while Buser's inequality is a lower bound on h, both in terms of the spectral gap. See Cheeger_constant. ylloh (talk) 17:18, 27 March 2012 (UTC)

What I am trying to focus on is the relation $h(G)\geq {\frac {d-\lambda _{2}}{2}}$, whatever its name. It enables to prove that a given graph is expander in a given ratio. We have nothing alike for $h_{\text{in}}(G)$ and $h_{\text{out}}(G)$.

Where is it stated in Bobkov that (their) $\lambda _{2}$ is the second-smallest eigenvalue of the Laplacian? All that I can see is a definition of (their) $\lambda _{2}$ as twice the smallest nonzero eigenvalue of the Laplacian (pages 153 and 156). --MathsPoetry (talk) 17:28, 27 March 2012 (UTC)

I'm sorry that this is confusing. The area does not have a streamlined notation.

• I don't think any of this is original research because the changes can be considered Routine calculations, and I find your proposal to put it on my webpage to be offensive. Nevertheless I appreciate your opinion.
• What we write in the notation of the wikipedia article as $d-\lambda _{2}$ is equal to $\lambda _{2}/2$ in the notation of Bobkov et al.. I wrongly thought it to be equal to $\lambda _{2}$ previously, thanks for catching that. I corrected this mistake for now.
• I agree that the Bobkov et al. source is not the best. Maybe Theorem 4.6 of this paper is better (it's newer and gives better bounds).
• The Cheeger inequalities for vertex expansion seem to be rather non-standard in the literature, so maybe we should indeed deemphasize them and move the definitions of vertex expansion and its inequalities to its own section about "vertex expansion". Also we should make clear the history of these expansion properties. My understanding is that they originate in the article of Alon. He uses vastly different notation, though, and I think the more modern vertex expansion notation (h_in and h_out) is better.
• I agree that it'd be nice to also state lower bounds for vertex expansion in terms of the spectral gap (like Buser's inequality). The edge expansion lower bound trivially carries over to h_out because of $h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G)$. But something better could be known. Do you know a reference?

Thanks again for sharing your opinion! ylloh (talk) 19:29, 27 March 2012 (UTC)

Sorry if I offended you. Please replace "your web site" with "a mathematical review with reading committee" and it will sound much more graceful.

Your calculations are not routine calculations at all, there is room for interpretation and error. ... as I proved it.

The fact that personal work should not be on wikipedia is a general principle. I suppose that you grasp the motivation for this rule way better now that I exhibited this mistake.

if $d-\lambda _{2}$ (ours) equals ${\frac {\lambda _{2}}{2}}$ (theirs), it means that the formulas in the article that you derived (with what was supposed to be routine !!!) are wrong. See proof below.

I can see why vertex expansion is more interesting than edge expansion from an intuitive point of view: in a computers network, you are interested in how many computers you can reach, not how many wires you go through.

I tried to find a paper that would tell me which inequality is Cheeger's and which one is Buser's and did not find any. Anyway, we were definitely using opposite names. Thanks for pointing out that.

E.g., Theorem 4.8 in Hoory et al.ylloh (talk) 20:45, 27 March 2012 (UTC)

???? That's in the manifold (continuous case), for the "other" Cheeger constant, isn't it? --MathsPoetry (talk) 20:53, 27 March 2012 (UTC)

Cheeger proved an inequality for manifolds. Later on, "Cheeger-like" inequalities were proven for graphs by other people. Many people refer to these inequalities now just as "Cheeger inequalities", even though Cheeger did not prove them.ylloh (talk) 21:48, 27 March 2012 (UTC)

I don't think there is a better lower vaue for $h_{\text{out}}$, and here is why: Let's take the complete graph, regular, degree d, d + 1 vertices. Let's take W to be all vertices but one. The edge boundary of W is made of d edges, while the outer vertex boundary is made of only one vertex (the missing one). I think this example proves that in this case you don't get a better value than ${\frac {h(G)}{d}}$.

I'd also like to thank you for your kind help on this, --MathsPoetry (talk) 20:04, 27 March 2012 (UTC)

Let's call $\mu _{2}$ what Bobkov et al. call $\lambda _{2}$, for the sake of our mental sanity.

• Bobkov states that : $\lambda _{\infty }\leq \mu _{2}$
• Because this is a regular graph, we know that ; $\mu _{2}=2(d-\lambda _{2})$

From that, we can infer that $\lambda _{\infty }\leq 2(d-\lambda _{2})$, but we cannot infer that $\lambda _{\infty }\leq d-\lambda _{2}$ as you announced. --MathsPoetry (talk) 20:27, 27 March 2012 (UTC)

That does not contradict with what is claimed in the current version of the article.ylloh (talk) 20:45, 27 March 2012 (UTC)

Correct, but your proof of it collapses. And I think that you'll have to introduce a factor 2 if you want to prove anything, which will radically change your formulas. --MathsPoetry (talk) 20:54, 27 March 2012 (UTC)

It's not radically different, it's a factor of 2. I introduced the factor of 2 already when I corrected the mistake in the article. The most recent version should be correct. ylloh (talk) 21:48, 27 March 2012 (UTC)

OK ! We got to it. We proved that your original formulas were wrong. This proves that it's dangerous to let contributors infer their own results. --MathsPoetry (talk) 22:20, 27 March 2012 (UTC)

Wow. Quoting : "Routine calculations - Policy shortcut: WP:CALC

This policy allows routine mathematical calculations, such as adding numbers, converting units, or calculating a person's age, provided there is consensus among editors that the calculation is an obvious, correct, and meaningful reflection of the sources."

Do we agree that this level of demonstration + calculations is far, far away from this definition? --MathsPoetry (talk) 21:14, 27 March 2012 (UTC)

This policy does not talk about math articles. The thing we're talking about, even though it is a bit confusing, can be derived using very basic algebraic manipulations. Once we agree on the correctness, I'd prefer not to remove the Cheeger inequalities for vertex expansion. The algebraic manipulations we're dealing with are trivial, especially compared with the proof of these inequalities. Yet I see your point, and I'd like to have an opinion on this from other wikipedia editors. ylloh (talk) 21:48, 27 March 2012 (UTC)

For the record, I don't agree on correctness yet, there are still so much thing that could make that result of yours wrong.

I think these formulas qualify as original work :

1. You've been browsing through Bobkov's article and assumed this variable A in Bobkov had the meaning of that variable B in Hoory, without even knowing whether the hypothesis were exactly the same... Also, you can't assume that people verifying those sources have a deep understanding of the subject that would enable them to do the same.
2. Then you twisted the formulas in algebraic operations that are all but obvious to the average reader, so even if they wanted to verify your formulas they *could* not, even if those operations were correct.

The most we can do with respect to maths is to copy the existing theorems from the sources, and sched some light on them, but we cannot infer new theorems by ourselves.

I have shown you it is very easy to miss some point, and we both know that the tiniest detail in maths can make the better-looking constructions collapse. As a matter of fact, your original formulas were wrong, which proves, if needed, that a) this was not such a "routine" as you said, and b) that the wikipedia policy against original work has a good reason for being so.

Feel free to bring more contributors in, the more the merrier. I think they will give me right on this : no original work. If it's not in the source, don't imagine it, and don't write it in the wikipedia article.

Do you realize that you introduced wrong formulas in a maths article since November, 9, 2010? If you had restrained from doing original work, that would not have happened.

I completly disagree that the sources should be verifiable by experts. They should be verifiable by any motivated reader. And a normal reaction if what is written in the source does not match what is written in the article is: "oh, this is not a valid source for that article", you can't expect people to reinvent the complex reasoning that went through your head one day.

Also, you did not convince me that WP:CALC does not apply to maths.

Thank you for your understanding. --MathsPoetry (talk) 22:12, 27 March 2012 (UTC)

Definition of spectral gap

"In some contexts, the spectral gap is defined to be $d-\lambda _{2}$. In other contexts, the spectral gap is $d-\lambda$, where $\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$."

What kind of a definition is that? What are these "contexts"? Do you mean that the authors don't agree on the definition of the spectral gap? And if so, why? The cheeger inequality clearly uses $d-\lambda _{2}$.

This article definitly needs clarification IMHO. --MathsPoetry (talk) 15:37, 24 March 2012 (UTC)

I clarified this a little bit. I agree that the article should have a single consistent definition. Cheeger's inequality uses $\lambda _{2}$ but, e.g., the expander mixing lemma breaks down if you replace $\lambda$ with $\lambda _{2}$ (although a bipartite version still holds). In Hoory et al., they switch after Section 2.3 from $\lambda _{2}$ to $\lambda$ and never seem to discuss the issue. Different authors do use different definitions based on what is more convenient for them. And there are many different choices:

• $\lambda$ vs. $\lambda _{2}$.
• adjacency matrix vs. normalized adjacency matrix.
• adjacency matrix vs. Laplacian.

So yes, the precise definition of 'spectral gap' depends on authors and contexts. ylloh (talk) 18:00, 25 March 2012 (UTC)

Yes. There are so many points that differ from one author to another. For example, vertex boundary version edge boundary, normalized eigenvalues or not, regular graphs or connected graphs or all graphs in the expander graph definition, limits on the maximum degree or not in that definition, constant degree in the expander families or not, etc. The list of all variations on this theme is really impressive.

To avoid the impression of a "mess" in the article (sorry for the bad word), I took the following approach: I just take one point of view (basically, the one of Shlomo Hoory's paper), and keep saying "one could define things differently", "similar relations exist for...", "definition might vary", etc. See fr:Graphe expanseur.

So instead of embracing all point of views, I just describe one, and let the reader dig for the other ones. Not perfect a solution, of course, probably just a matter of tastes...

Best, --MathsPoetry (talk) 20:38, 25 March 2012 (UTC)

Ah, as I understood it, in Hoory's paper, $\lambda$ is just a commodity writing for $\lambda _{2}$. Did I miss some point? --MathsPoetry (talk) 20:44, 25 March 2012 (UTC)

$\lambda$ is defined in the first sentence of Section 2.4 in [1]. I don't want to restrict the article to one type of expansion. The reason why this wikipedia article is useful (for me) is precisely because it puts several different ways of looking at expander graphs into context. However, I think it'd be a good idea to have more informal sections preceding the 'definitions' section, like the 'history' section on fr:Graphe expanseur, or a 'motivation' section that talks about applications and intuitions first. ylloh (talk) 15:16, 26 March 2012 (UTC)

Yes, but section 2.4 still does only say "a small λ (or a large spectral gap)", it does not say that the spectral gap is d - λ. Or did I miss it? As a matter of fact, a small lambda implies a small λ₂, and therefore a big d - λ₂ difference, if I am not wrong. I think there's a possibility the article did some overinterpretation of Hoory here. Please correct me if I'm wrong.

With respect to the need of informal stuff, motivation, and history, I do agree. Also, examples would help, see fr:Graphe expanseur.

In other sections of this discussion page (see above) I point out other things that I think are missing, or other points where I think there is room for improvement. Maybe what is missing the most is a definition of "expander graph" : after all, this paper is about expander graphs...

Don't think I'm lazy, if English were my mother language I would add this stuff myself. --MathsPoetry (talk) 17:00, 26 March 2012 (UTC)

Ping. I still don't see where they say the spectral gap is d - λ. Original research too ? --MathsPoetry (talk) 17:04, 27 March 2012 (UTC)

This is not claimed in the current version of the article.ylloh (talk) 19:31, 27 March 2012 (UTC)

Oh, you fixed that already. Thanks. This one is solved.

See two discussion sections above for another problem with d = log | G | lines... --MathsPoetry (talk) 20:14, 27 March 2012 (UTC)

"Original research" template

MathsPoetry (talk · contribs) added the "Original research" template in this edit. See also the discussion above, consisting of 80 edits this user made here on the talk page. The two inequalities in question are:

$h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1$

$h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}$

The inequalities are now accompanied by the following footnote:

This follows from Theorem 1 in Bobkov, Houdré & Tetali (2000) by solving for $h_{\text{out}}(G)$ and $h_{\text{in}}(G)$. Then notice that the quantity $\lambda _{\infty }$ that they use in the paper satisfies $\lambda _{\infty }\leq 2(d-\lambda _{2})$ (they explicitly state this inequality, albeit they use $\lambda _{2}$ instead of $2(d-\lambda _{2})$ to denote twice the smallest positive eigenvalue of the Laplacian matrix of $G$).

While the explanation in the footnote may or may not be sufficient, or may even be confusing for some readers, I don't think this constitutes original research. All that happens is a simple translation from an inequality for the smallest positive eigenvalue of the Laplacian (in the notation of Bobkov, Houdré & Tetali (2000)) to an inequality for the second-largest eigenvalue of the adjacency matrix. I would greatly appreciate the opinion of other editors.

(Interestingly, the question whether these inequalities satisfy Wikipedia:Notability did not come up. Weaker versions of these inequalities are maybe more well-known and appeared in Alon's "Eigenvalues and Expanders" (1986), where vertex expansion was called 'magnification' and the notation was less streamlined. Even better bounds are shown in Theorem 4.6 of this paper, and I'm inclined to replace Bobkov, Houdré & Tetali (2000) with the more recent reference.)

Thanks! ylloh (talk) 02:15, 28 March 2012 (UTC)

Ylloh asked me to comment here. To me, what he describes seems to fall clearly under Wikipedia:Scientific citation guidelines#Examples, derivations and restatements as the sort of routine change-of-notation that should be allowed here. It is not reasonable to require us to use the exact notation present in our sources (for one thing, because the sources likely do not all use the exact same notation themselves) and so this sort of conversion is both necessary and unproblematic. —David Eppstein (talk) 02:29, 28 March 2012 (UTC)

This was not a simple restatement. It involved (and still involves) a lot of interpretation, understanding of advanced graph theory, reasoning, inferring from several formulas, computations, and restatement.

It is made by artificially matching notions and quantities in one paper (Bobkov) with notions in another paper (Hoory). Ylloh has keept this part under silence when presenting the facts above. He is also keping under silence the fact that he has to use more formulas to reach his result (like the relation between $\lambda _{\infty }$ and $\lambda _{2}$).

The formulas that are in the article are in NO external source. You can search everywhere, you won't find it anywhere in the scientific litterature.

It is wrong that it is a simple transformation, or a simple change in the notation, that's more to it. Also, I am still not fully convinced that current result is correct.

Here is an example of one of the things that might still go wrong and that Ylloh eluded: Bobkov assumes his $\lambda _{2}$ variable to be the first nonzero eigenvalue of the laplacian matrix, while there's no such equivalent thing with Hoory (think about the case where two first eigenvalues of the adjacency matrix are d, i.e. the unconnected regular graph, in this case the definitions don't match).

During more than one year, this so-called simple transformation led to these wrong formulas:

$h_{\text{out}}(G)\leq ({\sqrt {2(d-\lambda _{2})}}+1)^{2}-1$

$h_{\text{in}}(G)\leq 2\cdot {\sqrt {d-\lambda _{2}}}$

These formulas, that Ylloh pretended to be proved by "routine" calculations, stayed in the article from November 9, 2010 to March, 27, 2012, until I tediously showed him a mistake in his original work.

Is the average reader ready to do that work of decomponing one's reasoning into little pieces and confronting it to sparse sentenses in a high-level mathematics document? Of course not. That's why there is no room for inferring new theorems on wikipedia. That's why sources must be immediately verifiable, i.e. the sentence or formula must appear in the source. Maybe with different notation, but the notation change must be obvious, here it's a discutable variable substitution and also the use of other inequities that appear somewhere else in the document.

What if Ylloh was not available for answering my questions, and be proven wrong, and "fixing" his original work? What if he had left wikipedia ? These wrong formulas would have stayed forever.

This very illustrative example should prevent anyone from the temptation of doing original work.

Show me a scientific publication where these formulas are shown, and you could put them here. Meanwhile: no sources, no sugar. --MathsPoetry (talk) 07:23, 28 March 2012 (UTC)

I am sorry, but I agree with David Eppstein above and disagree with Maths Poetry. Errors do happen (I note and fix my own errors here from time to time), but this is not a reason to declare changing notation OR. The notation in Bobkov et al. is different from that in our article, therefore it is not only allowed but actually desired to change it before citing their result. Sasha (talk) 14:25, 28 March 2012 (UTC)

Further agreed: translating between different notations is tough but is necessary to make a readable encyclopedia article; the fact that sometimes factors of 2 get lots in this process is evidence of human frailty, not original research. Putting the word "wrong" in boldface repeatedly doesn't make boring typos or arithmetic errors into something important or into violations of policy. --Joel B. Lewis (talk) 14:48, 28 March 2012 (UTC)

For your question about the correctness, notice that if $d=\lambda _{2}$, then the graph is disconnected and the inequalities are trivially satisfied (choose $S$ to be the vertex set of the smaller connected component). Otherwise, $\mu _{2}/2=d-\lambda _{2}$ is the smallest positive eigenvalue of the Laplacian. If you want, this fact can be added to the footnote. ylloh (talk) 14:51, 28 March 2012 (UTC)

I have edited the disputed footnote a bit, to make the ref-s more specific. Note that combining the BHT bound in terms of λ_∞ with the inequality between λ_∞ and λ₂ is also very far from OR by synthesis, since it is stated explicitly in the 3rd displayed formula on p.154. Sasha (talk) 16:02, 28 March 2012 (UTC)

to Ylloh: I noticed that the inaccuracy on matching Bobkov's $\lambda _{2}$ with the second smallest eigenvalue of the Laplacian did not make the proof collapse: I tried to build a counter example and the formula still holds. Nevertheless, you have to admit this is another detail you had overseen, which supports my claim that all of this derivation is non-obvious and fragile. --MathsPoetry (talk) 16:55, 28 March 2012 (UTC)

Ylloh's proof

In this section, I will detail Ylloh's proof of the disputed formulas, so everyone can make his/her opinion whether this is Original Research or just innocent rephrasing of existing material.

The academic paper these formulas are based on is λ∞, vertex isoperimetry and concentration. I will refer to it as [BOB00].

Also, there are three different notions referred to in this proof that are usually represented with the symbol $\lambda _{2}$. For the sake of our mental health, I will distinguish them clearly and call them $\lambda _{2}$, $\mu _{2}$, and $\nu _{2}$. But keep in mind that they all appear in the scientific publications as $\lambda _{2}$...

Proof

• (1) Let G = (V, E) be a finite, undirected, connected graph equipped with a probability measure $\pi$ ([BOB00] page 153)
• (2) Let's also assume G is d-regular (we will need that later on)
• (3) Let $\mu _{2}$ be twice the smallest non-zero eigenvalue of the Laplacian matrix of G ([BOB00] page 153)
• (4) Let $\nu _{2}$ be the second smallest eigenvalue of the Laplacian matrix of G
• (5) Assuming that the smallest non-zero eigenvalue and the second smallest eigenvalue are the same, we can write $\mu _{2}=2\cdot \nu _{2}$
• (6) Let $\lambda _{2}$ be the second biggest eigenvalue of the adjacency matrix of G
• (7) Since the graph G is d-regular, $\nu _{2}=d-\lambda _{2}$

(it's a general property of regular graphs, that can be demonstrated rather easily)

• (8) From (5) and (7), we can write $\mu _{2}=2\cdot (d-\lambda _{2})$
• (9) Let $\lambda _{\infty }$ be the Poincaré-type constant ([BOB00] page 155)
• (10) $\mu _{2}\geq \lambda _{\infty }$ ([BOB00] page 156)
• (11) From (8) and (10), $2\cdot (d-\lambda _{2})\geq \lambda _{\infty }$
• (12) $\lambda _{\infty }\geq {\frac {h_{\text{in}}^{2}}{4}}$ and $\lambda _{\infty }\geq {\frac {({\sqrt {1+h_{\text{out}}}}-1)^{2}}{2}}$ (theorem 1, [BOB00] page 156)
• (13) From (11) and (12), $2\cdot (d-\lambda _{2})\geq {\frac {h_{\text{in}}^{2}}{4}}$ and $2\cdot (d-\lambda _{2})\geq {\frac {({\sqrt {1+h_{\text{out}}}}-1)^{2}}{2}}$
• (14) Hence ${\sqrt {2\cdot (d-\lambda _{2})}}\geq {\frac {h_{\text{in}}}{2}}$ and ${\sqrt {2\cdot (d-\lambda _{2})}}\geq {\frac {{\sqrt {1+h_{\text{out}}}}-1}{\sqrt {2}}}$
• (15) Finally, $h_{\text{in}}(G)\leq {\sqrt {8\cdot (d-\lambda _{2})}}$ and $h_{\text{out}}(G)\leq ({\sqrt {4\cdot (d-\lambda _{2})}}+1)^{2}-1$

Remarks from MathsPoetry

• (1) the WP article does not assume the graph to be connected, nor equipped with a probability measure. As a matter of fact, Cheeger's formulas work with unconnected graphs, and even the formulas established by my contradictor work as well! I never studied probability measures of graphs, so I don't know whether this requirement has implications or not. Anyway: the disputed paragraph should add those assumptions.
• (2) Notice that Bobkov et. al.'s result is more general, since it does not assume a regular graph.
• (5) This is obviously dubious, but I did not succeed in building a counter-example out of that constatation... This does not mean it is correct to do such assumptions though.
• (13) By eliminating $\lambda _{\infty }$ from the inequations here, we are losing accuracy on the bound. I don't know "how much" though.

Remarks from Tkuvho

• If the graph is finite and connected, then 0 occurs with multiplicity 1 as only constant functions are harmonic, so in this case there does not seem to be any problem with (5). If the graph is not connected, for the same reason there is an obvious problem with (5). Am I missing something? Tkuvho (talk) 17:20, 28 March 2012 (UTC)

That's also the conclusion I reached. Readers will judge whether this point is just "routine" considerations. --MathsPoetry (talk) 17:28, 28 March 2012 (UTC)

A disconnected graph satisfies the inequalities in question (since the expansion of the smallest connected component is 0, and the right-hand sides are also 0). ylloh (talk) 20:27, 28 March 2012 (UTC)

Discussion

From your description, it still seems routine to me. The criterion for me is: would I be embarrassed to call it a "lemma" and supply an explicit proof if I were writing this in a research paper? In this case, yes. Everything that you break down into steps 1-8 is just a trivial change of variables, with the small exception that Tkuvho calls out, that we should justify the multiplicity of 0. The rest is just combining two nearby inequalities from the same source in an obvious way. —David Eppstein (talk) 18:17, 28 March 2012 (UTC)

With all due respect, we are not in a research paper. We are on wikipedia, and the average wikipedia's reader is not able to read research papers. My own definition of routine is reasonings and calculations that the average wikipedia reader would be able to do by matching the sources to the wikipedia article. That's what verifiability is all about, IMHO. --MathsPoetry (talk) 18:24, 28 March 2012 (UTC)

I'd be surprised if the average wikipedia reader can even understand the statement. This is a specialized article for people with a strong math background. I thank you very much for diligently checking that the way I stated the inequality is now correct, and for pointing out a mistake I made earlier. I think verifiability should mean 'obvious to experts', in this case experts in spectral graph theory / expander graphs. This means it can be verified by people with a rigorous math background, like yourself, with some effort. It can be verified by average wikipedians if they learn linear algebra and math first. As an example, I think it'd take serious effort for me to verify any technical claim made in Kaluza-Klein_theory. Yet I am happy that people contribute technical content there, and I am confident that some experts have verified claims made there. ylloh (talk) 20:27, 28 March 2012 (UTC)

Yes, the English article about expander graphs is very technical and is made to be understood only by specialists. Now you should ask to yourself: had it to be so? Isn't the purpose of wikipedia's math articles to do good vulgarization? Obviously, this one has failed that mission. Wikipedia math articles aren't meant to be by experts for experts. This is precisely the point where we completly diverge.

I hate to say "I did better", but the French article fr:Graphe expanseur isn't for "people with a strong math background". It completly relies on examples, plain text explanations, graphics, and can be understood by anyone who basically understood what an unoriented graph is. Which proves that it was possible to do something else than this catalogue of formulas that the current "expander graph" article has turned into. Also, every formula that lies in the French article can be found in the mentioned sources, without the need for a committee of experts to emit a doctrinal agreement.

I don't say I did something perfect, the French version is lacking the expander mixing lemma, the random walks and the geometrical interpretation of expander graphs. Also, the Margulis construction would need some explanation wrt why it works well. But there's a chance that even those advanced topics can be explained with simple words.

Let me show you how I see the current English article:

• no drawings, which is quite surprizing in a text about graph theory
• no examples
• no definition of an "expander graph", while it is the subject of the article (!!!)
• no vulgarization explanations
• prove-it-yourself assertions

Graph theory is unique among mathematics in the sense that someone with very little technical knowledge can have an intuitive understanding of a lot of things, why don't you take profit of that?

--MathsPoetry (talk) 21:10, 28 March 2012 (UTC)

First, please use the "Show preview" button -- your habit of making dozens of unimportant edits is extremely irritating, at least to me. Second, if you'd like to improve this article, by all means do so; but the problems with this article have nothing to do with your original complaint, which I hope you're finally willing to drop. --Joel B. Lewis (talk) 22:16, 28 March 2012 (UTC)

Remove the "Original Work" banner if you feel like, I really don't care. I don't feel it has be proven at all that this is not original work, so, no, I am not willing to drop this claim.

I have shown that it was very dangerous to do such personal research, since wrong formulas have given wrong informations during one year and a half, which would not have happened if their author had restrained himself to doing compilation of secondary sources, as everyone does in Wikipedia but maths.

I am explaining the problems of this article, because it is being explained to me that there is no need to do efforts to be understood or verified by the average reader, which is in complete opposition with my view of the role of Wikipedia, not to speak about the "no original work" or "verifiability" principles.

Sorry if I am irritating you.

To be honest, I am getting irritated too, and I will leave you alone in your tiny club of experts. Have a lot of mathematical fun together in the high spheres. From my part, I have finished trying to help on the English speaking wikipedia. Goodbye. --MathsPoetry (talk) 22:30, 28 March 2012 (UTC)

definition

Following the critique of MathsPoetry, I looked at the beginning of the article. The definition says: An expander is a finite, undirected multigraph that has good expansion properties. I think we can do better than that. Suggestions? Sasha (talk) 04:26, 29 March 2012 (UTC)

definition of expander

the definition of expander is missing: I am really disappointed!--2A00:1398:9:FB03:226:BBFF:FE0E:AC42 (talk) 16:03, 29 August 2017 (UTC)