Let $\ell$ be an integer parameter. I want to ask the existence of the following design: There is a universal constant $\beta < 1$ such that for all sufficiently large $\ell$, the following holds:
- The universe size $d = O(\ell)$.
- There are $\ell^2$ sets in the design, $S_1, \dots, S_{\ell^2} \subseteq [d]$.
- $(\forall i \in [\ell^2])\ |S_i| = \ell$.
- For every $t+1 \in [\ell^2]$, there exist $2$ disjoint subsets of $S_{t+1}$: $F_1, F_2$ (these are "forbidden" subsets), such that:
- $|F_1|, |F_2| \ge \beta \cdot \ell$.
- $S_1, \dots, S_t$ can be divided into $2$ consecutive chunks, $S_1, \dots, S_{i}$; $S_{i+1}, \dots, S_t$ such that for chunk $j \in [2]$, its intersection with $F_j$ is empty. In other words, for the first chunk, $\left( \bigcup_{j=1}^{i} S_j \right) \cap F_1 = \emptyset$, and so on.
btw. do we have a name for such block designs?
Some motivations. If we do not insist on the size of each set, then one could choose all the $2$-subsets of $[d]$, and then order them in, for example, reverse lexicographic order. Then for $S_{t+1} = \{b_1 < b_2\}$, all the sets that are lexicographically larger than it can be divided into two chunks, one that does not have $b_1$, and one that does not have $b_2$. The question I have is whether such a phenomenon still exists once we enlarge the set size while keeping (asymptotically) the same number of sets in the design.
Construction 1 with large universe. If $d = O(\ell^2)$, then there is an easy construction as well. Group $d$ into $O(\ell)$ blocks each with $\ell/2$ elements, then use the choose $2$ trick mentioned above, we have each set with $\ell$ elements, yet, the sets before any set can be split into two chunks that the first chunk does not know the first block of $\ell/2$ elements, and the second chunk that does not know the second block of $\ell/2$ elements.
Construction 2 with smaller universe but more chunks. Let $d = O(\ell\log \ell)$. We could again group $d$ into $O(\log\ell)$ blocks each with $\ell$ elements. Therefore, by choosing all the $O(\log\ell)$-subsets, we can generate any $\ell^{O(1)}$ sets, each of $O(\log\ell)$ blocks (each block has $\ell$ elements). Sort these sets in reverse lexicographic order according to the block number, then for each $S_{t+1}$ its predecessors can be decomposed into at most $O(\log\ell)$ chunks, each not covered some $\ell$ elements. Note that this works for any polynomial number of sets. However, each subset has now $O(\ell\log\ell)$ elements and there are $O(\log\ell)$ chunks.
Generalization. The tradeoff involves three things: (1) size of the universe, (2) number of elements in each set, (3) number of chunks we have. Let $k$ be another parameter which specify the number of chunks so that we have disjoint forbidden subsets $F_1, \dots, F_k$ each of size at least $\beta \cdot \ell$ and we allow to have $k$ consecutive chunks where chunk $j$ intersecting $F_j$ is empty. A more generalized definition is as follows:
A $(d, m, n, k, a)$-design satisfies the following:
- The universe is $[d]$.
- There are $m$ sets in the design, $S_1, \dots, S_m \subseteq [d]$.
- $(\forall i \in [m])\ |S_i| = n$.
- For every $t+1 \in [m]$, there exist $k$ disjoint subsets of $S_{t+1}$: $F_1, \dots, F_k$ such that
- $|F_1|, |F_2|, \dots, |F_k| \ge a$.
- $S_1, \dots, S_t$ can be divided into $k$ consecutive chunks (a chunk can be empty), so that the intersection of chunk $j \in [k]$ and $F_j$ is empty.
In term of this definition, our first construction achieves $(O(\ell^2), \ell^2, \ell, 2, \ell/2)$, and the second construction achieves $(O(\ell\log\ell), \ell^{O(1)}, O(\ell\log\ell), O(\log\ell), \ell)$.
General Question Suppose that we enforce $a = \ell$. Because forbidden sets are disjoint, thus with a worst-case guarantee of $k$ chunks, we need each set to have $n \ge k\ell$ elements. Do we have $(O(k\ell), \ell^k, k\ell, k, \ell)$ designs for all sufficiently large integer $k$? (note that for $k=O(\log\ell)$ construction 2 works, but I want to ask for constant $k$. Also, construction 1 can be used to give a $(O(\ell^2), \ell^k, k\ell, k, \ell)$.
Relaxations. Here I will describe some relaxations which already satisfy some applications in my mind. Can we have, for example, $(O(2^k\ell), \ell^k, k\ell, k, \ell)$-designs? Note that the dependence on $k$ is exponentially weaker than stated above.
Thank you for the attention.
