Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Ramsey theory; Erdös-Rado theorem; canonization
Ramsey theory; Erdös-Rado theorem; canonization
Summary:
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.
References:
[ErRa] Erdös P., Rado R.: A combinatorial theorem. Journal of the London Mathematical Society 25 (1950), 249-255. MR 0037886
[ErSp] Erdös P., Spencer J.: Probabilistic Methods in Combinatorics. Academic Press, New York, 1974. MR 0382007
[GrRoSp] Graham R., Rothschild B., Spencer J.: Ramsey Theory. Willey - Interscience Series in Discrete Mathematics, Willey, New York, 1980. MR 0591457 | Zbl 0705.05061
[LeRo93] Lefmann H., Rödl V.: On canonical Ramsey numbers for complete graphs versus paths. Journal of Combinatorial Theory, ser. B 58 (1993), 1-13. MR 1214886
[LeRo94] Lefmann H., Rödl V.: preprint.
[Ra86] Rado R.: Note on canonical partitions. Bulletin London Mathematical Society 18 (1986), 123-126. MR 0818813 | Zbl 0584.05006
[Sh37] Shelah S.: A two-cardinal theorem. Proceedings of the American Mathematical Society 48 (1975), 207-213. MR 0357105 | Zbl 0302.02017
Search
Partner of
