The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.

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...