Combinatorics and quantifiers
Nešetřil, Jaroslav
Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996), p. 433-443 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1996-01-01
Classification:  03C80,  03E05,  04A20,  05C55 
@article{118850,
     author = {Jaroslav Ne\v set\v ril},
     title = {Combinatorics and quantifiers},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {37},
     year = {1996},
     pages = {433-443},
     zbl = {0881.05096},
     mrnumber = {1426908},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118850}
}

Nešetřil, Jaroslav. Combinatorics and quantifiers. Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996) pp. 433-443. http://gdmltest.u-ga.fr/item/118850/

Alon N. Personal communication, via J. Spencer, .

Hella L.; Luosto K.; Väänänen J. The Hierarchy Theorem for generalized quantifiers, to appear in the Journal of Symbolic Logic. | MR 1412511

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. (1995) | MR 1336413

Lesniak-Foster L.; Straight H.J. The chromatic number of a graph, Ars Combinatorica 3 (1977), 39-46. (1977) | MR 0469805

Lindström P. First order predicate logic with generalized quantifiers, Theoria 32 (1966), 186-195. (1966) | MR 0244012

Luosto K. Personal communication, .

Mostowski A. On a generalization of quantifiers, Fundamenta Mathematicae 44 (1957), 12-36. (1957) | MR 0089816 | Zbl 0078.24401

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

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. (1978) | MR 0523311

Nešetřil J.; Rödl V. A structural generalization of the Ramsey theorem, Bull. Amer. Math. Soc. 83 (1977), 127-128. (1977) | MR 0422035

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

Väänänen J. Unary quantifiers on finite structures, to appear.

Westerståhl D. Personal communication, .