# Cardinality of families of (almost) disjoint subsets

Let $G = \{1, 2, \ldots, n\}$ be the ground set. What is the maximum number of subsets of size at least $n/3$ of $G$ where any two subsets have at least $n/10$ different elements?

I am interested in the asymptotic value. Say 1/3 and 1/10 represent constant fractions, is it possible to prove that there are at most a small number of such subsets?

• Please excuse the dumb question, but I'm not sure what "any two subsets have at least $n/10$ different elements" means, no doubt it's because my English isn't very good. Does it mean that $|A\cap B|\ge n/10?$ – bof Jan 22 '18 at 11:43
• @bof No, it means that $|A-B \cup B-A| \geq n/10$. – Soheil Jan 23 '18 at 8:10

Let us choose $\alpha$ many sets of size $n/3$ at random. The cardinality $X=|U\cap V|$ of the intersection of two of them is a hypergeometric random variable (well, given $U$, but the value of $U$ does not matter):

out of $M=n$ objects, with $K=n/3$ of them having the specific property of being in $U$, $X=k$ if there are $k$ many of $m=n/3$ many chosen objects that have the specific property.

A tail bound for hypergeometric random variables is $$\Pr(X\le (p+t)m)\ge 1-e^{-2t^2m}$$ where $p=K/M=1/3$. So as I understood your question, $$\Pr(U,V\text{ almost disjoint})=\Pr(X\le n/3-n/10)=\Pr\left(X\le \frac{21}{90}n\right)$$ $$= \Pr\left(X\le n/9+\frac{11}{90}n\right)=\Pr\left(X\le m/3+\frac{11}{30}m\right)\ge 1-e^{-2(11/30)^2m}.$$ So if we let $c=2(11/30)^2$ and $\alpha\le e^{cm/2}$, $$\Pr(\exists U,V\text{ are not almost disjoint})\le\sum_{(U,V)}\Pr(U,V\text{ not almost disjoint})\le {\alpha\choose 2}e^{-cm}$$ $$\le \frac{e^{cm/2}(e^{cm/2}-1)}{2}e^{-cm} = \frac12-\frac{e^{-cm/2}}2 <\frac12.$$ Since a set having probability at least 1/2 is nonempty, we conclude:

we can choose at least $e^{cm/2}=\exp((11/30)^2n/3)$ many such subsets.

Notes:

1. For $n=27$, this is just $3$ subsets.

2. The total number of subsets of $n$ of size $n/3$ is ${n\choose n/3}$ which is between $3^{n/3}$ and $(3e)^{n/3}$ -- significantly larger.