Ramsey numbers, polar spaces, and oddtowns

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 -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 where 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 of subsets of such that (i) every has odd cardinality, (ii) for any three distinct sets in there is a pair that shares an even number of elements. What is the largest possible size of ?

We can prove an upper bound on the size of such a family as follows. Consider the graph on sets in the family with two sets adjacent if they share an odd number of elements. Then by this graph has no triangles. Moreover, an independent set in corresponds to a classical Oddtown subfamily, and hence it has size at most . Therefore, , where is the Ramsey number of vs . But, is this bound any good?

For many months we thought that the maximum should around , 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 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 and treat them as elements of , 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 for which they can explicitly construct a nearly orthogonal set of size in .

We give an improvement to this construction by obtaining nearly orthogonal sets, and hence generalized oddtown families, of size roughy in . 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 -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 be odd. Then the dot product defines an alternating bilinear form when restricted to the even weight vectors of . Therefore, we get the so-called symplectic polar space of rank on the -dimensional vector space . Given a set of nearly orthogonal vectors in , we can look at the set of vectors where is obtained from by adding the all-one vector . Then each is in , since ‘s are of odd Hamming weight and is also odd. Moreover, the near orthogonality implies that for any three at least one of the pairs is non-orthogonal with respect to the alternating form on because for al . This set of points of the polar space that we get in is what is known as a partial -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 -ovoids: In general, an -ovoid in a polar space is a set of points that meets every generator in exactly 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 over a finite field of characteristic , there are no -ovoids when (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 such that the real rank of the matrix (which is at most one away from the rank of the complement graph) is small. Here we find a new triangle-free graph on vertices that has the binary rank equal to and nice enough eigenvalues that allows us to prove new bounds for both partial -ovoids (over ) and the Rank-Ramsey problem (over ).

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 -ovoids, where depends linearly on the rank, in polar spaces where the maximum size of a partial -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.