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)-dimensional projective space over F q that have size at most cqk for some universal constant 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-linear minimal codes of length n and dimension k , for every prime power q , for which n <= cqk . This solves one of the main open problems on minimal codes.