\documentstyle[12pt]{article}
\pagenumbering{arabic}
\textwidth 6.2in
\textheight 8.6in
\topmargin 0pt
\oddsidemargin 0.1in
\evensidemargin 0.1in
\baselineskip 3ex
\parskip 2ex
\parindent 0pt
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7}
(2000),
\#R29 \hfill}
\thispagestyle{empty}
\newtheorem{definition}{\sc Definition}
\newtheorem{theorem} {\sc {\bf Theorem}}
\newtheorem{lemma} {\sc Lemma}
\newtheorem{phase}{\sc Phase}
\newtheorem{claim}{\sc {\bf Claim}}
\newcommand{\modelm}{$G_{m}$}
\newcommand{\modelmm}{$G_{mm}$}
\newcommand{\modelp}{$G_{p}$}
\newcommand\E{\operatorname{\mathbb E{}}}
\renewcommand\P{\operatorname{\mathbb P{}}}
\newcommand\Var{\operatorname{Var}}
\newcommand\Cov{\operatorname{Cov}}
\newcommand\dilog{{\rm dilog}}
\newcommand\Li{{\rm Li}}
\newcommand\Polylog{{\rm Polylog}}
\newcommand\Fn[1]{F_{n,#1}}
\newcommand\RHS{right hand side}
\newcommand{\parfrac}[2]{\Bigl(\frac{#1}{#2}\Bigr)}
\newenvironment{proof} {\par\noindent {Proof.}}{\hfill \mbox{$\Box$}}
\newtheorem{Step}{\sc Step}
\newcommand{\prg}{\vskip .3cm \noindent}
\newcommand{\pf}{{\sc Proof} }
\newcommand{\pfo}{{\sc Proof (Outline)} }
\newcommand{\mod}{\,{\rm mod}\,}
\newcommand{\op}{\diamondsuit}
\newcommand{\cL}{{\cal L}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cF}{{\cal F}}
\newcommand{\QL}{Q_n [ {\cal L} ]}
\newcommand{\dep}{{\rm depth}}
\newcommand{\ord}{{\rm order}}
\newcommand{\prob}{\mbox{\bf Pr}}
\newcommand{\ex}{\mbox{\bf E}}
\newcommand{\G}{{\cal G}}
\def\thefootnote{\fnsymbol{footnote}}
\begin{document}
\title{{\bf A note on the non-colorability threshold of a random
graph}}
\author{Alexis C. Kaporis,
Lefteris M. Kirousis, and
Yannis C. Stamatiou\\
University of Patras\\
Department of Computer Engineering and
Informatics\\
Rio 265~00, Patras, Greece.\\
e-mail: \{kaporis,kirousis,stamatiu\}@ceid.upatras.gr\\
Third author also: Computer Technology Institute\\
61 Riga Feraiou Str., GR 262 21, Patras, Greece.
}
\date{Submitted: April 6, 2000; Accepted: May 23, 2000}
\maketitle
\begin{abstract}
\noindent
In this paper we consider the problem of establishing
a value $r_0$ such that almost all random graphs with $n$
vertices and $rn$ edges, $r > r_0$, are
asymptotically not 3-colorable. In our approach we combine the
concept of rigid legal colorings introduced by Achlioptas
and Molloy with the occupancy problem for random allocations
of balls into bins. Using the sharp estimates obtained
by Kamath et al. of the probability
that no bin is empty after the random placement
of the balls and exploiting the relationship
between the placement of balls and the rigid legal
colorings, we improve the value $r_0 = 2.522$
previously obtained by Achlioptas and Molloy to $r_0 = 2.495$.
\end{abstract}
% \def\thefootnote{\fnsymbol{footnote}}
% \newpage
%\pagenumbering{arabic}
\section{Introduction}
In this paper, we consider the problem of computing the
smallest value $r_0$ such that almost
all graphs with $rn$ edges, $r > r_0$, are not $3$-colorable.
We say that a graph $G(V, E)$
is 3-colorable if the set $V$ of its vertices
can be partitioned into 3 nonempty
cells $V_1, V_2$, and $V_3$ such that no two vertices of the same
partition
are adjacent. This partition is called a {\em 3-coloring}
of $G$ and the vertices of the set $V_j, j=1, 2, 3$
are said to have color $j$.
Like many other combinatorial problems on random structures
(e.g. formulas, graphs etc.), there appears that the property
of a graph being 3-colorable exhibits a {\em threshold behavior}.
That is, it is believed, and supported by experimental evidence,
that there exists a critical constant $r_c$
such that a randomly generated graph with $n$ vertices
and $(r_c - \epsilon)n$ edges is 3-colorable with high probability
while the opposite is true for a randomly generated graph
with $(r_c + \epsilon)n$ edges.
While the question of existence of this critical value
is still open (as it is also for the unsatisfiability threshold
for random formulas), there have been established rigorously
upper and lower bounds for this value.
The best lower bound is currently 1.923
and has been obtained by Achlioptas and Molloy in~\cite{am}
while the best upper bound is 2.522 by the same authors
(see~\cite{ach}).
In order to introduce our method,
we will briefly discuss the first moment method
that makes use of Markov's inequality and gives
as an upper bound to the non-colorability threshold the value 2.7.
Let $P = (V_1, V_2, V_3)$
be an arbitrary but fixed partition of the vertex set $V$ of a graph
$G(V,E)$
and let $C_P$ denote the event that $P$ is a $3$-coloring of the
graph $G$. The number of edges
that are allowed to exist in a graph with this
3-coloring is
$$
\sum_{i i$, i.e. only when color $j$ is ``higher'' than color
$i$.
We say that a vertex $u$ of color $i$ is {\it unmovable}
if every change to a higher indexed color $j$
invalidates the coloring $P$. Thus, $u$ of color $i$ is unmovable
if it is adjacent with at least one vertex of
every cell $V_j$, such that $j > i$.
Then $P$ is a {\it rigid} coloring of a graph $G$,
if $P$ makes every vertex of $G$ unmovable.
This event will be denoted by $R_P$.
{From} all possible 3-colorings of a random graph, only
its rigid colorings are used in order to obtain a smaller
expression for the right-hand side in~(\ref{eq}).
If by $R^{\sharp}$ we denote the set of rigid 3-colorings
of a random graph,
it can be easily proved (see~\cite{Kir} for the analogous
proof for 3-SAT) that the following Markov type
inequality holds:
%
\begin{equation}
\prob[G \mbox{ has a 3-coloring}] \leq
\ex[|R^{\sharp}|] = \sum_{P = (V_1, V_2, V_3)} \prob[R_P ~|~ C_P]
\prob[C_P].
\end{equation}
%
As in 3-SAT, this improves the value 2.7 obtained
by the simple first moment argument above.
The value obtained with the rigid colorings technique
is equal to 2.495.
In what follows, we will be concerned with the computation of
$\prob[R_P ~|~ C_P]$.
\section{Asymptotic approximations to probabilities
using the occupancy problem}
In this section, we will compute
the asymptotic probability of the conditional event
$R_P | C_P$ following a line of reasoning similar
to that in~\cite{Kap}.
First, fix a 3-coloring $P_0$:
%
$$
P_0 = (V_1, V_2, V_3), ~\mbox{such that},
~|V_1|=\alpha_0 n, |V_2|=\beta_0 n,|V_3|= \gamma_0 n,
$$
$$
\alpha_0 + \beta_0 + \gamma_0 =1,
~\alpha_0, \beta_0, \gamma_0 \geq 0.
$$
Since we condition on the event $C_{P_{0}}$, in each of the $rn$ edge
selections no edge with both its endpoints into a part $V_j, j=1, 2,
3$ is
allowed to
appear. The number of edges that do not violate this constraint is
$(\alpha_0 \beta_0 + \alpha_0 \gamma_0 + \beta_0 \gamma_0)n^2$. Thus
we obtain,
%
\begin{eqnarray}
\prob [C_{P_{0}}] =
[2(\alpha_0 \beta_0 + \alpha_0 \gamma_0 + \beta_0 \gamma_0)]^{rn}
= [2(\alpha_0 \beta_0 + (\alpha_0 + \beta_0) (1- \alpha_0 -
\beta_0))]^{rn}.
\label{eq_3}
\end{eqnarray}
%
When conditioning on the event $C_{P_{0}}$, the random graphs
of the resulting probability space may contain edges only from within
the edges
that connect vertices of different partitions of $P_0$.
The number of possible edges connecting parts $V_1, V_2$
is $\alpha_0 \beta_0 n^2$.
For each of these edges, their endpoint that belongs to $V_1$
is unmovable to $V_2$ since their other endpoint belongs to $V_2$.
Also, $\alpha_0 \gamma_0 n^2$ and $\beta_0 \gamma_0 n^2$ are the
numbers
of possible edges between vertices of partitions $V_1, V_3$ and
$V_2, V_3$ respectively. Let $E_{ij}, i