Return to Question

Thank you for the attention.

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.

• 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.

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 $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.

Misc. Comments I have a feeling that the above constructions are not optimal, though they are certainly nontrivial. The reason is that for a fixed the number of sets to generate, intuitively it holds that as we permit more chunks, the size of the forbidden sets (measured by the fraction of elements) should also go up. However, in our first construction, we have $2$ chunks, each has half elements uncovered, whereas in the second construction, the number of chunks goes to $\log\log m$, yet each now only has a $1/\log\log m$ fraction of uncovered elements. Another sign that the second construction is not optimal is that that setting of parameters simultaneously handle all $\ell^{O(1)}$ sets.

1. The universe size $d = O(\ell)$.
2. There are $\ell^2$ sets in the design, $S_1, \dots, S_{\ell^2} \subseteq [d]$.
3. $(\forall i \in [\ell^2])\ |S_i| = \ell$.
4. 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.

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:

1. The universe is $[d]$.
2. There are $m$ sets in the design, $S_1, \dots, S_m \subseteq [d]$.
3. $(\forall i \in [m])\ |S_i| = n$.
4. 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)$.

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.

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.

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.

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 $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.

Misc. Comments I have a feeling that the above constructions are not optimal, though they are certainly nontrivial. The reason is that for a fixed the number of sets to generate, intuitively it holds that as we permit more chunks, the size of the forbidden sets (measured by the fraction of elements) should also go up. However, in our first construction, we have $2$ chunks, each has half elements uncovered, whereas in the second construction, the number of chunks goes to $\log\log m$, yet each now only has a $1/\log\log m$ fraction of uncovered elements. Another sign that the second construction is not optimal is that that setting of parameters simultaneously handle all $\ell^{O(1)}$ sets.

Thank you for the attention.