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:
“Truth is used to vitalize a statement rather than devitalize it. Truth implies more than a simple statement of fact. “I don’t have any whisky,” may be a fact but it is not a truth.”
—William Burroughs (b. 1914)
“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)
“The parent is the strongest statement that the child hears regarding what it means to be alive and real. More than what we say or do, the way we are expresses what we think it means to be alive. So the articulate parent is less a telling than a listening individual.”
—Polly Berrien Berends (20th century)