Expander Mixing Lemma - Statement

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:

    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)

    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)