= Dense bipartite common-neighbour lemma
In a <bipartite graph> with parts of sizes $m,n$ and density $\delta>0$, a neighbourhood $V'$ of size at least $\delta m/2$ can be chosen so that at least a proportion $1-2\epsilon/\delta^2$ of its ordered pairs have at least $\epsilon n$ <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>.
Back to article page
