The middle-exponent case of the Erdős–Larson matching partition relation: does $\omega^{\eta+jk} \to (\omega^{\eta+j},\ \omega^k\text{-matching})$ hold for every limit ordinal $\eta$?

A 1991 paper of Paul Erdős and Jean A. Larson, "Matchings from a set below to a set above", strengthened the ordinal partition calculus by replacing the second homogeneous set with a matching: $\alpha \to (\beta, \gamma\text{-matching})$ demands that every graph on the ordered vertex set $\alpha$ contain either an independent set of order type $\beta$ or a "down-up $\gamma$-matching" — an injection $m: A \to B$ from a set $A$ of order type $\gamma$ into a set $B$ lying entirely above $A$, with $\{a, m(a)\}$ an edge for every $a \in A$. The paper proved a sharp sandwich for limit ordinals $\eta$ and integers $j \ge 1$, $k \ge 2$: $\omega^{\eta+jk+1} \to (\omega^{\eta+j}, \omega^k\text{-matching})$ holds, while $\omega^{\eta+jk-1}$ fails; it then asked whether the middle relation $\omega^{\eta+jk} \to (\omega^{\eta+j}, \omega^k\text{-matching})$ holds, remarking also that the uncountable analogue was uninvestigated. No resolution of the middle-exponent case is known in the literature to date. The middle-exponent case is posed here as an open problem, with the uncountable analogue as a secondary open-ended component.

Background

Ordinal partition relations. For ordinals $\alpha, \beta, \gamma$, the classical relation $\alpha \to (\beta, \gamma)$ (Erdős–Rado notation) asserts that for every 2-coloring of the two-element subsets of $\alpha$ there is either a red-homogeneous set of order type $\beta$ or a blue-homogeneous set of order type $\gamma$. Equivalently, in the graph form used throughout: every graph $G$ whose vertex set is the ordinal $\alpha$, equipped with its natural well-order, contains either an independent set (no two vertices adjacent) whose order type in the inherited well-order is $\beta$, or a clique of order type $\gamma$. "Order type" means the ordinal isomorphism type of the set under the inherited order.

The matching alternative. Erdős and Larson (1991) introduced a variant in which the clique is replaced by an infinite matching, importing ideas from infinite matching theory (Hall-type criteria for infinite bipartite graphs — infinite versions of Hall's marriage theorem, which characterizes when each set in a family can be matched to a distinct representative of its own; generalized by Aharoni; the transversal theory of Nash-Williams, a transversal being such a system of distinct representatives; and results of Podewski and Steffens — all appear in the paper's reference list). For a graph $G$ on an ordinal $\alpha$ and an ordinal $\gamma$, a down-up $\gamma$-matching is an injective map $m: A \to B$ with $A, B \subseteq \alpha$ such that (i) every element of $A$ is strictly less than every element of $B$ (written $A < B$), (ii) the order type of $A$ is $\gamma$, and (iii) $\{a, m(a)\}$ is an edge of $G$ for every $a \in A$; no condition is imposed on the order type of the upper set $B$ beyond injectivity. The relation $\alpha \to (\beta, \gamma\text{-matching})$ means that every graph on $\alpha$ contains an independent set of order type $\beta$ or a down-up $\gamma$-matching. When the matching parameter is an infinite cardinal $\kappa$ (as in the source paper's Theorem 1.4), condition (ii) becomes $|A| = \kappa$. The matching alternative is not directly comparable to the clique alternative; it is a distinct regime connecting the partition calculus of ordinals with infinite bipartite matching theory.

Ordinal arithmetic. Every nonzero ordinal has a unique Cantor normal form $\omega^{\gamma_1} c_1 + \dots + \omega^{\gamma_n} c_n$ with $\gamma_1 > \dots > \gamma_n$ and finite coefficients $c_i > 0$; the $\omega$-powers $\omega^\gamma$ are exactly the additively indecomposable ordinals (those not expressible as the sum of two smaller ordinals), and ordinal exponentiation obeys $\omega^{a+b} = \omega^a \cdot \omega^b$ and $(\omega^a)^b = \omega^{a \cdot b}$. The vertex ordinal in question, $\omega^{\eta+jk} = \omega^\eta \cdot \omega^{jk} = \omega^\eta \cdot (\omega^j)^k$, is thus an $\omega^\eta$-fold iteration of a $jk$-fold power grid, and the exponent product $jk = j \cdot k$ pairs the two parameters of the relation: the independent-set target $\omega^{\eta+j}$ and the matching lower side $\omega^k$.

Classical backdrop. Specker (1957) proved $\omega^2 \to (\omega^2, 3)$ but $\omega^n \not\to (\omega^n, 3)$ for every finite $n \ge 3$ — the first "one-step" threshold phenomenon for $\omega$-powers. Chang (1972) proved $\omega^\omega \to (\omega^\omega, 3)$, and E. C. Milner extended this to $\omega^\omega \to (\omega^\omega, m)$ for every finite $m$ (Milner's proof remained unpublished; the result is documented in the Erdős Problems database, entry #590, and was formalized by Džamonja–Koutsoukou-Argyraki–Paulson). The identification of countable partition ordinals — those countable $\alpha$ with $\alpha \to (\alpha, 3)$ — was advanced through Darby's negative partition relations for ordinals of the form $\omega^{\omega^\alpha}$ and Schipperus's work on countable partition ordinals; the Erdős Problems database (entries #590–#592) tracks this thread, and the surveys of Hajnal–Larson (Handbook of Set Theory, 2010) and Larson ("Erdős and ordinals", 2002) give the full picture. Komjáth (1999) contains related work on the ordinary partition calculus of ordinals.

The source paper's results. Erdős and Larson's matching calculus (Discrete Mathematics 95, 1991) established: (a) Theorem 1.4 — for every infinite cardinal $\kappa$ and every ordinal $\theta < \kappa^+$, the ordinal product $\kappa \cdot \theta \to (\theta, \kappa\text{-matching})$; (b) an amplification lemma — if $\alpha \to (\beta, \omega^k\text{-matching})$ then $\alpha \cdot \omega^{jk+1} \to (\beta \cdot \omega^j, \omega^k\text{-matching})$, in particular $\omega^{jk+1} \to (\omega^j, \omega^k\text{-matching})$; (c) the sandwich proposition — for every limit ordinal $\eta$ and integers $j \ge 1$, $k \ge 2$, $\omega^{\eta+jk+1} \to (\omega^{\eta+j}, \omega^k\text{-matching})$ holds while $\omega^{\eta+jk-1} \not\to (\omega^{\eta+j}, \omega^k\text{-matching})$; and (d) negative results at finite exponents, e.g. $\gamma^b \not\to (\omega^{b-1}+1, \gamma\text{-matching})$ for finite $b$, which settle the middle exponent negatively when $\eta = 0$ (taking $\gamma = \omega^k$, $b = j$, so that $\gamma^b = \omega^{jk}$ and an independent set of type $\omega^j$ would contain one of type $\omega^{j-1}+1$) — this is exactly why the paper's open question is posed for limit $\eta$.

In the 35 years since publication no research follow-up on the question is known, and the Isabelle/HOL formalization program for ordinal partition relations (Isabelle/HOL is a widely used interactive proof assistant for higher-order logic; Džamonja–Koutsoukou-Argyraki–Paulson, 2022, and Paulson's entries in the Archive of Formal Proofs, the Isabelle community's refereed library of formalized mathematics) covers the classical relations but not the down-up matching variant.

Problem Statement

Decide, for every limit ordinal $\eta$ (a nonzero ordinal with no immediate predecessor) and all integers $j \ge 1$ and $k \ge 2$, whether

$$\omega^{\eta+jk} \to (\omega^{\eta+j},\; \omega^k\text{-matching})$$

holds, under the following definitions. For a graph $G$ whose vertex set is an ordinal $\alpha$ carrying its natural well-order: an independent set of order type $\beta$ is a set $I \subseteq \alpha$, of order type $\beta$ in the inherited well-order, with no edge of $G$ between any two of its elements; a down-up $\gamma$-matching is an injective map $m: A \to B$ with $A, B \subseteq \alpha$ such that every element of $A$ is strictly less than every element of $B$, the order type of $A$ is $\gamma$, and $\{a, m(a)\}$ is an edge of $G$ for every $a \in A$ (when the matching parameter is an infinite cardinal $\kappa$, the requirement on $A$ is $|A| = \kappa$ instead). The relation $\alpha \to (\beta, \gamma\text{-matching})$ asserts that every such graph $G$ contains at least one of the two configurations. Note that $\eta$ ranges over all limit ordinals, countable and uncountable.

Known boundary conditions that any answer must respect (from the source paper): the relation holds at exponent $\eta+jk+1$ and fails at $\eta+jk-1$ for every limit $\eta$ and all $j \ge 1$, $k \ge 2$; and at $\eta = 0$ (not a limit ordinal) the middle case fails. Partial results — a fixed $k$, a restricted class of limit ordinals such as $\eta = \omega$, or countable $\eta$ only — are valuable progress but do not by themselves close the question.

A further open component, left uninvestigated by the source paper's closing remark, is the uncountable-order-type analogue of the matching partition calculus.

References

1. Paul Erdős and Jean A. Larson. Matchings from a set below to a set above. Discrete Mathematics, 95(1-3):169-182, 1991. doi:10.1016/0012-365X(91)90335-Y, https://doi.org/10.1016/0012-365X(91)90335-Y; zbMATH Zbl 0761.04003, https://zbmath.org/0761.04003.
2. F. R. K. Chung. Open problems of Paul Erdős in graph theory. Journal of Graph Theory, 25(1):3-36, 1997. doi:10.1002/(SICI)1097-0118(199705)25:1<3::AID-JGT1>3.0.CO;2-R, https://doi.org/10.1002/(SICI)1097-0118(199705)25:1%3C3::AID-JGT1%3E3.0.CO;2-R
3. Akihiro Kanamori. Erdős and set theory. The Bulletin of Symbolic Logic, 20(4):449-490, 2014. doi:10.1017/bsl.2014.38, https://doi.org/10.1017/bsl.2014.38
4. Ernst Specker. Teilmengen von Mengen mit Relationen. Commentarii Mathematici Helvetici, 31:302-314, 1957. doi:10.1007/BF02564361, https://doi.org/10.1007/BF02564361
5. C. C. Chang. A partition theorem for the complete graph on ω^ω. Journal of Combinatorial Theory, Series A, 12:396-452, 1972. doi:10.1016/0097-3165(72)90105-7, https://doi.org/10.1016/0097-3165(72)90105-7
6. Carl Darby. Negative partition relations for ordinals ω^{ω^α}. Journal of Combinatorial Theory, Series B, 76:205-222, 1999. doi:10.1006/jctb.1999.1903, https://doi.org/10.1006/jctb.1999.1903
7. Rene Schipperus. Countable partition ordinals. Annals of Pure and Applied Logic, 161:1195-1215, 2010. doi:10.1016/j.apal.2009.12.007, https://doi.org/10.1016/j.apal.2009.12.007
8. András Hajnal and Jean A. Larson. Partition relations. In Handbook of Set Theory, pages 129-213. Springer, 2010. doi:10.1007/978-1-4020-5764-9_3, https://doi.org/10.1007/978-1-4020-5764-9_3
9. Jean A. Larson. Erdős and ordinals. In Gábor Halász et al. (editors), Paul Erdős and His Mathematics II, Bolyai Society Mathematical Studies 11, pages 427-451. Springer, Berlin, 2002. ISBN 3-540-42236-6. zbMATH Zbl 1023.03045, https://zbmath.org/1023.03045
10. Mirna Džamonja, Angeliki Koutsoukou-Argyraki, and Lawrence C. Paulson. Formalizing ordinal partition relations using Isabelle/HOL. Experimental Mathematics, 31(2):383-400, 2022. doi:10.1080/10586458.2021.1980464, https://doi.org/10.1080/10586458.2021.1980464 (preprint: arXiv:2011.13218, https://arxiv.org/abs/2011.13218)
11. Péter Komjáth. Some remarks on the partition calculus of ordinals. The Journal of Symbolic Logic, 64(2):436-442, 1999. doi:10.2307/2586476, https://doi.org/10.2307/2586476
12. T. F. Bloom (editor). Erdős Problems database, entries #590, #591, #592. https://www.erdosproblems.com/592 (accessed 2026-09-06)