Expander Mixing Lemma

The expander mixing lemma states that, for any two subsets of a d-regular expander graph, the number of edges between and is approximately what you would expect in a random d-regular graph, i.e. .

Read more about Expander Mixing Lemma:  Statement, Converse

Famous quotes containing the word mixing:

    Give me Catholicism every time. Father Cheeryble with his thurible; Father Chatterjee with his liturgy. What fun they have with all their charades and conundrums! If it weren’t for the Christianity they insist on mixing in with it, I’d be converted tomorrow.
    Aldous Huxley (1894–1963)