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 I 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 a chunk that does not know the first $\ell/2$ elements, and the second chunk that does not know the second $\ell/2$ elements.
Construction II with smaller universe but more chunks. Let $d = O(\ell\log \ell)$. We could again group $d$ into $O(\log\ell)$ blocks each with $O(\ell)$ elements. Therefore, but choose all $O(\log \ell)$-subsets, we can generate any $\ell^{O(1)}$ sets, each of $\log\ell$ blocks with each block $\ell$ elements. Sort these sets in reverse lexicographic order according to block number, therefore we have $\log\ell$ chunks, each not covered some $\ell$ elements. Note that this works for any polynomial number of sets, but the number of chunks fails the requirement.
Therefore I would be happy to have any solution that gives $d = o(\ell^2)$, or it is proved that $d = \Omega(\ell^2)$. I would be surprised if the simple construction above is indeed optimal.