= Common neighbourhood from bipartite density
{title2=$|N(S)|\ge N(\beta/2)^s$}
If a <bipartite graph> with class sizes $m,N$ has at least $\beta mN$ <edges>, double count pairs consisting of an $s$-set in the first class and a common neighbour in the second. Convexity of binomial coefficients gives some $S$ with $|N(S)|\ge N\binom{\lfloor\beta m\rfloor}s/\binom ms$. When $s\le\beta m/2$, the quotient is at least $(\beta/2)^s$. This turns density into a large complete bipartite subgraph.
Back to article page
