Explicit Constructions of Optimal Blocking Sets and Minimal Codes
Anurag Bishnoi (TU Delft - Electrical Engineering, Mathematics and Computer Science)
István Tomon (Umeå University)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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)-dimensional projective space over Fq of size Os(qsk), which is optimal up to the constant factor depending on s. This also yields an optimal explicit construction of affine blocking sets in Fqk with respect to codimension-(s+1) 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.
help_outline