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:

    “He that writes to himself writes to an eternal public. That statement only is fit to be made public, which you have come at in attempting to satisfy your own curiosity.”
    —Ralph Waldo Emerson (1803–1882)

    “The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.”
    —Ralph Waldo Emerson (1803–1882)

    “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)