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?
 A: 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:


*

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

*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.
