% A LaTeX2e file for an 9 page document
%
%
%       Abstract
%
% We prove that for $c \geq 2.522$ a random graph with $n$ vertices and
% $m=cn$ edges is not 3-colorable with probability $1-\o(1)$. Similar
% bounds for  non-$k$-colorability are given for $k>3$.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}
\usepackage{amsfonts}

\topmargin 1cm
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep

\textheight 8.5in

\oddsidemargin 0pt
\evensidemargin \oddsidemargin

\textwidth 6.5in

\setlength{\textheight}{8.5in}

\newtheorem{theorem}{Theorem}

\newcommand{\proofstart}{{\bf Proof.\hspace{0.5em}}}
\newcommand{\proofend}{\medskip \hfill\mbox{$\Box$}\\}

\newcommand{\gnp}{\ensuremath{G(n,p)}}
\newcommand{\gn}[1]{\ensuremath{G(n,#1)}}
\newcommand{\gnm}{\ensuremath{G(n,m)}}

\def\as{w.h.p.\ }
\def\eg{e.g.\ }
\def\ie{i.e.\ }
\def\erd{Erd\H{o}s}
\def\luc{\L uczak}

\def\ex{{\bf E}}
\renewcommand{\c}{C_P}
\renewcommand{\r}{R_P}
\renewcommand{\o}{{\mathit o}}
\renewcommand{\O}{{\mathit O}}
\newcommand{\e}{\ensuremath{\epsilon}}
\newcommand{\ra}[0]{\rightarrow}

\def\thefootnote{\fnsymbol{footnote}}

\pagestyle{myheadings}

\markright{\sc the electronic journal of combinatorics 6 (1999),
\#R29\hfill}

\thispagestyle{empty}
\usepackage{latexsym}

\begin{document}
\makeatletter
\title{Almost all graphs with $2.522 n$ edges are not 3-colorable}



\author{
Dimitris Achlioptas
\thanks{Researh supported in part by an NSERC PGS Scholarship.
Current address: Microsoft Research, One Microsoft Way, Redmond
WA 98052, U.S.A. Email: {\small\texttt{optas@microsoft.com}}}\\
{\small\texttt{optas@cs.toronto.edu}}
\and
Michael Molloy
\thanks{Researh supported in part by an NSERC grant.}\\
{\small\texttt{molloy@cs.toronto.edu}}
\and
{\normalsize{Department of Computer Science}}\\
{\normalsize{University of Toronto}}\\
{\normalsize{Toronto, Ontario M5S 3G4, Canada.}}\
}

\date{\empty}
\maketitle
\begin{abstract}
We prove that for $c \geq 2.522$ a random graph with $n$ vertices and
$m=cn$ edges is not 3-colorable with probability
$1-\o(1)$. Similar bounds for  non-$k$-colorability are given
for  $k>3$.
\medskip

\begin{center}
1991 Mathematics Subject Classification: Primary 05C80; Secondary 05C15.
\end{center}

\end{abstract}


\section{Introduction}


Let $N(n,m,A)$ denote the number of graphs with vertices $\{1,\ldots,n\}$,
$m=m(n)$ edges and some property $A$. The term ``almost all'' in the title
has the meaning introduced by \erd\ and R\'{e}nyi~\cite{ErRe60}:
\begin{equation}\label{limdef}
\lim_{n \rightarrow \infty}\frac{N(n,m,A)}
{
{\textstyle{{n \choose 2}} \choose {{\scriptstyle m}}}
}=1 \enspace .
\end{equation}
Equivalently, one can consider a random graph $G=G(V,E)$ where $|V|=n$ and
$E$ is a uniformly random $m$-subset of all ${n \choose 2}$ possible edges
on $V$, \ie the \gnm\ model of random graphs.  If $n$ is an index running
over probability spaces, we will say that a sequence of events
${{\cal E}}_n$ occurs {\em with high probability\/} (w.h.p.)\ if
$\lim_{n \ra \infty}{\Pr[{{\cal E}}_n]}=1$. In particular, we will say that
``\gn{m(n)} has property $A$ w.h.p." if $m(n)$ is such that
(\ref{limdef}) holds for $A$.

In their seminal paper  introducing random graphs~\cite{ErRe60},
\erd\ and R\'{e}nyi pointed out that a number of interesting properties
exhibit a sharp threshold behavior on \gnm:  for each such property
$A$, there exists a critical number of edges $m_A(n)$ such that for $m$
around $m(n)$ the probability of \gnm\ having $A$ changes rapidly
from near 0 to  near 1. Such properties include having a multicyclic
component, having a perfect matching, connectivity, Hamiltonicity
and others.

A central property in this context is the \mbox{$k$-colorability}
of $G(n,cn)$ where $k$ is a fixed integer. For $k=2$, this
is very well-understood as bipartiteness is equivalent to
containing no odd cycles. In particular, the probability of
non-2-colorability is bounded away from 0 for any $c>0$
and keeps increasing gradually with $c$, reaching $1-\o(1)$ during the
emergence of the giant component at $c=1/2$.
For $k>2$, though, our  understanding of \mbox{$k$-colorability}
is not nearly as good; moreover, the situation is conjectured to be quite
different. In particular, see~\cite{ErRe60,alon}, \erd\ asked:
for each  $k > 2$, is there a constant $c_k$ such that for any
$\epsilon>0$,
\begin{equation}\label{erd}
{\mbox{$G(n,(c_k-\e) n)$ is w.h.p.     $k$-colorable $\;${and} $\;$
$G(n,(c_k+\e) n)$
                         is w.h.p. not $k$-colorable}} \enspace ?
\end{equation}


Recently, Friedgut~\cite{frie} made great progress in our understanding
of threshold phenomena in random graphs by establishing necessary and
sufficient conditions for a property to have a sharp threshold.
Using the main theorem of~\cite{frie}, Friedgut and the first
author~\cite{af} showed that for $k > 2$,  there exists a {\em function\/}
$t_k(n)$ such that~(\ref{erd}) holds upon replacing $c_k$ with $t_k(n)$,
\ie that indeed \mbox{$k$-colorability} has a sharp threshold.
While it is widely  believed that $\lim_{n \rightarrow \infty} t_k(n)$
exists, confirming this conjecture and determining the limit $c_k$, even
for $k=3$, seems very challenging.

Perhaps the main tool in attacking the question of $k$-colorability
for small values of $k>2$ has been  the elementary fact
that if a graph has no subgraph with minimum degree at least $k$, then
it is \mbox{$k$-colorable}. In particular, first \luc~\cite{luccore}  proved
that \as \gn{cn}\ remains  \mbox{3-colorable} after the emergence of the
giant component by showing that for $c \leq 0.50005$, \as \gn{cn}  has no
subgraph of
minimum degree 3. Shortly afterwards, Chv\'{a}tal~\cite{chv} improved this
greatly by showing that \gn{cn} \as has no subgraph with minimum degree 3
for $c \leq 1.44$ and Reed and the second author~\cite{mikemsc} improved the
bound even further to $c \leq 1.67$. Finally, Pittel, Spencer and
Wormald~\cite{PSW}, proved that, in fact, for all $k >2$ there exists
$\gamma_k$ such that for $c < \gamma_k$, \gn{cn}\ \as has no subgraph with
minimum degree at least $k$, while for $c > \gamma_k$   it has
such a subgraph w.h.p. Moreover,
they determined $\gamma_k$ exactly for all $k$, in particular yielding
$c_3 \geq \gamma_3 = 1.675...$  Following that, and in aswering a question
of Bollob\'{a}s~\cite{alon}, the second author~\cite{molloygap} proved
$c_k > \gamma_k$ for all $k \geq 4$ and conjectured $c_3 \neq \gamma_3$
as well. This conjecture
was verified recently by the authors~\cite{focs} after analyzing the
performance of a greedy ``list-coloring" heuristic on \gn{cn}. That
argument yielded $c_3 > 1.923$, which is the best known lower
bound for $c_3$.

In this paper, after briefly reviewing the known upper bounds for
$c_k$, we show how a technique of Kirousis et al.~\cite{KKK}, developed for
random $k$-SAT, can be used to yield an improved upper bound for $c_k$
for small values of $k$. For example, we obtain
\begin{theorem}
$$
c_3 < 2.522 \enspace .
$$
\end{theorem}

\section{The first moment method}


Grimmett and McDiarmid~\cite{grmc} gave the first lower bound on the
chromatic number of random graphs by determining $\alpha_k$ such that
\gn{m=\alpha_kn^2} \as has no independent set of size $n/k$, and thus
$\chi(G)>k$ (here $k \ra \infty$).
Moreover, they conjectured that the lower bound derived by
this argument is tight, and as evidence for this they showed that the
expected number of $k$-colorings of \gn{\alpha n^2} tends to infinity
for $\alpha < \alpha_k$. Devroye (see~\cite{chv}) later observed that when
$k$ is fixed, letting the expected number of $k$-colorings go to 0 as
$n \ra \infty$ yields much better lower bounds for the chromatic number
than letting the number of (suitably large) independent sets go to 0 as
$n \ra \infty$.

Our proof can be viewed as a refinement of Devroye's argument which we
will reproduce below to introduce some ideas and notation.
Before doing so, let us recall that in the \gnm\ model the edge set is
a random $m$-subset of the set of all ${n \choose 2}$ possible edges.
Equivalently, we can say that the edges of the  graph are selected from
the set of all possible edges one-by-one, uniformly, independently and
{\em without\/} replacement. For the calculations in this paper it will be
convenient to consider a slight modification of the \gnm\ model in that
the selection is  done {\em with\/} replacement, \ie multiple edges are
allowed. We will denote this model by $G^r(n,m)$. Intuitively, it is clear
that for any monotone increasing property $A$ and any value of $m$, the
probability of $A$ holding in \gnm\  is no smaller than it is in $G^r(n,m)$
since ``additional occurrences of an  edge do not help". Formally, this is
Theorem 5 in~\cite{KS} and, for our purposes, it will imply that if for a
given $m(n)$, $G^r(n,m(n))$ is \as non-$k$-colorable then so is
$\gn{m(n)}$\footnote{In fact, it turns out that since the expected number
of multiple edges in $G^r(n,cn)$ is $\O(1)$ the converse holds as well, \ie
if $G(n,cn)$ is \as non-$k$-colorable then so is $G^r(n,cn)$. Thus, by
switching to the $G^r(n,m)$ model we are not giving anything away with
respect to bounding $c_k$.}.


We will distinguish between a proper \mbox{$k$-coloring} of a graph and one
in which some adjacent vertices might have the same color by referring to
them as a \mbox{``$k$-coloring"} and a \mbox{``$k$-partition"},
respectively.
In fact, it will be helpful to think of a \mbox{$k$-coloring} of a graph
$G(V,E)$ as a \mbox{$k$-partition} of $V$ such that every $e \in E$ has its
endpoints
in distinct blocks of the partition, so that each block is an independent
set.

Let $P=V_1,\ldots,V_k$ be an arbitrary (ordered) $k$-partition of $V$ and
let $\c$ denote the event that $P$ is a $k$-coloring of $G$. For $\c$ to
hold, every edge of the random graph has to connect vertices from two
different blocks. Introducing
\begin{equation}\label{tdef}
T(P) = \sum_{i < j}{|V_i|\cdot|V_j|} \enspace ,
\end{equation}
the total number of pairs of vertices belonging to different blocks,
we  have
\begin{equation}\label{newcp}
\Pr[\c] = \left(\frac{T(P)}{{n \choose 2}}\right)^m \enspace .
\end{equation}
Now, using the fact $\sum_i{|V_i|}=n$ and the Cauchy-Schwartz inequality,
respectively, we bound
\begin{eqnarray*}
T(P) &  =   & \frac{n^2}{2}-\frac{1}{2}\sum_i|V_i|^2\\
     & \leq & \frac{n^2}{2}-\frac{1}{2}\cdot\frac{n^2}{k}\\
     &  =   &\frac{k-1}{2k}n^2 \enspace.
\end{eqnarray*}
Thus, (\ref{newcp}) yields
\begin{equation}\label{cp}
\Pr[C_P] \leq
\left(\frac{k-1}{k}\right)^m
\left(\frac{n}{n-1}\right)^m
\enspace .
\end{equation}
Since the number of $k$-partitions of $V$ is $k^n$, (\ref{cp}) implies
that the expected number of \mbox{$k$-colorings} of $G$, for $m = c n$,
is of order
$$
\left[k \left(\frac{k-1}{k}\right)^c\right]^n \enspace .
$$
Hence, if  $c > \frac{\ln k}{\ln k - \ln(k-1)}$ the expected number of
$k$-colorings of $G^r(n,cn)$ tends to 0 as $n \ra \infty$ implying
that $G^r(n,cn)$ is \as \mbox{non-$k$-colorable}. For $k=3$, this argument
yields $c_3 < 2.71$  and in general $c_k < k \ln k$.


It is worth noting that this simple argument is asymptotically tight:
the upper bound on $\chi(G(n,m))$ given by \luc~\cite{luc} implies that
for any $\e>0$ and all $k \geq k_0(\e)$, $c_k > (1 - \e)k \ln k$.  On the
other hand, the following two observations  can be used to show that
for $k >2$ this argument is not exact: (a) if a $k$-colorable graph has
$s_i$ vertices of
degree $i$ then it has at least $\prod_{i=0}^{k-1}(k-i)^{s_i}$ distinct
\mbox{$k$-colorings} and (b) with extremely high probability,
for every fixed $i$, \gn{cn} has $\Omega(n)$ vertices of degree $i$.
If $X$ is the number of $k$-colorings of $\gn{cn}$, using (a),(b), one
can show that there are values of $c$ such that for some $a>b>1$:
(i) $\ex[X]\approx b^n$  and (ii) \as if $X>0$ then $X>a^n$.
Hence, for such $c$, $\Pr[X>0]\leq(a/b)^n+\o(1)=\o(1)$, while
$\ex[X]$ is exponentially large.  Thus, it is not the case that \gn{cn}
is \as $k$-colorable for exactly those values of $c$ for which its
expected number of $k$-colorings is large.

Indeed, Reed and the second author~\cite{mikemsc} proved that this
``naive"
first moment argument is quite a bit off the mark for $k=3$. To that end,
they first extended the argument to uniformly
random pseudographs on a given degree sequence (for a definition see
also~\cite{MoReds}). In particular, they proved that such a pseudograph
with $\rho n$ edges is \as non-$k$-colorable if
$\rho > \frac{\ln k }{\ln k - \ln (k-1)}$. Then, in order to improve
over the naive bound, they considered the random
pseudograph resulting by repeatedly (20 times) removing all vertices of
degree less than 3 from \gn{m=cn}. They proved that  this pseudograph (i)
is uniformly random with respect to its degree sequence and
(ii) if $c \geq c_0 = 2.571...$, then \as it  has at least $\rho n$ edges where
$\rho > \frac{\ln 3}{\ln 3 - \ln 2}$. Hence,  \as $\gn{m=c_0 n}$  contains
a non-$3$-colorable subgraph, implying  $c_3 < 2.572$.

Inspired by the work of Kirousis et al.~\cite{KKK}, we will take a less
direct but more fruitful approach towards accounting for the wastefulness
of the first moment method. Instead of focusing on the
low degree vertices explicitly, we will prove the following: if $P$ is a
$k$-coloring of $G \in \gn{cn}$ and we randomly pick a vertex $v$,
then with  probability $\phi = \phi(k,c)>0$ we can assign a different color
to $v$ and still have a $k$-coloring of $G$. This  suggests that when
\mbox{$k$-colorings} exist, they tend to appear in large ``clusters" of
similar colorings. The approach of Kirousis et al.~\cite{KKK}, when
translated to \mbox{coloring}, suggests that instead of counting all
the $k$-colorings of a random graph (as the first moment does) we should
only count a few ``representative'' ones. Following this idea we will
consider as representatives those $k$-colorings satisfying a certain
``local maximality" condition and determine their expected
number in $G^r(n,cn)$.  Letting that expectation
go to 0 as $n\ra\infty$ will yield $c_3 < 2.522$.

\section{A refinement of the first moment method}

Recall that for a $k$-partition $P=V_1,V_2,\ldots,V_k$ of $V$, $\c$
denotes the event that $P$ is a $k$-coloring of $G$. Let us say that
a vertex $v \in V_i$ is {\em unmovable\/} in $P$ if for every
$j > i$ the partition resulting by moving $v$ to $V_j$ is not a
$k$-coloring of $G$.  We will say that $P$ is a {\em rigid}
$k$-coloring of $G$ if $\c$ holds and every vertex is unmovable in
$P$. We will denote this event by $\r$. Note now that if we consider
the $k$-partitions of $V$ as strings of length $n$ over
$\{1,\ldots,k\}$ then, clearly, the lexicographically last
$k$-coloring of $G$ (if any $k$-coloring exists) is rigid by definition.
Hence, $G$ has a rigid $k$-coloring iff it is {\mbox{$k$-colorable,}}
implying that the probability that $G^r(n,cn)$ is $k$-colorable is bounded
by the expected number of rigid \mbox{$k$-colorings} of $G^r(n,cn)$.
With this in mind, we  take $m = c n$ and seek $c=c(k)$ for which
this last expectation tends to 0 as $n\ra \infty$.


{\em Remark:} Note that requiring $k$-colorings to be rigid, immediately
eliminates all the redundant counting caused by vertices of degree
$k-1$ or less; only the $k$-colorings which assign every such vertex the
greatest possible color get counted.

\subsection{Probability Calculations}
For every $k$-partition $P=V_1,V_2,\ldots,V_k$ of $V$ we let
$$
\alpha_i=\alpha_i(P)= \frac{|V_i|}{n} \enspace .
$$
Also, recalling~(\ref{tdef}), we let
\begin{equation}\label{taudef}
\tau = \tau(P) = \frac{T(P)}{n^2} \enspace .
\end{equation}
{
It is well-known that for any $c >0$, the largest independent set
of \gn{cn} \as  contains only a constant fraction of all vertices.
Thus, the probability that \gn{cn} has a $k$-coloring where only
one color class contains $\Omega(n)$ vertices is $\o(1)$. Hence,
in the following we only consider partitions $P$ in which at least
two blocks have $\Omega(n)$ vertices (and bound the expected
number of rigid $k$-colorings among such partitions).}\medskip

We will first bound $\Pr[\r]$. For this, using (\ref{cp}),
it  suffices to bound $\Pr[\r \mid \c]$.\smallskip

For a given $k$-coloring $P$, any $i$, any vertex $v \in V_i$, and any
$j > i$ we let ${\cal E}(v,j)$ denote the event ``$v$ cannot be moved to
$V_j$". Thus,
\begin{equation}\label{produ}
\Pr[\r \mid \c] = \Pr
\left[ \left.
\bigcap_{\stackrel{\scriptstyle{i<j}}{v \in V_i} }
{\cal E}(v,j)  \right| \c
\right]
\enspace .
\end{equation}
Letting $E(v,j) = \{\{v,w\} :  w \in V_j\}$, we see
that ${\cal E}(v,j)$ occurs iff at least one member of $E(v,j)$ is
an edge of $G$. Note that since we have conditioned on
$\c$, only two-element sets $\{v,w\}$ enumerated by $T(P)$ can appear in
the graph. Thus, since the edges of $G$ were chosen uniformly,
independently and with replacement,
\begin{eqnarray}
\Pr[{\cal E}(v,j) \mid \c] & = & 1-\left(1-\frac{|V_j|}{T(P)}\right)^{m}
\label{mare}
\\
                   & = & 1 - e^{-\alpha_j c/\tau} + \O(n^{-1})
\label{gare}
\enspace ,
\end{eqnarray}
where the passage from~(\ref{mare}) to~(\ref{gare}) relies on the
fact that $P$ has more than one blocks with $\Omega(n)$ vertices
and, thus, $T(P) = \Omega(n^2)$. (This is our only use of the
fact that there are more than one blocks with $\Omega(n)$
vertices.)

To bound $\Pr[\r \mid \c]$ using~(\ref{produ}),(\ref{gare}) we first observe
that the sets $E(v,j)$ induce a partition of the set of two-element sets
$\{v,w\}$ enumerated by $T(P)$, since each $\{v,w\}$ where $v \in V_i$,
$w \in V_j$ and $i < j$ belongs to exactly one such set, namely $E(v,j)$.
Since the total number of edges is fixed and each event
${\cal E}(v,j)$ ``consumes" at least one edge of $E$, it is intuitively
clear that the events ${\cal E}(v,j)$ should be negatively correlated.
To prove this assertion, we view the formation of $E$ (conditional on $\c$)
as an allocation scheme with $m$ distinguishable balls,
$T(P)$ boxes, and a partition of the set of boxes into disjoint subsets
$E(v,j),\,(v\in V_i,\,i<j)$. Thus, the occurrence of ${\cal E}(v,j)$ simply
means that the total occupancy of boxes from $E(v,j)$ is at least one.
Now, the negative correlation of the events ${\cal E}(v,j)$ follows from
a classical result of McDiarmid~\cite{Farr}. As a result we get
\begin{equation}\label{my_neg_cor}
\Pr[\r \mid \c] \leq
\prod_{\stackrel{\scriptstyle{i<j}}{v \in V_i}}{\Pr[{\cal E}(v,j)]}
\enspace ,
\end{equation}
and, thus, using~(\ref{produ}),(\ref{gare}) and (\ref{my_neg_cor}) we
get
\begin{eqnarray}
\nonumber \Pr[\r \mid \c] & \leq &
\prod_{1\leq i<j \leq k}
      {\left(1-e^{-\alpha_j c/\tau} + \O(n^{-1})\right)^{\alpha_i n}}\\
         & = &
\left(
  \prod_{2 \leq j \leq k}
   {
    \left(
           1-e^{-\alpha_j c /\tau}
    \right)^{\sum_{i<j}{\alpha_i}}
   }
\right)^n \label{eq:prob_rigid} \times \O(1) \enspace .
\end{eqnarray}

Having bounded $\Pr[\r \mid \c]$, we bound the expected number
of rigid \mbox{$k$-colorings}, $\ex[R(G)]$, as follows.
For \mbox{$k$-partitions} $P_1=V^1_1,\ldots,V_k^1$ and
$P_2=V^2_1,\ldots,V_k^2$,
we say that $P_1$ is isomorphic to $P_2$ if $|V_i^1|=|V_i^2|$, for all
$i$.
Clearly, if $P_1$, $P_2$ are isomorphic then $\Pr[R_{P_1}]=\Pr[R_{P_2}]$.
Let ${\cal P}$ be any maximal set of non-isomorphic $k$-partitions of $V$.
Then
\begin{eqnarray}
\nonumber \ex[R(G)] & = &
\sum_{P}  {\Pr[R_P]} \\
\nonumber & = &
\sum_{P \in {\cal P}}
{
{n \choose {\alpha_1 n ,\ldots,\alpha_k n}}
\Pr[R_P]
} \\
& \leq &
\max_{P \in {\cal P}}
\left[
{n \choose {\alpha_1 n ,\ldots,\alpha_k n}}
\Pr[R_P]
\right] n^{k-1} \label{usef} \enspace ,
\end{eqnarray}
% where (\ref{usef}) follows by noting that that
as there are at most $n^{k-1}$ (ordered) partitions of $n$ into $k$
integers.
Moreover, if $n>0$ and all $\alpha_i n$ are integers
it is well-known that
\begin{equation}
{n \choose {\alpha_1 n ,\ldots,\alpha_k n}} <
\left(\frac{1}{\alpha_1^{\alpha_1}\cdots{\alpha_k}^{\alpha_k}}\right)^n
\label{eq:chb} \enspace  , \mbox{ where $0^0 \equiv 1$.}
\end{equation}

Thus, combining (\ref{newcp}),(\ref{taudef}) and
(\ref{eq:prob_rigid})--(\ref{eq:chb}) we have
\begin{equation}\label{takis}
\ex[R(G)] \leq
\left(
\max_{P\in{\cal P}} f(P)
\right)
^n \times
\O(n^{k-1})
\end{equation}
where
%(f(P))^n \O(n^{k-1})$, where
\begin{equation}\label{monster}
f(P) = %\left(
 %\max_{P\in{\cal P}}
 %\left[
         \frac{\left(2\sum_{i < j} \alpha_i \alpha_j\right)^c}
                     {\alpha_1^{\alpha_1}\cdots{\alpha_k}^{\alpha_k}}
         \prod_{2 \leq j \leq k}
     {
              \left(
                    1-e^{-\alpha_j c/\tau}
               \right)^{\sum_{i<j}{\alpha_i}}
     }
 %\right]
%\right)
%^n
%\O(n^k)
\label{eq:max} \enspace .
\end{equation}

Letting $Q=\{q/n : q \in \{0,\ldots,n\}\}$, it is clear that
maximizing $f$ over $P\in {\cal P}$ amounts to maximizing the
right-hand side of~(\ref{monster}) over $Q^k$ subject to
$\sum_i \alpha_i = 1$. Naturally, we still get an upper bound
on $\ex[R(G)]$ if  we relax each such $\alpha_i$ to an arbitrary real
number in $[0,1]$ and maximize the extended function, $g$, over
$D=[0,1]^k$ subject to $\sum_i \alpha_i = 1$.
If for some $c^*=c^*(k)$ the resulting maximum of $g$
is strictly less than 1, then~(\ref{takis}) implies that
$\ex[R(G)] \ra 0$ as $n \ra \infty$
and, thus, that $G^r(n,c^*n)$ is \as non-$k$-colorable.

It is straightforward to verify that $g$ is continuous,
differentiable and its gradient is bounded on $D$.
As a result, $g$ can be maximized numerically with arbitrarily good,
guaranteed precision (we used Maple~\cite{maple} and the code
in~\cite{recipes}). For example, for $k=3$ we have
$$
g(\alpha_1,\alpha_2,\alpha_3)=
\frac{\left(2 \tau_3\right)^c
\left(1-e^{-\alpha_2 c/\tau_3}\right)^{\alpha_1}
\left(1-e^{-\alpha_3 c/\tau_3}\right)^{\alpha_1+\alpha_2}}
{\alpha_1^{\alpha_1}\alpha_2^{\alpha_2}\alpha_3^{\alpha_3}}
$$
where $\tau_3=\alpha_1\alpha_2 + \alpha_1 \alpha_3 +\alpha_2\alpha_3$.
For $c^*=2.5217$, $g$ is maximized around
$\alpha_1=0.30746$, $\alpha_2=0.33527$, $\alpha_3=0.35727$ and at that
vicinity it is strictly less than $0.9999744$. Thus, $G^r(n,m=c^*n)$ is
\as non-$k$-colorable, implying $c_3 < 2.522$.

Similarly, we get the following new bounds for $c_k$ for
$3 \leq k \leq 7$. (The choice of 7 is rather arbitrary, as the numerical
computations remain manageable for substantially larger $k$.)
\begin{center}%\[
\begin{tabular}{|l|c|c|c|c|c|c||} \hline
$k$                  & 3      & 4      & 5      & 6      & 7 \\ \hline
First moment bound  & 2.710 & 4.819 & 7.213 & 9.828 & 12.714 \\ \hline
New bound            & 2.522 & 4.587 & 6.948 & 9.539 & 12.316 \\ \hline
\end{tabular}
\end{center}%\]
The above table gives an idea of how our improvement over the
first moment bound scales with $k$. Recalling that the first moment bound
is asymptotically tight, we see that already for $k=7$ the
improvement has dropped to less than $3\%$ from $7 \%$ for $k=3$.

It seems clear that one could improve the upper bound
on $c_k$ somewhat further by imposing a stricter local maximality condition.
For example, one could consider conditions that involve ``moving" two
vertices
at a time. Unfortunately, the lack of ``independence" between the
outcomes of different moves in that setting seems to
complicate matters greatly.

\subsection*{Acknowledgements}
We would like to thank the authors of \cite{KKK} for providing us with an
early draft of their paper and an anonymous referee for many valuable
comments.

\begin{thebibliography}{99}

\bibitem{af}
D. Achlioptas, E. Friedgut,
A sharp threshold for $k$-colorability,
{\em Random Structures \& Algorithms},
{\bf 14} (1999), 63--70.


\bibitem{focs}
D. Achlioptas, M. Molloy,
The analysis of a list-coloring algorithm on a random graph,
{\em 38th Annual Symposium on Foundations of Computer Science},
Miami, FL (1997),  \mbox{204--212}.

\bibitem{alon}
N. Alon, J.H. Spencer,
{\bf The Probabilistic Method,} with an Appendix of open
problems by P. \erd, J. Wiley \& Sons, New York, 1992.

\bibitem{chv}
V. Chv\'{a}tal,
Almost all graphs with $1.44n$ edges are 3-colorable,
{\em Random Structures \& Algorithms}, {\bf 2} (1991), 11--28.

\bibitem{ErRe60}
P. \erd,  A. R\'{e}nyi,
On the evolution of random graphs,
Publication of the Mathematical Institute of
the Hungarian Academy of Sciences, {\bf 5} (1960), 17--61.

\bibitem{frie}
E. Friedgut,
Necessary and sufficient conditions for sharp thresholds of graph
properties, and the $k$-SAT problem,
{\em Journal of the American Mathematical Society}, {\bf 12} (1999),
1017--1054.

\bibitem{grmc}
G.R. Grimmett, C.J.H. McDiarmid,
On colouring random graphs,
{\em Mathematical Proceedings of the Cambridge Philosophical Society},
{\bf 77} (1975), 313--324.


\bibitem{KKK}
L. M. Kirousis,  E. Kranakis,  D. Krizanc, and Y. Stamatiou,
Approximating the unsatisfiability threshold of random formulas,
{\em Random Structures \& Algorithms}, {\bf 12} (1998), 253--269.

\bibitem{KS}
L. M. Kirousis,  Y. Stamatiou,
An inequality for reducible increasing properties of random words,
Technical Report, Computer Technology Institute,  Greece, (1997), 1--3.



\bibitem{luc}
T. {\L}uczak,
The chromatic number of random graphs,
{\em Combinatorica}, {\bf 11} (1991), 45--54.


\bibitem{luccore}
T. {\L}uczak,
Size and connectivity of the $k$-core of a random graph,
{\em Discrete Mathematics}, {\bf 91} (1991), 61--68.

\bibitem{Farr}
C.J.H. McDiarmid,
On a correlation inequality of Farr,
{\em Combinatorics, Probability and Computing}, {\bf 1} (1992), 157--160.

\bibitem{mikemsc}
M. Molloy,
The chromatic number of sparse random graphs,
M. {M}ath {T}hesis, University of Waterloo, (1992).


\bibitem{molloygap}
M. Molloy,
A gap between the appearances of a $k$-core and a $(k+1)$-chromatic graph,
{\em Random Structures \& Algorithms}, {\bf 8} (1996), 159--160.


\bibitem{MoReds}
M. Molloy, B. Reed,
A critical point for random graphs with a given degree sequence,
{\em Random Structures \&  Algorithms},
{\bf 6} (1995), 161--179.


\bibitem{PSW}
B. Pittel, J.H. Spencer, and N.C. Wormald,
Sudden emergence of a giant $k$-core in a random graph,
{\em Journal of Combinatorial Theory Series B}, {\bf 67} (1996), 111--151.



\bibitem{recipes}
W.H. Press, S. Teukolsky, W.T. Vetterling, and B.P. Flannery,
{\bf Numerical recipes in {C}},
Cambridge University Press, Cambridge, 1992.

\bibitem{maple}
D. Redfern,
{\bf The {M}aple {H}andbook: {M}aple {V} {R}elease 3},
Springer, New York,  1994.

\end{thebibliography}


\end{document}

\end{document}