Off-diagonal Ramsey Numbers From Pseudorandom Graphs

Ramsey theory is a branch of mathematics that attempts to find uniformity in sufficiently large structures. It is arguably one of the most important branches of combinatorics and has deep connections to a variety of other fields, including number theory, geometry, ergodic theory, logic, and computer science. It also finds practical applications in areas such as coding and information theory, zero-error channel capacity for noisy communication channels, computational complexity of information retrieval, and very-large-scale integration design and network visualization. Here, we discuss a recent breakthrough on a decades-old Ramsey theory problem from renowned mathematician Paul Erdős.

The quintessential introductory example is sometimes called the party problem; given any group of six individuals at a party, Ramsey theory guarantees that one can either find at least three people who all know each other, or at least three people who all do not know each other. This problem is best phrased in the mathematical language of graph theory. If we designate the party attendees as vertices, we can place a red edge between two people who know each other and a blue edge between two people who do not. Regardless of the resulting configuration of red or blue edges, we are guaranteed to find a red triangle or blue triangle: in other words, three people who all know each other or three people who do not know each other. This scenario is the first and perhaps most famous example of a quantity known as a Ramsey number.

Frank Ramsey first showed the existence of Ramsey numbers in 1930 [10]. The definition is as follows: Given any integers \(s, t \geq 2\), the Ramsey number \(r(s,t)\) is the minimum number \(N\) such that no matter how we color the pairs (red or blue) in a set of \(N\) vertices, we are guaranteed a set of \(s\) vertices between which all edges are red, or a set of \(t\) vertices between which all edges are blue. We already alluded to these uniform substructures—called monochromatic subsets—in the party example. Now, the question at hand is to determine the value of \(N = r(s,t)\). The solution to the party problem is the statement that \(r(3,3) = 6\), combined with the observation that amongst only five people, it is possible that there may not be three who all know or do not know each other (see Figure 1).

The graph in Figure 1 fails to form a red or blue triangle and therefore shows that \(r(3,3) > 5\). Unfortunately, Ramsey numbers are exceedingly difficult to determine; in fact, only a few Ramsey numbers \(r(s,t)\) for \(t \geq s \geq 3\) have been verified over the course of nearly a century (see Figure 2).

Given this difficulty, mathematicians are more concerned with estimates of Ramsey number values — especially for large values of \(s\) and \(t\). In the 1930s, Erdős and George Szekeres proved one of the first general theorems along these lines, establishing in particular that \(r(s,t) \leq t^{s - 1}\) [4]. Another success in Ramsey theory was Jeong Han Kim’s determination that

\[r(3,t) \geq a \; \frac{t^2}{\log t} \tag1\]

for some constant \(a > 0\) [5]. Together with a theorem of James B. Shearer [12], Kim’s findings demonstrate that \(r(3,t)\) is not too far from \(t^2/\log t\) when \(t\) is large. This result arose from martingale analysis of the random triangle-free process, whereby red edges—which are uniformly selected from all edges that do not complete a triangle—are individually and randomly added to a graph with no edges. The process concludes with a red graph that has no triangles; all of the missing edges are blue.

According to Figure 2, only two Ramsey numbers \(r(4,t)\) are known. As such, the next major challenge is to study the growth of \(r(4,t)\) for large values of \(t\). The first upper bound comes from the Erdős-Szekeres theorem, which implies that \(r(4,t) \leq t^3\) for \(t \geq 2\) [4]. Erdős repeatedly conjectured that \(r(4,t)\) should not be too far from \(t^3\) [3]. Decades later, Tom Bohman and Peter Keevash used the so-called random \(K_4\)-free process to show that \(r(4,t)\) is at least roughly \(t^{5/2}/\log^2\! t\) [2]. If one starts with an empty graph on \(t^{5/2}/\log^2\! t\) vertices and repeatedly adds red edges uniformly at random—conditioned on not creating a \(K_4\)—the process ends with a random \(K_4\)-free graph in which all of the missing edges are blue. The key is to prove with positive probability that no complete blue subgraph of size more than \(t\) arises. Yusheng Li, Cecil Rousseau, and Wenan Zang established that

\[r(4,t) \leq b\;\frac{t^3}{\log^2\! t}, \tag2\]

where \(b > 1\) is close to \(1\) when \(t\) is large [6]. Unfortunately, the \(K_4\)-free process seems to hit a barrier if one starts with more than \(t^{5/2}/\log^2\! t\) vertices, which is far from Erdős’ conjecture that \(r(4,t)\) is not far from \(t^3\).

To find a lower bound for Ramsey numbers \(r(s,t)\), one must create a red-blue coloring of the edges between \(N\) vertices such that no subset of size \(s\) has all red edges and no subset of size \(t\) has all blue edges; one can then conclude that \(r(s,t) > N\). For instance, \(r(4,4) > 17\) since the graph in Figure 3a has no monochromatic subsets of size four. This example, which is known as a Paley graph, was discovered in 1955 and has many remarkable properties. Furthermore, Figure 3b depicts one of the more than 30,000 examples that show \(r(4,5) > 24\). It is difficult to conduct a computer search to identify examples that give lower bounds on \(r(4,t)\) for large \(t\), as there are generally too many colorings to examine. For this reason, \(r(4,6)\) and \(r(5,5)\) are currently unknown.

However, we recently achieved a breakthrough for \(r(4,t)\) by blending a broad variety of mathematical techniques [7]. More precisely, we employed a combination of finite geometry, linear algebra, probabilistic methods, and combinatorial structural arguments to prove Erdős’ conjecture. For some constant \(c > 0\) and all \(t \geq 4\),

\[r(4,t) \geq c\;\frac{t^3}{\log^4\! t}. \tag3\]

This result is close to the upper bound \((2)\) and was inspired in part by the recent discovery that good constructions tend to hide inside so-called pseudorandom graphs, which deterministically exhibit many of the likely properties of a truly random graph with the same expected edge density [8]. If the red edges in our coloring form a pseudorandom graph with no monochromatic set of size \(s\), then random sampling of the vertices with appropriate probability will likely yield a graph with no monochromatic blue set of size \(t\). This fact relies upon the modern method of containers, which essentially demonstrates that extraordinarily few monochromatic blue sets of size \(t\) exist in such colorings [1, 11]. When applied to a carefully constructed graph that arises from finite geometry, it yields \((3)\). Specifically, one can appeal to so-called Hermitian unitals in projective planes. Let \(\mathbb F_{q}\) denote the finite field of order \(q\) and \(V\) denote the three-dimensional vector space of triples \((x,y,z)\), where \(x,y,z \in \mathbb F_{q^2}\). The points of the Hermitian unital are thus all one-dimensional subspaces of \(V\) whose generators \((x,y,z)\) satisfy

\[x^{q + 1} + y^{q + 1} + z^{q + 1} = 0. \tag4\]

Arithmetic in this equation occurs over the finite field \(\mathbb F_{q^2}\). The lines of the Hermitian unital are the sets of collinear points that satisfy the equation and combinatorially form the blocks of a design or Steiner \((q + 1)\)-tuple system. Our graph for \(r(4,t)\) has vertices that represent the lines in the Hermitian unital; here, two vertices are adjacent via a red edge if their corresponding lines intersect on the unital. Remarkably, choosing these subsets of points and lines gives rise to an incidence structure that does not contain a configuration of four pairwise nonparallel lines, with no three concurrent at a single point. Figure 4 depicts this geometry—sometimes called the O’Nan or Pasch configuration—and labels the six points where the lines intersect as \(a\) through \(f\).

Michael O’Nan was the first researcher to verify that this configuration does not occur in the Hermitian unital [9]. This implies that all monochromatic subsets with four vertices in the aforementioned graph are somewhat atypical, as they comprise at least three concurrent lines and can be easily disposed of. Furthermore, this graph enjoys good pseudorandomness properties; when combined with substantial use of the probabilistic method, such pseudorandomness allows the final graph to prove that \(r(4,t)\) is not far from \(t^3\).

Although the pseudorandom graph approach to Ramsey theory is rather recent, it provides a new and exciting point of view for classical problems in the field [8]. Specifically, it laid the foundation for the solution of a decades-old conjecture on the growth rate of \(r(4,t)\)—which purely random processes were unable to achieve—and will likely produce more results across Ramsey theory and related areas in the future. The approach also facilities the study of many additional problems that pertain to Ramsey theory, such as Erdős-Rogers functions and more general Ramsey numbers for graphs. To attack the central problem of the growth rate of \(r(s,t)\) for each \(s \geq 5\), interested researchers might wish to find higher-order geometric analogues of the aforementioned Hermitian unital.

References

[1] Balogh, J., Morris, R., & Samotij, W. (2015). Independent sets in hypergraphs. J. Amer. Math. Soc., 28(3), 669-709.
[2] Bohman, T., & Keevash, P. (2010). The early evolution of the \(H\)-free process. Invent. Math., 181(2), 291-336.
[3] Erdős, P. (1947). Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53(4), 292-294.
[4] Erdős, P., & Szekeres, G. (1935). A combinatorial problem in geometry. Compos. Math., 2, 463-470.
[5] Kim, J.H. (1995). The Ramsey number \(R(3,t)\) has order of magnitude \(t^2/\log t\). Random Struct. Alg., 7(3), 173-207.
[6] Li, L., Rousseau, C.C., & Zang, W. (2001). Asymptotic upper bounds for Ramsey functions. Graphs Combin., 17, 123-128.
[7] Mattheus, S., & Verstraete, J. (2024). The asymptotics of \(r(4,t)\). Ann. Math. To appear.
[8] Mubayi, D., & Verstraete, J. (2023). A note on pseudorandom Ramsey graphs. J. Eur. Math. Soc.
[9] O’Nan, M.E. (1972). Automorphisms of unitary block designs. J. Algebra, 20(3), 495-511.
[10] Ramsey, F.P. (1930). On a problem of formal logic. Proc. London Math. Soc., s2-30(1), 264-286.
[11] Saxton, D., & Thomason, A. (2015). Hypergraph containers. Invent. Math., 201, 925-992.
[12] Shearer, J.B. (1983). A note on the independence number of triangle-free graphs. Discrete Math., 46(1), 83-87.