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\le t\le |A|$. Some ordered tuple of $t$ distinct vertices of $A$ has a common neighbourhood of size at leastSample 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.