Mathematicians recently gathered for a workshop in Canadaa to thrash out ideas inspired by a breakthrough a pair of researchers made in 2023 on a conjecture by Paul Erdős. The pair’s success at applying a novel combination of approaches to a problem that saw little progress in four decades looks to have larger implications in an area of mathematics that looks at how order forms out of random systems, and which also has proven influential for both practical and theoretical computer science.
“As soon as the paper appeared, we realized the need to organize something like this workshop,” said Anurag Bishnoi, assistant professor of mathematics at the Technical University of Delft in The Netherlands.
The conjecture tackled by Sam Mattheus, a postdoctoral researcher at Vrije University in Brussels, and Jacques Verstraete, a professor of mathematics at the University of California at San Diego, comes from a line of work that dates back almost a century to a proof produced by British logician Frank Ramsey. It showed that, in a party of six people, you could guarantee either three of them would have met before or that three would be strangers to each other.
The path to that original proof lay in the different ways it is possible to use two colors to draw all the possible lines between six nodes in a graph. Red lines, or edges in graph-theory terminology, might denote acquaintances. Blue would mean strangers. There is no way to color this graph that does not lead to at least one triangle of red or blue emerging from the otherwise seemingly random graph. But if you take one vertex away to reduce the total to five, and the certainty of such a triangle disappears.
As the number of nodes or vertices in a graph increases, larger structures appear. Similar patterns emerge in lists of numbers. Dutch mathematician and historian Bartel Leendert van der Waerden proved you can guarantee arithmetic patterns forming within lists of random integers. Determining the point at which these ordered structures become inevitable within random patterns as the number of vertices grows is the core of what mathematicians call Ramsey theory. However, they have found it extremely difficult to find the thresholds at which certain choices of pattern become inevitable for all but the smallest arrangements.
Consider the number of vertices in a graph that will guarantee a red or blue pentagon, denoted r(5,5). The precise threshold remains unknown, though proofs show it as lying between 43 and 48. In the early 1990s, Erdős said he could see a brute-force search for the precise Ramsey number completed in a year with huge amounts of computer power thrown at the problem. Yet he considered that r(6,6) would remain practically impossible.
Mathematicians have continued to try to tighten the bounds for individual problems within Ramsey theory. This is often because of the opportunity they offer for exploring novel ways to build proofs.
“In my view, knowing the exact value of a particular van der Waerden or Ramsey number does not change much in our understanding of Ramsey theory,” said Veselin Jungić, teaching professor in mathematics at Simon Fraser University, British Columbia, Canada. “Establishing such a number is a very difficult problem on its own merit and that is what attracts mathematicians and computing scientists.”
A long list of Ramsey-theory conjectures posed by Erdős and others over the past century has provided mathematicians with plenty to attack. Mattheus and Verstraete achieved their breakthrough tackling one that had not seen progress for four decades, and which is subtly different to that of classic Ramsey numbers. This was to find the upper bounds of “off-diagonal” Ramsey numbers. One example of such a case is r(3,t). This describes a graph that is guaranteed to contain either a set of edges arranged in a triangular “clique” of one color or a clique of a different, and potentially much larger size, in the other color.
Until recently, the proofs for this kind of problem revolved around techniques pioneered by Erdős and colleagues decades earlier. These methods use probabilities to indicate when a graph is highly likely to contain one of the target cliques. Clever deployment of mathematical axioms within this framework makes it possible to develop bounds that are not ridiculously large. The ideas proved not only successful for close to a century, but also helped show the power of randomness in algorithms.
William Gasarch, a professor of computer science at the University of Maryland, points to the use of probabilistic methods for network routing, as well as for more fundamental elements of theoretical computer science. Using these techniques, routing algorithms make random choices within a group of nodes and avoid the need to search the network exhaustively for a perfect structure. Other examples of applied Ramsey-theory principles followed a paper by Andrew Yao at Stanford University in the early 1980s. This work determined how big a table of data needs to be before its rows should be sorted to prevent a slowdown in access times.
However, in mathematics, the limitations of the purely probabilistic method have encouraged a change in tactics. Switching to graphs based on explicit rules that prevent certain cliques from forming up the threshold where they become impossible to avoid, should work better than purely random processes.
More than 30 years ago, Princeton University mathematics professor Noga Alon showed a successful technique for creating triangle-free graphs deterministically. The problem researchers face is there is no reliable way of achieving the same guarantee for larger graphs. Random generation remains more efficient.
Verstraete worked with Dhruv Mubayi, a professor of mathematics at the University of Illinois, on a paper published several years ago that showed how regular graphs that share important characteristics with random graphs provide a better starting point. The most important characteristic lies in the distribution of edges of these pseudorandom graphs.
“The work implied a lower bound on Ramsey numbers. But that construction is not good enough to prove any new bounds,” said Bishnoi.
The key to the most recent work has been to combine some pseudorandom starting structures and then apply random techniques that use the framework of finite geometry. Unlike Euclidean geometry where space is continuous, any shape in finite geometry must fit on a limited set of points on a discrete grid. These and other characteristics provide axioms mathematicians can use to eliminate various configurations of vertices and edges. Bishnoi uses the analogy of orthogonal vectors in a three-dimensional Euclidean space; it is easy to guarantee that only three vectors would be orthogonal to each other in such a space. Any additional vectors cannot be orthogonal to all the others.
Mattheus and Verstraete found tools in such a finite-geometry space to work on the bounds for r(4,t). They showed how they could use them to remove any four-vertex cliques from their initial pseudorandom graph and from that constructed a proof that showed how the upper bound would grow as t increases. According to Gasarch, this new proof followed around a decade after the last improvement made for the bounds of r(3,t). “It was thought any progress on r(4,t) would take much longer and be much harder,” he said.
Mathematicians aim to continue trying to apply the tools of finite geometry to Ramsey-theory problems. At a seminar in the late spring of 2024 organized by the University of Oxford, Verstraete explained how he and colleagues could extend the work to similar problems. They also set about trying to find a construct in finite geometry that would eliminate five-vertex cliques in a path towards the bounds of larger off-diagonal Ramsey numbers. September’s workshop in Banff, Alberta will provide an opportunity for a larger group of mathematicians working in Ramsey theory to tap experience in finite geometry and other areas such as coding theory and algebraic geometry. The mathematicians involved see important crossovers with the work going on in those fields as well as in Ramsey theory.
Bishnoi said the value of a face-to-face workshop that collects people from different fields in mathematics is that it can bring to the surface ideas that never made it into the published literature. “There is so much unpublished work. People are too self-critical. Often, they have a good idea but feel it is not good enough for a paper. When you talk to people you learn so much,” Bishnoi explained.
The cross-pollination that results from this effort could provide a boost to many Ramsey-theory problems that have remained stuck for years, not least because it is drawing in more researchers from different specialties.
“One of the reasons that Ramsey theory attracts so many smart people, in my view, is that it opens the space for new and frequently unexpected applications of techniques that come across different mathematical fields. And we are for sure not done in witnessing how Ramsey theory unites the mathematical community regardless of their primary research interests,” Jungić explained.
An open question is the degree to which these new approaches might be harnessed by fields such as computer science, as well as other branches of mathematics. The experience with the probabilistic method developed for the first wave of Ramsey theory led to a wide variety of algorithms. Access to a new collection of tools may have a similar effect across key parts of theoretical computer sciences. Said Gasarch, “I am optimistic. Why? Since r(4,t) used finite geometries, it is bringing more tools into combinatorics, which is close to complexity theory.”
Further Reading
- Mattheus, S., and Verstraete, J.
The Asymptotics of r(4,t), Annals of Mathematics, Vol 199 (2024), Issue 2. arXiv:2306.04007 - Mubayi, D., and Verstraete, J.
A Note on Pseudorandom Ramsey Graphs, Journal of the European Mathematical Society, 26 (2024), no. 1, pp. 153–161 - Rosta, V.
Ramsey Theory Applications, Electronic Journal of Combinatorics, Dynamic Surveys (2004) - Bishnoi, A.
Finite Geometry and Ramsey Theory, Course Notes: https://anuragbishnoi.wordpress.com/wp-content/uploads/2021/01/minicourse.pdf
Join the Discussion (0)
Become a Member or Sign In to Post a Comment