Anurag Bishnoi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Anurag Bishnoi has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Shagnik Das
Department of Mathematics, National Taiwan University, Taiwan
3 shared publications - Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
2 shared publications - Simona Boyadzhiyska
Univ Birmingham, Sch Math, Birmingham B15 2TT, England
2 shared publications - Yvonne Den Bakker
Delft Institute of Applied Mathematics, Technische Universiteit Delft, 2628 CD Delft, Netherlands
2 shared publications - Alessandro Neri
Department of Mathematics and Applications “R. Caccioppoli” University of Naples Federico II Monte Sant'Angelo Naples Italy
1 shared publication - Alessandro Neri
Ghent University Belgium
1 shared publication
Latest Publications
- Open Access
- 12 March 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (2) , 13
Explicit Constructions of Optimal Blocking Sets and Minimal Codes
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 $$\mathbb {F}_q$$ of size $$O_s(q^s k)$$ , 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$$ 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.- 12 March 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (2) , 13
Open AccessExplicit Constructions of Optimal Blocking Sets and Minimal Codes
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 $$\mathbb {F}_q$$ of size $$O_s(q^s k)$$ , 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$$ 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. - Open Access
The generalized trifference problem
We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. For $m = 1$, this is the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters.Open AccessThe generalized trifference problem
We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. For $m = 1$, this is the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. - 11 June 2024
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 377 (8) , 5389-5410
Strong blocking sets and minimal codes from expander graphs
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 ) (k-1) -dimensional projective space over F q \mathbb {F}_q that have size at most c q k c q k for some universal constant c c . Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F q \mathbb {F}_q -linear minimal codes of length n n and dimension k k , for every prime power q q , for which n ≤ c q k n \leq c q k . This solves one of the main open problems on minimal codes.
- 11 June 2024
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 377 (8) , 5389-5410
Strong blocking sets and minimal codes from expander graphs
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 ) (k-1) -dimensional projective space over F q \mathbb {F}_q that have size at most c q k c q k for some universal constant c c . Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F q \mathbb {F}_q -linear minimal codes of length n n and dimension k k , for every prime power q q , for which n ≤ c q k n \leq c q k . This solves one of the main open problems on minimal codes.
- Open Access
- 22 December 2023
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 3 (3)
Covering grids with multiplicity
Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments. Mathematics Subject Classifications: 05B40, 52C15, 05D40Keywords: Grid covering, Alon-Füredi Theorem, combinatorial geometry, linear programming- 22 December 2023
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 3 (3)
Open AccessCovering grids with multiplicity
Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments. Mathematics Subject Classifications: 05B40, 52C15, 05D40Keywords: Grid covering, Alon-Füredi Theorem, combinatorial geometry, linear programming - Open Access
Covering grids with multiplicity
Given a finite grid in $\mathbb{R}^2$, how many lines are needed to cover all but one point at least $k$ times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball--Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball--Serra and provide an asymptotic answer for almost all grids. For the standard grid $\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}$, we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.Open AccessCovering grids with multiplicity
Given a finite grid in $\mathbb{R}^2$, how many lines are needed to cover all but one point at least $k$ times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball--Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball--Serra and provide an asymptotic answer for almost all grids. For the standard grid $\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}$, we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments. - Open Access
- 1 January 2023
- Published by Masaryk University Press
- p. 19-27
Expander graphs, strong blocking sets and minimal codes
We give a new explicit construction of strong blocking sets in finite projective spaces using expander graphs and asymptotically good linear codes. Using the recently found equivalence between strong blocking sets and linear minimal codes, we give the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$ such that $n$ is at most a constant times $q k$. This solves one of the main open problems on minimal codes.- 1 January 2023
- Published by Masaryk University Press
- p. 19-27
Open AccessExpander graphs, strong blocking sets and minimal codes
We give a new explicit construction of strong blocking sets in finite projective spaces using expander graphs and asymptotically good linear codes. Using the recently found equivalence between strong blocking sets and linear minimal codes, we give the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$ such that $n$ is at most a constant times $q k$. This solves one of the main open problems on minimal codes. - Open Access
The minimum degree of minimal Ramsey graphs for cliques
We prove that $s_r(K_k) = O(k^5 r^{5/2})$, where $s_r(K_k)$ is the Ramsey parameter introduced by Burr, Erd\H{o}s and Lov\'{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.Open AccessThe minimum degree of minimal Ramsey graphs for cliques
We prove that $s_r(K_k) = O(k^5 r^{5/2})$, where $s_r(K_k)$ is the Ramsey parameter introduced by Burr, Erd\H{o}s and Lov\'{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.