Highly connected Ramsey theory
Chris Lambie-Hanson
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University

RIMS Workshop 2020
Set Theory: Reals and Topology
17 November 2020

I. Highly connectedpartition relations

Classical partition relations
Recall the Hungarian notation for partition relations: If λ, µ, andν are cardinals and k is a natural number, then
ν → (µ)kλis the assertion that, for every function c : [ν]k → λ, there isH ⊆ ν of size µ such that c  [H]k is constant.

Classical partition relations
Recall the Hungarian notation for partition relations: If λ, µ, andν are cardinals and k is a natural number, then
ν → (µ)kλis the assertion that, for every function c : [ν]k → λ, there isH ⊆ ν of size µ such that c  [H]k is constant.
• The infinite Ramsey theorem states that, for all k, m < ω,
ℵ0 → (ℵ0 )km .

Classical partition relations
Recall the Hungarian notation for partition relations: If λ, µ, andν are cardinals and k is a natural number, then
ν → (µ)kλis the assertion that, for every function c : [ν]k → λ, there isH ⊆ ν of size µ such that c  [H]k is constant.
• The infinite Ramsey theorem states that, for all k, m < ω,
ℵ0 → (ℵ0 )km .

• An uncountable cardinal κ is weakly compact if and only if
κ → (κ)22 .

Counterexamples at c
There are two simple, very strong counterexamples to naturalgeneralizations of Ramsey’s theorem to c.

Counterexamples at c
There are two simple, very strong counterexamples to naturalgeneralizations of Ramsey’s theorem to c.
• Define ∆ : [ω 2]2 → ω by letting ∆(f , g) be the least j suchthat f (j) 6= g(j). Then ∆ witnesses
c 6→ (3)2ℵ0 .

Counterexamples at c
There are two simple, very strong counterexamples to naturalgeneralizations of Ramsey’s theorem to c.
• Define ∆ : [ω 2]2 → ω by letting ∆(f , g) be the least j suchthat f (j) 6= g(j). Then ∆ witnesses
c 6→ (3)2ℵ0 .
• Define d : [R]2 → 2 as follows. Fix a well-ordering ≺ on R
and let d(x, y ) = 0 if ≺ agrees with the usual ordering of R
on the order of x and y , and d(x, y ) = 1 otherwise. Then dwitnesses
c 6→ (ℵ1 )22 .

Connectedness
The relation ν → (µ)2λ can be phrased in graph-theoretic
language: Whenever the edges of the complete graph on ν-manyvertices are colored with λ-many colors, we can find a complete
monochromatic subgraph of size µ.

Connectedness
The relation ν → (µ)2λ can be phrased in graph-theoretic
language: Whenever the edges of the complete graph on ν-many
vertices are colored with λ-many colors, we can find a complete
monochromatic subgraph of size µ. In search of nontrivial
partition relations that can hold at small uncountable cardinals,
one might try to slightly weaken the requirement that the
monochromatic subgraph we obtain is complete.

Connectedness
The relation ν → (µ)2λ can be phrased in graph-theoretic
language: Whenever the edges of the complete graph on ν-many
vertices are colored with λ-many colors, we can find a complete
monochromatic subgraph of size µ. In search of nontrivial
partition relations that can hold at small uncountable cardinals,
one might try to slightly weaken the requirement that the
monochromatic subgraph we obtain is complete. One natural way
to approach this is via considerations of connectedness.

Definition
Let G = (V, E) be a graph.
1

G is connected if, for all u, v ∈ V, there are u0 , u1 , . . . , un ∈ Vsuch that u0 = u, un = v , and, for all i < n, {ui , ui+1 } ∈ E.

Connectedness
The relation ν → (µ)2λ can be phrased in graph-theoretic
language: Whenever the edges of the complete graph on ν-many
vertices are colored with λ-many colors, we can find a complete
monochromatic subgraph of size µ. In search of nontrivial
partition relations that can hold at small uncountable cardinals,
one might try to slightly weaken the requirement that themonochromatic subgraph we obtain is complete. One natural way
to approach this is via considerations of connectedness.

Definition
Let G = (V, E) be a graph.
1

G is connected if, for all u, v ∈ V, there are u0 , u1 , . . . , un ∈ Vsuch that u0 = u, un = v , and, for all i < n, {ui , ui+1 } ∈ E.

2

G is κ-connected if it is connected and remains connected
after removing any fewer than κ-many vertices.

Highly connectedness
Definition (Bergfalk-Hrušák-Shelah ‘20)
1

A graph G is highly connected if it is |G|-connected.

Highly connectedness
Definition (Bergfalk-Hrušák-Shelah ‘20)
1

A graph G is highly connected if it is |G|-connected.

2

The partition relation
ν →hc (µ)2λis the assertion that, for every c : [ν]2 → λ, there are H ⊆ νof size µ and a highly connected graph (H, E ) such thatc  E is constant.

Highly connectedness
Definition (Bergfalk-Hrušák-Shelah ‘20)
1

A graph G is highly connected if it is |G|-connected.

2The partition relation
ν →hc (µ)2λis the assertion that, for every c : [ν]2 → λ, there are H ⊆ νof size µ and a highly connected graph (H, E ) such thatc  E is constant.

Note: A finite graph is highly connected if and only if it iscomplete, so the relation
ν →hc (µ)2λcan be seen as a genuine generalization of the classical finite
Ramsey partition relations.

Warm-up Exercise
Proposition (Bergfalk-Hrušák-Shelah ‘20)
If ν is an infinite cardinal and k is a natural number, then
ν →hc (ν)2k .
Proof:

Warm-up Exercise
Proposition (Bergfalk-Hrušák-Shelah ‘20)
If ν is an infinite cardinal and k is a natural number, then
ν →hc (ν)2k .
Proof:
A similar proof yields the following:

Proposition
If κ is strongly compact, λ < κ, and cf(ν) ≥ κ, then ν →hc (ν)2λ .

Warm-up Exercise
Proposition (Bergfalk-Hrušák-Shelah ‘20)
If ν is an infinite cardinal and k is a natural number, then
ν →hc (ν)2k .
Proof:
A similar proof yields the following:Proposition
If κ is strongly compact, λ < κ, and cf(ν) ≥ κ, then ν →hc (ν)2λ .
Some immediate negative results in ZFC: for all infinite λ,Warm-up Exercise
Proposition (Bergfalk-Hrušák-Shelah ‘20)
If ν is an infinite cardinal and k is a natural number, then
ν →hc (ν)2k .
Proof:
A similar proof yields the following:

Proposition
If κ is strongly compact, λ < κ, and cf(ν) ≥ κ, then ν →hc (ν)2λ .
Some immediate negative results in ZFC: for all infinite λ,• for all µ ≥ 3, λ+ 6→hc (µ)2λ ;Warm-up Exercise
Proposition (Bergfalk-Hrušák-Shelah ‘20)
If ν is an infinite cardinal and k is a natural number, then
ν →hc (ν)2k .
Proof:
A similar proof yields the following:

Proposition
If κ is strongly compact, λ < κ, and cf(ν) ≥ κ, then ν →hc (ν)2λ .
Some immediate negative results in ZFC: for all infinite λ,• for all µ ≥ 3, λ+ 6→hc (µ)2λ ;• 2λ 6→hc (2λ )2λ .

Consistent positive results

Theorem (Bergfalk-Hrušák-Shelah ‘20)
If the existence of a weakly compact cardinal is consistent, then itis consistent that2ω1 →hc (2ω1 )2ω .

Consistent positive results

Theorem (Bergfalk-Hrušák-Shelah ‘20)
If the existence of a weakly compact cardinal is consistent, then it
is consistent that2ω1 →hc (2ω1 )2ω .

Theorem (Hrušák-Shelah ‘2X)
If the existence of a measurable cardinal is consistent, then it isconsistent that
ω2 →hc (ω2 )2ω .

Motivating questions

1

What effect do other well-known
compactness/incompactness principles (e.g. PFA, squareprinciples) have on highly connected partition relations?

Motivating questions

1

What effect do other well-known
compactness/incompactness principles (e.g. PFA, squareprinciples) have on highly connected partition relations?

2

Are any nontrivial positive consistency results possible at thelevel of c?

Counterexamples from squares

Square bracket relations

To state our results, we need a variation on our highly connectedpartition relations.

Square bracket relations

To state our results, we need a variation on our highly connectedpartition relations.

Definition
The partition ν →hc [µ]2λ,κ (resp. ν → [µ]2λ,<κ ) is the assertion
that, for every coloring c : [ν]2 → λ, there is H ⊆ ν of size µ anda highly connected graph (H, E ) such that |c“E | ≤ κ (resp.
|c“E | < κ).

SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:

SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:1

Cβ is a club in β;SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:1

Cβ is a club in β;2(Coherence) for all α ∈ Lim(Cβ ), we have Cα = Cβ ∩ α;SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:1

Cβ is a club in β;2(Coherence) for all α ∈ Lim(Cβ ), we have Cα = Cβ ∩ α;3(Nontriviality) there is no club D in ν such that, for allα ∈ Lim(D), we have Cα = D ∩ α.

SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:1

Cβ is a club in β;2(Coherence) for all α ∈ Lim(Cβ ), we have Cα = Cβ ∩ α;3(Nontriviality) there is no club D in ν such that, for allα ∈ Lim(D), we have Cα = D ∩ α.

(ν)-sequences are canonical examples of set theoretic
incompactness.

SquaresDefinition (Todorcevic)
Suppose that ν is a regular uncountable cardinal. Then (ν) is~ = hCα | α < νi suchthe assertion that there is a sequence C
that, for all limit ordinals β < ν:
1Cβ is a club in β;2(Coherence) for all α ∈ Lim(Cβ ), we have Cα = Cβ ∩ α;3(Nontriviality) there is no club D in ν such that, for allα ∈ Lim(D), we have Cα = D ∩ α.

(ν)-sequences are canonical examples of set theoretic
incompactness.

Theorem (Jensen)
If ν is a regular uncountable cardinal and (ν) fails, then ν isweakly compact in L.

Negative results from square
Theorem (LH ‘20)
Suppose that λ < ν are infinite regular cardinals and (ν) holds.
Thenν 6→hc [ν]2λ,<λ .

Negative results from square
Theorem (LH ‘20)
Suppose that λ < ν are infinite regular cardinals and (ν) holds.
Thenν 6→hc [ν]2λ,<λ .
(We in fact get the failure of the weaker principle ν →wc [ν]2λ,<λ .)Negative results from square
Theorem (LH ‘20)
Suppose that λ < ν are infinite regular cardinals and (ν) holds.
Thenν 6→hc [ν]2λ,<λ .
(We in fact get the failure of the weaker principle ν →wc [ν]2λ,<λ .)Theorem (LH ‘20)
If µ is a singular cardinal and µ holds, thenµ+ 6→hc [µ]2cf(µ),<cf(µ) .

Subadditive unbounded functions
The proofs of these results can be factored through the notion ofsubadditive unbounded functions. For example:

Subadditive unbounded functions
The proofs of these results can be factored through the notion ofsubadditive unbounded functions. For example:
Step 1: Prove that (ν) entails the existence of a function
c : [ν]2 → λ such that

Subadditive unbounded functions
The proofs of these results can be factored through the notion ofsubadditive unbounded functions. For example:
Step 1: Prove that (ν) entails the existence of a function
c : [ν]2 → λ such that
• (Subadditive) for all α < β < γ < ν, we have• c(α, γ) ≤ max{c(α, β), c(β, γ)}; and• c(α, β) ≤ max{c(α, γ), c(β, γ)}.

Subadditive unbounded functions
The proofs of these results can be factored through the notion of
subadditive unbounded functions. For example:
Step 1: Prove that (ν) entails the existence of a function
c : [ν]2 → λ such that
• (Subadditive) for all α < β < γ < ν, we have• c(α, γ) ≤ max{c(α, β), c(β, γ)}; and• c(α, β) ≤ max{c(α, γ), c(β, γ)}.

• (Unbounded) for every unbounded H ⊆ ν and every i < λ,there are α < β in H such that c(α, β) > i .

Subadditive unbounded functions
The proofs of these results can be factored through the notion of
subadditive unbounded functions. For example:
Step 1: Prove that (ν) entails the existence of a function
c : [ν]2 → λ such that
• (Subadditive) for all α < β < γ < ν, we have• c(α, γ) ≤ max{c(α, β), c(β, γ)}; and• c(α, β) ≤ max{c(α, γ), c(β, γ)}.

• (Unbounded) for every unbounded H ⊆ ν and every i < λ,there are α < β in H such that c(α, β) > i .
Step 2: Prove that a subadditive unbounded function
c : [ν]2 → λ witnesses the failure of ν →hc [ν]2λ,<λ .

A positive result at c

The consistency result
Theorem (LH ‘20)
Suppose that ν is a weakly compact cardinal and P is the poset
to add ν-many Cohen reals. Then, in V P , for all λ < ν we havec →hc [c]2λ,2The consistency result
Theorem (LH ‘20)
Suppose that ν is a weakly compact cardinal and P is the poset
to add ν-many Cohen reals. Then, in V P , for all λ < ν we havec →hc [c]2λ,2This is sharp, since we know that• c 6→hc (c)2ω ;The consistency result
Theorem (LH ‘20)
Suppose that ν is a weakly compact cardinal and P is the poset
to add ν-many Cohen reals. Then, in V P , for all λ < ν we havec →hc [c]2λ,2This is sharp, since we know that• c 6→hc (c)2ω ;• c 6→ [ℵ0 ]2ℵ ,<ℵ00The consistency result
Theorem (LH ‘20)
Suppose that ν is a weakly compact cardinal and P is the poset
to add ν-many Cohen reals. Then, in V P , for all λ < ν we havec →hc [c]2λ,2This is sharp, since we know that• c 6→hc (c)2ω ;• c 6→ [ℵ0 ]2ℵ ,<ℵ
00Corollary (LH ‘20)
The following are equiconsistent over ZFC:
1

There exists a weakly compact cardinal.

2c →hc [c]2λ,2 .

Higher dimensions
What about statements of the form ν →hc (µ)kλ for k > 2?

Higher dimensions
What about statements of the form ν →hc (µ)kλ for k > 2? Wewould need to isolate the/a correct definition(s) of “highlyconnected k-uniform hypergraph”.

Higher dimensions
What about statements of the form ν →hc (µ)kλ for k > 2? We
would need to isolate the/a correct definition(s) of “highlyconnected k-uniform hypergraph”. One approach is via theexistence of paths between vertices; even here, there are different,non-equivalent definitions.

Higher dimensions
What about statements of the form ν →hc (µ)kλ for k > 2? We
would need to isolate the/a correct definition(s) of “highlyconnected k-uniform hypergraph”. One approach is via theexistence of paths between vertices; even here, there are different,non-equivalent definitions. Using any of these path-based
definitions, we can prove, for any k > 2:

Theorem (LH ‘20)
1

After adding a weakly compact number of Cohen reals, forall λ < c, we have c →hc [c]kλ,k .

2

In ZFC, we have c 6→hc [c]kλ,k−1 .

Higher dimensions
What about statements of the form ν →hc (µ)kλ for k > 2? We
would need to isolate the/a correct definition(s) of “highlyconnected k-uniform hypergraph”. One approach is via theexistence of paths between vertices; even here, there are different,
non-equivalent definitions. Using any of these path-based
definitions, we can prove, for any k > 2:

Theorem (LH ‘20)
1

After adding a weakly compact number of Cohen reals, forall λ < c, we have c →hc [c]kλ,k .

2

In ZFC, we have c 6→hc [c]kλ,k−1 .

Remaining speculations

But there are other definitions of connectedness of k-uniformhypergraphs that arise from more homological considerations, andthings seem less clear if these definitions are used.

Remaining speculations

But there are other definitions of connectedness of k-uniform
hypergraphs that arise from more homological considerations, andthings seem less clear if these definitions are used.

Also, to construct consistent counterexamples, we would want todevelop the theory of “subadditive unbounded functions”
f : [ν]k → λ.

References
Jeffrey Bergfalk, Michael Hrušák, and Saharon Shelah, Ramsey
theory for highly connected monochromatic subsets, Acta Math.
Hungar. (2020), To appear.
Jeffrey Bergfalk, Ramsey theory for monochromaticallywell-connected subsets, Fund. Math. 249 (2020), no. 1, 95–103.
Chris Lambie-Hanson, A note on highly connected andwell-connected Ramsey theory, (2020), Submitted.
https://arxiv.org/abs/2005.10812
All artwork by Sol LeWittThank you!