WorksMathematics
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 in the explicit construction of a strong blocking set of size in the -dimensional projective space over for every prime power .
Introduction
Strong blocking sets in projective spaces have been studied extensively in the last ten years. These objects were first introduced by Davydov et al. [18] to construct saturating sets and then reintroduced by Hégr et al. [25] to study the -analog of a classic combinatorial search problem: identifying an unknown projective point using subspace queries. Since then, these objects have been reinvented and studied under various names, such as cutting blocking sets [1, 9, 13], generating sets [19], and the now commonly used term of strong blocking sets [4, 24, 30].
The recent flurry of results is primarily motivated by a connection with coding theory that was independently discovered by Alfarano et al. [1] and Tang et al. [39]. They showed that a strong blocking set of size in a finite projective space is equivalent to a minimal -dimensional linear code of length . Minimal codes are linear codes in which the support of a nonzero codeword is a subset of the support of a nonzero codeword if and only if for some scalar . These codes have their own history dating back to 1993 in the work of Massey on secret sharing protocols [34]. Then Ashikhmin and Barg established sufficient conditions for their existence [7] which led to several interesting constructions [35] (also see [26] for minimal codes violating this condition). Recently, it was shown that minimal codes are in fact equivalent to strong blocking sets, thus converging these two threads of research. Since then, strong blocking sets and minimal codes have also found connections with perfect hashing [11] and additive combinatorics [14].
In [3], it was shown that the smallest length of a minimal code of dimension , or equivalently the smallest size of a strong blocking set in , must be at least . This lower bound was further improved in [11] and [38]. A probabilistic argument [11, 24] shows that such codes of length at most exist. One of the main problems on minimal codes is to give explicit constructions of such codes that have length at most for some constant . The main regime of interest is fixed, but possibly large, and . The first author solved this problem in collaboration with Alon, Das and Neri [4] by giving a graph-theoretic construction that combined explicit construction of asymptotically good error-correcting codes with explicit constant degree expander graphs. While for , the best constant is obtained via earlier concatenation based constructions [10], for all , the graph-theoretic construction is significantly better.
In this paper, we further optimize the graph-theoretic construction by following a similar general approach of [4] but using a better graph parameter that is fine-tuned for the geometry of finite projective spaces. This gives us a better constant for every , summarized in Table 2. For example, the best construction for was of size , while our new construction is of size at most . The key novelty of our work is the introduction of a new graph parameter for a graph that incorporates the field size by using the geometrical property that through a fixed codimension-2 space there are exactly hyperplanes. The previous graph parameter that was used in [4] is the vertex integrity of a graph, denoted by , which is independent of the field size. We show that for all graphs and , and we prove a spectral lower bound on that is much better than the best known lower bound on . This spectral lower bound on is the key source of improvement in the final optimization. From a coding-theoretic perspective, we reduce the length of the best known explicit constructions of -dimensional minimal linear codes, as the length corresponds to the size of the strong blocking set.
| Construction | Upper bound using | Upper bound using | |
| 2 | 3rd derivation | 116.43 | 117.46 |
| 3 | 2nd derivation | 74.51 | 76.38 |
| 4 | 2nd derivation | 58.22 | 58.73 |
| 5 | 2nd derivation | 52.39 | 52.59 |
| 7 | 1st derivation | 44.62 | 46.32 |
| 8 | 1st derivation | 40.23 | 41.45 |
| 9 | 1st derivation | 37.26 | 38.19 |
| 11 | 1st derivation | 33.51 | 34.09 |
| 13 | 1st derivation | 31.23 | 31.63 |
| 16 | 1st derivation | 29.11 | 29.37 |
| 17 | 1st derivation | 28.61 | 28.83 |
| 19 | 1st derivation | 27.80 | 27.97 |
| 1st derivation | 26.62 | 26.74 | |
| 1st derivation | 25.85 | 25.93 | |
| 1st derivation | 24.71 | 24.75 | |
| 1st derivation | 23.82 | 23.84 | |
| 1st derivation | 22.81 | 22.82 | |
| 1st derivation | 21.93 | 21.93 | |
| , non-square | 1st derivation | 21.93 | 21.93 |
| , square | original | 20.53 | 20.53 |
| , square | original | 20.00 | 20.00 |
Table 2. For given ranges of prime powers (First Column), this table provides the best upper bound on the size of strong blocking sets in finite projective spaces over that we have obtained in the normalized constant in front of (third column) together with an indication of which construction achieve this: Original (Theorem 5.1), 1st derivation (Theorem 5.2) or derivation. The fourth columns contains the earlier bounds obtained using the vertex integrity of a graph.
In § 2, we provide the necessary background and required notation to the reader about coding theory, projective spaces, strong blocking sets and expander graphs. In § 3, we introduce the new graph parameter and prove a spectral lower bound on this parameter for the family of -regular graphs. In § 4, we analyze the graph theoretic construction of the strong blocking set in relation to the graph parameter and its geometric implications. In § 5, we show the new results by optimize the size of strong blocking set and compare them with those previously derived by vertex integrity using algebraic-geometric codes, almost Ramanujan graphs and the tool of field reduction to handle non-quadratic fields. Finally, in § 6, we conclude the results of this paper and discuss how this new parameter can give rise to new fruitful questions and research directions.
Preliminaries
We review the basic notions from coding theory that will be used throughout the paper, with particular emphasis on minimal linear codes and their geometric interpretation. For a more detailed exposition we refer to standard references like [31] and [22].
Minimal codes and strong blocking sets
An code is a -dimensional vector subspace of with minimum Hamming distance . For a codeword , its support is given by and . The rate and relative distance of are and , respectively.
The standard problem in coding theory is to study the extremal values of one parameter with respect to the others. For a family of codes, with , the asymptotic rate and relative distance are defined as
and
An infinite family of codes is called asymptotically good if and (see [22 Section 1.8] or [31 Chapter 9]). Existence of such codes can be easily shown via a probabilistic argument [31 Section 5.1], but giving explicit constructions of such codes is highly nontrivial. Justensen gave the first explicit construction in [28]. Later, explicit constructions were found using modular curves that were even better than probabilistic constructions for all (see [17, 40, 41]).
Our main focus is on minimal codes, which we now define and discuss in detail. A nonzero codeword in a linear code is said to be minimal if the support is minimal with respect to the inclusion in the set
In a linear code, if is a minimal codeword then for any codeword we have if and only if for some scalar .
Definition 2.1. The (linear) code over a finite field is called a minimal code if all of its nonzero codewords are minimal. Equivalently, a linear code is minimal if , for all .
We now describe the equivalence between minimal codes and strong blocking sets that was discovered in [1] and [39]. Let denote the dimensional projective space defined over the vector space . We identify the points of with the -dimensional vector subspaces of and lines with the -dimensional vector subspaces. For a set of points in the projective space we denote by the span of these points, that is, the smallest dimensional projective subspace containing .
Definition 2.2. A projective system is a multiset of points, , such that (i) and (ii) .
A projective system can be viewed as a geometric representation of a nondegenerate code. By choosing representatives of the points of the system as the columns of a matrix yields a generator matrix of a nondegenerate code, that is, the row space of this matrix is an code and there are no zero columns. Conversely, the columns of a generator matrix of an arbitrary nondegenerate code define a multiset of points in that form an system.
We now introduce the main finite geometric object studied in this paper.
Definition 2.3. A set is said to be a strong blocking set if , for every hyperplane of .
Theorem 2.4 (see [1], [39]). Let be a nondegenerate code and let be any of its generator matrices. Then is a minimal code if and only if the projective system corresponding to is a strong blocking set in .
With this equivalence in mind, the natural question of studying the shortest possible length of a (linear) minimal code of dimension over translates to studying the smallest possible size of a strong blocking set in . In [3], a lower bound of the form was proved, that follows from the polynomial method. The following is the best known lower bound for this problem.
Theorem 2.5 (see [11 Theorem 1.4], [38 Theorem 3.3]). For any prime power , there is a constant such that every strong blocking set in has size at least , for large enough .
The best known existence results for the upper bounds on the size of the smallest strong blocking set have been proved via the probabilistic method for the cases when in [36] and for in [11, 2].
The key idea behind these probabilistic constructions, as well as many explicit constructions, is to consider points sets that are unions of lines in a projective space. If is the collection of lines, then their union forms a strong blocking set (of size at most ) if and only if there is no pair where is a codimension-2 subspace and is a hyperplane containing such that for all , either or is a single point contained in . These constructions often satisfy the following stronger property, synthesized in [19 Theorem 11].
Definition 2.6. A set of lines in is said to have the avoidance property if for all codimension-2 subspaces , there exists a line such that .
Theorem 2.7. If a set of lines satisfies the avoidance property, then the point-set forms a strong blocking set.
We will use this avoidance property in our construction as well.
Expander Graphs
Throughout the paper, our constructions are based on -regular expander graphs. Informally, expander graphs can be thought of as graphs whose edges are well distributed, ensuring that every vertex subset that is not too large has many outgoing edges. For formal definitions of this concept, as well as a discussion of their properties and applications in combinatorics, coding theory, and computer science, we refer the reader to [27, 5, 21].
We study expander graphs through the lens of spectral graph theory. Let a graph with vertices be a -regular graph with adjacency matrix and let the eigenvalues of its adjacency matrix be in the following decreasing order: from the largest to the smallest one.
Definition 2.8 (Expander Graph). A graph is called an -graph if it is a -regular connected graph on vertices with for all .
In our analysis, we will make use of a tight variant of the Expander Mixing Lemma. This lemma is often attributed to Alon and Chung [5], but it appears about 10 years earlier in the PhD thesis of Haemers [23].
Lemma 2.9. Let be an -graph. We set . Let . Denote by to be the number of pairs such that is an edge of , then it holds,
where is the largest absolute value of an eigenvalue other than .
It is worth noting that is the expected number of edges from to if the was a random graph formed by picking each independently with probability . We are closer to this value if is small. Thus, it is natural to make as small as possible with respect to . The Alon–Boppana bound [37] places a fundamental limitation on how small can be. It states that for any infinite family of -graphs, as . This naturally leads to the definition of Ramanujan graphs, which constitute one of the most prominent families of expander graphs.
Definition 2.10. Let a -regular graph with eigenvalues sorted as follows, . If , then is called a Ramanujan graph.
Lubotsky, Phillips and Sarnak [32] and Margulis [33] gave explicit constructions of an Ramanujan graphs for , where is a prime such that using linear algebraic groups. In general, the known constructions of Ramanujan graphs are very restrictive in their parameters. By a relaxation of the bound on , we can find constructions that works for every degree and . We will use this result instead.
Theorem 2.11 ([6], Theorem 1.3). For every positive integer , and every , there is an such that for all with to be even, there is an explicit construction of an -graph with
A new graph parameter
The previously known explicit construction of strong blocking sets that are constructed from expander graphs were based on the vertex integrity of a graph [4], § 4 (see [8] for a survey on this graph parameter). The vertex integrity, denoted as , is defined as
where is the set of connected components in the graph obtained by deleting from .
The new graph parameter that we will use is motivated by the line avoidance property Definition 2.6 that we want to guarantee and the fact that the hyperplanes through any fixed codimension-2 subspace in partition into parts. If a collection of lines does not have the avoidance property, then there exists a codimension-2 subspace such that all lines in our collection intersect . Therefore, among the hyperplanes containing , there is no pair with a line that contains a point of and a point of . We define a graph parameter that captures this property and then we prove that this new parameter is stronger than vertex integrity.
Definition 3.1. For a graph and integer , let
Remark 3.2. The definition is sensible for any integer , but for us will be a prime power and thus is a fair assumption.
Lemma 3.3. For every every graph , .
Proof. Take any subset for which it holds that and let to be disjoint sets of size with no edges between them. We can observe that for such a subset , every connected component of must be contained in one of the 's for , hence the maximum size of any connected component of is at most . Because the vertex integrity is the minimum over all subset we get that and the desired inequality follows. ∎
In [4], the authors established the following spectral lower bound on vertex integrity. For any -graph , we have that
Lemma 3.3 then implies . The following lemma gives a strictly better bound.
Lemma 3.4. For any -graph , we have that
Proof. Let be a partition of the vertex set of the graph , , such that there are no edges between the components and and . Without loss of generality, assume that the components have the following decreasing size ordering, where . Therefore, , where .
We now give a lower bound on . For the clarity of the analysis we define and . By Lemma 2.9, we get
and
for all . The upper bounds on imply
By combining Equation (4) and Equation (2) we get
To simplify the right hand side, we use to get . Therefore, we get
Dividing by , then substituting , and rearranging the equation we get
Now substitute and we are ready to prove the lower bound on , where . This gives
We now need a lower bound on in terms of the other parameters so that we can simplify this linear inequality into a lower bound on . Note that . This implies . Substituting it to Equation (5) we get
Solving for gives us the following lower bound,
Equation (1) gives a lower bound on the new parameter which is strictly better than the spectral lower bound on the vertex integrity of for all . For example, for , we get , whereas the bound on vertex integrity is always .
In the following section we compare the improvements we get in the strong blocking set constructions using this new parameter.
Strong blocking sets from graphs
In this section, we give the graph-theoretic construction from [4], which we adapt to our new graph parameter. Let be a set of points in . Let be a graph on these points. From this graph, we define the set of lines
and the set of points
By carefully choosing the set of points in and graph , we will ensure that is a strong blocking set. Note that the size of is at most . Therefore, to get such a set of size linear in , both and must be a linear function of . The following result provides a sufficient condition for the line-set to satisfy the avoidance property, which then implies that is a strong blocking set.
Lemma 4.1. Let , with such that every hyperplane contains at most points of , for some integer . Let be a graph such that . Then has the avoidance property.
Proof. Let us suppose for the sake of contradiction that the set of lines does not satisfy the avoidance property. Therefore, there exists a codimension-2 subspace such that every line contains a point of . Since is of codimension-2, there are exactly distinct hyperplanes containing , which partition the points of outside into parts. Define and let for , where is the -th hyperplane through W. Note that if a line contains two points of the subspace then it must be fully contained in it. Say, there exists an edge with and for some , and let . Since , is not fully contained in . If contains a point , then must be fully contained in both and , and thus , which is a contradiction. Therefore, there are no edges between any pair of components and for and from the definition of , we get . Since , we have for all . Therefore, , contradicting our assumption that .
Corollary 4.2. If is a projective system and is a graph with parameter , then is a strong blocking set in of size at most .
Proof. A projective system corresponds to a set of points in such that every hyperplane contains at most points of . We saw that must be a set of lines that satisfy the avoidance property, and hence is a strong blocking set of size at most .
We proceed now to the proof of the main result by giving an explicit construction of strong blocking sets in of size at most , with an improved constant than the one obtained in prior work [4].
Small explicit constructions of strong blocking sets
In this section we show how the explicit constructions via the new graph parameter that depends on the field size, can reduce the size of the explicit strong blocking sets, by using Algebraic-Geometric (AG) codes, expander graphs, and field reduction. This follows the same template given in [4] but with our new graph parameter, which then requires a new analysis and optimization of constants.
Analysis of the new parameter over quadratic fields
Our first result is obtained via a combination of Corollary 4.2 and Lemma 3.4 together with the expander graph explicit construction given by Theorem 2.11. Note that for every square prime power there exists an explicit AG-code families of rates that satisfy [40, 17], that is, we can construct an -family of codes for some increasing sequences , and .
Theorem 5.1. Let and let be a square prime power such that
and let . Then there is a strictly increasing sequence of dimensions for which we can explicitly construct strong blocking sets in of size at most
Before analyzing the proof, we show what this result implies about the size of the strong blocking set in , when is a square. We need to minimize the following function
First to simplify the analysis we substitute and then we set the derivative of the function to 0, to find a local extrema. For this we need to find the zeros of the polynomial
We can see that because we are working in the domain where while grows the roots of this polynomial converge to the roots of and the unique root is
All the other roots are either out of our domain or they are complex. So for large values of , then will be minimized for
so in that case someone should take either or now for large enough we have that: and so while tends to infinity, the optimal constant that this construction provides is
because in the fraction that appears in the leading terms cancel. In Table 1 we can see for smaller values of the computation of optimal choice of and the corresponding constant in the upper bound. Motivated by the previous analysis we are ready to prove Theorem Theorem 5.1.
| Upper bound using | Upper bound using | ||
| 9 | 264.63 | 292.68 | |
| 16 | 96.02 | 104.60 | |
| 25 | 62.60 | 66.86 | |
| 49 | 42.17 | 43.91 | |
| 64 | 37.82 | 39.07 | |
| 81 | 34.88 | 35.83 | |
| 121 | 31.15 | 31.76 | |
| 169 | 28.89 | 29.31 | |
| 26.79 | 27.06 | ||
| 24.32 | 24.44 | ||
| 22.42 | 22.46 | ||
| 20.52 | 20.52 |
Table 1. For given ranges of square prime powers , this table provides the degrees that minimize the size of strong blocking sets obtained by Theorem 5.1 and upper bounds the normalized constant in front of on the corresponding sizes (third column) and in fourth column we provide the previous bound in the normalized constant that was obtained using the graph parameter of vertex integrity.
Proof. Let be sufficiently small and we set . We have and we set also and .
Let be the -family of projective systems. Theorem 2.11 shows that there exists some for which we obtain an explicit sequence of -graphs. By the spectral bound of Eq. (1) we have that
Since , we have for sufficiently large . Then from Corollary 4.2 is a strong blocking set in . Since has edges by the handshaking lemma, we have that
Now, since the , there exists some such that for sufficiently large . After we make the substitution, and recall our choice of so the upper bound becomes.
If we choose now to be sufficiently small, we obtain the upper bound to be:
and if we recall that we get
and the result follows provided that is sufficiently small.
General construction via field reduction
We extend the construction to arbitrary prime powers by using the field reduction method from [1] and [4]. The field reduction map, denoted by , sends the points of to -dimensional -subspaces of (see [29]). For a set of lines in we select a so-called viable set [4], denoted by that consist of four points on each line of that are not contained in any -subline. It was shown in [3, 4] that if the union of a set of lines in is a strong blocking set, then is a strong blocking set in . This gives us the following result.
Theorem 5.2. Let , and let be such that
For every , there is a strictly increasing sequence of dimensions for which we can explicitly construct strong blocking sets in of size at most
Proof. Let be sufficiently small and we set . We have and we set also and . When we consider some to be an -family of projective systems, and to be a sequence of graphs. If we take to be sufficiently large then we have that . We conclude that has the avoidance property in . Therefore, by Theorem 2.7, the union of those lines forms a strong blocking set. Then by [4 Lemma 5.5], we can find a viable set for that has size at most . The set gives a strong blocking set in . Because each line in has points, this strong blocking set has size at most . We know as well that , and recalling our choices for the parameters and and setting then gives the result.
We again determine the optimal degree to use by minimizing the following quantity:
The optimum corresponds to . The asymptotically optimal degree must then be or , and after some inspection in the values we have that while .
Note that the process of derivation can be repeated by using maps for as well. This leads to a construction of strong blocking sets in of size at most
for some increasing sequence provided that .
We summarize all the results of our optimizations in Table 2, where we give the size of the smallest strong blocking sets obtained from this explicit construction.
Conclusion
We introduced a new graph parameter that incorporates the size of the finite field and used it to give improved explicit constructions of strong blocking sets. Specifically, we provide a lower bound on this new graph parameter for the family of –regular graphs that depends on both the eigenvalues of the adjacency matrix and the size of the finite filed , this deviating from the earlier work [4] that relied on a graph parameter which was independent of the field size.
In a recent preprint, Chen [15] has improved the explicit construction of strong blocking sets in for all using concatenation of codes. For the best construction is described in [14] which gives a strong blocking set of size roughly in . For the best construction can be obtained by using the trifferent code of length 24 and dimension 3 as described in [11], which gives an explicit strong blocking set of size roughly in . For , however, the strong blocking sets from Theorem 5.2 and Theorem 5.1 are smaller than those described in [15] and all previous constructions [10, 16, 15, 4].
Several directions for future work remain. Firstly, it would be nice to find a graph theoretic construction of strong blocking sets that does not require the stronger line avoidance property. Such a construction might involve a new graph parameter that further optimizes the constant and leads to a smaller explicit constructions of strong blocking sets. Second, motivated by [12], it would be interesting to extend our constructions based on the new graph parameter to strong blocking sets with respect to codimension–2 spaces. Specifically, we would like to define and analyze similar parameter for 3–uniform hypergraphs which could improve the bounds from [12]. Finally, one can try generalizing our constructions to strong -blocking sets in other ways. It would be interesting to match, or improve, the recent bounds of Guo et al. [20] using these graph-theoretic techniques on strong -blocking sets.
Acknowledgments
The work of the first author has been supported by the Dutch Research Council (NWO) through the NWO Talent Programme Vidi project “Extremal problems in finite geometry” (project number VI.Vidi.243.039).
The work of the second author has been partially supported by the MEYS of the Czech Republic under the INTER-EXCELLENCE II program (project No. LUAUS26294), the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22_008/0004590) and also supported by the Grant Agency of the Czech Technical University in Prague, grant No.SGS26/181/OHK3/3T/18. The research visit of the second author to TU Delft was supported by the Vidi grant of the first author.
Statement on software use
The authors did not use generative AI to produce any mathematical proofs or writing. WolframAlpha was used for finding minima for large values of in Table 1 and for searching for optimal values of in Table 2. Google search, that often included AI-generated overviews, was used to explore relevant literature and to obtain citation information.
References
- [1]G. N. Alfarano, M. Borello, and A. Neri. “A geometric characterization of minimal codes and their asymptotic performance”. In: Advances in Mathematics of Communications 16.1 (2022), pp. 115–133.
- [2]G. N. Alfarano, M. Borello, and A. Neri. “Outer strong blocking sets”. In: The Electronic Journal of Combinatorics 31.2 (2024), P2.18.arxiv.org/abs/2301.09590
- [3]G. N. Alfarano, M. Borello, A. Neri, and A. Ravagnani. “Three combinatorial perspectives on minimal codes”. In: SIAM Journal on Discrete Mathematics 36.1 (2022), pp. 461–489.arxiv.org/abs/2010.16339
- [4]N. Alon, A. Bishnoi, S. Das, and A. Neri. “Strong blocking sets and minimal codes from expander graphs”. In: Transactions of the American Mathematical Society 377.8 (2024), pp. 5389–5410.arxiv.org/abs/2305.15297
- [5]N. Alon and F. K. Chung. “Explicit construction of linear sized tolerant networks”. In: Discrete Mathematics 72.1–3 (1988), pp. 15–19.
- [6]Noga Alon. “Explicit expanders of every degree and size”. In: Combinatorica 41.4 (2021), pp. 447–463.arxiv.org/abs/2003.11673
- [7]A. Ashikhmin and A. Barg. “Minimal vectors in linear codes”. In: IEEE Transactions on Information Theory 44.5 (1998), pp. 2010–2017.DOI
- [8]K. S. Bagga, L. W. Beineke, W. D. Goddard, M. J. Lipman, and R. E. Pippert. “A survey of integrity”. In: Discrete Applied Mathematics 37–38 (1992), pp. 13–28.DOI
- [9]D. Bartoli, A. Cossidente, G. Marino, and F. Pavese. “On cutting blocking sets and their codes”. In: Forum Mathematicum 34.2 (2022), pp. 347–368.arxiv.org/abs/2011.11101
- [10]Daniele Bartoli and Martino Borello. “Small strong blocking sets by concatenation”. In: SIAM Journal on Discrete Mathematics 37.1 (2023), pp. 65–82.arxiv.org/abs/2109.00584
- [11]A. Bishnoi, J. D’haeseleer, D. Gijswijt, and A. Potukuchi. “Blocking sets, minimal codes and trifferent codes”. In: Journal of the London Mathematical Society 109.6 (2024), e12938.arxiv.org/abs/2301.09457
- [12]A. Bishnoi and István Tomon. “Explicit constructions of optimal blocking sets and minimal codes”. In: Combinatorica 46.2 (2026), p. 13.DOI
- [13]M. Bonini and M. Borello. “Minimal linear codes arising from blocking sets”. In: Journal of Algebraic Combinatorics 53 (2021), pp. 327–341.arxiv.org/abs/1907.04626
- [14]M. Borello, W. Schmid, and M. Scotti. “The geometry of intersecting codes and applications to additive combinatorics and factorization theory”. In: Journal of Combinatorial Theory, Series A 214 (2025), p. 106023.arxiv.org/abs/2406.04034
- [15]H. Chen. A simple explicit construction of smaller strong blocking sets. 2026. arXiv: 2610.12819 [math.CO].arxiv.org/abs/2610.12819
- [16]G. Cohen, S. Mesnager, and H. Randriam. “Yet another variation on minimal linear codes”. In: Advances in Mathematics of Communications 10.1 (2016), pp. 53–61.
- [17]A. Couvreur and H. Randriambololona. “Algebraic geometry codes and some applications”. In: Concise Encyclopedia of Coding Theory. Ed. by W. C. Huffman, J.-L. Kim, and P. Solé. Chapman and Hall/CRC, 2021, pp. 307–362.arxiv.org/abs/2009.01281
- [18]A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco. “Linear nonbinary covering codes and saturating sets in projective spaces”. In: Advances in Mathematics of Communications 5.1 (2011), pp. 119–147.arxiv.org/abs/0904.3835
- [19]S. Fancsali and P. Sziklai. “Lines in higgledy-piggledy arrangement”. In: The Electronic Journal of Combinatorics 21.2 (2014), P2.56.DOI
- [20]Z. Guo, R. Raj, C. Shangguan, and Z. Zhang. “Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets”. In: arXiv preprint arXiv:2604.13431 (2026).arxiv.org/abs/2604.13431
- [21]V. Guruswami and P. Indyk. “Expander-based constructions of efficiently decodable codes”. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE. 2001, pp. 658–667.DOI
- [22]V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft. 2022. URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/.
- [23]W. H. Haemers. “Eigenvalue Techniques in Design and Graph Theory”. PhD thesis. Eindhoven University of Technology, 1979.DOI
- [24]T. Héger and Z. L. Nagy. “Short minimal codes and covering codes via strong blocking sets in projective spaces”. In: IEEE Transactions on Information Theory 68.2 (2022), pp. 881–890.arxiv.org/abs/2103.07393
- [25]T. Héger, B. Patkós, and M. Takáts. “Search problems in vector spaces”. In: Designs, Codes and Cryptography 76.2 (2015), pp. 207–216.DOI
- [26]Z. Heng, C. Ding, and Z. Zhou. “Minimal linear codes over finite fields”. In: Finite Fields and Their Applications 54 (2018), pp. 176–196.arxiv.org/abs/1803.09988
- [27]S. Hoory, N. Linial, and A. Wigderson. “Expander graphs and their applications”. In: Bulletin of the American Mathematical Society 43.4 (2006), pp. 439–561.DOI
- [28]J. Justesen. “Class of constructive asymptotically good algebraic codes”. In: IEEE Transactions on Information Theory 18.5 (1972), pp. 652–656.DOI
- [29]M. Lavrauw and G. Van de Voorde. “Field reduction and linear sets in finite geometry”. In: Topics in Finite Fields. Ed. by G. Kyureghyan, G. L. Mullen, and A. Pott. Vol. 632. Contemporary Mathematics. American Mathematical Society, 2015, pp. 271–293.arxiv.org/abs/1310.8522
- [30]S. Lia and G. Van de Voorde. “A note on strong blocking sets and higgledy-piggledy sets of lines”. In: The Electronic Journal of Combinatorics 32.3 (2025), P3.27.arxiv.org/abs/2402.06939
- [31]J. H. van Lint. Introduction to Coding Theory. Vol. 86. Graduate Texts in Mathematics. Berlin, Heidelberg: Springer-Verlag, 1982.
- [32]A. Lubotzky, R. Phillips, and P. Sarnak. “Ramanujan graphs”. In: Combinatorica 8.3 (1988), pp. 261–277.
- [33]G. A. Margulis. “Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators”. In: Problemy Peredachi Informatsii 24.1 (1988), pp. 51–60.
- [34]J. L. Massey. “Minimal codewords and secret sharing”. In: Proceedings of the 6th joint Swedish-Russian international workshop on information theory. 1993, pp. 276–279.
- [35]S. Mesnager and A. Sinak. “Several classes of minimal linear codes with few weights from weakly regular plateaued functions”. In: IEEE Transactions on Information Theory 66.4 (2019), pp. 2296–2310.arxiv.org/abs/1808.03877
- [36]D Miklós. “Linear binary codes with intersection properties”. In: Discrete Applied Mathematics 9.2 (1984), pp. 187–196.DOI
- [37]A. Nilli. “On the second eigenvalue of a graph”. In: Discrete Mathematics 91.2 (1991), pp. 207–210.DOI
- [38]Martin Scotti. “On the lower bound for the length of minimal codes”. In: Discrete Mathematics 347.1 (2024), p. 113676.arxiv.org/abs/2302.05350
- [39]C. Tang, Y. Qiu, Q. Liao, and Z. Zhou. “Full characterization of minimal linear codes as cutting blocking sets”. In: IEEE Transactions on Information Theory 67.6 (2021), pp. 3690–3700.arxiv.org/abs/1911.09867
- [40]M. A. Tsfasman and S. G. Vlădut. Algebraic-geometric codes. Vol. 58. Springer Science & Business Media, 2013.
- [41]M. A. Tsfasman, S. G. Vlădut, and T. Zink. “Modular curves, Shimura curves, and Goppa codes, better than the Varshamov–Gilbert bound”. In: Mathematische Nachrichten 109.1 (1982), pp. 21–28.DOI