A partition theorem for a large dense linear order

DOI10.1007/S11856-009-0049-2MaRDI QIDQ836116zbMATH OpenOpenAlexFDO

Authors Jean A. Larson, William J. Mitchell, Mirna Džamonja

Publication date 31 August 2009

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0506123

coloring dense linear order ordered tree partition theorem strong embedding

Other combinatorial set theory (03E05) Consistency and independence results (03E35) Large cardinals (03E55) Coloring of graphs and hypergraphs (05C15)

Abstract: Let Q_K=(Q,<_Q)$ be a strongly K-dense linear order of size K for a suitable cardinal K. We prove, for all integers m > 1 that there is a finite value t_m^+ such that the set of all m-tuples from Q can be divided into t_m^+ many classes, such that whenever any of these classes C is colored with fewer than K many colors, there is a copy Q* of Q_K such that all m-tuples from Q* in C receive the same color. As a consequence we obtain that whenever we color the m-tuples of Q with fewer than K many colors, there is a copy of Q_K all m-tuples from which are colored in at most t_m^+ colors. In other words, the partition relation Q_K -->(Q_K)^m_{<K,r} holds for some finite r=t_m^+. We show that t_m^+ is the minimal value with this property. We were not able to give a formula for t_m^+ but we can describe t_m^+ as the cardinality of a certain finite set of types. We give an upper and a lower bound on its value and for m=2 we obtain t_2^+ = 2, while for m>2 we have t_m^+ > t_m, the m-th tangent number. The paper also contains similar partition results about K-Rado graphs. A consequence of our work and some earlier results of Hajnal and Komjath is that a theorem of Shelah known to follow from a large cardinal assumption in a generic extension, does not follow from any large cardinal assumption on its own.

Review text

For $t<\omega$, $\mathbb Q\to (\mathbb Q)^n_{<\omega,t}$ means that, when one colors $[\mathbb Q]^n$ with finitely many colors then there is a copy $\mathbb Q^*$ of $\mathbb Q$ with the property that $[\mathbb Q^*]^n$ is colored with at most $t$ colors. D. Devlin proved that for any $n$, $\mathbb Q\rightarrow (\mathbb Q)^n_{<\omega,t_n}$ and $\mathbb Q\not\rightarrow (\mathbb Q)^n_{<\omega,t_n-1}$. Here $t_n$ denotes the $n$-th tangent number which may be computed using the power series $\tan x= \sum_1^{\infty} t_n \frac{x^{2n-1}}{(2n-1)!}$. The main result of the paper is the following: For every natural number $m$ there is a $t^+_m<\omega$ such that for any cardinal $\kappa$ which is measurable in the generic extension obtained by adding $\lambda$ Cohen subsets of $\kappa$, where $\lambda$ is some cardinal satisfying $\lambda \rightarrow (\kappa)^{2m}_{2^{\kappa}}$, the $\kappa$-dense linear order $\mathbb Q_{\kappa}$ satisfies \[ \mathbb Q_{\kappa} \rightarrow (\mathbb Q)^m_{<\omega,t^+_m} \quad\text{and} \quad \mathbb Q_{\kappa} \not\rightarrow (\mathbb Q)^m_{<\omega,t^+_m-1} . \] In order to obtain this result, the authors start with a theorem of Shelah which is a generalization of the Halpern-Läuchli theorem. Further on, they characterize $t_m^+$ as the cardinality of a certain finite set of ordered trees and obtain an upper and a lower bound on this value. In particular, $t^+_2 = 2$ and, for $m>2$, $t^+_m> t_m$.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: A partition theorem for a large dense linear order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q836116)