| Title:
|
Combinatorics and quantifiers (English) |
| Author:
|
Nešetřil, Jaroslav |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
37 |
| Issue:
|
3 |
| Year:
|
1996 |
| Pages:
|
433-443 |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $\binom{I}{m}$ be the set of subsets of $I$ of cardinality $m$. Let $f$ be a coloring of $\binom{I}{m}$ and $g$ a coloring of $\binom{I}{m}$. We write $f\rightarrow g$ if every $f$-homogeneous $H\subseteq I$ is also $g$-homogeneous. The least $m$ such that $f\rightarrow g$ for some $f:\binom{I}{m}\rightarrow k$ is called the {\sl $k$-width} of $g$ and denoted by $w_k(g)$. In the first part of the paper we prove the existence of colorings with high $k$-width. In particular, we show that for each $k>0$ and $m>0$ there is a coloring $g$ with $w_k(g)=m$. In the second part of the paper we give applications of wide colorings in the theory of generalized quantifiers. In particular, we show that for every monadic similarity type $t=(1,\ldots,1)$ there is a generalized quantifier of type $t$ which is not definable in terms of a finite number of generalized quantifiers of a smaller type. (English) |
| Keyword:
|
generalized quantifier |
| Keyword:
|
Ramsey theory |
| MSC:
|
03C80 |
| MSC:
|
03E05 |
| MSC:
|
04A20 |
| MSC:
|
05C55 |
| idZBL:
|
Zbl 0881.05096 |
| idMR:
|
MR1426908 |
| . |
| Date available:
|
2009-01-08T18:25:07Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118850 |
| . |
| Reference:
|
[1] Alon N.: Personal communication, via J. Spencer.. |
| Reference:
|
[2] Hella L., Luosto K., Väänänen J.: The Hierarchy Theorem for generalized quantifiers.to appear in the Journal of Symbolic Logic. MR 1412511 |
| Reference:
|
[3] Kolaitis Ph., Väänänen J.: Pebble games and generalized quantifiers on finite structures.Annals of Pure and Applied Logic 74 (1995), 23-75; Abstract in {\sl Proc. 7th IEEE Symp. on Logic in Computer Science}, 1992. MR 1336413 |
| Reference:
|
[4] Lesniak-Foster L., Straight H.J.: The chromatic number of a graph.Ars Combinatorica 3 (1977), 39-46. MR 0469805 |
| Reference:
|
[5] Lindström P.: First order predicate logic with generalized quantifiers.Theoria 32 (1966), 186-195. MR 0244012 |
| Reference:
|
[6] Luosto K.: Personal communication.. |
| Reference:
|
[7] Mostowski A.: On a generalization of quantifiers.Fundamenta Mathematicae 44 (1957), 12-36. Zbl 0078.24401, MR 0089816 |
| Reference:
|
[8] Nešetřil J.: Ramsey Theory.In: {\sl Handbook of Combinatorics}, (ed. R.L. Graham, M. Grötschel, L. Lovász), North-Holland, 1995. MR 1373681 |
| Reference:
|
[9] Nešetřil J., Rödl V.: A simple proof of Galvin-Ramsey property of all finite graphs and a dimension of a graph.Discrete Mathematics 23 (1978), 49-55. MR 0523311 |
| Reference:
|
[10] Nešetřil J., Rödl V.: A structural generalization of the Ramsey theorem.Bull. Amer. Math. Soc. 83 (1977), 127-128. MR 0422035 |
| Reference:
|
[11] Shelah S.: A finite partition theorem with double exponential bounds.to appear in {\sl Mathematics of Paul Erdös} (ed. R.L. Graham and J. Nešetřil), Springer Verlag, 1996. MR 1425218 |
| Reference:
|
[12] Väänänen J.: Unary quantifiers on finite structures.to appear. |
| Reference:
|
[13] Westerståhl D.: Personal communication.. |
| . |
