Sets with Small Intersection

2 minute read

Published:

Suppose that we want to construct subsets $S_1, \ldots, S_m \subseteq \{1,\ldots,n\}$ with the following properties:

  1. $S_i\geq k$ for all $i$
  2. $S_i \cap S_j\leq 1$ for all $i \neq j$

The goal is to construct as large a family of such subsets as possible (i.e., to make $m$ as large as possible). If $k \geq 2\sqrt{n}$, then up to constants it is not hard to show that the optimal number of sets is $\frac{n}{k}$ (that is, the trivial construction with all sets disjoint is essentially the best we can do).

Here I am interested in the case when $k \ll \sqrt{n}$. In this case I claim that we can substantially outperform the trivial construction: we can take $m = \Omega(n^2 / k^3)$. The proof is a very nice application of the asymmetric Lovasz Local Lemma. (Readers can refresh their memory here on what the asymmetric LLL says.)

Proof. We will take a randomized construction. For $i \in \{1,\ldots,n\}$, $j \in \{1,\ldots,m\}$, let $X_{i,a}$ be the event that $i \in S_a$. We will take the $X_{i,a}$ to be independent each with probability $\frac{2k}{n}$. Also define the events

\[Y_{i,j,a,b} = I[i \in S_a \wedge j \in S_a \wedge i \in S_b \wedge j \in S_b]\] \[Z_{a} = I[|S_a| < k]\]

It suffices to show that with non-zero probability, all of the $Y_{i,j,a,b}$ and $Z_{a}$ are false. Note that each $Y_{i,j,a,b}$ depends on $Y_{i’,j,a’,b}, Y_{i’,j,a,b’}, Y_{i,j’,a’,b}, Y_{i,j’,a,b’}, Z_a, Z_b$, and each $Z_a$ depends on $Y_{i,j,a,b}$. Thus each $Y$ depends on at most $4nm$ other $Y$ and $2$ other $Z$, and each $Z$ depends on at most $n^2m/2$ of the $Y$. Also note that $P(Y_{i,j,a,b}) = (k/n)^4$ and $P(Z_a) \leq \exp(-k/4)$ (by the Chernoff bound). It thus suffices to find constants $y, z$ such that

\[(k/n)^4 \leq y(1-y)^{4nm}(1-z)^2\] \[exp(-k/4) \leq z(1-y)^{n^2m/2}\]

We will guess $y = \frac{k}{n^2m}$, $z = \frac{1}{2}$, in which case the bottom inequality is approximately $\exp(-k/4) \leq \frac{1}{2}\exp(-k/2)$ (which is satisfied for large enough $k$, and the top inequality is approximately $\frac{k^4}{n^4} \leq \frac{k}{4n^2m} \exp(-4k/n)$, which is satisfied for $m \leq \frac{n^2}{4ek^3}$ (assuming $k \leq n/4$). Hence in particular we can indeed take $m = \Omega(n^2/k^3)$, as claimed.

Comments

Emmett

jacob advantage shane cheap meds price order drugs online generic tablets available in canada tablets cheap price price of meds tirastam online pharmacy generic meds where to order florida buy drugs fast delivery generic myambutol price i need a tizanidine generic drugs find buy meds spain money order drugs pharmacy europe meds price united kingdom drugs price buy cheap tablets purchase drugs online legally buy tiotropium from london buy tablets no doctor online tablets no prescription fexofenadine can i order shopping europe ordered growling

Hazel

spike black satellite prosecution drugs find online purchase cheap tablets order tonavir online canada tablets online shop generic tablets find generic imuran order money order now cheapest emthexate florida where to buy tablets buy diarex shop canada buy antabuse thailand cheap prices on drugs order combigan online without prescription medications order cheapest tablets buy drugs usa online buy drugs in usa without prescription low price tablets sinemet the pill tablets price usa cheapest meds mail order cheapest budecort buy recommended royce rear

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...