Anurag's Math Blog

Small complete cap sets

Posted on March 10, 2026 by Anurag Bishnoi

The following post is (partly) based on discussions with Dion Gijswijt and Ananth Ravi from September 2025.

The famous cap set problem has attracted the attention of various mathematicians from different areas over the last few decades. It asks for the largest possible size, $c(n)$ , of a 3-term arithmetic progression free subset of the abelian group $\mathbb{F}_3^n$ , or geometrically the largest size of a points set in the affine geometry $\mathrm{AG}(n, 3)$ where no three points are collinear. In 1982, Brown and Buhler gave the first non-trivial upper bound of $c(n) = o(3^n)$ . In 1995, Meshulam improved their upper bound to $c(n) = O(3^n/\log n)$ by using Fourier analytic techniques. Bateman and Katz further refined these techniques and managed to prove the upper bound of $O(3^n/n^{1 + \epsilon})$ . Then came the big breakthrough of Ellenberg and Gijswijt in 2016, who used polynomial rank arguments (building up on the work of Croot, Lev and Pach), to prove that

$c(n) = O(2.756^n)$ .

These results initiated the so-called slice rank method that has been used to make progress on several problems in combinatorics. Also see my old blog post on this topic.

In this post, I want to discuss the question of finding the smallest possible cap sets (which I will call affine caps from now on) in $\mathrm{AG}(n, 3)$ , with the obvious condition that they are maximal/complete, that is, the addition of any point to the cap gives rise to three collinear points. This was asked to me by Dion who said that he is only aware of constructions of size roughly $2^n$ , and there was a recent student thesis in Leiden that investigate small values of this function. Note that the binary vectors $\{0, 1\}$ inside $\mathbb{F}_3^n$ give a construction of size $2^n$ . The problem is also interesting from the coding theoretic perspective and it has been investigated for a long time (see this survey).

A simple counting argument shows a lower bound of roughly $3^{n/2}$ as follows.

Let $S$ be complete affine cap in $\mathrm{AG}(n, 3)$ . Then for every point outside $S$ there must be a line through that point that meets $S$ in two points. Moreover, the line joining any pair of points in $S$ gives rise to a third point outside $S$ . Therefore, $|S|(|S| - 1)/2 \geq 3^n$ .

Let $t(n)$ denote the smallest size of a complete cap in $\mathrm{AG}(n, 3)$ . We have just seen that $\sqrt{2} 3^{n/2} \leq t(n) \leq 2^n$ . Can we improve the upper bound?

This problem has been studied by finite geometers, and the question has been explicitly stated as an open problem in this paper from 2025 (see Problem 5.1) by Bence Csajbók and Zoltán Lóránt Nagy. Recently, Cassie Grace and Felipe Voloch found an elegant algebraic construction of size $O(3^{n/2})$ , thus solving the problem.

The main purpose of this post is to advertise that a solution to this problem already follows from a 2021 result of Cossidente, Csajbók, Marino, and Pavese, who constructed small complete projective caps, of size $2(q^{2n + 1} - 1)/(q - 1)$ , in the projective space $\mathrm{PG}(4n + 1, q)$ for all $q > 2$ and all positive integers $n$ . This is tight up-to a constant factor. The corresponding problem for even $q$ had long been solved (by Pambianco and Storme), but the odd cases remained open. They found a beautiful geometric construction using Veronese varieties over finite fields. However, they, and others, did not realize that for $q = 3$ their construction can also be used to construct complete affine caps of size $O(3^{n/2})$ . Here is how it works.

Projective complete caps give affine complete caps over $\mathbb{F}_3$ as follows. Let $C$ be a complete cap in the projective space $\mathrm{PG}(N -1, 3)$ , that is, a set of points such that no three points in $C$ are collinear and every point outside $C$ lies on a line that contains at least two points from $C$ . The points of $\mathrm{PG}(N - 1, 3)$ correspond to $1$ -dimensional vector subspaces of $\mathbb{F}_3^n$ and the lines correspond to $2$ -dimensional vector subspaces. Therefore, each point $\langle x \rangle$ of $C$ , where $x$ is a non-zero vector, corresponds to three affine points of $\mathrm{AG}(N, 3)$ , namely, the points $\vec{0}$ , $x$ and $-x$ . Let $S$ be the affine set obtained by taking the union of sets $\{x, -x\}$ for all $\langle x \rangle \in C$ . This is a set of size $2|C|$ in $\mathrm{AG}(N, 3)$ . I claim that $S$ must be a complete cap.

Let $x, y, z$ be three collinear points in $S$ . Then they must be pairwise linearly independent, as otherwise one of these points will have to be $\vec{0}$ which is not in $S$ . But then, we get three collinear points $\langle x \rangle, \langle y \rangle, \langle z \rangle$ in $C$ , which is a contradiction. Therefore, $S$ is an affine cap. Now let $x$ be an affine point outside $S$ in $\mathrm{AG}(N, 3)$ . If $x = \vec{0}$ , then we get the affine line $\{\vec{0}, y, -y\}$ through $x$ containing exactly two points of $S$ for every $y \in S$ . Let $x \neq \vec{0}$ . Then there exist $\langle y \rangle$ and $\langle z \rangle$ in $C$ such that the projective points $\langle x \rangle, \langle y \rangle, \langle z \rangle$ are collinear in $\mathrm{PG}(N - 1, 3)$ since $C$ is complete. Thus, the vectors $x, y, z$ are linearly dependent and hence $x = \alpha y + \beta z$ for some $\alpha, \beta \in \mathbb{F}_3 \setminus \{0\}$ . The points $-\alpha y$ and $-\beta z$ are in $S$ and we have $x + (-\alpha y) + (-\beta z) = 0$ , which implies that these three are collinear in the affine space, thus proving the completeness of the affine cap $S$ .

Now let $N = 4n + 2$ and $C$ a projective cap of size $2(3^{2n + 1} - 1)/(3 - 1) = 3^{2n + 1} - 1$ in $\mathrm{PG}(N - 1, 3)$ . Then we get an affine cap $S$ of size $2 (3^{N/2} - 1)$ in $\mathrm{AG}(N, 3)$ . This is just a factor of $\sqrt{2}$ away from the best lower bound. Also note that even though this construction only works for $N = 4n + 2$ , from any complete affine cap $S$ in $\mathrm{AG}(N, 3)$ we can get a complete cap of size $2|S|$ in $\mathrm{AG}(N + 1, 3)$ by taking $S \times \{0, 1\}$ , thus proving that in general we have a construction of size $O(3^{N/2})$ for all $N$ .

This doubling construction has long been known (see Theorem 5 in the 1999 paper of Edel and Bierbrauer), but I have not found any reference where it talks about completeness (for $q = 3$ ).

The new construction of Grace and Voloch is simpler to describe. Let $N = 4n + 2$ and let $q = 3^{2n + 1}$ . Then the set $\{(x, x^2) : x \in \mathbb{F}_q, x \neq 0\} \cup \{(x, -x^2) : x \in \mathbb{F}_q, x \neq 0\}$ in $\mathbb{F}_q^2$ can be seen as a set of points in $\mathrm{AG}(2(2n + 1), 3)$ as each element of $\mathbb{F}_q$ can be naturally identified as a $2n + 1$ dimensional vector over the base field $\mathbb{F}_3$ . This gives the required complete cap, which is also of size $2(3^{2n + 1} - 1)$ . I haven’t checked if this construction is isomorphic to the earlier construction using Veronese varieties. The construction fits the theme of `union of parabolas’ that was discussed in my last blog post and the recent work of Terry Tao where he rediscovered an old construction of non-classical unitals. Perhaps there are some more nice applications of this idea.

For $q > 3$ , the doubling construction can also be used to get an affine cap of size $2|C|$ from a projective cap $C$ , but the proof of completeness does not work as for each $\langle x \rangle \in C$ we can only pick two non-zero vectors in the space and not all of them. There are other constructions known in these cases which can asymptotically solve the problem. For example, a construction of Davydov and Östergård give a complete projective cap of the correct asymptotic size over all finite fields $\mathbb{F}_q$ with $q \geq 5$ a fixed odd prime power. It can be checked that there is a hyperplane disjoint from their cap, thus giving us a complete affine cap of size $O(q^{N/2})$ for every fixed odd $q \geq 5$ . A 2007 paper of Giulietti makes this observation and gives others construction for odd $q \geq 7$ . In fact, the affine cap is simply $\{(x, x^2): x \in \mathbb{F}_{q^{2n + 1}}\}$ , when viewed as a point set in $\mathrm{AG}(4n + 2, q)$ , which can be shown to be complete for all odd $q \geq 5$ . Therefore, this is pretty similar to the construction of Grace and Voloch.

I believe what’s really an open problem now is to find the correct constant in front of $3^{n/2}$ and then the exact value of the function $t(n)$ for all $n$ .

Posted in Extremal Combinatorics, Finite Geometry | Tagged affine caps, cap set, combinatorics, complete caps, Dion Gijswijt, extremal problems, finite fields, finite geometry, mathematics, projective caps | Leave a comment

Large induced matchings and minimal blocking sets using parabolas

Posted on March 2, 2026 by Anurag Bishnoi

In this post, I will discuss a recent breakthrough of Hunter, Pohoata, Verstraete and Zhang on an old problem in finite geometry, which also has interesting consequences outside this area. For example, it improves constructions in a minimal distance problem in $\mathbb{R}^2$ and it has been adapted by Ihringer and Zhou to give an improved construction of certain locally repairable codes.

The problem is to find large induced matchings in the bipartite incidence graph of finite projective planes. This has been studied at least since 1991, when Illés, Szőnyi and Wettl investigated these objects under the name of maximal strong representative systems, motivated by the work of Bruen and Thas from 1977 on minimal blocking sets. The point-set corresponding to the induced matching, that is, the vertices of the matching that lie on the side of points, is also called a tangency set. It has the property that through each point of the set there is a line that meets the set in exactly that point. The complement of such sets are precisely the so-called (weak) Nikodym sets over finite fields. Also see this old post of Sam Mattheus on our joint work discussing large minimal blocking sets and their generalizations.

It has long been known that there are minimal blocking sets, and hence induced matchings, of size $c p \log p$ in the projective plane of prime order $p$ , but the best upper bound is $p^{1.5} + 1$ (also see Blokhuis-Metsch) . Hunter et al. improve the lower bound from $p \log p$ to $p^{1+c}$ for some positive constant $c$ and give several applications of their construction. I will describe this particular construction from their paper, giving the necessary background and historical context. I will rephrase the construction to show its direct relation to the earlier construction of Tamás Szőnyi. Their paper contains other nice constructions as well, which I recommend reading.

A blocking set in a finite projective plane is a set of points that intersects every line non-trivially. A trivial example is the set of points on a line of the plane since any two lines meet each other, and this is known to be the smallest possible blocking set. Therefore, the focus in finite geometry has been on studying non-trivial blocking sets, that is, those that do not contain any lines in them. A blocking set is called minimal if there is no proper subset of the set that is also a blocking set. The classic result of Bruen and Thas, shows that in $\mathrm{PG}(2, q)$ , if $B$ is a non-trivial minimal blocking set, then

$q + \sqrt{q} + 1 \leq |B| \leq q \sqrt{q} + 1.$

Both of these bounds are tight when $q$ is a square. The lower bound is achieved by Baer subplanes and the upper bound by Unitals. When $q$ is not a square, and in particular when $q$ is a prime, we do not have these constructions. In fact, when $q$ is equal to a prime $p$ , Aart Blokhuis showed in 1994, using polynomial method, that the smallest size of a non-trivial blocking set is $3(p + 1)/2$ , thus settling an old conjecture of J. di Paola. Finding the largest size of a minimal blocking set $\mathrm{PG}(2, p)$ remains open.

Let $B$ be a minimal blocking set. Then for every point $lated P$ in $B$ , there must be a line $\ell_P$ such that $\ell_P \cap B = \{P\}$ , since otherwise $B \setminus \{P\}$ will also be a blocking set. We call such a line a tangent line (or $1$ -secant) at $P$ . A tangency set is a set of points such that for each point in the set there exists a tangent line through that point. Therefore, a minimal blocking set gives rise to a tangency set. A Nikodym set is a set of points $N$ in the plane such that for every point $P$ outside $N$ , there exists a line through $P$ that is completely contained in $N$ except for the point $P$ itself. Therefore, a Nikodym set is precisely the complement of a tangency set.

Looking at the incidences $(P, \ell_P)$ with $P \in B$ as edges in the bipartite incidence graph, we get an induced matching because all these lines are distinct and $P$ does not lie on $\ell_P'$ for any $P \neq P'$ . For example, in the image below we have a (trivial) minimal blocking set in the Fano plane on the left and a corresponding induced matching on the right, where we take the tangent lines to be the three sides of the triangle.

The proof of Bruen and Thas, and the one linked above using eigenvalues, can easily be adapted to these tangency sets, and hence induced matchings. This was already done by llés, Szőnyi and Wettl in their 1991 paper. Therefore, an induced matching in $\mathrm{PG}(2, q)$ has size at most $q \sqrt{q} + 1$ for all prime powers $q$ . Interestingly, this upper bound does not follow from the Hoffman bound applied to the corresponding non-oppositeness graph on the $(q^2 + q + 1)(q + 1)$ flags as this graph has eigenvalues $2q(q + 1), q\sqrt{q} - 1, 0, -q\sqrt{q} - 1$ (see Section 2.2 of this paper by Brouwer). Still, the eigenvalues of the incidence graph of $\mathrm{PG}(2, q)$ do imply the upper bound via the expander mixing lemma for bipartite graphs.

The old construction using Paley graphs: For arbitrary odd prime power $q$ , the remarkable construction of Tamás Szőnyi gives induced matchings in the incidence graph of a (Desarguesian) projective plane using independent sets in Paley graphs as follows.

We work in the affine setting of $\mathrm{AG}(2, q)$ , where each point is just a pair $(x, y) \in \mathbb{F}_q \times \mathbb{F}_q$ . Let $\mathcal{P}_a = \{(x, y) : y = x^2 + a\}$ be a parabola parametrized by an element $a$ of $\mathbb{F}_q$ . Our point-set will be a union of these parabolas for some subset $A$ of $\mathbb{F}_q$ , and the tangent lines will be tangents to these parabolas at those points. We need to ensure that for distinct $a \neq a'$ , the tangent lines to $\mathcal{P}_a$ do not contain any point of $\mathcal{P}_{a'}$ .

At point $(x_0, y_0)$ of $\mathcal{P}_a$ , the tangent line has equation $y = 2x_0 x - x_0^2 + a$ . This line intersects $\mathcal{P}_a$ in precisely $(x_0, y_0)$ . This line meets $\mathcal{P}_{a'}$ for some $a' \neq a$ if and only if the equation $x^2 + a' = 2x_0 x - x_0^2 + a$ has a solution. Rewriting the equation, we get

$(x - x_0)^2 = a - a'.$

In other words, an arbitrary line tangent to the parabola $\mathcal{P}_a$ intersects the parabola $\mathcal{P}_{a'}$ if and only if $a - a'$ is a square in $\mathbb{F}_q$ . Thus, all we need to do is pick a subset $A$ of $\mathbb{F}_q$ which has the property that the difference of any two elements of $A$ is a non-square, and we will get an induced matching of size $q |A|$ . Such subsets are precisely the independent sets in the Paley graph (assuming that $q \equiv 1 \pmod{4}$ ), and Ramsey theory implies that for any $q$ such subsets exist with size $c \log q$ for some constant $c$ . In fact, under the assumption of General Riemann Hypothesis, even larger subsets are known for infinite sequences of primes. When $q$ is a prime, it’s an extremely hard open problem in number theory to construct larger independent sets in the Paley graph. Therefore, we probably can’t improve this construction further, unless we change our perspective.

The new construction using square-difference-free sets: A subset $A$ of the integers $\{0, \dots, n\}$ is known as a square–difference–free set if $a - a'$ is not a square for all $a > a'$ in $A$ . Let us identify the elements of $\mathbb{F}_p$ with the integers $\{0, 1, \dots, p - 1\}$ . The argument above would still work as long as the modular equation $(x - x_0)^2 \equiv a - a' \pmod{p}$ is just an integer equation with no wraparounds. To ensure that, we pick a square-difference-free subset $A$ of integers $\{0, 1, \dots, \lfloor p/2 \rfloor\}$ , and let

$B = \bigcup_{a \in A} \{(x, y) : y = x^2 + a, 0 \leq x \leq \sqrt{p/2 - 1}\}.$

Then $B$ is a set of points in $\mathbb{F}_p^2$ of size roughly $|A| \sqrt{p/2}$ and we claim that the points of $B$ along with the unique tangent lines as described above give rise to an induced matching.

Suppose we have the tangent line at $(x_0, y_0) \in \mathcal{P}_a$ meeting the parabola $\mathcal{P}_{a'}$ at $(x, y)$ , with $0 \leq x_0, x \leq \sqrt{p/2 - 1}$ and $0 \leq a, a' \leq \lfloor p/2 \rfloor$ . Then we get the congruence $(x - x_0)^2 \equiv a - a' \pmod{p}$ . The left hand side is an integer which is less than or equal to $p/2 - 1$ . If $a < a'$ , then $a - a' \in \{\lceil p/2 \rceil , \dots, p - 1\}$ , which gives a contradiction. Therefore, $a > a'$ . Then we get an integer solution of $(x - x_0)^2 = a - a'$ as both sides of the congruence are integers in $\{0, 1, \dots, \lfloor p/2 \rfloor - 1\}$ , which contradicts the square-difference-free property of $A$ .

It is known that asymptotically we can pick square-difference-free sets of size roughly $n^{0.733}$ in $\{0, 1, \dots, n\}$ . This implies that we have an induced matching of size roughly $p^{1/2} (p/2)^{0.733} = \Omega( p^{1.233})$ . Thus giving us the improvement over the old construction of size $\Omega(p \log p)$ .

Concluding remarks: With a little extra work*, the construction above also gives minimal blocking set of size $\Omega(p^{1.2333})$ in $\mathrm{PG}(2, p)$ , whereas the best upper bound that we know is $p^{1.5}$ . If we could improve the upper bound to $p^{1.5 - c}$ for any constant $c$ , then this would be a massive breakthrough as the constructions above would imply that (a) the independence number of the Paley graph over $\mathbb{F}_p$ has size $O(p^{1/2 - c})$ , and (b) a square-difference-free set in $[n]$ has size at most $O(n^{1 - c})$ improving the current best upper bound on the Furstenberg-Sárközy theorem. This shows both the difficulty and the importance of the finite geometry problem of determining the largest possible size of a minimal blocking set in planes of prime order.

* this is false, as pointed out by Zach Hunter in the comments. We need a lot more work to get blocking sets, and you don’t get the same exponent of $p$ but still get one of size $p^{1 + c}$ for some constant $c > 0$ .

Posted in Combinatorics, Finite Geometry | Tagged blocking set, combinatorics, extremal problems, finite fields, finite geometry, Furstenberg–Sárközy, induced matchings, mathematics, minimal blocking sets, Nikodym sets, Paley Graphs, square-difference-free sets, Tamas Szonyi | 4 Comments

PhD and postdoc positions in Finite Geometry

Posted on December 2, 2025 by Anurag Bishnoi

I am hiring people on my NWO Vidi project. There is one PhD position (4 years) and one postdoc position (2 years) that you can apply for if you are interested. Use the following links to get more information and apply:

PhD: https://careers.tudelft.nl/job/Delft-PhD-Position-Discrete-Mathematics-Extremal-Problems-in-Finite-Geometry-2628-CD/1333394457/

Postdoc: https://careers.tudelft.nl/job/Delft-Postdoc-in-Discrete-Mathematics-Extremal-Problems-in-Finite-Geometry-2628-CD/1333394757/

Deadline: 1 February 2026.

Here are some of my recent papers that are representative of the project:

The chromatic number of finite projective spaces, with Wouter Cames van Batenburg and Ananthakrishnan Ravi. arXiv.
Ramsey numbers and extremal structures in polar spaces, with John Bamberg, Ferdinand Ihringer and Ananthakrishnan Ravi. arXiv.
Explicit constructions of optimal blocking sets and minimal codes, with István Tomon. arXiv.
Strong blocking sets and minimal codes from expander graphs, with Noga Alon, Shagnik Das, and Alessandro Neri. Transactions of the AMS, 377, 5389-5410 (2024). arXiv, journal.
Blocking sets, minimal codes, and trifferent codes, with Jozefien D’haeseleer, Dion Gijswijt and Aditya Potukuchi. JLMS, 109 (2024) . arXiv, journal.

Posted in Combinatorics, Finite Geometry, Job openings | Tagged combinatorics, extremal problems, finite geometry, Job openings, mathematics, PhD, postdoc | Leave a comment

Coloring projective spaces and Ramsey theory

Posted on December 2, 2025 by Anurag Bishnoi

What is the minimum number of colors needed to color the points of the Fano plane such that there is no monochromatic line?

It is a nice exercise to prove that two colors do not suffice. This fact has been known at least since the 1956 paper of Richardson that introduced the notion of blocking sets in projective spaces, and it commonly appears in the extremal combinatorics literature in the context of Property-B and minimal non-2-colorable hypergraphs (see for example, Section 1.3 in the notes on Probabilistic Combinatorics by Yufei Zhao). Here is a proper three-coloring of the points, which then shows that the chromatic number of $\mathrm{PG}(2,2)$ is equal to $3$ . .

Interestingly, for every larger projective plane two colors do suffice. One way to see this is to take three non-concurrent lines (a triangle), color all points on these lines except for the intersection points (vertices of the triangle) red, and every other point in the plane blue. Then each line contains at least one and at most $\max\{3, q-1\}$ red points, and thus no line is monochromatic.

Let $\chi_q(n)$ denote the smallest number of colors needed to color the points of the projective space $\mathrm{PG}(n - 1, q)$ with no monochromatic lines. In other words, $\chi_q(n)$ is the chromatic number of the hypergraph whose vertices are the $1$ -dimensional vector subspaces of $\mathbb{F}_q^n$ and edges are the $2$ -dimensional vector subspaces. We have just seen that $\chi_2(3) = 3$ and $\chi_q(3) = 2$ for all prime powers $q > 2$ . We know some other specific values as well. It was shown by Gary Ebert that the projective space $\mathrm{PG}(3, q)$ can be partitioned into $q+1$ many elliptic quadrics, that is, $q + 1$ sets of points, each of size size $q^2 + 1$ points, such that no three points in the same part are collinear. Such a partition of $\mathrm{PG}(3, 2)$ gives a proper three-coloring, and then the fact that $\chi_q(n) \geq \chi_q(n - 1)$ implies $\chi_2(4) = 3$ . It is known that $\mathrm{PG}(3, q)$ contains a non-trivial blocking set for all $q \geq 5$ , which implies $\chi_q(4) = 2$ for all $q \geq 5$ . Computationally we can show that $\chi_3(4) = \chi_4(4) = 3$ .

The binary case has been investigated by the design theory community as the lines of $\mathrm{PG}(n - 1, 2)$ form a Steiner triple system (STS). In this context, Rosa proved that $\chi_2(4) = 3$ and $\chi_2(5) = 4$ in 1970 and then in 1994 Fugère, Haddad and Wehlau proved that $\chi_2(6) = 5$ . In fact, in 1999 Haddad conjectured that $\chi_2(n) = n - 1$ for all $n \geq 4$ .

In my work with Wouter and Ananth, we solve the next open case for binary projective spaces and show that $\chi_2(7) = 5 < 6$ . We deduce this from the following general upper bound that we prove using a novel recursion combined with the base case of $\chi_2(4) = 3$ :

$\chi_2(n) \leq \lfloor 2n/3 \rfloor + 1$ .

The recursion is $\chi_2(n) \leq \chi_2(d) + \chi_2(n - d + 1) - 1$ , which improves the more general recursion of $\chi_q(n) \leq \chi_q(d) + \chi_q(n - d)$ , that we prove using quotient spaces. Therefore, the conjecture of Haddad is false for all $n \geq 7$ and $\lim_{n \rightarrow \infty} \chi_2(n)/n \leq 2/3$ .

For lower bounds, we use a natural connection between $\chi_2(n)$ and the multicolor Ramsey number for triangles $R(3; k)$ , implicitly observed by Abbot and Hanson in the setting of sum-free partitions of abelian groups in 1972. Given a proper $k$ -coloring of $\mathrm{PG}(n - 1, 2)$ define a coloring of the edges of the complete graph $K_{2^n}$ by identifying the vertices by vectors in $\mathbb{F}_2^n$ and coloring the edge joining $u$ and $v$ by the index of the part that the non-zero vector $u - v$ belongs to. This $k$ -coloring has no monochromatic triangles. Therefore,

$\chi_2(n) \leq k \implies R(3; k) > 2^n$ .

Since we know that $R(3; k) \leq e k! + 1 < 2^{k \log k}$ , where the last inequality is true for $k \geq 3$ , we get

$\chi_2(n) > n/\log n.$

We can also use this connection and our new upper bound to solve some of the new cases. For example, we get $\chi_2(7) \geq \chi_2(6) > 4$ since we know that $R(3; 4) \leq 2^6$ . Moreover, $\chi_2(7) \leq \lfloor 2 \cdot 7/3 \rfloor + 1 = 5$ , thus proving that $\chi_2(7) = \chi_2(6) = 5$ .

This connection between the chromatic number of $\mathrm{PG}(n - 1, 2)$ and the Ramsey number $R(3; k)$ opens a new direction for improving the lower bounds on $R(3; k)$ and potentially solving the famous open problem of Erdős. If we could show that $\chi_2(n) = o(n)$ then $\lim_{k \rightarrow \infty} R(3; k)^{1/k} = \infty$ . In fact, any improvements in the upper bounds on $\chi_2(n)$ directly lead to improvements on the lower bounds of $R(3; k)$ . Our arguments show that proving $\chi_2(8) \leq 5$ or $\chi_2(13) \leq 8$ would already beat the current best lower bound. Currently, these lower bounds are obtained by partitioning the abelian group $Z/mZ$ into sum-free sets, whereas we show that perhaps the group $(\mathbb{Z}/2\mathbb{Z})^n$ is a good candidate as well.

The connection between the chromatic number of finite projective spaces and Ramsey theory goes deeper than this. Ramsey numbers have been generalized to various settings, and in particular we have the vector space Ramsey number $R_q(t_1, \dots, t_k)$ , which is the smallest integer $n$ such that every coloring of the $1$ -dimensional vector subspaces of $\mathbb{F}_q^n$ using the palette $\{1, \dots, k\}$ contains a latex $t_i$ -dimensional vector subspace all of whose $1$ -dimensional subspaces have color $i$ . When $t_1 = t_2 = \cdots = t_k = t$ , we denote this number by $R_q(t; k)$ .

Geometrically, $R_q(t; k)$ is the smallest $n$ for which every $k$ -coloring of the points of $\mathrm{PG}(n - 1, q)$ contains a monochromatic $(t - 1)$ -space. Let $\chi_q(t; n)$ denote the minimum number of colors needed to color the points of $\mathrm{PG}(n - 1, q)$ with no monochromatic $(t - 1)$ -space. Then it is clear that

$\chi_q(t; n) \leq k \iff R_q(t; k) > n.$

This simple observation can be used to improve some of the bounds on these Ramsey numbers. Recently, Bryce Frederickson and Liana Yepremyan proved that $R_q(t; k)$ is bounded from above by a tower function of height $(k-1)(t-1) + 1$ and a standard probabilistic argument gives a lower bound of $R_q(t; k) = \Omega(q^t \log_q k/t)$ , for every $q,t$ . Zach Hunter and Cosmin Pohoata used the breakthrough result of Kelley and Meka to prove that for $q=t = 2$ we have the much better upper bound of $R_2(2;k) = O(k \log^7 k)$ . The above lower bound on $\chi_2(n)$ immediately gives the following:

$3k/2 < R_2(2; k) \leq \log_2(R(3;k)) + 1 \leq k \log k$

For other cases, we have been unable to prove any new upper bounds, but we do prove a general recursion of $\chi_q(t; n_1 + n_2) \leq \chi_q(t; n_1) + \chi_q(t; n_2)$ , which implies $R_q(t; k_1 + k_2) > R_q(t; k_1) + R_2(t; k_2)$ , and thus

$R_q(t; k) > (t - 1)k.$

This is much better than the probabilistic lower bounds for every fixed $q, t$ .

Returning to $t = 2$ , we can compute some more values of $\chi_q(n)$ , which give better lower bounds than this. For example, we prove $\chi_3(5) = \chi_4(5) = 3$ which gives the lower bound of $5k/3$ on $R_3(2; k)$ and $R_4(2; k)$ . We also know that $\chi_q(4) = 2$ for all $q \geq 5$ (as shown by Rajola in 1988 in the context of non-trivial blocking sets w.r.t lines), which implies $R_q(2; k) > 2k$ for $q \geq 5$ .

Our work leads to several interesting open problems. The biggest one is the following whose resolution could solve one of the oldest open problems of Erdős:

Open Problem. Is $\lim_{n \rightarrow \infty} \chi_2(n)/n = 0$ ?

Other natural open problems are improving the upper and lower bounds on $\chi_q(t; k)$ for $t > 2$ , or for $q > 2$ and $t = 2$ . This seems wide open, but I am confident that these new connections to finite geometry will soon lead to some advances.

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Ramsey Theory | Tagged blocking set, caps, chromatic number, combinatorics, extremal problems, finite fields, finite geometry, math, mathematics, ramsey, ramsey numbers, sum-free sets, vector spaces | Leave a comment

Circular Sorting

Posted on November 4, 2025 by Anurag Bishnoi

How many swaps do you need to sort $n$ objects on a circle in clockwise order?

This fairly simple and natural question quickly leads to some deep mathematics that I would like share. Let’s start with an example for $n = 6$ :

After swapping 2 with 6, 1 with 4, and then 4 with 5, we get the following `sorted’ arrangement:

It turns out that for $n = 6$ , every arrangement can be sorted in at most three moves. The natural extremal question is then to study

$t(n) :=$ max number of swaps required to sort any circular permutation of $1, 2, \dots, n$ .

This problem was very recently introduced by Adin, Alon and Roichman who proved various interesting bounds on $t(n)$ . In particular, they showed that $t(n) \leq n - 2$ for all $n$ , with equality for $n$ prime. They also made the following two conjectures.

Conjecture 1: $t(n) = n - 2$ if and only if $n$ is a prime number.

Conjecture 2: For primes $p$ , the only circular permutations that required $p - 2$ swaps to sort are the affine permutations.

An affine permutation modulo a prime number $p$ is a permutation $\pi$ of the form $\pi(x) = ax + b$ for some $a, b$ .

In my recent joint work with Paul Bastide, Carla Groenland, Dion Gijswijt, and Rohinee Joshi, we give some evidence towards Conjecture 1 by proving it for special values of $n$ , and also for some special type of permutations. Moreover, we refute Conjecture 2 by giving counterexamples for various primes. At the core of our arguments is the following result:

Definition. A permutation $\pi$ of $\mathbb{Z}_n = \{0, 1, \dots, n - 1\}$ is called a strong complete mapping if the functions $\pi(x) - x$ and $\pi(x) + x$ are permutations of $\mathbb{Z}_n$ .

Proposition. If a circular permutation $\pi$ of $\mathbb{Z}_n$ requires $n - 2$ swaps to sort, then it must be a strong complete mapping.

We use this new observation, combined with a classical result of Pólya from 1918 (who attributes the proof to Hurwitz), to prove that $t(n) \leq n - 3$ whenever $n$ is divisible by $2$ or $3$ . For disproving Conjecture 2, we found special kind of strong complete mappings known as quadratic orthomorphisms that are non-affine maps, and for specific parameters have the property that they require $n - 2$ swaps to sort. These special counterexamples exists for the following primes: 23, 31, 41, 59, 71, 83, 89, 97, 103, 113, 131, 137, 139, 149, 151, 157, 163, 173, 179, 181, 197, 199, 211, 223, 227, 239, 251, 271, 283, 293, 307, 311, 331, 347, 349, 367, 379, 383, 389, 401, 409, 419, 431, 433, 461, 467, 487, 491, 499, ….

We have not been able to extend this to an infinite sequence, as the underlying algebraic structure appears quite intricate; nonetheless, the data strongly suggest that one should exist. For $p = 23$ , an exhaustive computer search shows that these are the only counterexamples, whereas for larger primes there may be additional families.

In our paper, we give some new lower bounds like $t(pq) \geq pq - 5$ for prime $p, q$ and the tight result of $t(3p) = 3p - 3$ for all primes, using a construction based on wreath products. We also show that for all composite $n$ every permutation that can be written as a permutation polynomial, can be sorted in at most $n - 3$ swaps. Finally, we compute $t(n)$ for small values, where $t(22)$ is the smallest open case. Studying this function raises a number of interesting questions and conjectures that I hope will interest many mathematicians—and perhaps others as well.

Posted in Combinatorics, Number Theory | Tagged circular sorting, combinatorics, finite fields, math, mathematics, orthomorphisms, polynomials, strong complete mappings, wreath products | Leave a comment

Constructing blocking sets using expander graphs and hypergraphs

Posted on November 19, 2024 by Anurag Bishnoi

Blocking sets are one of the central topics in finite geometry, which was originally introduced in the context of game theory under the name of `blocking coalitions’: On Finite Projective Games. I first learned about them during my Ph.D. as a source of extremal problems that over the years as led to the development of techniques like the polynomial method and the variance trick. The latter can sometimes be replaced by spectral arguments like the expander mixing lemma, as shown here. All of these interesting methods are only used for proving lower bounds on their size (or upper bounds in case of minimal blocking sets), the constructions have always been geometrical. That changed recently, when Alessandro Neri proposed a graph-theoretical approach to constructing something known as a strong blocking set in his talk at the 2022 Combinatorics conference in Mantua. Using his initial idea, we managed to construct asymptotically optimal strong blocking sets using expander graphs in a joint work with Noga Alon and Shagnik Das (also see this blog post).

In another joint work with Jozefien D’haeseleer, Dion Gijswijt, Aditya Potukuchi, that started parallely as a project on the trifference problem, we ended up showing that strong blocking sets give rise to affine blocking sets with respect to codimension-2 subspaces, that is, sets of points in $\mathbb{F}_q^k$ that intersect every affine subspace of dimension $(k - 2)$ . We’ll refer to these sets as affine 2-blocking sets. So now we have a construction of affine 2-blocking set that is asymptotically optimal and uses expander graphs! Here is a rough sketch of the construction:

Start with a set of $O(k)$ 1-dim vector subspaces in `general position’.
Take a constant-degree expander graph with these subspaces as its vertex set.
Each edge of the graph gives a 2-dim vector subspace spanned by its vertices. Take the union of all of these 2-dim subspaces.

With the right choice of `general position’ and the correct parameters for the expander, we end up with an (explicit) affine 2-blocking set of size $O(q^2 k)$ , which is a union of $O(k)$ many 2-dim vector subspaces. This size is best possible up-to the absolute constant hidden in the $O$ notation. I encourage the reader to find a “purely geometrical” explicit construction, as I couldn’t come up with any. The only other known constructions that are of this size are probabilistic, and they have the best constant.

I doubt anyone working in finite geometry would have ever imagined such a strange construction of something as basic as an affine 2-blocking set, especially because we know that the smallest size of an affine 1-blocking set is $k(q - 1) + 1$ , and it’s achieved by the union of $k$ axes of $\mathbb{F}_q^k$ . The problem of finding the smallest size of an affine $s$ -blocking set is somehow much harder for every $s > 1$ .

In a new paper with István Tomon, we have extended the construction above to get affine $s$ -blocking sets of size $O(q^s k)$ for every constant $s > 1$ . The main idea is to define certain hypergraphs on top of these expander graphs, and then find tree-like substructures within them. The final blocking set us a union of vector subspaces whose dimensions are $\leq s$ , and it is quite intricate. Our work also has some surprising links to size-Ramsey numbers of hypergraphs.

Let’s end with a natural question in coding theory that is relevant for our construction, which I believe should be explored further:

For any constant $s$ , find an explicit construction of an infinite family of $[n, k, d]_q$ codes where both $k$ and $d$ are linear functions of $n$ and the minimum distance of the dual code is at least $s + 1$ .

Such a construction of codes corresponds to a set of $n = O(k)$ points in $\mathbb{F}_q^k$ such that any $s$ of them are linearly independent and any $\epsilon n$ of them span the whole space, which is the kind of `general position’ we need in one of our constructions. Here $\epsilon$ is the limit of $1 – d/n$.

In our paper, we used the known estimates on the dual distance of Goppa codes to find a construction for large enough $q$ ‘s but I believe that something simpler might be possible, with better parameters. It’ll help us improve the hidden constants in our construction, which is quite interesting, especially considering the fact that our constructions gives optimal $s$ -minimal codes.

Posted in Coding Theory, Finite Geometry, Ramsey Theory | Tagged affine blocking sets, blocking set, expanders, extremal problems, finite geometry, Graph Theory, Istvan Tomon, math, mathematics, Spectral Graph Theory, strong blocking sets | Leave a comment

The Rank-Ramsey problem

Posted on November 18, 2024 by Anurag Bishnoi

The Ramsey number $R(s, t)$ is the smallest $n$ such that every graph on $\geq n$ vertices either contains a clique of size $s$ or an independent set of size $t$ . Ramsey’s theorem implies that these numbers always exist, and determining them (precisely or asymptotically) has been a major challenge in mathematics for the last one century, with some amazing breakthroughs occuring in last couple of years (also see this recent paper). In this post, we’ll discuss a variation of the problem that was recently introduced by Beniamini, Linial and Shraibman, motivated by the log-rank conjecture from communication complexity.

The Rank-Ramsey number $R^{rk}(s, t)$ is the smallest $n$ such that every graph $G$ on $n$ vertices either has a clique of size $s$ or $\mathrm{rank}(A_G + I) \geq t$ , where $A_G$ is the adjacency matrix of $G$ . Since the independence number $\alpha(G)$ is always at most $\mathrm{rank}(A_G + I)$ (this is a simple exercise), we see that $R^{rk}(s, t) \leq R(s, t)$ . The Rank-Ramsey can also be rephrased as finding the smallest $\nu_d(n) = \mathrm{rank}(A_G + I)$ among all graphs on $n$ vertices that have clique number at most $d$ . Note that $n < R^{rk}(d + 1, \nu_d(n) + 1) \leq R(d + 1, \nu_d(n) + 1)$ .

In the first non-trivial case of triangle-free graphs, it was shown by Beniamini et al. that $\nu_2(n) \leq (3/8 + o(1))n$ , or in other words $R^{rk}(3, t) > (8/3 + o(1)) t$ . Compared to the best upper bound of $R^{rk}(3, t) \leq R(3, t) = O(t^2/\log t)$ , this is pretty bad, but it seems like a highly non-trivial problem to bridge the gap. While the independence number of a triangle-free graph can be as low as $\Theta( \sqrt{n \log n})$ , so far we are only able to find triangle-free graphs with $\mathrm{rank}(A + I) = \Theta(n)$ .

It might be that $\nu_2(n)$ is a linear function of $n$ , but improving the lower bounds on this number seems like a difficult problem in spectral graph theory. Since $\mathrm{rank}(A + I)$ is equal to $n$ minus the multiplicity of the eigenvalue $-1$ of the graph, to prove that $\nu_2(n) > \alpha n$ for some constant $0 < \alpha < 1$ , we will have to prove that in any triangle-free graph on $n$ vertices, the multiplicity of the eigenvalue $-1$ is always at most $(1 - \alpha) n$ . Currently we can only prove an upper bound of $n - \Theta(\sqrt{n \log n})$ on this multiplicity.

In my recent work with Bamberg, Ihringer and Ravi (my PhD student), we prove that $\nu_2(n) \leq (1/4 + o(1))$ by using a Cayley graph that comes from a finite geometric object known as a cap. While the main focus of our paper is on the binary rank of the matrix $A + I$ , where the problem has many equivalent formulations and nice connections to other extremal problems, we also looked at the real rank of this matrix and made a small improvement to the bounds on the Rank-Ramsey problem. Here is a quick description of our construction.

We first construct a Cayley graph $G_1$ over the abelian group $(\mathbb{F}_2^k, +)$ with a generating set $S \subseteq \mathbb{F}_2^k$ , such that $S$ is sum-free and the multiplicity of eigenvalue $1$ in $G_1$ is large. The sum-freeness ( $a + b \not \in S$ for all $a, b \in S$ ) ensures that $G_1$ is triangle-free, and the multiplicity ensures that $\mathrm{rank}(A_{G_1} - I)$ is small (via the Rank-Nullity theorem). After this step we take $G$ as the tensor product/Kronecker product of $G_1$ with the complete graph $K_m$ . In this graph product the clique number is at most the minimum of the two clique numbers and the eigenvalues get pairwise multiplied. Therefore, $G$ is a triangle-free graph on $2^k m$ vertices with $\mathrm{mult}_{-1}(G) = \mathrm{mult}_{1}(G) (m - 1)$ , as the multiplicity of the eigenvalue $-1$ in $K_m$ is equal to $m - 1$ .

Here is our sum-free set $S$ that was discovered by my PhD student Ananth Ravi:

Let $C$ be the complement of a $(k-2)$ -dimensional subspace inside a $(k - 1)$ -dimensional subspace $H$ of $\mathbb{F}_2^k$ and let $V$ be a $2$ -dimensional subspace in $\mathbb{F}_2^k$ that is not contained in $H$ such that $C \cap V = \{v\}$ for some non-zero vector $v$ . We define $S = (C \cup V) \setminus \{0, v\}$ .

Projectively, $S$ is a cap in $\mathrm{PG}(k - 1, 2)$ obtained by taking the largest cap $C$ in a hyperplane $H$ , removing a point from $C$ , and adding the remaining points on a line through this point that does not lie in the hyperplane.

We can be more concrete by taking specific subspaces for our construction. For example, take $S = (\{(0, 1, x_2, \dots, x_k) : x_i \in \mathbb{F}_2\} \setminus \{(0, 1, 0, \dots, 0)\}) \cup \{(1, 0, \dots, 0), (1, 1, 0, \dots, 0)\}.$

Now $G_1$ is the graph with vertex set equal to $\mathbb{F}_2^k$ and $u$ is adjacent to $v$ if $u - v \in S$ . From the character theory of finite abelian groups, we can find the eigenvalues of this Cayley graph in a combinatorial/geometric way. In particular, the eigenvalue $1$ corresponds to a hyperplane $H$ intersecting $S$ in exactly $(|S| + 1)/2$ points, and the multiplicity of this eigenvalue corresponds to the total number of such hyperplanes. From the geometric description of the set $S$ , it is fairly straightforward to calculate that $\mathrm{mult}_{1}(G_1) = 3(2^{k - 2} - 1)$ and thus $\mathrm{rank}(A_G + I) = (2^k \cdot m + 2^k \cdot 3 + 12 \cdot m - 12)/4 = (1/4 + o(1)) n$ , since $n = 2^k \cdot m$ .

It will be great to find more such constructions and improve the bound further. The major challenge though is to get a sub-linear upper bound on $\nu_2(n)$ or prove that such a bound does not exist.

Posted in Combinatorics, Ramsey Theory, Spectral Graph Theory | Tagged ananth ravi, combinatorics, extremal problems, Ferdinand Ihringer, finite fields, finite geometry, John Bamberg, math, mathematics, ramsey numbers | Leave a comment

Daisies and hypercubes

Posted on August 21, 2024 by Anurag Bishnoi

What is the smallest number $f(n, d)$ of points in the $n$ -dimensional (hyper)cube $Q_n = \{0, 1\}^n$ needed to hit every $d$ -dimensional subcube? To be clear, a subcube of dimension $d$ is obtained by fixing $n - d$ coordinates to some specific values and then letting the other $d$ coordinates vary. Therefore, in total there are $\binom{n}{d} 2^{n - d}$ copies of $Q_d$ in $Q_n$ and our set of points must intersect each of them. For example, $f(3, 2) = 2$ and an optimal construction is shown below with the red vertices of the cube hitting every face of the cube.

Instead of exact values, we are mainly interested in $\mu_d = \lim_{n \rightarrow \infty} f(n, d)/2^n$ . This natural combinatorial question has been studied by various communities under different names, and a good reference for that is the paper by Alon, Krech and Szabo, where they also prove

$\frac{\log d}{2^{d + 2}} \leq \mu_d \leq \frac{1}{d + 1}$

The upper bound is easily obtained by taking all vectors that have $k(d + 1)$ entries equal to $1$ for some non-negative integer $k$ , or equivalently, taking every $(d + 1)$ ‘st layer of $Q_n$ . The lower bound was shown by Kleitman and Spencer in 1973 where they studied the dual problem of the so-called $t$ -independent sets. In 1976, Kostochka proved that $\mu_2 = 1/3$ , thus suggesting that perhaps the upper bound is tight (which became a folklore conjecture). This belief was destroyed recently in a beautiful paper of Ellis, Ivan, and Leader, who proved that $\mu_d \leq 2^{-d/8 + o(d)}$ , and their arguments were later refined by Alon to prove that $\mu_d \leq 2^{-d/2 + o(d)}$ .

The core argument of their result is a finite geometric construction of `Daisy-free’ hypergraphs. An $r$ -Daisy, denoted by $D_r$ , is the $r$ -uniform hypergraph on $r + 2$ vertices whose edges are obtained by fixing a `stem’ of size $r - 2$ and then appending it with all pairs of vertices from the remaining four vertices. In other words, it’s the hypergraph obtaining by augmenting the edges of complete graph $K_4$ with a fixed $r - 2$ sized set. For example, $D_3$ is the hypergraph with the following $6$ edges $\{123, 124, 125, 134, 135, 145\}$ . The Turán density $\pi(D_r)$ is defined as $\lim_{n \rightarrow \infty} ex(n, D_r)/\binom{n}{r}$ , where $ex(n, H)$ is the largest number of edges that an $r$ -uniform hypergraph can have while avoiding any copies of $H$ . It was conjectured that the Turán density of $D_r$ converges to $0$ as $r \rightarrow \infty$ , and the following simple construction of Ellis, Ivan and Leader disproves that.

Let $\mathcal{B}_r$ be the hypergraph whose vertices are the non-zero vectors of $\mathbb{F}_2^r$ and edges are the bases of this vector space. Then $\mathcal{B}_r$ containes no copies of $D_r$ . Let’s prove it for $r = 3$ , where we can visualise the space as the Fano plane. The lines of the plane denote triples of points that are linearly dependent. Therefore, the edges of $\mathcal{B}_3$ are triples of points of this plane that are non-collinear.

Now let $S$ be a set of $4$ points in the Fano plane, and let $P$ be a point outside this set. There are $3$ lines through $P$ and every point is contained in at least one of them. Thus, at least one of the three lines must contain two points of $S$ . Therefore, we cannot have a copy of $D_3$ in this hypergraph. We can easily extend this argument to higher dimensions via projections or quotient spaces. This construction is on $2^r - 1$ vertices, but using blow-ups we can extend it to arbitrarily large number of vertices which finally gives us

$\pi(D_r) \geq \frac{|\mathcal{B}_r|}{\binom{2^r - 1}{r}} = \frac{(2^r - 1)(2^r - 2)(2^r - 4) \cdots (2^r - 2^{r - 1})}{(2^r - 1)(2^r - 2)(2^r - 3) \cdots (2^r - r)} > \prod_{i = 1}^r (1 - 2^{-i}),$

and it is known that this product converges to roughly $0.288$ as $r$ goes to infinity.

The same counting argument shows that the hypergraph $B_{r, q}$ consisting of the bases of $\mathbb{F}_q^r$ contains no copies of the generalized Daisy $D_r(2, q + 2)$ formed by augmenting $K_{q + 2}$ with a stem of size $r - 2$ . In general, we define $D_r(s, t)$ to be the graph obtained by augmenting a stem of size $r - s$ to the complete $s$ -uniform hypergraph on $t$ vertices.

This construction is applied to the hypercube blocking problem as follows. Firstly note that any $r$ -uniform hypergraph on $n$ vertices can be seen as a subset of the $r$ -th layer of $\{0, 1\}^n$ . We now show that the Turan density of the generalized Daisy $D_r(k + 2 \log k, 2k + 3 \log k)$ is at least $1 - 2^{-k}$ , for every (fixed) large $k$ and $r \rightarrow \infty$ . The construction here is taking all $r$ -element independent sets in $\mathbb{F}_2^{r + k}$ and then show that a Daisy with these parameters would give us $t = 2k + 3 \log k$ binary vectors in a subspace isomorphic to $\mathbb{F}_2^{s + k}$ such that every $s = k + 2 \log k$ of them are linearly independent, thus contradicting the Plotkin bound applied to the code whose parity check matrix has these $t$ vectors as its columns. Now for every large enough $r$ , in the $r$ -th layer of the hypercube $\{0, 1\}^n$ , we take the complement of this generalized Daisy-free family, and for small values of $r$ we take the whole layer. This gives us a set of roughly $2^{n - k}$ vertices in $Q_n$ that intersects every copy of $D_r(s, t)$ . Since any copy of $Q_t$ , with its base at the $r-s$ layer, must contain a copy of $D_r(s, t)$ , this set of vertices hits every $Q_t$ inside $Q_n$ , where $t = 2k + 3 \log k$ .

It’s nice to see a finite geometrical construction doing its magic in such extremal problems. It’ll be very interesting to construct other such geometrical hypergraphs for various Turan-type problems.

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry | Tagged blocking set, daisies, David Ellis, finite fields, finite geometry, hypercube, Imre Leader, Maria-Romina Ivan, Noga Alon | Leave a comment

Ramsey numbers, polar spaces, and oddtowns

Posted on June 12, 2024 by Anurag Bishnoi

I have uploaded a preprint which concludes a joint work with John Bamberg and Ferdinand Ihringer that started last year during their visit to TU Delft. In this work, we have done one of my favorite things in mathematics research: combining unrelated topics to create something new in each of them. Here is a quick description of the three topics that appear in the title of the post, and then we’ll encounter some more later, while describing the results.

Ramsey numbers: A classical subject in combinatorics where we study the smallest number of vertices in a complete graph which ensure that there is a monochromatic copy of a sub-graph (often a clique) in the specified color for every $k$ -coloring of the edges. While traditionally the probabilistic method played the major role in improving our understanding of these numbers, recently we have realized that it’s better to combine the probabilistic method with some explicit algebraic constructions. You can see some of my posts on this here.

Polar spaces: These were introduced by Jacques Tits in 1959 as natural geometrical objects to understand the structure of some classical simple groups. They capture the incidence relations between totally singular/totally isotropic subspaces with respect to a sesquilinear or a quadratic form over a vector space. Some good references for them are the notes by Peter Cameron, the notes by Akihiro Munemasa, and the book by Simeon Ball. In the last few decades, one of the main problems in finite geometry has been to understand extremal objects like ovoids, spreads and their generalizations in finite classical polar spaces. These special objects are often constructed using algebraic or geometric methods and they have nice connections to things like strongly regular graphs.

Oddtowns: In a town called the `Oddtown’ people form clubs with the property that every club has an odd number of members and any two clubs share an even number of members. Using a linear algebraic argument one can prove that the maximum number of clubs that they can form with these rules is at most the total number of people in the town. This is perhaps surprising if you consider the variation called Eventown where each club has en even number of members and any two clubs share an odd number of membets, and then the total number of clubs can be as large as $2^{n/2}$ where $n$ is the number of people. These theorems were proved by Elwyn Berlekamp in 1969 and they have been generalized in various directions. The notes of Babai and Frankl serve a good starting point for exploring them.

Here is a generalization of Oddtowns that we came up with, motivated by a problem on polar spaces that I’ll describe later. Say we have a set family $\mathcal{F}$ of subsets of $\{1, \dots, n\}$ such that (i) every $S \in \mathcal{F}$ has odd cardinality, (ii) for any three distinct sets $S_1, S_2, S_3$ in $\mathcal{F}$ there is a pair $S_i, S_j$ that shares an even number of elements. What is the largest possible size of $\mathcal{F}$ ?

We can prove an upper bound on the size of such a family $\mathcal{F}$ as follows. Consider the graph $G$ on sets in the family with two sets adjacent if they share an odd number of elements. Then by $(ii)$ this graph has no triangles. Moreover, an independent set in $G$ corresponds to a classical Oddtown subfamily, and hence it has size at most $n$ . Therefore, $|\mathcal{F}| < R(3, n + 1) \leq (1 - o(1)) n^2/\log n$ , where $R(3, n + 1)$ is the Ramsey number of $K_3$ vs $K_{n + 1}$ . But, is this bound any good?

For many months we thought that the maximum should around $4n$ , which is much lower than the upper bound, because of a nice algebraic construction we discovered along with some computational data. But that turns out to be far from the truth as was proven two years back by Golovnev and Haviv, in the language of nearly orthogonal vectors. In fact our algebraic construction already appeared in a 2000 paper of Codenotti, Pudlák, and Resta. A set of vectors in $\mathbb{F}^n$ is called nearly orthogonal if for any three of them at least one pair is orthogonal to each other, and no vector is orthogonal to itself. Here orthogonality is defined via the `standard’ dot product. If we take the characteristic vectors of sets in a family $\mathcal{F}$ and treat them as elements of $\mathbb{F}_2^n$ , then they form a nearly orthogonal set if and only if the family is a generalized Oddtown. Golovnev and Haviv proved that there exists a small positive constant $\delta$ for which they can explicitly construct a nearly orthogonal set of size $n^{1 + \delta}$ in $\mathbb{F}_2^n$ .

We give an improvement to this construction by obtaining nearly orthogonal sets, and hence generalized oddtown families, of size roughy $n^{1.12895}$ in $\mathbb{F}_2^n$ . The construction uses a Cayley graph related to the BCH codes that was also used by Alon in 1994 to give an explicit construction of (pseudorandom) triangle-free graphs with low independence numbers. More recently, this graph was used by Deng, Huang, Weng and Xiang, to solve an open problem on storage codes. In particular, they proved that the $\mathbb{F}_2$ -rank of the complement of this graph is polynomially smaller than the number of vertices, which turns out to be crucial for us. You can see the details in the preprint.

What does all of this have to do with polar spaces? For convenience, let $n = 2r + 1$ be odd. Then the dot product $\beta(x, y) = \sum x_i y_i$ defines an alternating bilinear form when restricted to the even weight vectors of $\mathbb{F}_2^n$ . Therefore, we get the so-called symplectic polar space of rank $r$ on the $2r$ -dimensional vector space $V = \{(x_1, \dots, x_n) \in \mathbb{F}_2^n : \sum x_i = 0\}$ . Given a set $\{u_1, \dots, u_k\}$ of nearly orthogonal vectors in $\mathbb{F}_2^n$ , we can look at the set $\{v_1, \dots, v_k\}$ of vectors where $v_i$ is obtained from $u_i$ by adding the all-one vector $(1, \dots, 1)$ . Then each $v_i$ is in $V$ , since $u_i$ ‘s are of odd Hamming weight and $n$ is also odd. Moreover, the near orthogonality implies that for any three $v_i, v_j, v_k$ at least one of the pairs is non-orthogonal with respect to the alternating form $\beta$ on $V$ because $\beta(u_i, u_j) = 1 + \beta(v_i, v_j)$ for al $i, j$ . This set of points of the polar space that we get in is what is known as a partial $2$ -ovoid, since it is a set of points that meets every generator in at most two points. Therefore, we get constructions and bounds for these objects as well!

Non-existence of $m$ -ovoids: In general, an $m$ -ovoid in a polar space is a set of points that meets every generator in exactly $m$ points, where a generator is just a totally singular/isotropic subspace of maximal dimension. These objects have been studied for decades and there are many nice constructions, and non-existence results. Even though the connection to nearly orthogonal sets seems to be quite specific to the binary symplectic space, the Ramsey upper bound works in general and allows us to prove that for any finite classical polar space of rank $r$ over a finite field of characteristic $p$ , there are no $m$ -ovoids when $r > m p$ (see the preprint for the more precise bound). This confirms the belief that these objects do not exist in polar spaces of `large rank’, which was previously only known for roughly half of the infinite families of polar spaces.

Rank-Ramsey problem: Finally, we also get a nice connection to the recently introduced Rank-Ramsey problem by Beniamini, Linial, and Shraibman, which was motivated by the log-rank conjecture in communication complexity. We want to construct graphs with all cliques of size at most $d$ such that the real rank of the matrix $A + I$ (which is at most one away from the rank of the complement graph) is small. Here we find a new triangle-free graph on $32$ vertices that has the binary rank equal to $10$ and nice enough eigenvalues that allows us to prove new bounds for both partial $m$ -ovoids (over $\mathbb{F}_2$ ) and the Rank-Ramsey problem (over $\mathbb{R}$ ).

I believe that these new connections can lead to many interesting results in both finite geometry and Ramsey theory. In particular, I hope that one can find explicit constructions of exponentially large partial $m$ -ovoids, where $m$ depends linearly on the rank, in polar spaces where the maximum size of a partial $1$ -ovoid is upper bounded by a linear function of the rank. That will lead to the first exponential sized explicit construction for the diagonal Ramsey numbers!

In the other direction, I hope that these graph theoretic techniques can be used to construct other interesting objects inside finite geometries. Recently, in a joint work with Noga Alon, Shagnik Das, and Alessandro Neri, we constructed the so-called strong blocking sets using expander graphs which also fits this general theme.

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Ramsey Theory, Spectral Graph Theory | Tagged BCH codes, cayley graphs, combinatorics, extremal problems, Ferdinand Ihringer, finite geometry, John Bamberg, log-rank conjecture, m-ovoids, math, mathematics, nearly orthogonal sets, oddtown, ovoids, polar spaces, ramsey numbers, Rank-Ramsey | 3 Comments

A new upper bound on the trifference problem

Posted on February 13, 2024 by Anurag Bishnoi

In a recent preprint, Siddharth Bhandari and Abhishek Khetan have improved the decades old upper bound on the trifference problem by using a clever combinatorial argument involving extremal graph theory. As discussed in my previous posts a trifferent code of length $n$ is a subset $C$ of $\{0, 1, 2\}^n$ with the property that for any three distinct elements $x, y, z$ of $C$ , there exists a coordinate position $i$ at which these codewords have distinct values, that is, $\{x_i, y_i, z_i\} = \{0, 1, 2\}$ . Let $T(n)$ denote the largest possible size of a trifferent code of length $n$ . The exact value of $T(n)$ is only known for $n \leq 9$ (the last three values were determined by Sascha Kurz recently), and thus the main focus has been on understanding the asymptotic behaviour of $T(n)$ .

The folklore upper bound is $T(n) \leq 2 (3/2)^n$ , proved in the 80s, and the only improvements it has seen are of the form $T(n) \leq c (3/2)^n$ , where the latest best constant $c = 0.6937$ follows from the work of Kurz. The new result of Bhandari and Khetan shows the following:

$T(n) \leq c' n^{-2/5} (3/2)^n.$

There are two main steps to their proof. First they show that for any subset $S$ of $\{0, 1, 2\}^n$ , we have the upper bound

$T(n) \leq T_S(n) 3^n/|S|,$

where $T_S(n)$ is the largest size of a trifferent code whose each codeword is contained inside the set $S$ . The term $T_S(n)/|S|$ can be seen as the density of a trifferent code restricted to a subset $S$ of all possible ternary strings. After this step they pick a particular subset $S$ for which they can prove good upper bounds on $T_S(n)$ .

The choice of their $S$ is the set $\Delta_3$ of all $x \in \{0, 1, 2\}^n$ for which $|\{x_i = 2: 1 \leq i \leq n | = 3$ , that is, the symbol $2$ only appears thrice in each word. For this $\Delta_3$ they define a graph on $n$ vertices and use it, with a nice application of the Kővári–Sós–Turán theorem to deduce their bound.

An easier case is $S = \Delta_2$ , where we can define the graph $G$ on $\{1, \ldots, n\}$ such that $i$ is adjacent to $j$ iff there is is a codeword $x$ with $x_i = x_j = 2$ . The number of edges in this graph is at least $T_S(n)/2$ , because for any $i, j$ there can’t be three distinct codewords $x, y, z$ such that the only positions where they have value equal to $2$ are $i$ and $j$ , otherwise these will contradict the trifference property. Therefore, it suffices to give an upper bound on the number of edges in $G$ . Bhandari and Khetan show that the graph $G$ has no subgraph isomorphic to $K_{3, 9}$ , and hence by the Kővári–Sós–Turán theorem we have $e(G) \leq C n^{5/3}$ . Therefore, we get

$T(n) \leq 2C n^{5/3} 3^n/(\binom{n}{2} 2^{n - 2}) = O(n^{-1/3} (3/2)^n).$

A more involved argument for $S = \Delta_3$ gives their main result. It’s clear from this argument that to improve the upper bound further, we should find other sets $S$ for which we can upper bound $T_S(n)$ . Potentially, this technique can also lead us to prove that $T(n) \leq C (3/2)^n/f(n)$ for any polynomial function $f$ .

Posted in Coding Theory, Extremal Combinatorics | Tagged Bhandari, combinatorics, extremal problems, Khetan, mathematics, research, trifference, trifferent, trifferent codes | Leave a comment