Statement
Let be a d-regular graph with normalized second-largest eigenvalue (in absolute value) of the adjacency matrix. Then for any two subsets, let denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is, . We have
For a proof, see references.
Read more about this topic: Expander Mixing Lemma
Famous quotes containing the word statement:
“One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
—Rebecca West (1892–1983)
“If we do take statements to be the primary bearers of truth, there seems to be a very simple answer to the question, what is it for them to be true: for a statement to be true is for things to be as they are stated to be.”
—J.L. (John Langshaw)
“He has the common feeling of his profession. He enjoys a statement twice as much if it appears in fine print, and anything that turns up in a footnote ... takes on the character of divine revelation.”
—Margaret Halsey (b. 1910)