Flat-containing and shift-blocking sets in \({\mathbb F}^{r}_{2}\) (Q2249144)

Let \(V\) be a finite vector space and \(d\) an integer, with \(0\leq d \leq \dim V\). A subset \(C\) of \(V\) is called \textit{\(d\)-complete} if for every vector \(v\in V\), there exists a \(d\)-subspace \(L_v\leq V\) such that \(v+(L_v\setminus \{0\}) \subseteq C\). The value \(\gamma_V(d)\) denotes the smallest possible size of a \(d\)-complete subset \(C\) of \(V\). A subset \(C\) of \(V\) is \(d\)-complete if and only if its complement \(B=V\setminus C\) has the property that for every \(v\) in \(V\), there is a \(d\)-subspace \(L_v\leq V\) with \((v+(L_v\setminus \{0\}))\cap B=\emptyset.\) A set with this property is called \textit{non-blocking}. The value \(\beta_V(d)\) denotes the largest possible size of a \(d\)-non-blocking subset \(B\) of \(V\). The two parameters \(\gamma_V(d)\) and \(\beta_V(d)\) are related via the formula \(\beta_V(d)=|V|-\gamma_V(r-d)\). The authors investigate these sets and parameters for vector spaces over the binary field. The corresponding parameters \(\beta_{\mathbb{F}_2^r}(d)\) and \(\gamma_{\mathbb{F}_2^r}(d)\), are abbreviated to \(\beta_r(d)\) and \(\gamma_r(d)\). The authors determine the values \(\gamma_r(1)\) and \(\beta_r(1)\), and consequently, also \(\gamma_r(r-1)\) and \(\beta_r(r-1)\). They also determine \(\gamma_r(2)\), up to a multiplicative factor. They present non-existence results showing that complete sets are large, and equivalently, non-blocking sets are small. They also present upper bounds on \(\gamma_r\), so equivalently, lower bounds on \(\beta_r\), by constructing specific examples of complete and non-blocking sets. The techniques involved include techniques from coding theory.