Combinatorics and quantifiers

Nešetřil, Jaroslav. "Combinatorics and quantifiers." Commentationes Mathematicae Universitatis Carolinae 37.3 (1996): 433-443. <http://eudml.org/doc/247917>.

@article{Nešetřil1996,
abstract = {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 $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.},
author = {Nešetřil, Jaroslav},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {generalized quantifier; Ramsey theory; generalized quantifier; Ramsey theory},
language = {eng},
number = {3},
pages = {433-443},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Combinatorics and quantifiers},
url = {http://eudml.org/doc/247917},
volume = {37},
year = {1996},
}

TY - JOUR
AU - Nešetřil, Jaroslav
TI - Combinatorics and quantifiers
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1996
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 37
IS - 3
SP - 433
EP - 443
AB - 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 $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.
LA - eng
KW - generalized quantifier; Ramsey theory; generalized quantifier; Ramsey theory
UR - http://eudml.org/doc/247917
ER -