🔢 mathematics

On a problem of Erdos and Hajnal

This paper resolves a question posed by Erdős and Hajnal by establishing the negative partition relation $\aleph_{\omega+1}\nrightarrow(\aleph_{\omega+1},(3)_{\aleph_0})^2$ and extending the result down to $\aleph_{\omega}$ .

Original authors: Shimon Garti, Yair Hayut, Saharon Shelah

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shimon Garti, Yair Hayut, Saharon Shelah

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive party with an infinite number of guests. You want to know if, no matter how you assign colors to the handshakes between guests, you are guaranteed to find a specific pattern.

In the world of mathematics, this is a problem about graphs (guests are dots, handshakes are lines) and coloring (assigning a color to every line).

The Big Question

The famous mathematicians Paul Erdős and András Hajnal asked a specific question about a very large, "messy" type of infinity called $\aleph_\omega$ (think of it as a tower of infinities built one on top of another).

They wanted to know: If you have a huge group of people where everyone is connected to almost everyone else (no one is isolated), and you color every handshake with one of $\aleph_0$ (countably infinite) colors, must you inevitably find a "monochromatic triangle"?

A monochromatic triangle is three people who all shake hands with each other, and all three handshakes are the exact same color.

Mathematicians already knew that if the "rules of the universe" (specifically the Generalized Continuum Hypothesis, or GCH) were strict, the answer was NO. You could color the handshakes in a clever way to avoid making any single-colored triangles.

But Erdős and Hajnal asked: Is this "No" answer dependent on those strict rules? Or is it true even if the universe is "looser" and allows for more possibilities (where $2^\lambda > \lambda^+$ )?

The Paper's Discovery

The authors of this paper, Garti, Hayut, and Shelah, say: Yes, the "No" answer is still possible, even in that looser universe.

They proved that you can construct a mathematical world where:

The "loose" rules apply (the size of the power set is larger than the next cardinal).
The specific infinity $\aleph_\omega$ is a "strong limit" (a very robust type of infinity).
Despite all this, you can still color the handshakes to avoid monochromatic triangles.

This means the negative result (that you can avoid the triangles) is consistent with the failure of the strict rules. It doesn't prove it's always true, but it proves it's possible to build a universe where it happens.

How Did They Do It? (The Metaphors)

The paper uses two main strategies to build this "party" where triangles are avoided.

Strategy 1: The "Ladder" Approach (pcf Theory)

Imagine you are trying to build a bridge to a distant island (the huge infinity $\lambda^+$ ). Usually, you need a solid foundation (the strict rules of GCH) to build it.

The authors realized they didn't need the whole foundation. Instead, they built a ladder made of smaller, manageable rungs (smaller infinities below the big one).

They assumed that on each small rung, you could already avoid the triangles.
Using a sophisticated mathematical tool called pcf theory (which studies how infinities interact), they showed that if you can avoid triangles on the rungs, you can "lift" that ability up to the top of the ladder.
The Catch: This first method worked for many infinities, but it couldn't reach the specific "bottom" of the tower ( $\aleph_\omega$ ) because the rungs there were too different from each other.

Strategy 2: The "Magic Filter" Approach (Stick Principle)

For the specific case of $\aleph_\omega$ , they used a different trick involving a concept called "Stick" (or tiltan).

Imagine you have a magical rod (the "stick") that can peek into the future.

The "Stick" principle says: There is a collection of small groups of people (sets of size $\lambda$ ) such that for any huge group of people you pick (size $\lambda^+$ ), at least one of your small groups is completely inside it.
The authors used this "Stick" to organize the party. They arranged the guests so that the "Stick" could predict where to place the colors to break up any potential triangles.
They proved that if this "Stick" exists, you can successfully color the handshakes to avoid the forbidden triangles, even in the "loose" universe.

The "Catch" and the Open Mystery

The paper is a triumph of "consistency." It shows that the scenario is possible.

However, the authors admit they don't know if it is inevitable.

The Question: Is it true in our standard mathematical universe (ZFC) that you can always avoid these triangles?
The Unknown: They don't know. They have shown you can build a house where this happens, but they haven't proven that every house must be built this way.

They also note a difficulty: To make the "Stick" work in this specific "loose" universe, the "Stick" needs to be made of pieces that are as big as the infinity itself. It's like trying to use a giant fishing net to catch a tiny fish; it works, but it's hard to construct the net in the first place.

Summary

The Problem: Can you color handshakes in a huge crowd to avoid same-colored triangles?
The Old Answer: Yes, but only if the universe follows strict rules.
This Paper's Answer: Yes, you can do it even if the universe is "looser" and follows different rules.
The Method: They built a mathematical "ladder" and used a "magic stick" to prove it's possible to construct such a world.
The Limit: They proved it's possible, but haven't proven it's always true in every possible mathematical world.

Technical Summary: On a Problem of Erdős and Hajnal

Problem Statement
The paper addresses a specific question posed by Erdős and Hajnal regarding the ordinary partition relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ . This relation asserts that for any coloring of the pairs of $\lambda^+$ with $\text{cf}(\lambda)$ colors, there is either a monochromatic triangle or a monochromatic set of size $\lambda^+$ (interpreted as an independent set in graph theory terms).

Erdős, Hajnal, and Rado established that if $\lambda$ is a singular cardinal and the Generalized Continuum Hypothesis (GCH) holds at $\lambda$ (i.e., $2^\lambda = \lambda^+$ ), then the negative relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ holds. They asked whether the assumption $2^\lambda = \lambda^+$ is indispensable. Specifically, Question 0.2 asks if the relation $\aleph_{\omega+1} \nrightarrow (\aleph_{\omega+1}, (3)_{\aleph_0})^2$ can be proven without assuming GCH. While it is known that the negative relation holds if $2^{\text{cf}(\lambda)} \ge \lambda^+$ , the status of the relation when $\lambda$ is a strong limit singular cardinal with $2^\lambda > \lambda^+$ remained open.

Methodology
The authors employ three distinct strategies to demonstrate the consistency of the negative relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ with the failure of GCH ( $2^\lambda > \lambda^+$ ) for strong limit singular cardinals $\lambda$ .

Simple pcf Arguments (Section 1):
The first approach utilizes the theory of possible cofinalities (pcf). The authors assume the existence of a supercompact cardinal $\mu$ and force a model where $\mu$ becomes a strong limit singular cardinal. They construct an unbounded sequence of regular cardinals $(\mu_i \mid i \in \theta)$ below $\mu$ such that $\text{tcf}(\prod \mu_i^+, J_{\text{bd}}^\theta) = \mu^+$ . By assuming GCH below $\mu$ (specifically $2^{\mu_i} = \mu_i^+$ ), they obtain negative partition relations at each $\mu_i^+$ . Using a scale in the product and a specific coloring construction, they lift these local negative relations to $\mu^+$ .
- Limitation: This method requires $\mu$ to be a limit of singular cardinals of the same cofinality. Consequently, it applies to cardinals like $\aleph_{\omega_2}$ but fails for $\aleph_\omega$ , which has no singular cardinals below it.
Refined pcf Arguments for $\aleph_\omega$ (Section 2):
To address the case of $\lambda = \aleph_\omega$ , the authors refine the pcf approach to handle regular cardinals (specifically $\aleph_n$ ) rather than just successors of singulars.
- Claim 2.1: They prove that for regular $\kappa < \lambda$ , there exists a coloring $c: [\lambda]^2 \to \{0,1\}$ and a $\kappa$ -complete filter $D$ such that there are no 1-monochromatic triangles and no 0-monochromatic sets of size $\lambda$ modulo $D$ .
- Forcing Strategy: They utilize a $(<\lambda)$ -strategically-closed forcing notion to construct a scale satisfying specific filter properties (Lemma 2.3). They then employ a Laver-style preparation (Lemma 2.5) to make a supercompact cardinal $\lambda$ indestructible under this specific forcing. Finally, they use Extender-based Prikry forcing with interleaved collapses (following Merimovich) to singularize $\lambda$ to $\aleph_\omega$ while increasing $2^\lambda$ to $\lambda^{++}$ . This preserves the necessary pcf structure and the negative relations derived from the ground model.
Prediction Principles (Stick) (Section 3):
The third approach replaces the pcf assumptions with the "stick" principle, denoted $\bullet(\lambda)$ . This principle asserts the existence of a family of subsets of $\lambda^+$ of size $\lambda$ that "guesses" every subset of $\lambda^+$ of size $\lambda^+$ (i.e., for every $A \in [\lambda^+]^{\lambda^+}$ , there is a $B$ in the family such that $B \subseteq A$ ).
- Theorem 3.3: The authors prove that if $\bullet(\lambda)$ holds, then $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ . The proof constructs a partition of $[\lambda^+]^2$ based on set mappings derived from the stick sequence and a free set lemma (Lemma 3.2).
- Constraint: The proof relies critically on the guessing sets having size $\lambda$ . The authors note that it is currently unknown whether $\bullet(\lambda)$ is consistent with $2^\lambda > \lambda^+$ when $\lambda$ is a strong limit singular cardinal.

Key Contributions and Results

Consistency of Negative Relation with $2^\lambda > \lambda^+$ : The paper establishes that the negative partition relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ is consistent with $\lambda$ being a strong limit singular cardinal and $2^\lambda > \lambda^+$ .
Resolution for $\aleph_\omega$ : The authors successfully push the result down to $\lambda = \aleph_\omega$ (Theorem 2.2 and the subsequent forcing construction), answering the specific instance of the Erdős-Hajnal question for the first infinite singular cardinal.
Large Cardinal Assumptions: The consistency proofs rely on the existence of large cardinals (supercompact or strong cardinals). Specifically, the result for $\aleph_\omega$ is derived from a supercompact cardinal in the ground model, which is singularized via Prikry-type forcing.
Indestructibility: The paper provides a modification of Laver's indestructibility proof (Lemma 2.4, Lemma 2.5) to show that supercompactness can be preserved under $(<\lambda)$ -strategically-closed forcing notions, which is crucial for the pcf construction.

Significance and Open Questions
The paper demonstrates that the assumption $2^\lambda = \lambda^+$ in the Erdős-Hajnal theorem is not necessary for the consistency of the negative relation; the relation can hold even when GCH fails at $\lambda$ . However, the authors explicitly state that they do not know if the relation holds in ZFC (i.e., without large cardinal assumptions).

The paper concludes with several open questions:

Is it consistent that $\lambda$ is a strong limit singular cardinal and the positive relation $\lambda^+ \to (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ holds?
What is the exact consistency strength of the negative relation with $2^\lambda > \lambda^+$ for $\lambda = \aleph_\omega$ ? (The paper uses a supercompact cardinal, whereas Gitik's work on the failure of SCH requires only $o(\kappa) = \kappa^{++}$ ).
Is it consistent that $\lambda$ is supercompact, $\bullet(\lambda)$ holds, and $2^\lambda > \lambda^+$ ? This would unify the stick-based approach with the failure of GCH.

The authors emphasize that while powerful methods for successors of singular cardinals exist, this specific problem regarding the independence of GCH in this partition relation remains a significant challenge, and their work provides the first consistency results for the failure of GCH in this context.