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 most distinct and beautiful statement of any truth must take at last the mathematical form.”
—Henry David Thoreau (1817–1862)
“Eloquence must be grounded on the plainest narrative. Afterwards, it may warm itself until it exhales symbols of every kind and color, speaks only through the most poetic forms; but first and last, it must still be at bottom a biblical statement of fact.”
—Ralph Waldo Emerson (1803–1882)
“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)