Explicit Constructions of Optimal Blocking Sets and Minimal Codes

Abstract A strong s -blocking set in a projective space is a set of points that intersects each codimension- s subspace in a spanning set of the subspace. We present an explicit construction of such sets in a $$(k - 1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -dimensional projective space over $$\mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math> of size $$O_s(q^s k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>O</mml:mi> <mml:mi>s</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>q</mml:mi> <mml:mi>s</mml:mi> </mml:msup> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , which is optimal up to the constant factor depending on s . This also yields an optimal explicit construction of affine blocking sets in $$\mathbb {F}_q^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> </mml:msubsup> </mml:math> with respect to codimension- $$(s+1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> affine subspaces, and of s -minimal codes. Our approach is motivated by a recent construction of Alon, Bishnoi, Das, and Neri of strong 1-blocking sets, which uses expander graphs with a carefully chosen set of vectors as their vertex set. The main novelty of our work lies in constructing specific hypergraphs on top of these expander graphs, where tree-like configurations correspond to strong s -blocking sets. We also discuss some connections to size-Ramsey numbers of hypergraphs, which might be of independent interest.