Ramsey lower bounds for bounded degree hypergraphs

This paper establishes the first lower bound of the form $r(H) \geq \tw_{k-1}(c_k \Delta) \cdot n$ for the Ramsey number of $k$-uniform hypergraphs with maximum degree $\Delta$, marking initial progress toward a conjecture by Conlon, Fox, and Sudakov that such bounds should reach the tower height of $k$.

The Gist

Imagine you are hosting a massive party where every guest is a vertex in a giant network. The "edges" of this network are groups of friends hanging out together (specifically, groups of $k$ people). You have a huge supply of red and blue party hats. Your goal is to hand out these hats to the edges (the groups) in such a way that no single group of friends ends up wearing all the same color hat.

In the world of mathematics, this is called a Ramsey problem. The question is: How big does your party need to be before it becomes impossible to avoid having at least one group of friends all wearing red hats, or all wearing blue hats?

This number—the size of the party where you must have a monochromatic group—is called the Ramsey number.

The Big Problem: How Fast Does the Party Need to Grow?

For a long time, mathematicians knew that for very complex networks (called hypergraphs), the party size needed to be astronomically huge. It grows like a "tower of numbers."

• If you have 3 people in a group, the party size might need to be a tower of 2s that is 3 levels high.
• If you have 4 people in a group, the tower is 4 levels high.
• And so on.

However, there was a nagging question: What if the guests at the party aren't allowed to have too many connections?
Imagine a rule: "No guest can be part of more than $\Delta$ groups." (This is called "bounded degree").

• For simple pairs of people (graphs), we knew that if everyone has a limited number of friends, the party size only needs to grow linearly (a straight line).
• But for groups of 3 or more people (hypergraphs), the big question (posed by Conlon, Fox, and Sudakov) was: Does the "bounded degree" rule still keep the party size small, or does it still need to be a massive tower?

They guessed that even with the limit on connections, the party size would still need to be a tower of height $k$.

What This Paper Did: A New Lower Bound

The authors, Chunchao Fan and Qizhong Lin, didn't solve the whole problem (they didn't prove the tower needs to be height $k$), but they made a huge breakthrough.

They proved that for any group size $k$, if you limit the connections, the party size still needs to be a tower of height $k-1$.

In simple terms:

• Old Guess: The party needs to be a tower of height $k$.
• Previous Knowledge: We didn't even know if it needed to be a tower of height $k-1$.
• New Result: They proved it definitely needs to be a tower of height $k-1$.

They moved the goalpost one step closer to the ultimate answer.

The Magic Trick: How They Did It

To prove this, they had to build a specific, tricky party (a mathematical structure) that is just big enough to force a monochromatic group, but small enough to keep the "connection limit" rule.

They used a clever two-part construction, like building a house with a foundation and a frame:

1. The Random Foundation (The "HR" part):
   Imagine you start with a completely random mess of groups. You sprinkle them together randomly. The authors showed that if you do this just right, you get a "pseudorandom" structure that is very hard to color without creating a monochromatic group. This acts as the base case (the bottom of the tower).

2. The Stepping-Up Ladder (The "HE" part):
   This is the most creative part. They used a technique called "Stepping Up."

   • Imagine you have a coloring scheme for groups of 3 people.
   • They figured out how to take that scheme and "step it up" to work for groups of 4, then 5, and so on.
   • The Analogy: Think of it like a video game level. You beat Level 3 (groups of 3). To get to Level 4 (groups of 4), you don't start from scratch; you use the strategy from Level 3 and add a new "ladder" to reach higher.
   • The Catch: Usually, when you climb these ladders, the "connection limit" (the number of friends a person has) explodes and gets too big. The authors' genius was in controlling the ladder. They built the ladder so carefully that even as they climbed from $k=3$ to $k=100$, the number of connections per person stayed within the limit ($\Delta$).

The "Tower" Explained

What is a "Tower Function"?

• $2^2 = 4$ (Level 2)
• $2^{2^2} = 16$ (Level 3)
• $2^{2^{2^2}} = 65,536$ (Level 4)
• $2^{2^{2^{2^2}}}$ is a number so big it has more digits than there are atoms in the universe (Level 5).

The authors proved that for a group size of $k$, the party size must be at least a tower of height $k-1$.

• If you are grouping 3 people, the party needs to be a tower of height 2 (which is just a big number, but manageable).
• If you are grouping 4 people, the party needs to be a tower of height 3 (which is 16... wait, no, it's a tower of 2s of height 3, which is 16, but with the parameters in the paper, it's actually a massive number).
• Basically, the numbers get insanely large very quickly, but the authors proved you can't get away with a smaller number.

Why This Matters

This paper is a major step forward in understanding the limits of order and chaos.

• Before: We didn't know if limiting connections in complex groups made the problem "easy" (linear) or "hard" (tower).
• Now: We know it's definitely "hard" (tower), and we are just one step away from knowing the exact height of that tower.

It's like finding out that a monster in a video game is definitely Level 99, even if we haven't beaten it yet. We know it's not a Level 10 monster, and we know it's not infinite. It's a Level 99 monster, and that changes how we prepare for the fight.

In summary: The authors built a mathematical "party" that proves even if you limit how many friends each person has, you still need an unimaginably huge number of people to guarantee that some group of friends will all wear the same color hat. They proved the number of people needed grows like a tower of height $k-1$.

Technical Summary

1. Problem Statement and Context

The Core Problem:
The paper addresses the growth rate of Ramsey numbers for hypergraphs with bounded maximum degree. Specifically, it investigates Problem 1.1, proposed by Conlon, Fox, and Sudakov (2009):

Is it true that for all $k \ge 3$ and $\Delta$, there exists a $k$-uniform hypergraph $H$ with $n$ vertices and maximum degree $\Delta$ such that $r(H) \ge \text{tw}_k(c\Delta) \cdot n$?

Here, $r(H)$ is the smallest integer $N$ such that any 2-coloring of the edges of the complete $k$-uniform hypergraph $K_N^{(k)}$ contains a monochromatic copy of $H$. The function $\text{tw}_k$ denotes the tower function of height $k$ (e.g., $\text{tw}_1(x)=2^x$, $\text{tw}_2(x)=2^{2^x}$, etc.).

Current State of Knowledge:

• Upper Bounds: It is known that $r(H) \le \text{tw}_k(c\Delta) \cdot n$ for $k \ge 4$ and $r(H) \le \text{tw}_3(c\Delta \log \Delta) \cdot n$ for $k=3$.
• Lower Bounds: For graphs ($k=2$), Graham, Rödl, and Ruciński showed $r(G) \ge 2^{c\Delta} \cdot n$. For hypergraphs ($k \ge 3$), no tower-type lower bound of height $k$ was known. The best known lower bounds were significantly weaker than the upper bounds.

The Gap:
The conjecture suggests the Ramsey number grows as a tower of height $k$. The authors aim to prove a lower bound of tower height $k-1$, which is the first step toward resolving the full conjecture.

---

2. Methodology

The proof combines probabilistic methods with a modified "stepping-up" coloring argument. The strategy involves two main components:

A. The Stepping-Up Coloring Scheme

The authors adapt a coloring scheme recently developed by Bradač, Hunter, and Sudakov [1].

• Recursive Definition: They define a coloring $\phi_m^{(k)}$ on multisets of $k$ elements from $[0, M_k(m))$.
  • For $k=3$, the coloring is essentially random.
  • For $k \ge 4$, the color of a set $\{x_1, \dots, x_k\}$ depends on the vector of "bit-differences" $\delta(\{x_1, \dots, x_k\})$.
  • If the sequence of differences is monotone, the color is inherited from the $(k-1)$-uniform coloring.
  • If not monotone, the color is determined by the position of the maximum difference (red if at the ends, blue if in the middle).
• Embedding: A key concept is an almost monochromatic embedding. If a hypergraph $H$ can be embedded into this coloring without creating a monochromatic copy, then $r(H)$ must be larger than the size of the domain.

B. Hypergraph Construction

The target hypergraph $H$ is constructed as the union of two parts: $H = H_R \cup H_E$.

1. The Random Base ($H_R$):
   • A random $k$-graph constructed to serve as the "base case" for the induction.
   • It must satisfy a specific "pseudorandom" property (being $(\alpha, m)$-good), ensuring that any induced 3-uniform subgraph behaves like a random graph with high probability.
   • Lemma 3.11: The authors prove the existence of an $n$-vertex $k$-graph with bounded degree that is $(\alpha, m)$-good. This generalizes a previous 3-uniform result to arbitrary $k$.
2. The Expander Part ($H_E$):
   • Constructed using a collection of graphs and a hypergraph expander $T$.
   • This part facilitates the inductive step by ensuring that the "stepping-up" process can be applied recursively while keeping the maximum degree bounded.

C. Inductive Argument

The proof proceeds by reverse induction on the uniformity $k$ (from $k$ down to 3).

• Hypothesis: Assume there is a monochromatic embedding of $H$ into the coloring $\phi_m^{(k)}$.
• Step: Using the structure of $H_E$ and the properties of the coloring, the authors show that this implies the existence of an almost monochromatic embedding of a smaller uniformity subgraph into $\phi_m^{(k-1)}$.
• Base Case ($k=3$): The induction reduces the problem to finding an almost monochromatic embedding of a 3-uniform subgraph $H_R^{(3)}$ into $\phi_m^{(3)}$.
• Contradiction: The authors prove that $H_R^{(3)}$ belongs to a class of graphs $\mathcal{G}_m$ (defined via partition properties) for which Lemma 3.7 guarantees no almost monochromatic embedding exists. This contradiction proves that the original embedding cannot exist.

---

3. Key Contributions

1. First Tower-Type Lower Bound for Bounded Degree Hypergraphs:
   The paper establishes the first lower bound of the form $\text{tw}_{k-1}(c\Delta) \cdot n$ for $k$-uniform hypergraphs with bounded degree. This brings the lower bound one "step" closer to the conjectured $\text{tw}_k(c\Delta) \cdot n$.

2. Generalization of the Base Case Construction:
   The authors provide a novel construction (Lemma 3.11) of a $k$-uniform hypergraph that is $(\alpha, m)$-good. This generalizes the 3-uniform case handled in previous literature to arbitrary $k$, which is crucial for the induction to work for $k > 3$.

3. Adaptation of Stepping-Up to Bounded Degree:
   While the stepping-up lemma is a standard tool in Ramsey theory, applying it to bounded degree hypergraphs is non-trivial because standard constructions often cause the degree to explode. The authors carefully control the degree growth at each inductive step by combining a random base with a structured expander component.

---

4. Main Results

Theorem 1.2:
For any $k \ge 3$, there exists a constant $c_k > 0$ such that for any integers $\Delta \ge 1/c_k$ and $n \ge 2\Delta$, there exists a $k$-uniform $n$-vertex hypergraph $H$ with maximum degree at most $\Delta$ satisfying:
$$r(H) \ge \text{tw}_{k-1}(c_k \Delta) \cdot n$$

Implications:

• This result confirms that the Ramsey number for bounded degree hypergraphs grows at least as a tower of height $k-1$.
• It resolves the problem for $k=3$ up to a tower of height 2 (since $\text{tw}_2$ is double exponential), whereas the conjecture asks for $\text{tw}_3$.

---

5. Significance and Future Directions

Significance:

• Bridging the Gap: Prior to this work, the lower bounds for hypergraphs were far below the upper bounds. This paper significantly narrows the gap, proving that the tower height is at least $k-1$.
• Methodological Advance: The combination of pseudorandom hypergraph constructions with the stepping-up coloring technique provides a robust framework for future Ramsey theory problems involving degree constraints.

Open Problems & Limitations:

• The Final Step: The paper does not yet achieve the full conjecture of tower height $k$ (i.e., $\text{tw}_k$). The authors identify the main bottleneck: constructing the base hypergraph $H_R$ for the case where the parameter $s$ (related to the size of the random graph) is $\text{tw}_3(cm)$. Currently, they can only construct it for $s = \text{tw}_2(10^{-5}m)$.
• Future Work: To fully resolve Problem 1.1, future research must find a way to construct the necessary pseudorandom base case for higher tower heights, likely requiring new probabilistic or combinatorial techniques.

In summary, Fan and Lin have made a landmark contribution to extremal combinatorics by proving that bounded degree hypergraphs exhibit tower-type Ramsey growth of height $k-1$, setting a new foundation for the eventual proof of the full tower height $k$ conjecture.