3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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?$ $\endgroup$ – bof Jan 22 '18 at 11:43
  • $\begingroup$ @bof No, it means that $|A-B \cup B-A| \geq n/10$. $\endgroup$ – Soheil Jan 23 '18 at 8:10
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.