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 Fq 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 Fq-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.