Explicit strong blocking sets and minimal codes from expander graphs using a new graph parameter
Abstract
A strong blocking set is a set of points in a finite projective space that intersects every hyperplane of the space in a spanning set of the hyperplane. These objects have been studied both in finite geometry and coding theory due to their equivalence with minimal codes. We give an explicit construction of strong blocking sets using expander graphs that improves the explicit construction of Alon et al. (Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri, Strong blocking sets and minimal codes from expander graphs. Transactions of the American Mathematical Society ) by introducing a new geometrically motivated graph parameter that is better suited for this problem. Using this approach, we improve the constant C in the explicit construction of a strong blocking set of size C (q+1) k in the $(k - 1)$-dimensional projective space over 𝔽q for every prime power q ≥ 7.
Related
- A Simple Explicit Construction of Smaller Strong Blocking Sets
- Strong and Explicit Forms of the One-Sided Nullstellensatz over Division Rings
- ETM-3D: A One-Parameter Multistable Quadratic Flow with an Explicit Absorbing Set and Intermittent Chaos
- Forgetting matters: when subspace optimization accelerates without the strong convexity parameter
- Instability of mean curvature flow in expander coordinates
BibTeX
@misc{bishnoi2026explicit,
title = {{Explicit strong blocking sets and minimal codes from expander graphs using a new graph parameter}},
author = {Anurag Bishnoi and Ioannis Kakatelis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33219},
eprint = {2610.33219},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33219},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Explicit strong blocking sets and minimal codes from expander graphs using a new graph parameter
AU - Anurag Bishnoi
AU - Ioannis Kakatelis
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33219
UR - https://arxiv.org/abs/2610.33219
AB - A strong blocking set is a set of points in a finite projective space that intersects every hyperplane of the space in a spanning set of the hyperplane. These objects have been studied both in finite geometry and coding theory due to their equivalence with minimal codes. We give an explicit construction of strong blocking sets using expander graphs that improves the explicit construction of Alon et al. (Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri, Strong blocking sets and minimal codes from expander graphs. Transactions of the American Mathematical Society ) by introducing a new geometrically motivated graph parameter that is better suited for this problem. Using this approach, we improve the constant C in the explicit construction of a strong blocking set of size C (q+1) k in the $(k - 1)$-dimensional projective space over 𝔽_q for every prime power q ≥ 7.
ER -