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:
“The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.”
—Ralph Waldo Emerson (1803–1882)
“I think, therefore I am is the statement of an intellectual who underrates toothaches.”
—Milan Kundera (b. 1929)
“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)