Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}} [|T \cap S| > k] \quad=\quad p $$

Question: Given a (sane) parameter $t$, is there an explicit family of sets $\mathcal{F} = \{ S_1,\dots S_t \}$, where each $S_i$ is a subset of $[N]$ of size $n$ such that: $$ \Pr_{\substack{T\subset [N]\\|T| = m}} [\forall i \in [t] \;:\; |T \cap S_i| > k] \quad \leq \quad p^{t/1000} $$ Here are some examples for which such a bound holds:

  • If each $S_i$ is picked at random, then the probability is $p^t$, as the events are truly independent.
  • If each $S_i$ is disjoint, then the probability is $p^t$ (again as the events are independent).
  • If $t$ is large enough to allow $\mathcal{F}$ to be the set of all subsets of size $n$, then any choice of $T$ would surely miss some set (if $m \ll N$)

The sort of set system I have in mind is something like a Nisan-Wigderson design (where pairwise intersection between the $S_i$'s are small, and $t \gg N$). The vague intuition is that mutually disjoint sets are independent events, and for almost disjoint sets we ought to have an exponential drop (maybe not $p^t$, but $p^{t/1000}$ or $p^{\sqrt{t}}$ or something).


Your Answer

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

Browse other questions tagged or ask your own question.