# Asymptotics of the number of elements in the intersection of two growing sets

Let $[n]:=\{1,\dots,n\}$ and $0\leq p_n\leq n$. Fix any subset $A_n$ of $[n]$ with $p_n$ elements. The number of subsets $B$ of $[n]$ with $p_n$ elements that are disjoint from $A$ is $\binom{n-p_n}{p_n}$ and so the number of subsets $B$ with $p_n$ elements that have a non-empty intersection with $A$ is given by $\binom{n}{p_n}-\binom{n-p_n}{p_n}$ which asymptotically behaves like $\binom{n}{p_n}$ if $\sqrt{n}\ll p_n$. Precisely: $$\lim_{n\to\infty}\frac{\binom{n}{p_n}-\binom{n-p_n}{p_n}}{\binom{n}{p_n}}=\begin{cases}1 &\text{if }\sqrt{n}\ll p_n\\ 0&\text{if }p_n\ll\sqrt{n}\\ e^{-a^2}&\text{if }\lim_{n\to\infty}\frac{p_n}{\sqrt{n}}=a\end{cases}$$ To put it differently, any two subsets of $[n]$ with $p_n$ elements typically have non-empty intersection if $p_n$ grows faster than $\sqrt{n}$.

Now, I am interested in the typical number of elements in their intersection if $p_n$ grows faster than $\sqrt{n}$. My feeling would be that this number also grows with $n$. Precisely, I believe (numerics support this) that if $q_n$ grows slower than $p_n/\sqrt{n}$ then eventually all sets $A_n$, $B_n$ with $p_n$ elements each share at least $q_n$ elements. To put it in formulas, if $A_n$ is any set with $p_n$ elements, then $$\lim_{n\to\infty }\frac{\lvert\{B_n\subset[n]~~\lvert~~\lvert B_n\lvert=p_n\text{ and }\lvert A_n\cap B_n\lvert\geq q_n\}\rvert}{\binom{n}{p_n}}=1.$$

Since there is no exact combinatorial count (only in terms of generalised hypergeometric functions) on the number of $B_n$ of a given size that share at least $q_n$ elements with some fixed sets, I would need some good lower bound on it. Has anybody seen those asymptotics worked out? Any references would be welcome.

• The details are taking more time than I have right now, but you should be able to get good answers for some ranges of the parameters by looking at random sets and using concentration of measure. – Ben Barber Jun 18 '14 at 11:21
• Note that the number of sets $B$ intersecting $A$ in exactly $j$ elements is $\binom{p_n}{j}\binom{n-p_n}{p_n-j}$. From this one can calculate what you want. The number of elements in the intersection is approximately distributed like a Poisson random variable with parameter $p_n^2/n$. – Lucia Jun 18 '14 at 15:35
• Thank you for your comment! I don't think that there is an easy (without hypergeometric functions) expression for $\sum_{j=q_n}^{p_n}\binom{p_n}{j}\binom{n-p_n}{p_n-j}$?! How do I get an approximation for this quantity? Could you elaborate on how the Poisson distribution comes up? – whz Jun 18 '14 at 16:41

To avoid subscripts, I'll write simply $p$ instead of $p_n$. We'll assume that $p$ is small compared with $n$; certainly say $3p<n$. Given $A$ of cardinality $p$, the number of sets $B$ of size $p$ intersecting $A$ in exactly $j$ elements is $$\binom{p}{j} \binom{n-p}{p-j} \le \frac{p^j}{j!} \Big(\frac{p}{n-2p}\Big)^j \binom{n-p}{p} \le \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j \Big(\frac{n-p}{n}\Big)^p \binom{n}{p}.$$ Since $(1-x)\le e^{-x}$, the above is $$\le \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j e^{-p^2/n} \binom{n}{p}.$$ Thus the probability that $B$ intersects $A$ in exactly $j$ elements is at most $$\frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j e^{-p^2/n}. \tag{1}$$ (In fact, in a wide range this is essentially an asymptotic, and so the number of elements in the intersection is essentially Poisson with parameter $p^2/n$.)
But we can continue with actual inequalities rather than asymptotics. Consider the probability that the size of the intersection is at most $J$ (and assume that $J\le p^2/(n-2p)$). By (1) this probability is $$\le e^{-p^2/n} \sum_{j=0}^{J} \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j.$$ For any $\alpha >0$ the above is (since $e^{\alpha(J-j)}\ge 1$ for $j\le J$ and non-negative otherwise) $$\le e^{-p^2/n} \sum_{j=0}^{\infty} e^{\alpha(J-j)} \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j = e^{-p^2/n} \exp\Big(\alpha J + \frac{p^2}{n-2p} e^{-\alpha}\Big).$$ Choose optimally $\alpha$ such that $J=e^{-\alpha}(p^2/(n-2p))$ and so the above estimate becomes $$\le e^{-p^2/n} \exp\Big( J \Big( 1+ \log \frac{p^2}{J(n-2p)}\Big)\Big).$$ This is a completely explicit bound, and for example shows that the probability that the intersection is at most $p^2/(e(n-2p))$ is at most $$\exp\Big(-\frac{p^2}{n} + \frac{2}{e} \frac{p^2}{n-2p} \Big).$$ Clearly this is very small if $p^2/n$ is large, but $p$ is small compared to $n$.