Strong blocking sets and minimal codes from expander graphs

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 ) (k-1) -dimensional projective space over F q F_q that have size at most c q k c q k for some universal constant c c . Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F q F_q -linear minimal codes of length n n and dimension k k , for every prime power q q , for which n ≤ c q k n ≤ c q k . This solves one of the main open problems on minimal codes.