Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that:

  1. $\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$.
  2. $\forall i \neq j \in [m]$, $|S_i \cap S_j| \le a$.

For example, it is known that such designs exist for $a = \log m$, $\ell = C\log m$ and $d = O(C^2\log m)$. I am interested (in general) in such kind of settings of parameters: where you can generate a large number ($m$ in total) of small sets (each of size $O(\log m)$) over a small universe ($O(\log m)$ items in total), and with a small pairwise intersection ($\log m$).

My question concerns with the behavior of intersections. Specifically, fix any $S_t$ in the system to consider. Consider the sets before it, $S_1,\dots,S_{t-1}$. Start with $S_1$ and find the maximal $i$ such that $|\left(\bigcup_{j=1}^i S_j\right) \cap S_t| \le a$. Let $S_1,\dots,S_i$ be the first chunk you find. Then you repeat this process starting at $S_{i+1}$ (find the second chunk). Let the total number of chunks you identify this way be $k$ (so $k$ is in general a function of $t$ and the set system).

Now, do we know anything about upper bounding $k$? (over all choices of $t$, say). The intuition is that, at least on average, it should not be the case that $k$ can always reach ${\ell \choose a}$. Do we know anything about constructing an $(\ell, a)$-design (with the above settings of parameters in general) so that one can bound $k$ in the worst-case?

Thanks in advance for any help!


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.