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.