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 is a subset of with the property that for any three distinct elements of , there exists a coordinate position at which these codewords have distinct values, that is, . Let denote the largest possible size of a trifferent code of length . The exact value of is only known for (the last three values were determined by Sascha Ku ..read more

Sam Mattheus and Jacques Verstraete have posted a preprint today where they solve the classic open problem of determining the asymptotics of the Ramsey number . They show that which is just a factor of away from the upper bound. The only other off-diagonal Ramsey number for which we knew the correct asymptotics prior to their work was , and the best lower bounds on were . These earlier bounds are in fact at the limit of what could be proved using the random -free process. That barrier has finally been broken by using completely different techniques involving finite geometry! It’s an amazing ..read more

Finite geometry is often used to construct graphs with certain extremal properties. For example, the Norm graphs are one of the best-known constructions in extremal graph theory (see this for a geometrical description of these graphs). Similarly, generalized polygons, and their substructures, give various constructions in Ramsey theory, the degree-diameter problem, and the (bipartite) forbidden subgraphs problem. In this post, we will flip this direction of applications and see new constructions in finite geometry that rely on families of graphs known as constant-degree expanders. In particula ..read more

In the previous post, we saw the problem of determining the asymptotic growth of the function , which is the largest size of vector subspace , with the property that for any three distinct vectors in , there is a coordinate , such that . A code with these properties is called a linear trifferent code. Note that, , and thus it suffices to study the largest dimension of such codes. In this post, I will show that linear trifferent codes are in fact related to another well-studied notion in coding theory, minimal codes. A (linear) code is a -dimensional subspace of such that every codeword has ..read more

What is the largest possible size of a set of ternary strings of length , with the property that for any three distinct strings in , there is a position where they all differ? Let denote this largest size. Trivially, as you can take all possible ternary strings of length one. After some playing around you can perhaps prove that (I encourage you to try it so that you understand the problem). With a bit more effort and the help of a computer, you might also be able to show that , and . For example, here is a set of nine ternary strings showing that : . You should check that for any three str ..read more

Jacques Tits invented generalized polygons to give a geometrical interpretation of the exceptional groups of Lie type. The prototype of these incidence geometries already appears in his 1956 paper, while they are axiomatically defined in his influential 1959 paper on triality. The finite versions of these objects have played an important role in the study of finite simple groups and in the general the theory of permutation groups. In the 70’s and 80’s, generalized polygons also started being studied under the theory of distance regular graphs (and more broadly association schemes). The theory ..read more

Thanks to Anita Liebenau, I have recently been introduced to some very interesting questions in Ramsey theory and I have been working on them for the past few months in collaboration with various people. In my recent joint work with John Bamberg and Thomas Lesgourgues (Anita’s PhD student), that has just appeared on the arXiv, we have  proved an interesting new result in one of these problems. Before I discuss that, let’s look at some background in this post. The well known fact that in any party of six people either at least three of them are mutual strangers or at least three of th ..read more

This summer I will be one of the main mentors for a project on Ramsey numbers as a part of the Polymath REU. This is my first time being involved with this program and I am super excited about it. If you are an undergraduate student, anywhere in the world, interested in doing some mathematical research this summer, then please consider applying! The applications deadline is 1st April, 2022. Here is the link to apply ..read more

I was recently involved in making a 1 minute maths video for a contest organised by Veritasium. Here is the main requirement for the video We are looking for videos that clearly and creatively explain complex or counterintuitive concepts in the fields of Science, Technology, Engineering, and Mathematics. And, here is the final video that we uploaded some days back on Youtube: https://www.youtube.com/watch?v=WN_tQWIkeV0. This project started with Aditya Potukuchi telling me about the contest some weeks back after which we immediately started brainstorming for possible topics. I then suggested t ..read more

The recent breakthrough of Conlon and Ferber has shown us that algebraic methods can be used in combination with probabilistic methods to improve bounds on multicolour diagonal Ramsey numbers. This was already shown for the off-diagonal Ramsey numbers by Mubayi and Verstraete last year, as discussed here. Sadly, for two colours we still don’t have any improvement over the classic probabilistic bound proved by Erdős in 1947 (except for some constant factors in front of the exponential function). More concretely, we haven’t been able to prove , for any since 1947, despite considerable effort by ..read more