Skip to main content
6 of 10
fix some presentation, and add proving lower bound as an option.
Xi Wu
  • 143
  • 5

Existence of a block design

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:
    1. $|F_1|, |F_2| \ge \beta \cdot \ell$.
    2. $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.

Easy construction 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.

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.

Xi Wu
  • 143
  • 5