Finite canonization

Shelah, Saharon. "Finite canonization." Commentationes Mathematicae Universitatis Carolinae 37.3 (1996): 445-456. <http://eudml.org/doc/247904>.

@article{Shelah1996,
abstract = {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,\cdots ,m^*\}]^n$, for some $A \in [\{1,\cdots ,m^*\}]^m$, the question of when the equality $f(\{i_1,\cdots ,i_n\}) = f(\{j_1,\cdots ,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 \lbrace 1,\cdots ,n\rbrace $ 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.},
author = {Shelah, Saharon},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Ramsey theory; Erdös-Rado theorem; canonization; Ramsey theory; Erdös-Rado theorem; canonization},
language = {eng},
number = {3},
pages = {445-456},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Finite canonization},
url = {http://eudml.org/doc/247904},
volume = {37},
year = {1996},
}

TY - JOUR
AU - Shelah, Saharon
TI - Finite canonization
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1996
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 37
IS - 3
SP - 445
EP - 456
AB - 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,\cdots ,m^*}]^n$, for some $A \in [{1,\cdots ,m^*}]^m$, the question of when the equality $f({i_1,\cdots ,i_n}) = f({j_1,\cdots ,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 \lbrace 1,\cdots ,n\rbrace $ 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.
LA - eng
KW - Ramsey theory; Erdös-Rado theorem; canonization; Ramsey theory; Erdös-Rado theorem; canonization
UR - http://eudml.org/doc/247904
ER -