Finite canonization

Shelah, Saharon

Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996) no. 3, pp. 445-456

Résumé

The canonization theorem says that for given $m,n$ for some $m^*$ (the first one is called $ER(n;m)$) we have for every function $f$ with domain $[{1,\dotsc,m^*}]^n$, for some $A \in [{1,\dotsc,m^*}]^m$, the question of when the equality $f({i_1,\dotsc,i_n}) = f({j_1,\dotsc,j_n})$ (where $i_1 \cdots i_n$ and $j_1 \cdots j_n$ are from $A$) holds has the simplest answer: for some $v \subseteq \{1,\dotsc,n\}$ the equality holds iff $\bigwedge_{\ell \in v} i_\ell = j_\ell$. We improve the bound on $ER(n,m)$ so that fixing $n$ the number of exponentiation needed to calculate $ER(n,m)$ is best possible.

Détail

Classification : 05C55, 05D10, 11B75
Keywords: Ramsey theory; Erdös-Rado theorem; canonization