Strong blocking sets and minimal codes from expander graphs

Journal Article (2024)
Author(s)

Noga Alon

Anurag Bishnoi (TU Delft - Discrete Mathematics and Optimization)

Shagnik Das

Alessandro Neri (Student TU Delft)

Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.1090/tran/9205
More Info
expand_more
Publication Year
2024
Language
English
Research Group
Discrete Mathematics and Optimization
Bibliographical Note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. @en
Issue number
8
Volume number
377
Pages (from-to)
5389-5410
Reuse Rights

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

Files

Tran9205.pdf
(pdf | 0.316 Mb)
- Embargo expired in 30-12-2002
License info not available