1
$\begingroup$

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!

$\endgroup$

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.