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.
@article{118851,
author = {Saharon Shelah},
title = {Finite canonization},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {37},
year = {1996},
pages = {445-456},
zbl = {0881.05097},
mrnumber = {1426909},
language = {en},
url = {http://dml.mathdoc.fr/item/118851}
}
Shelah, Saharon. Finite canonization. Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996) pp. 445-456. http://gdmltest.u-ga.fr/item/118851/
A combinatorial theorem, Journal of the London Mathematical Society 25 (1950), 249-255. (1950) | MR 0037886
Probabilistic Methods in Combinatorics, Academic Press, New York, 1974. | MR 0382007
Ramsey Theory, Willey - Interscience Series in Discrete Mathematics, Willey, New York, 1980. | MR 0591457 | Zbl 0705.05061
On canonical Ramsey numbers for complete graphs versus paths, Journal of Combinatorial Theory, ser. B 58 (1993), 1-13. (1993) | MR 1214886
preprint, .
Note on canonical partitions, Bulletin London Mathematical Society 18 (1986), 123-126. (1986) | MR 0818813 | Zbl 0584.05006
A two-cardinal theorem, Proceedings of the American Mathematical Society 48 (1975), 207-213. (1975) | MR 0357105 | Zbl 0302.02017