= Common-neighbourhood sampling bound
Let a <bipartite graph> with nonempty parts $A,B$ have <edge density of a bipartite graph> at least $p$, and let $1\leq t\leq|A|$. Some ordered tuple of $t$ distinct vertices of $A$ has a <common neighbourhood> of size at least
$$
|B|\left(\max\left\{p-\frac{t-1}{|A|},0\right\}\right)^t.
$$
Sample the tuple uniformly without replacement. A vertex $b\in B$ belongs to its common neighbourhood with probability $(d(b))_t/(|A|)_t$, where $(m)_t=m(m-1)\cdots(m-t+1)$. This is at least $((d(b)-t+1)_+/|A|)^t$. The function $u\mapsto(u-t+1)_+^t$ is convex, so averaging over $b$ and using <Jensen's inequality> proves the bound.
For fixed $p>0$ and $t$, taking $|A|$ sufficiently large compared with $t^2/p$ makes this at least $p^t|B|/2$. The positive part in the formula is essential: without it, a negative base raised to an even power would assert a spurious positive common neighbourhood.
Back to article page
