# DRMacIver's Notebook

Notes on Blocking Sets

Notes on Blocking Sets

Here's some stuff I'm playing with related to some problems in the combinatorics of test case reduction.

Let $X = \{1, \ldots, n\}$.

Let $S \subseteq X$ and $\pi$ be a permutation of $X$. Say $S$ starts $\pi$ if $S = \{\pi_1, \ldots, \pi_{|S|}\}$.

Let $B \subseteq \mathcal{P}(X)$. Say $B$ blocks $\pi$ if $S$ starts $\pi$ for some $S \in B$. If $B$ blocks every possible $\pi$, say it is blocking.

Lemma: Suppose $B$ is a blocking set such that $k \leq |U| \leq n - k$ for all $U \in B$. Then $|B| \geq n\choose{k}$, and this bound is tight.

Proof:

To see that the bound must be tight note that the we can choose the set of all subsets of $X$ of size $k$, and this is a blocking set of the desired size.

Suppose now that $|B| < n\choose{k}$. Pick a permutation $\pi$ uniformly at random. For each $k$, $\pi$ starts with each subset of $X$ of size $k$ with equal probability. Thus for any given subset of size $k$ the probability that $\pi$ starts with it is $\frac{1}{n\choose{k}}$. Thus the expected number of sets in $B$ that start $\pi$ is $\sum\limits_{U \in B} \frac{1}{n\choose{|U|}} \leq \frac{|B|}{n\choose{k}} < 1$.

If the expected number of sets that start $\pi$ is less than one, then the probability of it being equal to zero must be non-zero. In particular, there is some $\pi$ that does not start with any of these sets, and thus is not blocked by $B$. Therefore $B$ is not blocking.

QED

The question I'm really interested in is the following:

Say $S$ is a critical set for $B$ if $B$ is non-blocking but $B \cup \{S\}$ is blocking.

Suppose $B$ is some non-blocking set such that $|U| \geq 2$ for all $U \in B$, and suppose that $B$ has a critical set of size $2$. How small can $B$ be?

I believe the answer is that it most have at least ${n - 1}\choose{2}$ elements, but I keep failing to pin down the details.