%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% AMSLaTeX file for
%
% ``On Essentially Infinite Colourings''
% 
% renamed to ``Essentially Infinite Colourings of Graphs''
%
% by B. Bollob\'as, Y. Kohayakawa, and R.H. Schelp
%
% Revision: 11 February 1999
% 
% JLMS manuscript no.~31.105 
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=
\documentclass[11pt]{amsart}

\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below
  {}%         Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\itshape}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\theoremstyle{plain}
\newtheorem{theorem}             {Theorem}       
\newtheorem{claim}     [theorem] {Claim}         
\newtheorem{lemma}     [theorem] {Lemma}         
\newtheorem{corollary} [theorem] {Corollary}     
\newtheorem{fact}      [theorem] {Fact}          
\newtheorem{conjecture}[theorem] {Conjecture}    
\newtheorem{problem}   [theorem] {Problem}       

\theoremstyle{note}
\newtheorem{remark}              {Remark}       
\newtheorem{example}   [remark] {Example}       
\newtheorem{note}      [remark] {Note}       
\newtheorem{definition} [remark] {Definition}       

\newtheorem{case}                {Case}       

\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\def\casebody{\noindent\ignorespaces}

\def\({\left(}
\def\){\right)}  
\let\:=\colon
\def\ZZ{{\mathbb Z}}
\def\cC{{\mathcal C}}
\def\tcC{\widetilde{\mathcal C}}
\def\cCloc{{\mathcal C}_{\text{\rm loc}}}
\def\cClocalk{{\mathcal C}_{\text{\textrm{local-}}k}}
\def\cCall{{\mathcal C}_{\text{\rm all}}}
\def\cCinj{{\mathcal C}_{\text{\rm inj}}}
\def\cD{{\mathcal D}}
\def\kloc{k_{\text{\rm loc}}}
\def\im{\mathop{\rm im}\nolimits}
\def\tgamma{\widetilde\gamma}
\def\gammabip{\gamma_{\text{\rm bip}}}
\def\gammaconst{\gamma_{\text{\rm const}}}
\def\gammavertex{\gamma_<}
\def\gammainj{\gamma_{\text{\rm inj}}}
\def\gammamatch{\gamma_{\text{\rm match}}}
\def\cCbip{\cC_{\text{\rm bip}}}
\def\tT{{\widetilde T}}
\def\tV{{\widetilde V}}
\let\del=\partial
\let\epsilon=\varepsilon
\let\phi=\varphi

\begin{document}
\title{Essentially Infinite Colourings of Graphs} 

\author{B.~Bollob\'as} 
\address{Department of Mathematical Sciences, The
  University of Memphis, Memphis, TN 38152, USA, {\rm and} Trinity College, 
  Cambridge CB2~1TQ, UK} \email{bollobas@msci.memphis.edu}

\author{Y.~Kohayakawa} 
\address{Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de S\~ao
  Paulo, Rua do Mat\~ao 1010, 05508--900~S\~ao Paulo, Brazil}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\address{{\rm(Visiting)} Department of Mathematical
%    Sciences, The University of Memphis, Memphis, TN 38152, USA {\rm and}
%  {\rm(Permanent)} Instituto de Matem\'atica e Estat\'{\i}stica, Universidade
%  de S\~ao Paulo, Rua do Mat\~ao 1010, 05508--900~S\~ao Paulo, Brazil}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\email{yoshi@ime.usp.br}

\author{R.$\,$H.~Schelp}
\address{Department of Mathematical Sciences, The
  University of Memphis, Memphis, TN 38152, USA} 
\email{schelpr@msci.memphis.edu}
%
\dedicatory{Dedicated to the memories of Professors Paul Erd\H os and Richard
  Rado}
%
\thanks{The second author was partially supported by FAPESP
  (Proc.~96/04505--2), by CNPq (Proc.~300334/93--1), and by MCT/FINEP
  (PRONEX project~107/97).  Part of this work was done while the
  second author was visiting The University of Memphis, whose kind
  hospitality and support he gratefully acknowledges.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\thanks{Part of this work was done while the second author was visiting The
%  University of Memphis, whose kind hospitality and support he gratefully
%  acknowledges.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subjclass{Primary 05D10; % Ramsey theory
  %05C55,                 % Generalised Ramsey theory
  %05C80;                 % Random graphs 
  Secondary: 05C35}       % Extremal problems
\keywords{Ramsey theory, canonical colourings, anti-Ramsey type results, local
  colourings} 
%\date{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
  The classical Canonical Ramsey Theorem of Erd\H os and Rado states
  that, for any integer~$q\geq1$, any edge colouring of a large enough
  complete graph contains one of three canonically coloured complete
  subgraphs of order~$q$.  Of these canonical subgraphs, one is
  coloured monochromatically while each of the other two have its edge
  set coloured with many different colours.  In this paper, we present
  a condition on colourings that, roughly speaking, requires them to
  make effective use of many colours (``essential infiniteness'');
  this condition is then shown to imply that the colourings in
  question must contain large refinements of one of two `unavoidable'
  colourings that are rich in colours.  As it turns out, one of these
  unavoidable colourings is one of the canonical colourings of Erd\H
  os and Rado, and the other is a `bipartite variant' of this
  colouring.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\maketitle
\thispagestyle{empty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}
A seminal result of Erd\H os and Rado~\cite{ErdosRadoCanonical} states
that if we colour the edges of a large enough complete graph, then a
large \textit{canonically coloured} complete subgraph must occur in our
colouring.  If our colouring uses only a bounded number of colours,
and hence it is `poor' in colours, then the canonically coloured
complete subgraph that we are guaranteed to have is in fact a
\textit{monochromatic} complete graph.  This is Ramsey's well known
theorem~\cite{Ram}.  What, then, is the situation if our colouring is
`rich' in colours?  In other words, \textsl{what are the unavoidable
  substructures in rich colourings}?  

The main result of this paper, Theorem~\ref{thm:main}, gives a
complete answer to this question.  At this early stage, the reader
will most probably find more useful the dry but more direct
formulation of Theorem~\ref{thm:main} given in
Remark~\ref{thm:unwrapped}; the only definition that the reader will
need is given in Definition~\ref{def:bounded}.  We hope that the
discussion that follows will put our result in a broader context.

%\subsection{The canonical colourings of Erd\H os and Rado}
%\label{sec:can-col}
Let us first recall the canonical colourings of Erd\H os and Rado.
There are three canonical colourings of the $n$-vertex complete
graph~$K^n$, namely~$\gammaconst$, $\gammavertex$, and~$\gammainj$.
The colouring~$\gammaconst$ assigns the same colour to all the edges
of~$K^n$ and~$\gammainj$ assigns all different colours.  Strictly
speaking, $\gammavertex$ is a class of colourings.  To describe a
member of this class, we assume that the vertex set of~$K^n$ is
linearly ordered by some ordering~$<$.  Then, two edges have the same
colour under~$\gammavertex$ if and only if their $<$-minimal elements
coincide.  The theorem of Erd\H os and Rado states that, for any given
integer~$q\geq1$, all sufficiently large complete graphs~$K^n$ with an
arbitrary edge-colouring $\gamma\:E(K^n)\to\ZZ$
%\begin{equation*}
%  %\label{eq:general_gamma}
%  \gamma\:E(K^n)\to\ZZ
%\end{equation*}
must contain a complete subgraph~$K^q$ on~$q$ vertices such that~$\gamma$
restricted to~$E(K^q)$ may be identified with one of the
colourings~$\gammaconst$, $\gammavertex$, and~$\gammainj$, if we
disregard the names of the colours.
%(in other words, the partition of the edge set of~$K^q$ induced
%by~$\gamma$ coincides with the partition induced by one of the three
%canonical colourings).

If we require the given colouring~$\gamma$ to use at most a fixed
number of colours, the canonical colourings~$\gammavertex$
and~$\gammainj$ will not arise (as long as~$q$ is large enough).  Thus
a monochromatic~$K^q$ will always be present.  Hence, the boundedness
of the number of colours to be used in~$\gamma$ ``forces'' the
conclusion in the Erd\H os--Rado theorem.  A slightly weaker condition
that forces the same conclusion is that~$\gamma$ should be a locally
bounded colouring, that is, only a bounded number of colours should be
present at any given vertex.  Many Ramsey type results for such
colourings are known (see, \textit{e.g.}, Gy{\'a}rf{\'a}s \textit{et
  al.}~\cite{GyLeNeRoSchTuLocal,gyarfas87:_ramsey}, Ruci\'nski and
Truszczy\'nski~\cite{rucinski97Local},
Truszczy\'nski~\cite{truszczynski92:_gener}, Truszczy\'nski and
Tuza~\cite{TruTuzaLocal}).  On the other hand, a way of forcing the
canonical colouring~$\gammainj$ is to impose the condition
that~$\gamma$ should be a \textit{proper} edge-colouring,
\textit{i.e.}, no two edges of the same colour should share an
endvertex.  Let us mention in passing that surprisingly precise
estimates exist for the numerical problems that arise in connection
with this observation.  See, \textit{e.g.}, Alon, Lefmann, and
R\"odl~\cite{ALR}, Babai~\cite{babai85:_ramsey}, and Lefmann, R\"odl,
Wysocka~\cite{lefmann96:_multic}.

Intuitively, the condition that~$\gamma$ should be proper is a local
condition that imposes that the colours should be `very mixed'.  Is
there a definition of `richness' for colourings, more global in nature
(say, in terms of the number of colours `effectively' used
by~$\gamma$), that forces the conclusion in the Erd\H os--Rado theorem
to be~$\gammavertex$ or~$\gammainj$?  Put simply, what can we say
about colourings~$\gamma$ that use \textit{many} colours?

Consider the following example: let~$\gammamatch$ be the colouring
that assigns colour~$0$ to all edges of~$K^n$, except for the edges of
a fixed matching~$M\subset E(K^n)$ with~$|M|=\lfloor n/2\rfloor$.
Furthermore, $\gammamatch$ is injective on~$M$, and colour~$0$ is not
used on any edge from~$M$.  Then the number of colours that have been
used by~$\gammamatch$ is large, but no large~$\gammavertex$
or~$\gammainj$ occurs in~$\gammamatch$.  Thus, the na\"\i ve condition
that~$\gamma$ should use many colours is too weak.

Let us observe that~$\gammamatch$ is just a small perturbation of a
bounded colouring: if we disregard a certain vanishing proportion of
the edges of~$K^n$, we are left with only one colour.  Thus, we may
say that~$\gammamatch$ does not \textit{effectively} use many colours,
and hence it is, essentially, a bounded or \textit{finite} colouring.
To exclude examples such as~$\gammamatch$, we impose the condition
that~$\gamma$ should not be `close' to a bounded colouring.  More
precisely, we impose the condition that the \textsl{deletion of no
  vanishing proportion of the edge set of~$K^n$ should lead to a
  finite colouring}.  We call such colourings \textit{essentially
  infinite}.  The formal definition is given in
Section~\ref{sec:basics} (see Definition~\ref{def:ess_inf}).

In the main result of this paper, we identify the unavoidable
substructures in essentially infinite colourings (see
Theorem~\ref{thm:main}).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Our result is best possible in a certain
%precise sense (see Remark~\ref{thm:beste_moeglich}).  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As an application of our result, we completely characterize certain
natural local conditions on colourings that imply the essential
finiteness of the colourings (see Corollary~\ref{cor:main}).  We
believe that this interplay between local and global phenomena is of
interest.  The problem of giving local conditions to guarantee
essential finiteness of colourings was inspired by a conjecture of
Clapsadle and Schelp~\cite{clapsadle94:_local}.

The organization of this paper is as follows.  In
Section~\ref{sec:basics}, we carefully state and discuss the
definitions required in the sequel.  The main result is presented in
Section~\ref{sec:main_result}.  The above-mentioned application of our
main result is given in Section~\ref{sec:local}.  The proofs of our
results are presented in Section~\ref{sec:proofs}.  We close with some
concluding remarks in Section~\ref{sec:concluding}.

\section{The main results}
\label{sec:results}

\subsection{Basic definitions}
\label{sec:basics}
The basic objects that we shall be dealing with here are edge-colourings of
complete graphs, namely, arbitrary functions
\begin{equation*}
  %\label{eq:arb_colg}
  \gamma\:E(K)\to\ZZ,  
\end{equation*}
where~$K$ is a complete graph and, for the sake of definiteness, we
let the colours to be used be the integers.  If~$K$ has~$n$ vertices,
and we wish to emphasise that~$\gamma$ above is an edge-colouring of a
complete graph of order~$n$, we write~$\gamma^n$ for~$\gamma$.  In the
sequel, we use the simpler term \textit{colouring} to mean
edge-colouring of a complete graph.

We say that two colourings~$\gamma\:E(K^n)\to\ZZ$
and~$\gamma'\:E(K^m)\to\ZZ$ are \textit{isomorphic} if there are
bijections~$\phi\:V(K^n)\to V(K^m)$ and~$\psi\:\ZZ\to\ZZ$ for which
$$
\psi\gamma=\gamma'\phi^{(2)},
$$
where~$\phi^{(2)}$ is the map~$E(K^n)\to E(K^m)$ naturally induced
by~$\phi$.  In other words, $\gamma$ and~$\gamma'$ are isomorphic
if~$n=m$ and there is a bijection between~$V(K^n)$ and~$V(K^m)$ under
which the partitions of~$E(K^n)$ and~$E(K^m)$ naturally defined
by~$\gamma$ and~$\gamma'$ may be identified.

\begin{example}
  \label{ex:k-colgs}
  If~$k\geq1$ is an integer, we let~$\cC_k$ be the set of colourings that use
  at most~$k$ colours.  Thus, $\gamma\in\cC_k$ if and only if~$|\im\gamma|\leq
  k$.   
\end{example}

\begin{example}
  \label{ex:local-k}
  If~$k\geq1$ is an integer, we let~$\cClocalk$ be the set of \textit{local
    $k$-colourings}.  Thus, $\gamma\:E(K)\to\ZZ$ belongs to~$\cClocalk$ if and
  only if~$|\gamma(\del(x))|\leq k$ for all vertices~$x\in V(K)$, where, here
  and below, we write~$\del(x)$ for the set of edges incident to~$x$.
\end{example}

The following terminology will be convenient for the sequel.

\begin{definition}
  \label{def:bounded}
  Suppose~$\gamma=\gamma^n\:E(K^n)\to\ZZ$ is an arbitrary colouring, and
  let~$k\geq1$ and~$0<\epsilon<1$ be given.  We shall say that~$\gamma$ is a
  \textit{$(k,\epsilon)$-bounded} colouring if there is a set~$S\subset\ZZ$
  with~$|S|\leq k$ and
  \begin{equation*}
    %\label{eq:k_eps-bdd}
    |\gamma^{-1}(S)|\geq(1-\epsilon){n\choose2}.
  \end{equation*}  
\end{definition}

Thus, we may say that~$\gamma$ is $(k,\epsilon)$-bounded if it uses
not more than~$k$ colours `modulo a set of edges of
measure~$\epsilon$'.  As an example, we mention that~$\gammamatch$
defined in the introduction is $(1,1/(n-1))$-bounded.
%In the sequel, we shall sometimes say that~$\gamma$ is
%\textit{$(k,\epsilon)$-unbounded} %or
%%\textit{$(k,\epsilon)$-multicoloured} 
%if~$\gamma$ is not $(k,\epsilon)$-bounded.
The following quite simple but pleasant result, proved in
Section~\ref{sec:pf_lem:local_k}, shows that a simple local condition
can guarantee $(k,\epsilon)$-boundedness for arbitrarily
small~$\epsilon>0$.

\begin{lemma}
  \label{lem:local_k}
  For any~$0<\epsilon<1$ and~$k\geq1$, there is an
  integer~$\kloc=\kloc(\epsilon,k)$ such that any local $k$-colouring is
  $(\kloc,\epsilon)$-bounded.
\end{lemma}

We may rephrase the lemma above by saying that local $k$-colourings are
`essentially finite'.  To be precise, we make the following definition.  

\begin{definition}
  \label{def:ess_finite}
  We shall say that the members of a given class~$\cC$ of colourings
  are \textit{essentially finite} if, for any~$0<\epsilon<1$, there
  exists an integer~$k=k(\epsilon)\geq1$ for which any member of~$\cC$
  is $(k,\epsilon)$-bounded.
\end{definition}

\begin{example}
  \label{ex:local-k-is-fin} 
  Trivially, $\cC_k$ is a class of essentially finite colourings for
  any fixed~$k\geq1$.  Lemma~\ref{lem:local_k} says that the same
  holds for~$\cClocalk$.
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Clearly, to say that the colourings of a class~$\cC$ are \textit{not}
%essentially finite means that there is an~$0<\epsilon<1$ such that, for any
%integer~$k\geq1$, there is~$\gamma\in\cC$ that is $(k,\epsilon)$-unbounded.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%In fact, a moment's thought shows that, in fact, in this case, there
%is~$0<\epsilon<1$ such that, for any~$k\geq1$, there are infinitely many
%non-isomorphic $(k,\epsilon)$-unbounded colourings~$\gamma$ in~$\cC$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Loosely speaking, our aim is to show that families of colourings that
are \textit{not} essentially finite must contain certain unavoidable
substructures.  As to be expected, such substructures will be `rich in
colours'.  

\begin{remark}
  \label{ex:all_colgs}
  Naturally, the family~$\cCall$ of \textit{all} colourings is not
  essentially finite.  However, we cannot claim that all
  members~$\gamma\in\cCall$ (or all members~$\gamma=\gamma^n\in\cCall$
  with~$n$ sufficiently large) comprise `subcolourings' that are rich
  in colours, because, for instance, $\cCall$ contains monochromatic
  (that is, constant) colourings.
\end{remark}

In view of trivial examples such as~$\cCall$ above, we make the
following definition.

\begin{definition}
  \label{def:ess_inf}
  Let~$\cC$ be an infinite class of colourings.  Then, we shall say
  that the members of~$\cC$ are \textit{essentially infinite} if there
  exists~$0<\epsilon=\epsilon(\cC)<1$ such that, for any
  integer~$k\geq1$, there is~$n_0=n_0(k)$ such that
  \textsl{all~$\gamma^n\in\cC$ with~$n\geq n_0$ fail to be
    $(k,\epsilon)$-bounded}.
\end{definition}

In the sequel, if~$\cC$ is a class of essentially infinite colourings,
$k\geq1$ is an integer, and~$\epsilon>0$ is a small enough real, we
shall write~$n_\cC(k,\epsilon)$ for the least integer with the
property that any~$\gamma=\gamma^n\in\cC$ with~$n\geq
n_\cC(k,\epsilon)$ is not $(k,\epsilon)$-bounded.  Notice
that~$n_\cC(k,\epsilon)$ is indeed well-defined as long as~$\epsilon$
is small enough.

A simple argument shows that any class~$\cC$ whose members are not
essentially finite contains a subset~$\cC'\subset\cC$ of essentially
infinite colourings.  A trivial example of a class of essentially
infinite colourings is the class of injective colourings
$$
  \cCinj=\{\gamma\:\gamma\text{ is injective}\}.
$$
The following two examples of essentially infinite colourings will be
crucial in what follows.

\begin{example}
  \label{ex:ess_inf_linear}
  Let us write~$\gamma_<=\gamma_<^n\:E(K^n)\to\ZZ$ for the colouring
  under which~$\gamma_<(ij)=i$ for all~$1\leq i<j\leq n$, where we
  suppose~$V(K^n)=[n]=\{1,\dots,n\}$.  The class~$\cC_<$ of colourings
  consists of all the colourings~$\gamma$ that are isomorphic to
  some~$\gamma_<$.  It is immediate that~$\cC_<$ is a class of
  essentially infinite colourings.  One may in fact take
  any~$0<\epsilon<1$ for~$\epsilon(\cC_<)$ in
  Definition~\ref{def:ess_inf}.
\end{example}

\begin{example}
  \label{ex:ess_inf_bip}
  Suppose now that~$K^{2n}$ ($n\geq1$) has vertex
  set
  $$
    V(K^{2n})=\{u_1,\dots,u_n,w_1,\dots,w_n\}.
  $$
  We write~$\gammabip=\gammabip^{2n}$ for the colouring of~$E(K^{2n})$ under
  which, for all~$i$ and~$j$, we have~$\gamma(u_iw_j)=i$ and, for all~$i\neq
  j$, we have~$\gamma(u_iu_j)=\gamma(w_iw_j)=0$.  We let~$\cCbip$ consist of
  all the colourings~$\gamma$ that are isomorphic to some~$\gammabip$.  It is
  again immediate that~$\cCbip$ is a class of essentially infinite
  colourings.  In this case, any~$0<\epsilon<1/2$ will do
  for~$\epsilon(\cCbip)$. 
\end{example}

We shall see soon that, in a certain precise sense, the two classes of
essentially infinite colourings~$\cC_<$ and~$\cCbip$ play a more
fundamental r\^ole than~$\cCinj$.

\subsection{The main result}
\label{sec:main_result}
Roughly speaking, our main result says that any large enough
essentially infinite colouring must `contain' arbitrarily large
members from~$\cC_<\cup\cCbip$.  We need to define a suitable notion
of containment to make this precise.

%\begin{definition}
%  \label{def:induced}
%  Suppose~$\gamma\:E(K^n)\to\ZZ$ is a colouring, and let~$\tV\subset
%  V(K^n)$ be given.  We may then naturally define the \textit{induced
%  colouring} or the \textit{restricted colouring} 
%  $$
%    \gamma_\tV\:{\tV\choose2}\to\ZZ
%  $$
%  by restricting~$\gamma$ to the complete graph~$K^n[\tV]$.  
%\end{definition}

%\begin{definition}
%  \label{def:refinement}
%  Suppose~$\gamma_1$, $\gamma_2\:E(K^n)\to\ZZ$ are colourings.  We say
%  that~$\gamma_1$ \textit{refines}~$\gamma_2$ if the partition
%  $$
%    E(K^n)=\bigcup_{i\in\ZZ}\gamma_1^{-1}(i)
%  $$
%  %
%  of~$E(K^n)$ naturally determined by~$\gamma_1$ refines the
%  corresponding partition determined by~$\gamma_2$.  In other words,
%  $\gamma_1$ is a refinement of~$\gamma_2$ if, for all~$e$, $f\in
%  E(K^n)$ with~$\gamma_1(e)=\gamma_1(f)$, we
%  have~$\gamma_2(e)=\gamma_2(f)$.
%\end{definition}

%\begin{definition}
%  \label{def:contain}
%  We shall say that a colouring~$\tgamma$ is \textit{contained} in a
%  colouring~$\gamma\:E(K^n)\to\ZZ$ if there is a refinement
%  of~$\tgamma$ that is isomorphic to a restriction 
%  %
%  $
%    \gamma_\tV%\:{\tV\choose2}\to\ZZ
%  $ 
%  %
%  of~$\gamma$ for some~$\tV\subset V(K^n)$.  We shall
%  write~$\tgamma\preceq\gamma$ if~$\tgamma$ is contained in~$\gamma$.
%\end{definition}

\begin{definition}
  \label{def:contain}
  We shall say that a colouring~$\tgamma\:E(K^m)\to\ZZ$ is
  \textit{contained} in a colouring~$\gamma\:E(K^n)\to\ZZ$ if and only
  if there is an injection~$\phi\:V(K^m)\hookrightarrow V(K^n)$ such
  that if~$e$ and~$f\in E(K^m)$ and~$\tgamma(e)\neq\tgamma(f)$,
  then~$\gamma(\phi^{(2)}(e))\neq\gamma(\phi^{(2)}(f))$.  As before,
  $\phi^{(2)}$ denotes the map~$E(K^m)\to E(K^n)$ naturally induced
  by~$\phi$.  We shall write~$\tgamma\preceq\gamma$ if~$\tgamma$ is
  contained in~$\gamma$.
\end{definition}

It is immediate that, as the notation suggests, the relation of
containment defined above is an order relation.  Intuitively speaking,
if~$\gamma$ contains~$\gamma'$ then, at least somewhere, the
colouring~$\gamma$ is `more colourful' than (or at least as colourful
as) the colouring~$\gamma'$.

Clearly, if~$\gamma^n$ is a constant colouring,
then~$\gamma^n\preceq\tgamma^{\,m}$ for any~$\tgamma^{\,m}$
with~$n\leq m$.  Also, if~$\tgamma^{\,m}$ is an injective colouring,
then~$\gamma^n\preceq\tgamma^{\,m}$ for any~$\gamma^n$ with~$n\leq m$.
In order to gain further familiarity with the definition above, the
reader is invited to show that no~$\gamma_<^n$ ($n\geq4$) is contained
in any~$\gammabip$ and that no~$\gammabip^{2n}$ ($n\geq2$) is
contained in any~$\gamma_<$.  One may thus say that the
colourings~$\gamma_<$ and~$\gammabip$ are intrinsically distinct sorts
of essentially infinite colourings.

Our main result, Theorem~\ref{thm:main}, states that~$\gamma_<$
and~$\gammabip$ are unavoidable objects in essentially infinite colourings.
Before we state our result, for the sake of convenience, we extend
the~$\preceq$ relation to \textit{classes} of colourings.

\begin{definition}
  \label{def:cC1preceqcC2}
  Let~$\cC_1$ and~$\cC_2$ be two classes of colourings.  We shall write
  \begin{equation*}
    %\label{eq:cC1preceqcC2}
    \cC_1\preceq\cC_2
  \end{equation*}
  if, for any~$q_0\geq1$, there is an integer~$n_0=n_0(q_0)\geq1$ such
  that any~$\gamma_2=\gamma_2^n\in\cC_2$ with~$n\geq n_0$ contains some
  member~$\gamma_1=\gamma_1^q$ of~$\cC_1$ with~$q\geq q_0$.
\end{definition}

Note that the~$\preceq$ relation, when applied to classes of colourings, is
reflexive and transitive (and hence it is a so-called \textit{quasi-order}).
We may now state our result. 

\begin{theorem}
  \label{thm:main}
  For any class~$\cC$ of essentially infinite colourings, we have
  $$
    \cC_<\cup\cCbip\;\preceq\;\cC.
  $$ 
\end{theorem}

Theorem~\ref{thm:main} is best possible in the following sense. 

\begin{remark}
  \label{thm:beste_moeglich}
  Suppose~$\tcC$ is a class of colourings with the property
  that~$\tcC\preceq\cC$ for any class~$\cC$ of essentially infinite
  colourings.  Then~$\tcC\;\preceq\;\cC_<\cup\cCbip$. 
\end{remark}

Thus, for any~$\tcC$ as in Remark~\ref{thm:beste_moeglich} and any
class~$\cC$ of essentially infinite colourings, we have
$$
  \tcC\;\preceq\;\cC_<\cup\cCbip\;\preceq\;\cC.
$$
%
Remark~\ref{thm:beste_moeglich} is, in fact, almost a tautology,
since~$\cC_<\cup\cCbip$ is a family of essentially infinite
colourings.  

\begin{remark}
  \label{thm:unwrapped}
  Theorem~\ref{thm:main} may be stated in the following direct but
  somewhat dry way.  For any~$q\geq1$ and~$0<\epsilon<1$, there
  exist~$k_0=k_0(q,\epsilon)$ and~$n_0=n_0(q,\epsilon)$ for which the
  following holds. If~$\gamma\:E(K^n)\to\ZZ$, where~$n\geq n_0$, is
  not $(\epsilon,k_0)$-bounded, then
  \begin{itemize}
  \item[(\textit{i})] there exists~$Z=\{z_1,\dots,z_q\}\subset V(K^n)$
    such that~$\gamma(z_iz_j)\neq\gamma(z_{i'}z_{j'})$ whenever~$i<j$,
    $i'<j'$, and~$i\neq i'$, or
  \item[(\textit{ii})] there exist~$U=\{u_1,\dots,u_q\}$
    and~$W=\{w_1,\dots,w_q\}$ such that
    $\gamma(u_iw_j)\neq\gamma(u_{i'}w_{j'})$ whenever~$i\neq i'$, and,
    moreover, no colour that occurs on the $U$--$W$ edges occurs
    within~$U$ or within~$W$.
  \end{itemize}
\end{remark}

It is a pleasant surprise that, in Remark~\ref{thm:unwrapped} above,
we \textit{have} to allow for case~(\textit{ii}), which describes
colourings distinct from the canonical colourings of Erd\H os and
Rado.

\subsection{Local versus global colourings}
\label{sec:local}
Our main application of Theorem~\ref{thm:main} is to do with the following
general question: are there purely local conditions on colourings that force
`essential finiteness'?  We have the following type of local condition in
mind.

Let~$H$ be a graph with at least one edge and let an integer~$k\geq1$ be
given.  We shall say that a colouring~$\gamma\:E(K^n)\to\ZZ$ is
\textit{$(H,k)$-local} if any subgraph~$H'$ of~$K^n$ isomorphic to~$H$
receives at most~$k$ colours under~$\gamma$.  For example, if~$H=K^{1,k+1}$,
the star with~$k+1$ rays, then a colouring is $(H,k)$-local if and only if it
is a local $k$-colouring.  For conciseness, write~$\cCloc(H,k)$ for the class
of $(H,k)$-local colourings.  Moreover, put
\begin{equation*}
  %\label{eq:def_f}
  f(H)=\max\{k\:\cCloc(H,k)\text{ is a class of essentially finite
                 colourings}\}. 
\end{equation*}
Our main result in this section, Corollary~\ref{cor:main},
determines~$f(H)$ exactly.  We need to introduce some notation.  Let a
colouring~$\gamma\:E(K^n)\to\ZZ$ be given.  Denote by~$\mu(H,\gamma)$
the maximal number of colours that the isomorphic copies~$H'\subset
K^n$ of~$H$ receive under~$\gamma$.  Furthermore, put
\begin{equation*}
  %\label{eq:def_mu}
  \mu(H,\cC)=\max\{\mu(H,\gamma)\:\gamma\in\cC\}
\end{equation*}
for any class of colourings~$\cC$.  Note that, then, $\mu(H,\cC)$ is the
smallest integer~$\mu$ for which we have~$\cC\subset\cCloc(H,\mu)$.
%\begin{equation*}
%  %\label{eq:mu_remark}
%  \cC\subset\cCloc(H,\mu).
%\end{equation*}
We now put
\begin{equation}
  \label{eq:def_muH}
  \mu(H)=\min\{\mu(H,\cC_<),\mu(H,\cCbip)\}.
\end{equation}
Our main result is then the following.

\begin{corollary}
  \label{cor:main}
  We have~$f(H)=\mu(H)-1$ for any graph~$H$ with at least one edge. 
\end{corollary}

One may easily check that~$\mu(C^3)=2$ and that~$\mu(C^\ell)=\lceil
\ell/2\rceil+1$ if~$\ell\geq4$, where, as usual, $C^\ell$ denotes the
cycle of length~$\ell$.  Moreover, $\mu(K^\ell)=\ell-1$.  Thus,
Corollary~\ref{cor:main} implies that~$f(C^3)=f(K^3)=1$,
$f(C^\ell)=\lceil\ell/2\rceil$ if~$\ell\geq4$, and~$f(K^\ell)=\ell-2$.

\section{Proofs}
\label{sec:proofs}

\subsection{Proof of Corollary~\ref{cor:main}}
\label{sec:proof_corollary}
We first prove that~$f(H)\leq\mu(H)-1$.  Suppose~$\mu(H)=\mu(H,\cC_<)$.
Then~$\cC_<\subset\cCloc(H,\mu(H))$, and~$\cCloc(H,\mu(H))$ cannot be
essentially finite, since~$\cC_<$ is essentially infinite.  The same argument
holds if~$\mu(H)=\mu(H,\cCbip)$.  Thus~$\cCloc(H,\mu(H))$ is not essentially
finite, which proves that~$f(H)<\mu(H)$.

Let us now show that~$f(H)<\mu(H)-1$ leads to a contradiction.
Put~$k=\mu(H)-1$ and suppose~$k>f(H)$.  Then~$\cCloc(H,k)$ is not
essentially finite, by the definition~$f(H)$.  Let
then~$\cC\subset\cCloc(H,k)$ be an infinite class of essentially
infinite colourings.  

Pick a large enough even integer~$q_0$ so
that $\mu(H,\cC_<)=\mu(H,\gamma_<^{q_0})$
and $\mu(H,\cCbip)=\mu(H,\gammabip^{q_0})$.  Theorem~\ref{thm:main}
implies that, then, there must be a colouring~$\gamma\in\cC$ for which
there exists~$\gamma_0^{q_0}\in\cC_<\cup\cCbip$
with~$\gamma_0^{q_0}\preceq\gamma$.  (Of course,
Theorem~\ref{thm:main} says that every~$\gamma=\gamma^n$ with~$n\geq
n_0(q_0)$ is such a colouring.)  Suppose~$\gamma_0^{q_0}\in\cC_<$; the
case in which~$\gamma_0^{q_0}\in\cCbip$ is similar.  Then
$$
\mu(H)\leq\mu(H,\cC_<)
      =\mu(H,\gamma_0^{q_0})
      \leq\mu(H,\gamma)
      \leq k=\mu(H)-1.
$$
%
The first inequality follows from~(\ref{eq:def_muH}), the equality
follows from the choice of~$q_0$, the next inequality follows from the
fact that~$\gamma_0^{q_0}\preceq\gamma$, and the last inequality
follows from the fact that~$\gamma\in\cC\subset\cCloc(H,k)$.  This
contradiction proves that~$f(H)\geq\mu(H)-1$.  The proof of
Corollary~\ref{cor:main} is complete. \qed

\subsection{Proof of Lemma~\ref{lem:local_k}}
\label{sec:pf_lem:local_k}
We shall show
that~$\kloc(\epsilon,k)\leq\ell=\lfloor2k^2/\epsilon^2\rfloor$.
Suppose for a contradiction that~$\gamma$ is a local $k$-colouring
of~$K^n$ ($n\geq2$), with~$e_i$ edges of colour~$i$, where~$e_1\geq
e_2\geq\dots$, and such that
\begin{equation}
  \label{eq:pf_local_k}
  \sum_{i>\ell}e_i>\epsilon{n\choose2}.
\end{equation}
Note that colour~$i$ must occur at more than~$\sqrt{2e_i}$ vertices.
Since~$\gamma$ is a local $k$-colouring, we have
\begin{equation}
  \label{eq:pf_local_k2}
  \sum_{i\geq1}{\sqrt{2e_i}}\leq kn.
\end{equation}
As~$e_i\leq e_{\ell+1}\leq(\ell+1)^{-1}\sum_{1\leq
  i\leq\ell+1}e_i\leq(\ell+1)^{-1}{n\choose2}$ for
every~$i\geq\ell+1$, recalling~(\ref{eq:pf_local_k})
and~(\ref{eq:pf_local_k2}), we have
\begin{equation*}
  {\epsilon{n\choose2}\over\big\{{n\choose2}\big/(\ell+1)\big\}^{1/2}}
    <{1\over\big\{{n\choose2}\big/(\ell+1)\big\}^{1/2}}
       \sum_{i>\ell}e_i
    \leq\sum_{i>\ell}\sqrt{e_i}<{kn\over\sqrt2}.  
\end{equation*}
But then~$\ell+1<2k^2/\epsilon^2$, which is a contradiction.  \qed

\begin{remark}
  For the purposes of this paper, the rate of growth of the
  function~$\kloc(\epsilon,k)$ does not matter.  A bound better than
  the one shown above may be deduced from Corollary~3 of Gy\'arf\'as
  \textit{et al.}~\cite{GyLeNeRoSchTuLocal}.  
  
  The proof of Lemma~\ref{lem:local_k} above considers the colours in
  decreasing order of frequency.  N.~Alon pointed out to us that if we
  consider the colours in decreasing order of the number of vertices
  that they are incident to, then one may prove a better bound.  His
  proof gives that~$\kloc(\epsilon,k)<k^2/\epsilon$, which is best
  possible up to a multiplicative constant.  To see how his proof
  goes, suppose we have chosen some set of colours but they still
  leave out more than~$\epsilon{n\choose2}$ edges.  Considering a
  vertex of maximum degree in the graph that remains, and recalling
  that we have a local $k$-colouring, we see that there is a
  monochromatic star with more than~$\epsilon(n-1)/k$ rays.
  Therefore, some yet unused colour touches more
  than~$\epsilon(n-1)/k+1\geq\epsilon n/k$ vertices.  Since no vertex
  may be touched by more than~$k$ colours, the number of colours that
  we will obtain in this process is less than~$k^2/\epsilon$.  A lower
  bound of the same order of magnitute follows from a construction
  based on affine planes.
\end{remark}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Let~$\epsilon$ and~$k$ as in the statement of Lemma~\ref{lem:local_k}
%be given.  Put
%\begin{equation*}
%  %\label{eq:def_K}
%  K=\left\lfloor{4k^3\over\epsilon^2}\right\rfloor.
%\end{equation*}
%We shall show that~$K$ above will do for~$\kloc=\kloc(\epsilon,k)$ in
%Lemma~\ref{lem:local_k}.  Thus, let a local
%$k$-colouring~$\gamma=\gamma^n\:E(K^n)\to\ZZ$ be fixed.  We may assume
%that~$n\geq2k/\epsilon$, since otherwise the number of edges
%in~$E(K^n)$ is less than~$K$.  Moreover, assume that the colours that
%are effectively used in this colouring are all strictly positive.  For
%all~$i\geq1$, let us write~$W_i\subset V(K^n)$ for the set of vertices
%of~$K^n$ that are incident to at least one edge coloured with
%colour~$i$.  Without loss of generality, we may assume that
%\begin{equation}
%  \label{eq:decreasing_W_i}
%  |W_1|\geq|W_2|\geq\cdots.
%\end{equation}
%Note that the total number of colours that appear on the $2n-3$ edges incident
%to a pair of vertices~$x$, $y\in V(K^n)$ is at most~$2k-1$, because our
%colouring~$\gamma$ is $k$-local.  This implies that
%\begin{equation*}
%  %\label{eq:W_sum_i_bd}
%  \sum_{i\geq1}{|W_i|\choose2}\leq(2k-1){n\choose2}.
%\end{equation*}
%We now put
%\begin{equation*}
%  %\label{eq:def_eta}
%  \eta={\epsilon\over k}.
%\end{equation*}

%\begin{claim}
%  \label{claim:No_W_i}
%  At most~$K$ of the sets~$W_i$ satisfy~$|W_i|\geq\eta n$. 
%\end{claim}
%To prove the claim, simply note that the number of such sets~$W_i$ is at most 
%\begin{equation}
%  \label{eq:no_W_i_bd}
%  {\eta n\choose2}^{-1}\sum_i{|W_i|\choose2}
%    \leq(2k-1){n\choose2}\left/{\eta n\choose2}\right., 
%\end{equation}
%where the sum above is extended over all~$i$ such that~$|W_i|\geq\eta
%n$.  However, since~$n\geq2k/\epsilon=2/\eta$, the right-hand side
%of~(\ref{eq:no_W_i_bd}) is bounded from above by~$4k^3/\epsilon^2$.
%This completes the proof of Claim~\ref{claim:No_W_i}.

%The proof of Lemma~\ref{lem:local_k} will be finished if we now prove the
%following claim.  

%\begin{claim}
%  \label{claim:No_W_i_end}
%  The number of edges~$e$ with~$\gamma(e)>K$ is at most
%  \begin{equation*}
%    %\label{eq:No_W_i_end}
%    \epsilon{n\choose2}.
%  \end{equation*}
%\end{claim}
%To prove this claim, it suffices to notice that a vertex~$x$ belongs
%to at most~$k$ sets~$W_i$, and each such~$W_i$ with~$|W_i|<\eta n$ can
%`contribute' less than~$\eta n-1$ edges to~$\del(x)$.  Thus, summing
%over all vertices~$x$, and recalling~(\ref{eq:decreasing_W_i}) and
%Claim~\ref{claim:No_W_i}, we see that the number of edges as specified
%in the statement of Claim~\ref{claim:No_W_i_end} is less than
%\begin{equation*}
%  %\label{eq:No_W_i_end_last_line}
%  {1\over2}nk(\eta n-1)\leq\epsilon{n\choose2},
%\end{equation*}
%completing the proof of our claim.  Lemma~\ref{lem:local_k} is proved.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Theorem~\ref{thm:main}}
\label{sec:proof_main}
Let~$\cC$ be a class of essentially infinite colourings.  Our aim is
to prove that~$\cC_<\cup\cCbip\preceq\cC$.  Thus, let an
integer~$q_0\geq1$ be given.  We have to show that a suitable
integer~$n_0=n_0(q_0)=n_0(q_0,\cC)$ as in
Definition~\ref{def:cC1preceqcC2} exists.

Let~$0<\epsilon=\epsilon(\cC)<1$ be as in Definition~\ref{def:ess_inf}.  We
now define a few constants that will be important in the proof.  We start by
letting 
\begin{equation*}
  %\label{eq:def_epsilon1_delta}
  \epsilon_1=\epsilon/6
    \qquad\text{and}\qquad
    \delta=\epsilon/12.
\end{equation*}
Moreover, we pick integers
\begin{equation*}
  %\label{eq:def_loose}
  n_0,
    \qquad k_0\gg k_1,
    \quad\text{and}\qquad Q\gg Q_1\gg Q_2\gg Q_3
\end{equation*}
as follows.  Let 
\begin{equation}
  \label{eq:def_Q3}
  Q_3=R(q_0,q_0,q_0), 
\end{equation}
where we write~$R$ for the usual Ramsey function relative to~$3$
colours.  Let~$Q_2$ be the minimal integer~$\geq Q_3$ for which
we have
\begin{equation}
  \label{eq:def_Q2}
  {Q_2\choose2}{Q_2-3\choose Q_3-3}<{Q_2\choose Q_3}.
\end{equation}
Put
\begin{equation}
  \label{eq:def_Q1}
  Q_1={Q_2\choose2}+Q_2, 
\end{equation}
and set
\begin{equation}
  \label{eq:def_Q}
  Q=\left\lceil Q_1^4\over2\right\rceil.
\end{equation}
%\begin{equation}
%  \label{eq:def_Q}
%  Q=Q_1\prod_{2\leq i\leq Q_1}(2i-1)={(2Q_1)!\over2^{Q_1}(Q_1-1)!}.
%\end{equation}
Now put
\begin{equation}
  \label{eq:def_k1_k0}
  k_1=\left\lceil{2Q\over\delta}\right\rceil
  \qquad\text{and}\qquad
  k_0=\kloc(\epsilon_1,k_1+1), 
\end{equation}
where~$\kloc$ is as in Lemma~\ref{lem:local_k}.  Finally, let
\begin{equation}
  \label{eq:def_n0}
  n_0=\max\left\{n_\cC(k_0,\epsilon),
           \left\lceil(2k_1)^Q\over\epsilon_1(Q-1)!\right\rceil
          \right\}, 
\end{equation}
where~$n_\cC(k_0,\epsilon)$ is as introduced just after
Definition~\ref{def:ess_inf}. 

\begin{lemma}
  \label{claim:n0_will_do}
  $n_0=n_0(q)=n_0(q,\cC)$ defined in~{\rm(\ref{eq:def_n0})} will do.
\end{lemma}

In the remainder of Section~\ref{sec:proof_main}, we prove
Lemma~\ref{claim:n0_will_do}.  Thus, let
$$
\gamma=\gamma^n\:E(K^n)\to\ZZ
$$
be a colouring in~$\cC$ with~$n\geq n_0$.  As~$n_0\geq
n_\cC(k_0,\epsilon)$, we know that
\begin{equation}
  \label{eq:gamma_cond}
  \text{$\gamma$ is not $(k_0,\epsilon)$-bounded.}
\end{equation}
For any~$x\in V(K^n)$, let
\begin{equation}
  \label{eq:def_cdelta}
  c_\delta(x)=\min\{|\gamma(\del(x)\setminus F_x)|
                 \:F_x\subset\del(x)\text{ and }|F_x|\leq\delta(n-1)\}.
\end{equation}
Put
\begin{equation*}
  %\label{eq:def_W}
  W=\{x\in V(K^n)\:c_\delta(x)>k_1\}.
\end{equation*}

\begin{case}
  \label{case:W_small}
  $|W|<\epsilon_1n.$
\end{case}
\casebody Let~$K'$ be the complete graph obtained from~$K^n$ by the removal of
the vertices in~$W$.  Suppose~$K'$ has~$n'$ vertices.  Also, write~$\tgamma$
for the colouring induced by~$\gamma$ on~$E(K')$.  We now wish to define a
new colouring~$\gamma'$ for~$K'$, taking into account that, for all~$x\in
V(K')$, we have~$c_\delta(x)\leq k_1$.  Let
\begin{equation}
  F=\bigcup\{F_x\cap E(K')\:x\in V(K')\},
\end{equation}
where~$F_x$ denotes, for all~$x\in V(K')$, a set of edges incident to~$x$ for
which the minimum in~(\ref{eq:def_cdelta}) is attained.  It is clear that
\begin{equation}
  \label{eq:Fbd}
  |F|\leq\delta n^2.
\end{equation}
Suppose~$\tgamma$ uses colours~$1,2,3,\dots$, and recolour all the
edges in~$F$ with colour~$0$.  Let~$\gamma'$ be this new colouring
of~$K'$.  Observe that~$\gamma'$ is in fact a local
$(k_1+1)$-colouring.  Recalling the definition of~$k_0$
in~(\ref{eq:def_k1_k0}), we see that there exists~$S\subset\ZZ$
with~$|S|\leq k_0$ for which we have
$$
\big|(\gamma')^{-1}(S)\big|\geq(1-\epsilon_1){n'\choose2},   
$$
and hence, by~(\ref{eq:Fbd}), we have 
\begin{equation*}
  %\label{eq:bd1}
  \big|(\gamma')^{-1}(S\setminus\{0\})\big|
   \geq{n'\choose 2}-\left\{\epsilon_1{n'\choose2}+\delta n^2\right\}.   
\end{equation*}  
Thus, noticing that there are at most~$|W|n\leq\epsilon_1n^2$ edges that touch
the vertices in~$W$, we see that the set~$S\setminus\{0\}$, of at most~$k_0$
colours, fails to `cover' at most
$$
\({1\over2}\epsilon_1+\delta+\epsilon_1\)n^2<\epsilon{n\choose2}
$$
of the edges of our original complete graph~$K^n$.  In other words, we have
proved that~$\gamma$ is $(k_0,\epsilon)$-bounded, which is a
contradiction to~(\ref{eq:gamma_cond}). 
\endcasebody

\begin{case}
  \label{case:W_big}
  $|W|\geq\epsilon_1n.$
\end{case}
\casebody We start by stating a simple auxiliary result, which may be proved
by a straightforward greedy argument.  (The easy proof of this result uses the
fact that~$k_1$ is at least as large as~$2Q/\delta$;
see~(\ref{eq:def_k1_k0}).) 
\begin{lemma}
  \label{lem:bunch-up}
  Let~$Q$, $k_1$, and~$\delta$ be as above.
  Let~$\alpha_1\geq\alpha_2\geq\dots\geq0$ be reals such that
  \begin{equation}
    \label{eq:add-up-1}
    \sum_{i\geq1}\alpha_i=1,
  \end{equation}
  but
  \begin{equation}
    \label{eq:add-up-less}
    \sum_{1\leq i\leq k_1}\alpha_i<1-\delta.
  \end{equation}
  Then there exist indices~$0=i_{-1}<i_0<\dots<i_Q$ such that,
  putting 
  \begin{equation*}
    %\label{eq:def_betas}
    \beta_j=\sum_{i_{j-1}<i\leq i_j}\alpha_i
     \qquad\qquad(0\leq j\leq Q),
  \end{equation*}
  we have 
  \begin{equation*}
    %\label{eq:beta_prop}
    {1\over k_1}\leq\beta_j<{2\over k_1}
  \end{equation*}
  for all~$j=1,\dots,Q$. \qed
\end{lemma}

The lemma above and a Zarankiewicz type argument leads us to our next claim.
In what follows, we write~$E(A,B)$ for the set of edges that join vertices
in~$A$ to vertices in~$B$.  Moreover, if, \textit{e.g.}, $A=\{a\}$, we
write~$E(a,B)$ for~$E(\{a\},B)$.

\begin{lemma}
  \label{claim:K_QQ}
  There exist disjoint sets~$S$ and~$T\subset V(K^n)$ with~$|S|=|T|=Q$ such
  that, for any~$s\in S$, the colouring~$\gamma$ restricted to~$E(s,T)$ is
  injective.
\end{lemma}
\begin{proof}
  For~$x\in V(K^n)$ and~$i\in\ZZ$, let
  $$
  d(x,i)=|\del(x)\cap\gamma^{-1}(i)|.
  $$
  Thus, $d(x,i)$ is the number of edges of colour~$i$ incident to~$x$.
  Fix~$x\in W$, and put
  $$
  \alpha_i={d(x,i)\over n-1}
  $$
  for all~$i\in\ZZ$.  Without loss of generality, we may assume that only
  strictly positive colours~$i$ occur at~$x$, and that~$d(x,1)\geq
  d(x,2)\geq\cdots$.  Then~$\alpha_1\geq\alpha_2\geq\cdots$,
  identity~(\ref{eq:add-up-1}) holds, and, since~$x\in W$,
  inequality~(\ref{eq:add-up-less}) holds as well.  Thus,
  Lemma~\ref{lem:bunch-up} gives us a
  sequence~$J_1^{(x)},\dots,J_Q^{(x)}\subset\ZZ$ of pairwise disjoint sets of
  colours for which
  $$
  d(x,J_i^{(x)})=\sum_{j\in J_i^{(x)}}d(x,j)\geq{n-1\over k_1}
  $$
  for all~$i=1,\dots,Q$.

  We conclude that the number of stars~$K^{1,Q}$ with~$Q$ rays and
  centre~$x\in W$, each with all its~$Q$ edges coloured differently, is at
  least
  $$
  \sum_{x\in W}\prod_{1\leq i\leq Q}d(x,J_i^{(x)})
    \geq|W|\(n-1\over k_1\)^Q\geq\epsilon_1n\(n\over2k_1\)^Q.
  $$
  Let us call the stars counted above \textit{special} stars.  Averaging over
  all subsets of~$V(K^n)$ of size~$Q$, we see that there is 
  \begin{equation}
    \label{eq:def_T}
    T=\{t_1,\dots,t_Q\}\in{V(K^n)\choose Q}
  \end{equation}
  such that $t_1,\dots,t_Q$ are the~$Q$ endvertices of at least 
  \begin{equation}
    \label{eq:star_lb}
    {\epsilon_1Q!\over(2k_1)^Q}\;n
  \end{equation}
  special stars.  Recalling~(\ref{eq:def_n0}) and that~$n\geq n_0$, we obtain
  that~(\ref{eq:star_lb}) is at least~$Q$.  Hence, there are~$Q$ centres that
  form a set~$S$ that, together with~$T$ in~(\ref{eq:def_T}) above, is as
  required in Lemma~\ref{claim:K_QQ}.
\end{proof}

For~$A\subset S$ and~$B\subset T$, let us say that property~$\cD(A,B)$
holds if
\begin{equation*}
  %\label{eq:D_prop}
  \text{for any distinct~$b$, $b'\in B$, }
  \gamma(E(A,b))\cap\gamma(E(A,b'))=\emptyset.
\end{equation*}

\begin{lemma}
  \label{claim:Q1Q1}
  There exist~$S_1\subset S$ and~$T_1\subset T$ with~$|S_1|=|T_1|=Q_1$
  for which~$\cD(S_1,T_1)$ holds.
\end{lemma}
\begin{proof}
  Observe that property~$\cD(S_1,T_1)$ holds if~$S_1\cup T_1$ does not
  induce a pair of independent $S_1$--$T_1$ edges of the same colour.
  Let~$M_i$ be the set of edges of colour~$i$.  Then~$m_i=|M_i|\leq
  Q$, and~$\sum_im_i=Q^2$.  The number of pairs of independent edges
  of the same colour is at most
  \begin{equation*}
    \sum_i{m_i\choose2}\leq Q{Q\choose2}.
  \end{equation*}
  Hence, the probability that a random pair of sets~$(S_1,T_1)$
  with~$|S_1|=|T_1|=Q_1$ violates~$\cD(S_1,T_1)$ is at most
  \begin{equation*}
    Q{Q\choose2}{Q-2\choose Q_1-2}^2\bigg/{Q\choose Q_1}^2
      ={Q_1^2(Q_1-1)^2\over2(Q-1)}<1, 
  \end{equation*}
  where in the last inequality we used~(\ref{eq:def_Q}).
  Consequently, some pair~$(S_1,T_1)$ will do.
\end{proof}

%\begin{proof}
%  We first show that we may inductively define
%  \begin{equation*}
%    %\label{eq:growing_S'}
%    S'_1\subset S'_2\subset\dots\subset S'_{Q_1}\subset S
%  \end{equation*}
%  and
%  \begin{equation*}
%    %\label{eq:shrinking_T'}
%    T=T'_1\supset T'_2\supset\dots\supset T'_{Q_1}
%  \end{equation*}
%  such that~$|S'_i|=i$ for all~$i$ and,
%  \begin{equation}
%    \label{eq:size_T'}
%    \text{for all~$2\leq i\leq Q_1$, we have }
%      |T'_i|\geq{1\over2i-1}|T'_{i-1}|
%  \end{equation}
%   and, moreover, such that~$\cD(S'_i,T'_i)$ holds.
  
%  We start by picking~$s_1\in S$ arbitrarily, and by setting~$S'_1=\{s_1\}$.
%  We also put~$T'_1=T$.  Suppose that, for some~$i\geq2$, the
%  sets~$S'_1,\dots,S'_{i-1}$ and~$T'_1,\dots,T'_{i-1}$ have been found as
%  required.
  
%  Fix~$s\in S\setminus S'_{i-1}$ and put~$S'_i=S'_{i-1}\cup\{s\}$.
%  Let~$\tT$ be a maximal subset of~$T'_{i-1}$ for
%  which~$\cD(S'_i,\tT)$ holds.  We claim that
%  \begin{equation}
%    \label{eq:tTlbd}
%    |\tT|\geq{1\over2i-1}|T'_{i-1}|.
%  \end{equation}
%  In order to prove~(\ref{eq:tTlbd}), we let
%  \begin{equation*}
%    %\label{eq:defB1}
%    B_1=\{t'\in T'_{i-1}\setminus\tT\:
%          \text{there is an }s'\in S'_{i-1}
%          \text{ with }\gamma(s't')\in\gamma(E(s,\tT))\}
%    %
%    \end{equation*}
%    and
%    \begin{equation*}
%      %\label{eq:defB2}
%      B_2=\{t'\in T'_{i-1}\setminus\tT\:
%            \gamma(st')\in\gamma(E(S'_{i-1},\tT))\}.
%    \end{equation*}
%    Put also~$B=B_1\cup B_2$.  One may easily check that
%    \begin{equation*}
%      %\label{eq:B1upbd}
%      |B_1|\leq|S'_{i-1}||\gamma(E(s,\tT))|=(i-1)|\tT|
%    \end{equation*}
%    and that
%    \begin{equation*}
%      %\label{eq:B2upbd}
%      |B_2|\leq|\gamma(E(S'_{i-1},\tT))|
%        \leq|E(S'_{i-1},\tT)|=(i-1)|\tT|.
%    \end{equation*}
%    Thus~$|B|\leq2(i-1)|\tT|$.  One may now check in a straightforward manner
%    that if~$t'\in T'_{i-1}\setminus\big(\tT\cup B\big)$, then
%    property~$\cD(S'_i,\tT\cup\{t'\})$ holds.  Therefore, by the maximality
%    of~$\tT$, we have~$T'_{i-1}\subset\tT\cup B$.  However, we then have
%    $$
%    |T'_{i-1}|\leq|\tT|+|B|\leq|\tT|+2(i-1)|\tT|\leq(2i-1)|\tT|, 
%    $$
%    and~(\ref{eq:tTlbd}) is proved.  We may thus take~$T'_i=\tT$ and the
%    induction step is complete.
    
%    We now go back to the proof of Claim~\ref{claim:Q1Q1}.  In fact, it only
%    remains to notice that the definition of~$Q$ in~(\ref{eq:def_Q}) together
%    with~(\ref{eq:size_T'}) imply that~$|T'_{Q_1}|\geq Q_1$.  To complete the
%    proof of our claim, it suffices to let~$S_1=S'_{Q_1}$ and pick an
%    arbitrary $Q_1$-subset of~$T'_{Q_1}$ for~$T_{Q_1}$.
%\end{proof}

Lemma~\ref{claim:Q1Q1} and~(\ref{eq:def_Q1}) give the following.

\begin{lemma}
  \label{claim:Q2Q2}
  There exist~$S_2\subset S_1$ and~$T_2\subset T_1$ with~$|S_2|=|T_2|=Q_2$
  such that, for any~$s$, $s'\in S_2$, we
  have~$\gamma(ss')\notin\gamma(E(S_2,T_2))$. 
%  \begin{equation*}
%    %\label{eq:S2T2_prop}
%    \gamma(ss')\notin\gamma(E(S_2,T_2)).
%  \end{equation*}
\end{lemma}
\begin{proof}
  Pick for~$S_2$ an arbitrary $Q_2$-subset of~$S_1$.  
  Since~$\cD(S_1,T_1)$ holds, a colour that occurs on~${S_2\choose2}$
  occurs in~$\gamma(E(S_1,t))$ for at most one~$t\in T_1$.
  Thus~(\ref{eq:def_Q1}) ensures that a suitable set~$T_2\subset T_1$
  exists.
\end{proof}

For our next step in the proof, we need the following lemma.

\begin{lemma}
  \label{lem:neat}
  Let~$Q_2$ and~$Q_3$ be as above, and suppose we have a function
  \begin{equation*}
    %\label{eq:def_phi}
    \sigma:E(K^{Q_2})\to\{0\}\cup[Q_2]=\{0,1,\dots,Q_2\}, 
  \end{equation*}
  where we assume that~$V(K^{Q_2})=[Q_2]$.  Then there exists a set~$T'\subset
  V(K^{Q_2})$ with~$|T'|\geq Q_3$ such that, for all~$i\in T'$, we have
  \begin{equation}
    \label{eq:T'_prop}
    \sigma^{-1}(i)\cap{T'\choose2}\subset\del(i)\cap{T'\choose2}.
  \end{equation}
\end{lemma}
\begin{proof}
  Suppose that, for any~$T'\subset[Q_2]$ with~$|T'|=Q_3$, there is~$i\in T'$
  violating~(\ref{eq:T'_prop}).  Let us call an edge~$e$ induced by~$T'$
  that witnesses the fact that~(\ref{eq:T'_prop}) fails a
  \textit{$T'$-witness}.  Let us count the number of pairs~$(T',e)$,
  where~$T'\subset[Q_2]$ has cardinality~$Q_3$ and~$e$ is a $T'$-witness.  By
  hypothesis, this number is at least~${Q_2\choose Q_3}$.
%  \begin{equation*}
%    %\label{eq:Q2chooseQ3}
%    {Q_2\choose Q_3}.
%  \end{equation*}
  On the other hand, any edge~$e$ in~$K^{Q_2}$ is a $T'$-witness for
  none, or for
  \begin{equation*}
    %\label{eq:T'_upper_bound}
    {Q_2-3\choose Q_3-3} 
  \end{equation*}
  $Q_3$-sets~$T'$.  Hence the total number of pairs~$(T',e)$ as above is at
  most 
  \begin{equation*}
    %\label{eq:(T',e)_upper_bound}
    {Q_2\choose2}{Q_2-3\choose Q_3-3}.
  \end{equation*}
  In view of~(\ref{eq:def_Q2}), this is a contradiction.
\end{proof}

We apply Lemma~\ref{lem:neat} to the complete graph induced by~$T_2$, and the
colouring~$\sigma$ defined by
\begin{equation*}
  %\label{eq:def_sigma}
  \sigma(tt')=
    \begin{cases}
      \;i  &\text{ if }\gamma(tt')\in\gamma(E(S_2,i))
            \text{ and }i\in T_2,\\
      \;0  &\text{ if }\gamma(tt')
             \notin\bigcup_{i\in T_2}\gamma(E(S_2,i))
             =\gamma(E(S_2,T_2)).
    \end{cases}
\end{equation*}
(If we wish to follow the notation in Lemma~\ref{lem:neat} exactly, we may
assume without loss of generality that~$T_2=[Q_2]$.)  Recalling that
property~$\cD(S_1,T_1)$ holds, we notice that the fact that~$S_2\subset S_1$
and~$T_2\subset T_1$ implies that~$\sigma$ is well-defined.
Since~(\ref{eq:def_Q2}) holds, Lemma~\ref{lem:neat} gives the following.

\begin{lemma}
  \label{claim:Q3Q3}
  There exist~$S_3\subset S_2$ and~$T_3\subset T_2$ with~$|S_3|=|T_3|=Q_3$
  such that, for any distinct~$t$, $t'\in T_3$, we have
  \begin{equation*}
    %\label{eq:S3T3_prop}
    \gamma(tt')\notin\bigcup\nolimits_{t''}\gamma(E(S_3,t'')), 
  \end{equation*}
  where the union is taken over all~$t''\in T_3\setminus\{t,t'\}$. \qed
\end{lemma}

We are now able to finish the proof of Lemma~\ref{claim:n0_will_do},
and hence of Theorem~\ref{thm:main}.  Consider the following
$\{\pm1,0\}$-colouring~$\rho$ of the edges of the complete graph
on~$T_3$.  First, equip~$T_3$ with some arbitrary linear order~$<$.
Then, colour~$tt'$ ($t\neq t'\in T_3$) with colour~$0$ if
\begin{equation*}
  %\label{eq:colour_0}
  \gamma(tt')\notin\bigcup_{t''\in T_3}\gamma(E(S_3,t'')). 
\end{equation*}
We colour~$tt'$ with colour~$1$ if~$t<t'$
and~$\gamma(tt')\in\gamma(E(S_3,t))$, 
%\begin{equation*}
%  %\label{eq:colour_1}
%  \gamma(tt')\in\gamma(E(S_3,t)),  
%\end{equation*}
and, finally, we colour~$tt'$ with colour~$-1$ if~$t<t'$
and~$\gamma(tt')\in\gamma(E(S_3,t'))$. 
%\begin{equation*}
%  %\label{eq:colour_-1}
%  \gamma(tt')\in\gamma(E(S_3,t')). 
%\end{equation*}
Because of~(\ref{eq:def_Q3}), we know that there is~$T_\rho\subset T_3$
with~$|T_\rho|=q_0$ such that~$\rho$ is constant on~${T_\rho\choose2}$.

If~$\rho$~has value~$0$ on~${T_\rho\choose2}$, then it is easily seen
that we have found an isomorphic copy of a `refinement'
of~$\gammabip^{2q_0}\in\cCbip$ in our original colouring~$\gamma$.
(As the terminology suggests, a \textit{refinement} of a given
colouring of a complete graph~$K$ is a colouring of~$E(K)$ that
induces a partition of~$E(K)$ that is finer than the partition induced
by the given colouring.)  Therefore, we
have~$\gammabip^{2q_0}\preceq\gamma$.  If, on the other hand,
$\rho$~is~$-1$ or~$1$ on~${T_\rho\choose2}$, then, since
property~$\cD(S_3,T_3)$ holds, it follows that~$\gamma$ restricted
to~$T_\rho$ is isomorphic to a refinement of~$\gamma_<^{q_0}\in\cC_<$,
and hence~$\gamma_<^{q_0}\preceq\gamma$.  Thus, in either case, we
have found~$\gamma_1=\gamma_1^q\in\cC_<\cup\cCbip$ with~$q\geq q_0$
contained in~$\gamma$, as required.  Lemma~\ref{claim:n0_will_do} is
proved.
%
\endcasebody

\section{Concluding remarks}
\label{sec:concluding}
The reader has undoubtedly noticed that we were quite generous in the
estimates in our proofs.  Indeed, we have not attempted to obtain
particularly good bounds for the natural extremal functions that arise
in connection with Theorem~\ref{thm:main}.

We have only considered colourings of finite graphs.  Clearly, similar
investigations may be pursued for other combinatorial structures.  In
the infinite case, the questions may be formulated in
measure-theoretic or topological terms.  We shall come back to such
topics in a future note.

\subsection*{Acknowledgements}
\label{sec:acknow}
The second author thanks S.~Hougardy, H.$\,$J.~Pr\"omel, and A.~Taraz
for interesting discussions.  It is also a pleasure for us to thank
N.~Alon for his comments and to acknowledge the careful work of an
anonymous referee, whose many suggestions improved the presentation of
this paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{amsplain}
%\bibliography{refs}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{ALR}
N.~Alon, H.~Lefmann, and V.~R{\"o}dl, \emph{On an anti-{R}amsey type result},
  Sets, Graphs and Numbers, vol.~60, Colloquia Mathematica Societatis J\'anos
  Bolyai, North-Holland, 1991, pp.~9--22.

\bibitem{babai85:_ramsey}
L.~Babai, \emph{An anti-{R}amsey theorem}, Graphs and Combinatorics
  \textbf{1} (1985), no.~1, 23--28.
  
\bibitem{clapsadle94:_local} 
R.$\,$A. Clapsadle and R.$\,$H. Schelp, \emph{Local edge colorings that
  are global}, Journal of Graph Theory \textbf{18} (1994), no.~4, 389--399.

\bibitem{ErdosRadoCanonical}
P.~Erd{\H o}s and R.~Rado, \emph{Combinatorial theorems on classifications of
  subsets of a given set}, Proceedings of the London Mathematical Society
  \textbf{2} (1952), no.~3, 417--439.
  
\bibitem{GyLeNeRoSchTuLocal} A.~Gy{\'a}rf{\'a}s, J.~Lehel,
  J.~Ne{\v{s}}et{\v{r}}il, V.~R{\"o}dl, R.$\,$H.~Schelp, and Zs.~Tuza,
  \emph{Local $k$-colorings of graphs and hypergraphs}, Journal of
  Combinatorial Theory, Series B \textbf{43} (1987), no.~2, 127--139.

\bibitem{gyarfas87:_ramsey}
A.~Gy{\'a}rf{\'a}s, J.~Lehel, R.$\,$H. Schelp, and Zs. Tuza,
  \emph{Ramsey numbers for local colorings}, Graphs and Combinatorics
  \textbf{3} (1987), no.~3, 267--277.

\bibitem{lefmann96:_multic}
H.~Lefmann, V.~R{\"o}dl, and B.~Wysocka, \emph{Multicolored
  subsets in colored hypergraphs}, Journal of Combinatorial Theory, Series A
  \textbf{74} (1996), no.~2, 209--248.

\bibitem{Ram}
F.$\,$P. Ramsey, \emph{On a problem of formal logic}, Proceedings of
  the London Mathematical Society \textbf{30} (1930), 264--286.

\bibitem{rucinski97Local}
A.~Ruci{\'n}ski and M.~Truszczy{\'n}ski, \emph{A note on local
  colorings of graphs}, Discrete Mathematics \textbf{164} (1997), no.~1-3,
  251--255, The Second Krakow Conference on Graph Theory (Zgorzelisko, 1994).

\bibitem{truszczynski92:_gener}
M.~Truszczy{\'n}ski, \emph{Generalized local colorings of graphs},
  Journal of Combinatorial Theory, Series B \textbf{54} (1992), no.~2,
  178--188.

\bibitem{TruTuzaLocal}
M.~Truszczy\'nski and Zs.~Tuza, \emph{Linear upper bounds for local
  {R}amsey numbers}, Graphs and Combinatorics \textbf{3} (1987), no.~1, 67--73.

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
