Let $\left(\genfrac{}{}{0pt}{}{I}{m}\right)$ be the set of subsets of $I$ of cardinality $m$. Let $f$ be a coloring of $\left(\genfrac{}{}{0pt}{}{I}{m}\right)$ and $g$ a coloring of $\left(\genfrac{}{}{0pt}{}{I}{m}\right)$. We write $f\to g$ if every $f$-homogeneous $H\subseteq I$ is also $g$-homogeneous. The least $m$ such that $f\to g$ for some $f:\left(\genfrac{}{}{0pt}{}{I}{m}\right)\to k$ is called the $k$-width of $g$ and denoted by $w_k\left(g\right)$. 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\left(g\right)=m$. In the second part of the paper we give applications of wide colorings in the theory of generalized quantifiers....

A family f₁,..., fₙ of operators on a complete metric space X is called contractive if there exists a positive λ < 1 such that for any x,y in X we have $d(f_i\left(x\right),f_i\left(y\right))\le \lambda d(x,y)$ for some i. Austin conjectured that any commuting contractive family of operators has a common fixed point, and he proved this for the case of two operators. We show that Austin’s conjecture is true for three operators, provided that λ is sufficiently small.

The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification...

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 ${\left[1,\cdots ,m^{*}\right]}^n$, for some $A\in {\left[1,\cdots ,m^{*}\right]}^m$, the question of when the equality $f\left(i_1,\cdots ,i_n\right)=f\left(j_1,\cdots ,j_n\right)$ (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,\cdots ,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.

In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.