New Upper Bounds for the Classical Ramsey Numbers $R(4,4,4)$, $R(3,4,5)$ and $R(3,3,6)$

This paper establishes new, improved upper bounds for the classical Ramsey numbers $R(4,4,4)$, $R(3,4,5)$, and $R(3,3,6)$, surpassing the previous limits derived from the standard recursive inequality.

The Gist

Imagine you are hosting a massive party, and you have a huge box of colored markers. You invite a group of people, and you ask every single pair of guests to draw a line connecting them on a giant whiteboard. But here's the catch: you tell them, "You can only use one of these three colors (Red, Blue, or Green) for your line."

The question mathematicians ask is: How many guests do you need to invite to guarantee that, no matter how they color their lines, there will inevitably be a group of four people who are all connected to each other using the same color?

This number is called a Ramsey Number. It's a measure of how much chaos (random coloring) you can have before order (a perfect, single-colored group) is forced to appear.

The Old Rulebook

For decades, mathematicians had a standard "recipe" (a formula) to guess the maximum number of guests needed. It was a bit like a rough estimate: "If you need 10 people for a Red group and 10 for a Blue group, you probably need about 20 for both."

This recipe worked well, but it wasn't perfect. It often gave answers that were slightly too high, like saying a room needs 100 chairs when it actually only needs 95. The paper you shared is about finding a way to tighten that estimate, proving that we actually need fewer people than the old recipe suggested.

The New Discovery: The "Modulo 3" Trick

The author, Luis Boza, found a clever loophole in the old recipe.

Imagine you are trying to build a tower out of blocks. The old recipe says, "You need 230 blocks to be safe." But Luis noticed something strange about the math:

1. If you try to build a tower with exactly 230 blocks, the math implies that the tower must be built in a very specific, rigid way.
2. However, the laws of physics (in this case, the laws of numbers) say that if you try to build it that way, you run into a contradiction. It's like trying to build a square circle; the math simply doesn't add up.

Luis found that for certain combinations of colors (like needing a Red group of 4, a Blue group of 4, and a Green group of 4), the old recipe's answer (230) is impossible because of a specific rule involving the number 3.

He calls this the "Modulo 3" rule. Think of it like a game of musical chairs where the number of chairs is always one less than a multiple of 3. If the math says you need a certain number of guests, but that number breaks the "3-rule," then the answer must be lower.

The New, Tighter Numbers

Using this new trick, Luis has updated the "guest list" for three specific party scenarios:

1. The "Four of Each" Party (R(4, 4, 4)):

   • Old Guess: You needed up to 230 guests to guarantee a same-colored group of 4.
   • New Reality: You only need 229.
   • Analogy: It's like realizing that if you invite 230 people, you are guaranteed a perfect group, but if you invite 229, you are also guaranteed one. The old math was just one person too generous.

2. The Mixed Party (R(3, 4, 5)):

   • Old Guess: 157 guests.
   • New Reality: Still 157.
   • Wait, didn't it change? Actually, for this specific mix, the old recipe was already as tight as it could get using the old method, but Luis proved that we can't go any lower than 157 without breaking the rules. It confirmed the limit is solid.

3. The "Three, Three, Six" Party (R(3, 3, 6)):

   • Old Guess: 92 guests.
   • New Reality: 91.
   • Analogy: Just like the first one, the old recipe overestimated the crowd size by one. We can get away with one fewer guest.

Why Does This Matter?

You might ask, "Who cares if the number is 229 or 230?"

In the world of pure math, these numbers are like the "speed limits" of the universe. Knowing the exact speed limit helps us understand the structure of reality.

• Efficiency: It saves computer scientists time. If they are running complex algorithms to check these numbers, knowing the limit is lower means they don't have to check as many possibilities.
• Pattern Recognition: It shows us that the universe of numbers has hidden patterns (like the "Modulo 3" rule) that we didn't see before. It's like finding a secret shortcut in a maze that everyone thought was a dead end.

The Big Picture

Luis Boza didn't just solve a puzzle; he handed mathematicians a new tool. He showed that for certain types of "parties" (Ramsey numbers), we can stop guessing and start proving that the answer is strictly lower than we thought.

It's a reminder that even in a field as abstract as mathematics, there are always tighter bounds to be found, and sometimes, all it takes is looking at the numbers through a slightly different lens (like checking if they are divisible by 3) to see the truth more clearly.

Technical Summary

Here is a detailed technical summary of the paper "New Upper Bounds for the Classical Ramsey Numbers R(4, 4, 4), R(3, 4, 5) and R(3, 3, 6)" by Luis Boza.

1. Problem Statement

The paper addresses the problem of determining upper bounds for classical multicolor Ramsey numbers, denoted as $R(k_1, \dots, k_r)$.

• Definition: $R(k_1, \dots, k_r)$ is the smallest integer $N$ such that any $r$-coloring of the edges of the complete graph $K_N$ contains a monochromatic clique of size $k_i$ in color $i$ for some $1 \le i \le r$.
• Current State: Exact values for Ramsey numbers with $r \ge 3$ colors are extremely scarce. The standard method for establishing upper bounds is a recursive inequality (Theorem 1.1) derived from the pigeonhole principle.
• The Gap: For decades, the best known upper bounds for $r \ge 3$ were almost exclusively derived from this standard inequality. The paper seeks to break this stagnation by finding tighter bounds that cannot be derived solely from the standard recursive formula.

2. Methodology

A. The Standard Baseline (Theorem 1.1)

The paper establishes the well-known inequality as the baseline:
$$R(k_1, \dots, k_r) \le P(k_1, \dots, k_r) = 2 - r + \sum_{i=1}^r R(k_1, \dots, k_i-1, \dots, k_r)$$
The inequality is strict if the right-hand side is even and at least one term in the sum is even. Historically, improvements over this bound have been rare (only two known cases prior to this work).

B. The Core Innovation: Modular Arithmetic and Triangle Counting

The author introduces a new criterion (Theorem 2.1) to improve the upper bound by 1 (i.e., proving $R \le P - 1$) under specific modular conditions. The methodology relies on a proof by contradiction involving graph regularity and triangle counting:

1. Assumption: Assume the Ramsey number equals the standard bound, $R = P$.
2. Graph Construction: Consider a graph $G$ with $n = P-1$ vertices that avoids monochromatic cliques of the required sizes (i.e., $G \in R(k_1, \dots, k_r; P-1)$).
3. Degree Analysis: Using Lemma 1.2, the author deduces that if $n = P-1$, the graph must be regular in specific colors. Specifically, for a chosen color $i_0$, every vertex $v$ has a fixed degree $d_{i_0}(v)$.
4. Triangle Counting:
   • The number of monochromatic triangles of color $i_0$ containing a specific vertex $v$ is calculated based on the degrees in the induced subgraph.
   • Summing over all vertices, the total count of such triangles is $(P-1) \times M$, where $M$ is the number of triangles per vertex.
   • Since each triangle is counted 3 times (once for each vertex), the total sum must be divisible by 3.
5. Modular Contradiction:
   • The author imposes conditions where $P \not\equiv 1 \pmod 3$ and specific sub-Ramsey numbers also satisfy non-congruence conditions modulo 3.
   • Under these conditions, the calculated total number of triangles is not divisible by 3.
   • This contradiction implies that a graph with $P-1$ vertices avoiding the cliques cannot exist, thereby proving $R \le P-1$.

3. Key Contributions

1. New Theoretical Criterion (Theorem 2.1): The paper provides a rigorous sufficient condition to lower the standard upper bound by 1. This condition relies on the values of the bound $P$ and related sub-Ramsey numbers modulo 3.
2. Systematic Application: The author demonstrates how to apply this criterion to specific cases where the standard recursive bounds are "tight" but potentially loose by 1.
3. Refinement of Existing Bounds: The paper clarifies that for many cases, the new bounds are direct consequences of the new theorem applied to previously known sub-bounds.

4. Key Results

The paper presents new, improved upper bounds for three specific classical Ramsey numbers:

Ramsey Number	Previous Best Bound (from Thm 1.1)	New Upper Bound	Improvement
$R(4, 4, 4)$	230	229	-1
$R(3, 4, 5)$	158	157	-1
$R(3, 3, 6)$	92	91	-1

Detailed Proofs Summary:

• For $R(4, 4, 4)$: The author shows $P_3(4) = 230$. By verifying that $P_3(4) \not\equiv 1 \pmod 3$ and that the relevant sub-number $R(3, 4, 4) = 77$ satisfies the modular conditions, Theorem 2.1 reduces the bound to 229.
• For $R(3, 4, 5)$: Similarly, $P(3, 4, 5)$ is calculated as 158. The modular conditions are met, reducing the bound to 157.
• For $R(3, 3, 6)$: $P(3, 3, 6)$ is calculated as 92. The conditions hold, reducing the bound to 91.
• Large Scale Result: The paper also derives a bound for $R(3, \dots, 3, 4)$ (10 threes and one four) as $\le 608,152,553$, improving upon the standard recursive bound of 608,152,554.

5. Significance

• Breaking the Stagnation: Since the mid-20th century, improvements to Ramsey number upper bounds for $r \ge 3$ have been exceptionally rare. This paper provides the first systematic method to improve these bounds in over a decade, adding three new entries to the list of known improvements.
• Methodological Advancement: The technique of using modular arithmetic (specifically modulo 3) combined with triangle counting arguments offers a new tool for the field. It moves beyond simple degree counting to structural constraints on the existence of specific subgraphs.
• Precision: While the improvements are numerically small (reducing the bound by 1), in the context of Ramsey theory, tightening a bound by even a single integer is a significant theoretical achievement, as it narrows the gap between known lower and upper bounds.
• Limitations: The author notes that the method is not universally applicable; for many other combinations (e.g., $R(3, \dots, 3, 5)$ for $r \le 10$), the modular conditions are not met, and no improvement over Theorem 1.1 is currently possible using this method.

In conclusion, Luis Boza's paper successfully refines the landscape of multicolor Ramsey numbers by introducing a modular constraint that forces a reduction in the standard upper bound for specific, carefully chosen parameters.