Proof of `Homogeneous rectangles for colorings of pairs of tuples`

groundedproofs/Lax185574Proofs/BipartiteHomogeneity.lean · lax-185574

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 60 of this submission's paper

Description

Concatenate the two tuples to one tuple of length 2ℓ2ℓ and apply the Erdős–Rado theorem for order types of tuples to the induced coloring. This gives a set HH of size 2m2m on which the color depends only on the order type of the concatenation. Split HH into its mm smallest elements II and its mm largest elements JJ. Every entry from II lies below every entry from JJ, so for a∈Iℓa ∈ I^ℓ and b∈Jℓb ∈ J^ℓ the order type of the concatenation is determined by the order types of aa and bb. The function U(t)U(t) is the largest m≤tm ≤ t such that every n≥tn ≥ t admits such sets of size mm for every coloring. It is non-decreasing by definition and unbounded by the Ramsey step.

The Ramsey core is adapted from lax-345067 (finite Ramsey theorems for pairs and tuples).