zbMATH — the first resource for mathematics

Finite canonization. (English) Zbl 0881.05097
This paper concerns the generalized Ramsey theory. The canonization theorem, due to P. Erdös and R. Rado, is considered. It says that for given positive integers \(m\), \(n\) a number ER\((n;m)\) exists such that for each \(m^*\geq\text{ER}(n;m)\) and each function \(f\) whose domain is the set \([1,\dots ,m^*]^n\) of all \(n\)-element subsets of the set \(\{1,\dots ,m^*\}\) and for some \(A\in [1,\dots ,m^*]^n\) there exists \(v\subseteq \{1,\dots ,n\}\) such that \(f(i_1,\dots ,i_n)=f(j_1,\dots ,j_n)\) (where \(i_1<i_2<\dots <i_n\) and \(j_1<j_2<\dots <j_n\) are from \(A\)) holds if and only if \(i_l=j_l\) for all \(l\in v.\) In the paper the bound for ER\((n;m)\) is improved so that for fixed \(n\) the number of exponentiations needed to calculate ER\((n;m)\) is the best possible.

05C55 Generalized Ramsey theory
11B75 Other combinatorial number theory
Full Text: EuDML arXiv