| Title:
|
Finite canonization (English) |
| Author:
|
Shelah, Saharon |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
37 |
| Issue:
|
3 |
| Year:
|
1996 |
| Pages:
|
445-456 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Ramsey theory |
| Keyword:
|
Erdös-Rado theorem |
| Keyword:
|
canonization |
| MSC:
|
05C55 |
| MSC:
|
05D10 |
| MSC:
|
11B75 |
| idZBL:
|
Zbl 0881.05097 |
| idMR:
|
MR1426909 |
| . |
| Date available:
|
2009-01-08T18:25:11Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118851 |
| . |
| Reference:
|
[ErRa] Erdös P., Rado R.: A combinatorial theorem.Journal of the London Mathematical Society 25 (1950), 249-255. MR 0037886 |
| Reference:
|
[ErSp] Erdös P., Spencer J.: Probabilistic Methods in Combinatorics.Academic Press, New York, 1974. MR 0382007 |
| Reference:
|
[GrRoSp] Graham R., Rothschild B., Spencer J.: Ramsey Theory.Willey - Interscience Series in Discrete Mathematics, Willey, New York, 1980. Zbl 0705.05061, MR 0591457 |
| Reference:
|
[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 |
| Reference:
|
[LeRo94] Lefmann H., Rödl V.: preprint.. |
| Reference:
|
[Ra86] Rado R.: Note on canonical partitions.Bulletin London Mathematical Society 18 (1986), 123-126. Zbl 0584.05006, MR 0818813 |
| Reference:
|
[Sh37] Shelah S.: A two-cardinal theorem.Proceedings of the American Mathematical Society 48 (1975), 207-213. Zbl 0302.02017, MR 0357105 |
| . |
