# 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://mathoverflow.net/questions/291223/cardinality-of-families-of-almost-disjoint-subsets", "fetch_time": 1585881566000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2020-16/segments/1585370509103.51/warc/CC-MAIN-20200402235814-20200403025814-00235.warc.gz", "warc_record_offset": 581366771, "warc_record_length": 27075, "token_count": 730, "char_count": 2067, "score": 3.90625, "int_score": 4, "crawl": "CC-MAIN-2020-16", "snapshot_type": "latest", "language": "en", "language_score": 0.8734935522079468, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00017-of-00064.parquet"}