Strong blocking sets and minimal codes from expander graphs

Abstract

A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the $(k-1)$-dimensional projective space over ${\mathbb{F}}_q$ that have size $O(qk)$. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of ${\mathbb{F}}_q$-linear minimal codes of length $n$ and dimension $k$, for every prime power $q$, for which $n=O(qk)$. This solves one of the main open problems on minimal codes.

20 pages