Dense bipartite common-neighbour lemma
ID: dense-bipartite-common-neighbour-lemma
In a bipartite graph with parts of sizes and density , a neighbourhood of size at least can be chosen so that at least a proportion of its ordered pairs have at least common neighbours. Choose a random vertex on the other side, use the second moment of its degree, and penalize pairs with few common neighbours. This is a simple dependent random choice tool for controlling restricted sumsets.
New to topics? Read the docs here!