Skip to main content
3 of 10
refine the typeset.
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 example 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 number of sets generated.

Xi Wu
  • 143
  • 5