\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.34}{22(1)}{2015} %\setlength{\textwidth}{6.5in} %\setlength{\textheight}{9in} %\setlength{\topmargin}{-0.5in} %\setlength{\oddsidemargin}{0in} %\setlength{\evensidemargin}{0in} \renewcommand{\emph}[1]{\textit{#1}} \usepackage{enumerate,amsmath,amsthm,latexsym,amssymb} \usepackage{color}\usepackage{graphicx} \usepackage{algpseudocode} \def\bV{{V_\l}} \definecolor{brown}{cmyk}{0, 0.72, 1, 0.45} \definecolor{grey}{gray}{0.5} %\newcommand{\gbs}[1]{{\blue #1}} \newcommand{\dun}{\,\dot\cup\,} \newcommand{\gbs}[1]{#1} \def\blue{\color{blue}} \def\green{\color{green}} \def\cyan{\color{cyan}} \def\magenta{\color{magenta}} \def\brown{\color{brown}} \def\black{\color{black}} \def\yellow{\color{yellow}} \def\grey{\color{grey}} \newcommand{\old}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \newcounter{rot}%\addtocounter{rot}{1}, \therot \newcommand{\bignote}[1]{\vspace{0.25 in}\fbox{\parbox{6in}{\blue #1}}% \marginpar{\fbox{{\bf {\red \large Q \therot}}}}\addtocounter{rot}{1}} \newcommand{\ignore}[1]{} \newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}} \def\bM{{\bf M}} \newcommand{\M}[1]{M^{(#1)}} \newcommand{\Gi}[1]{\Gamma^{(#1)}} \def\cA{{\cal A}} \def\cB{{\cal B}} \def\dD{{\vec D}} \def\dE{\vec E} \def\dG{\vec G} \def\hcT{\hat{\cT}} \def\inn{{\rm in}} \def\out{{\rm out}} \def\pee{{\mathcal P}} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\ee}{\mathcal{E}} \def\cP{\mathcal{P}} \def\cQ{\mathcal{Q}} \newcommand{\gap}[1]{\mbox{\hspace{#1 in}}} \newcommand{\prend}{\hspace*{\fill}\mbox{$\Box$}} \newcommand{\prf}{\emph{Proof. }} \newcommand{\proofstart}{{\noindent \bf Proof\hspace{2em}}} \newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}\\ \medskip\\ \medskip} \newcommand{\ratio}[2]{\mbox{$\frac{#1}{#2}$}} \def\ii_(#1,#2){i_{#1}^{#2}} \newcommand{\eqlabel}[1]{\parbox{3em}{\vspace{-\atopdisplayskip}% \begin{equation} \label{#1}\end{equation}}} \renewcommand{\S}[1]{S^{(#1)}} \newcommand{\T}[1]{T^{(#1)}} \newcommand{\hS}[1]{\hat{S}^{(#1)}} \newcommand{\hT}[1]{\hat{T}^{(#1)}} \def\qs{{\bf qs}} \def\LL{\Lambda} \newcommand{\lfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\dee}{L_0} \newcommand{\aand}{\mbox{ and }} \def\bx{{\bf x}} \def\hg{\hat{\g}} \def\cM{\mathcal{M}} \def\a{\alpha} \def\b{\beta} \def\d{\delta} \def\D{\Delta} \def\e{\varepsilon} \def\f{\phi} \def\F{\Phi} \def\g{\gamma} \def\G{\Gamma} \def\k{\kappa} \def\K{\Kappa} \def\z{\zeta} \def\h{\theta} \def\th{\theta} \def\Th{\Theta} \def\l{\lambda} \def\m{\mu} \def\n{\nu} \def\p{\pi} \def\P{\Pi} \def\r{\rho} \def\R{\Rho} \def\s{\sigma} %\def\S{\Sigma} \def\t{\tau} \def\om{\omega} \def\Om{\Omega} \def\w{\omega} \def\x{\xi} \newcommand{\half}{\mbox{$\frac{1}{2}$}} \newcommand{\mnote}[1]{\marginpar{\footnotesize\raggedright#1}} \def\mstar{\mnote{****}} \newcommand{\sfrac}[2]{{\scriptstyle {#1 \over #2} }} \newcommand{\rdup}[1]{\left\lceil #1 \right\rceil} \newcommand{\rdown}[1]{\mbox{$\left\lfloor #1 \right\rfloor$}} \newcommand{\limninf}{\mbox{$\lim_{N \rightarrow \infty}$}} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\whp}{{\bf whp}\xspace} \newcommand{\Whp}{{\bf Whp}\xspace} \newcommand{\gi}{{\bf G}} \newcommand{\ngi}{\overline{{\bf G}}} \newcommand{\imp}{\Longrightarrow} \newcommand{\ra}{\longrightarrow} \newcommand{\rai}{\ra \infty} \newcommand{\raz}{\ra 0} \newcommand{\ooi}{(1+o(1))} \newcommand{\Si}[2]{S_{#1}^{(#2)}} \newcommand{\Sit}{S_i} \newcommand{\Ti}[2]{T_{#1}^{(#2)}} \newcommand{\Tit}{T_i} \newcommand{\Ai}[2]{A_{#1}^{(#2)}} \newcommand{\hSi}[2]{\hat{S}_{#1,\rho}^{(#2)}} \newcommand{\hTi}[2]{\hat{T}_{#1,\rho}^{(#2)}} \newcommand{\Kdir}{\vec{K}} \newcommand{\Pois}{\operatorname{Pois}} \newcommand{\pone}{\frac{\log n}{n}} %\newcommand{\prob}{\mathbb{P}} \def\cE{\mathcal{E}} \def\cF{\mathcal{F}} \def\cN{{\cal N}} \def\cT{{\cal T}} \def\prob{\Pr} \def\Re{\mathbb{R}} \def\Z{\mathbb{Z}} \newcommand{\brac}[1]{\left( #1 \right)} \newcommand{\bfm}[1]{\mbox{\boldmath $#1$}} \newcommand{\ul}[1]{\mbox{\boldmath $#1$}} \def\hx{\hat{x}} \def\hy{\hat{y}} \def\bn{\ul{n}} \def\ulsi{\ul{\s}} \newcommand{\expect}{\operatorname{\bf E}} \def\E{\expect} \renewcommand{\Pr}{\operatorname{\bf Pr}} \newcommand\bfrac[2]{\left(\frac{#1}{#2}\right)} \def\cq{c_Q} \def\dus{d(\ulsi)} \def\bC{\bar{C}} \def\hC{\hat{C}} \newcommand{\ep}{\varepsilon} \newtheorem{theorem}{Theorem} \newtheorem{conjecture}{Conjecture} \newtheorem{lemma}{Lemma} \newtheorem{corollary}[lemma]{Corollary} \newtheorem{cons}[lemma]{Construction} \newtheorem{remthm}[lemma]{Remark} \newtheorem{claim}[lemma]{Claim} \newtheorem{observation}[lemma]{Observation} \newenvironment{remark}{\begin{remthm}\rm }{\end{remthm}}% \newcounter{thmtemp} \newenvironment{thmnum}[1]{ \setcounter{thmtemp}{\value{theorem}} \setcounter{theorem}{#1} \addtocounter{theorem}{-1} \begin{theorem} }{ \end{theorem} \setcounter{theorem}{\value{thmtemp}} } % \newcommand{\ignore}[1]{} \newcommand{\nospace}[1]{} \def\Otilde{\operatorname{\tilde{O}}} \def\path{\operatorname{PATH}} \def\PD{\operatorname{PD}} \def\END{\operatorname{END}} \def\ATSP{\ensuremath{\operatorname{ATSP}}\xspace} \def\AP{\ensuremath{\operatorname{AP}}\xspace} \newcommand{\eqdef}{\doteq} \newcommand{\al}{\alpha} \newcommand{\chic}{\chi_{\mathrm{c}}} \newcommand{\lo}{\ln} \newcommand{\iS}{{i_S}} \newcommand{\iT}{{i_T}} \newcommand{\xs}{{x}} \newcommand{\yt}{{y}} \newcommand{\inunif}{\in_{\operatorname{unif}}} \newcommand{\ubar}{\bar{u}} \newcommand{\vbar}{\bar{v}} \newcommand{\pinv}{\p^{-1}} \newcommand{\eee}{\mathbb{E}} \newcommand{\N}{\mathbb{N}} \def\BDTS{\texttt{BDAPTA}} \def\expdist{\ensuremath{\operatorname{Exp}}} \def\EX{\expdist(1)} \newcommand{\Bin}{\ensuremath{\operatorname{Bin}}} \newcommand{\Be}{\ensuremath{\operatorname{Be}}} \def\V{{\bf Var}} \newcommand{\beq}[1]{\begin{equation}\label{#1}} \def\eeq{\end{equation}} \newcommand{\ZP}[1]{Z^{P}_{#1,n}} \newcommand{\ZA}[1]{Z^{A}_{#1,n}} \renewcommand{\Re}{\mathbb{R}} \newcommand{\Xijk}{X_{i,j,k}\:} \newcommand{\Cijk}{C_{i,j,k}} \def\hX{\widehat{X}} \def\hV{\widehat{V}} \parindent 0in \parskip .15in \def\leb{\leq_b} \newcommand{\sbs}{\subset} \newcommand{\stm}{\setminus} \newcommand{\dist}{\mathrm{dist}} \newcommand{\bbb}{\mathcal{B}} \newcommand{\st}{\mid} \begin{document} \title{\bf Between 2- and 3-colorability} \author{Alan Frieze\thanks{Research supported in part by NSF grant ccf1013110} \,\ and \ Wesley Pegden\thanks{Research supported in part by NSF grant dms1363136}\\ \small Department of Mathematical Sciences\\[-0.8ex] \small Carnegie Mellon University\\[-0.8ex] \small Pittsburgh PA 15213, U.S.A\\ \small \texttt{alan@random.math.cmu.edu},\,\, \texttt{wes@math.cmu.edu}} \date{\dateline{Sep 10, 2014}{Jan 14, 2015}{Feb 16, 2015}\\ \small Mathematics Subject Classifications: 05C80; 05C15 } \maketitle \begin{abstract} We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n,\,12$, the chromatic number may well be concentrated on the single value $k$, see Friedgut \cite{Fried} and Achlioptas and Friedgut \cite{AcFr}. In this paper, we consider finer notions of colorability for the graphs $G_{n,\frac c n}$ for $c\in (1,c_3)$, by considering homomorphisms from $G_{n,\frac c n}$ to odd cycles $C_{2\ell+1}$. Recall that a graph homomorphism from $G$ to $H$ is a function $f:V(G)\to V(H)$ such that $u\sim v$ implies $f(u)\sim f(v)$\footnote{For a graph $G=(V,E)$ and $a,b\in V$, we write $a\sim b$ to mean that $\set{a,b}\in E$}. In particular, the existence of a homomorphism from a graph $G$ to $C_{2\ell+1}$ implies the existence of homomorphisms to $C_{2k+1}$ for all $k<\ell$. As the 3-colorability of a graph $G$ corresponds to the existence of a homomorphism from $G$ to $K_3$, the existence of a homomorphism to $C_{2\ell+1}$ implies 3-colorability. Thus considering homomorphisms to odd cycles $C_{2\ell+1}$ gives a hierarchy of 3-colorable graphs amenable to increasingly stronger constraint satisfaction problems. Note that a fixed graph having a homomorphism to all odd-cycles is bipartite. Our main result is the following: \begin{theorem} \label{t.hom} For any integer $\ell>1$, there is an $\ep>0$ such that with high probability, $G_{n,\frac{1+\ep}{n}}$ either has odd-girth $<2\ell+1$ or has a homomorphism to $C_{2\ell+1}$. \end{theorem} Conversely, we expect the following: \begin{conjecture} \label{c.nohom} For any $c>1$, there is an $\ell_c$ such that with high probability, there is no homomorphism from $G_{n,\frac c n}$ to $C_{2\ell+1}$ for $\ell\geq \ell_c$. \end{conjecture} As $c_3$ is known to be at least $4.03$ \cite{AM}, the following confirms Conjecture \ref{c.nohom} for a significant portion of the interval $(1,c_3)$. \begin{theorem} \label{t.nohom} For any $c>2.774$, there is an $\ell_c$ such that with high probability, there is no homomorphism from $G_{n,\frac c n}$ to to $C_{2\ell+1}$ for $\ell\geq \ell_c$. \end{theorem} We also have that $\ell_4=2$: \begin{theorem} \label{t.l4} With high probability, $G_{n,\frac{4}{n}}$ has no homomorphism to $C_5$. \end{theorem} Note that as $c_3>4.03>4$, see Achlioptas and Moore \cite{AM}, we see that there are triangle-free 3-colorable random graphs without homomorphisms to $C_5$. Our proof of Theorem \ref{t.l4} involves computer assisted numerical computations. The same calculations which rigorously demonstrate that $\ell_4=2$ suggest actually that $\ell_{3.75}=2$ as well. Our results can be reformulated in terms of the \emph{circular chromatic number} of a random graph. Recall that the circular chromatic number $\chic(G)$ of $G$ is the infimum $r$ of circumferences of circles $C$ for which there is an assignment of open unit intervals of $C$ to the vertices of $G$ such that adjacent vertices are assigned disjoint intervals. (Note that if circles $C$ of circumference $r$ were replaced in this definition with line segments $S$ of length $r$, then this would give the ordinary chromatic number $\chi(G)$.) It is known that $\chi(G)-1< \chic(G)\leq \chi(G)$, that $\chic(G)$ is always rational, and moreover, that $\chic(G)\leq \frac{p}{q}$ if and only if $G$ has a homomorphism to the circulant graph $C_{p,q}$ with vertex set $\{0,1,\dots,q-1\}$, with $v\sim u$ whenever $\dist(v,u):=\min\{\abs{v-u},v+q-u,u+q-v\}\geq q$. (See \cite{zhu}.) Since $C_{2\ell+1,\ell}$ is the odd cycle $C_{2\ell+1}$ our results can be restated as follows: \begin{theorem} %Let $G^g_{n,p}$ deonote an instance of the random graph $G_{n,p}$ conditioned on having odd-girth $\geq g$. We have: In the following, inequalities for the circular chromatic number hold with high probability. \begin{enumerate} \item For any $\delta>0$, there is an $\ep>0$ such that, $G=G_{n,\frac{1+\ep}{n}}$ has $\chic(G)\leq2+\delta$ unless it has odd girth $\leq \frac{2}{\delta}$. \item For any $c>2.774$, there exists $r>2$ such that $\chic(G_{n,\frac c n})>r$. \item $2.5\leq \chic(G_{n,\frac 4 n})<3$. \end{enumerate} \end{theorem} Note that for any $c$ and $\ell>1$, there is positive probability that $G_{n,\frac c n}$ has odd girth $<2\ell+1$, and a positive probability that it does not. In particular, as the probability that $G_{n,\tfrac{c}{n}}$ has small odd-girth can be computed precisely, Theorem \ref{t.hom} gives an exact probability in $(0,1)$ that $G_{n,\frac{1+\ep}{n}}$ has a homomorphism to $C_{2\ell+1}$. Indeed, Theorem \ref{t.hom} implies that if $c=1+\e$ and $\e$ is sufficiently small relative to $\ell$, then \beq{eq1} \lim_{n\to\infty}\Pr(\chic(G_{n,\frac{c}{n}})\in (2+\tfrac{1}{\ell+1}, 2+\tfrac 1 \ell])=e^{-\f_{\ell}(c)}-e^{-\f_{\ell+1}(c)}, \eeq where $$\f_\ell(c)=\sum_{i=1}^{\ell-1} \frac{c^{2i+1}}{2(2i+1)}.$$ We close with two more conjectures. The first concerns a sort of pseudo-threshold for having a homomorphism to $C_{2\ell+1}$: \begin{conjecture} \label{c.sharp} For any $\ell$, there is a $c_\ell>1$ such that $G_{n,\frac c n}$ has no homomorphism to $C_{2\ell+1}$ for $c>c_\ell$, and has either odd-girth $<2\ell+1$ or has a homomorphism to $C_{2\ell+1}$ for $c1$, the 2-core consists of a linear size sub-graph together with a few vertex disjoint cycles. By few we mean that in expectation, there are $O(1)$ vertices on these cycles. Let $00$.} at most $\log n$. It follows from this and \eqref{Z=} that $$\th_k=1+o(1)\text{ for }k\leq \log^2n\text{ and }\th_k=O(n^{1/2})\text{ in general}.$$ \begin{lemma} \label{l.long} For any $\alpha,\beta$, there exists $c_0>1$ such that w.h.p. any cycle $C$ of length greater than $\alpha\log n$ in the 2-core of $G_{n,p}$, $p=\frac{c}{n}$, $10$ such that w.h.p. we can decompose the edges of the $G=G_{n,p}$, $p=\frac{1+\ep}{n}$, $0<\ep<\ep_0$, as $F\cup M$, where $F$ is a forest, and where the distance in $F$ between any two edges in $M$ is at least $k$. \end{lemma} \newcommand{\ppp}{\mathcal{P}} \proofstart We fix some $\a<\frac 1 {10}$. By choosing $\beta<\frac 1 {2k}$ in Lemma \ref{l.long} we can find, in every cycle of length $>\alpha \log n$ of the $2$-core $K_2$ of $G$ (which includes all cycles of $G$), a path of length at least $2k+1$ whose interior vertices are all of degree 2. We can thus choose in each cycle of $K_2$ of length $>\alpha \log n$ such a path of maximum length, and let $\ppp$ denote the set of such paths. (Note that, in general, there will be fewer paths in $\ppp$ than long cycles in $K_2$ due to duplicates, but that the elements of $\ppp$ are nevertheless disjoint paths in $K_2$.) We now choose from each path in $\ppp$ an edge from the center of the path to give a set $M_1$. Note that the set of cycles in $G\stm M_1$ is the same as the set of cycles in $G\stm \bigcup_{P\in \ppp} P$. (In particular, the only cycles which remain have length $\leq \alpha \log n$ and are at distance $\geq k$ from $M$.) Thus, letting $M_2$ consist of one edge from each cycle of $G\stm M_1$, Lemma \ref{l.short} implies that $M=M_1\cup M_2$ is as desired. \proofend \begin{proof}[Proof of Theorem \ref{t.hom}] Our goal in this section is to give a $C_{2\ell+1}$-coloring of $G=G_{n,\frac{1+\ep}{n}}$ for $\ep>0$ sufficiently small. By this we will mean an assignment $c:V(G)\to \{0,1,\dots,2\ell\}$ such that $x\sim y$ in $G$ implies that $c(x)\sim c(y)$ as vertices of $C_{2\ell+1}$; that is, that $x=y\pm 1\pmod {2\ell+1}$. Consider a decomposition of $G$ as $F\cup M$ as given by Lemma \ref{l.decomp}, with $k=4\ell-2$. We begin by 2-coloring $F$. Let $c_F:V\to \{0,1\}$ be such a coloring. Our goal will be to modify this coloring to give a good $C_{2\ell+1}$ coloring of $G$. Let $\bbb$ be the set of edges $xy\in M$ for which $c_F(x)=c_F(y)$, and let $B$ be a set of distinct representatives for $\bbb$, and for $i=0,1$, let $B^i=\{v\in B \st c_F(v)=i\}$. We now define a new $C_{2\ell+1}$ coloring $c:V\to \{0,1,\ldots,2\ell\}$, by \begin{equation}\label{qw} c(v)= \begin{cases}%\left\{\begin{array}{cl} c_F(v) & \mbox{if }\dist_F(v,B)\geq 2\ell-1\\ c_F(x)-(-1)^j(\dist_F(x,v)+1) & {\mbox{if } \exists x\in B^j \mbox{ s.t. } \dist(x,v)_F<2\ell-1.}\\ \end{cases} %\end{array}\right. \end{equation} (Color addition and subtraction are computed modulo $2\ell+1$.) Since edges in $M$ are separated by distances $\geq 4\ell-2$, this coloring is well-defined (i.e., there is at most one choice for $x$). Moreover, $c$ is certainly a good $C_{2\ell+1}$-coloring of $F$. Thus if $c$ is a not a good $C_{2\ell+1}$-coloring of $G$, it is bad along some edge $xy\in M.$ But if such an edge was already properly colored in the 2-coloring $c_F$, it is still properly colored by $c$, since it has distance $\geq 4\ell-2\geq 2\ell-1$ from other edges in $M$. On the other hand, if previously we had $c_F(x)=c_F(y)=i$, and WLOG $x\in B^i$, then the definition of $c(v)$ gives that we now have that $c(x)\in\set{i-1,i+1}$ (modulo $2\ell-1$). Thus if $c$ is not a good $C_{2\ell+1}$-coloring of $G$, then there is an edge $xy\in M$ such that $x\in B^i$ and $y$'s color also changes in the coloring $c$; but by the distance between edges in $M$, this can only happen if $x$ and $y$ are at $F$-distance $<2\ell-1$. Note also that $c_F(x)=c_F(y)$ implies that $\dist_F(x,y)$ is even. Thus in this case, $F\cup \{xy\}$ contains an odd cycle of length $\leq 2\ell-1$, and so $G$ has odd girth $<2\ell+1$, as desired. \end{proof} \section{Avoiding homomorphisms to long odd cycles}\label{ah} For large $\ell$, one can prove the non-existence of homomorphisms to $C_{2\ell+1}$ using the following simple observation: \begin{observation} If $G$ has a homomorphism to $C_{2\ell+1}$, then $G$ has an induced bipartite subgraph with at least $\frac{2\ell}{2\ell+1} |V(G)|$ vertices. \end{observation} \begin{proof}Delete the smallest color class.\end{proof} \begin{proof}[Proof of Theorem \ref{t.nohom}] The probability that $G_{n,\frac c n}$ has an induced bipartite subgraph on $\beta n$ vertices is at most \begin{equation}\label{e.bipartite} \binom{n}{\beta n}2^{\beta n}\brac{1-\frac{c}{n}}^{\beta^2 n^2/4}<\left(\frac{2^\beta e^{-c\beta^2/4}}{\beta^\beta(1-\beta)^{1-\beta}}\right)^n \end{equation} The expression inside the parentheses is unimodal in $\beta$ for fixed $c$, and, for $c>2.774$, is less than 1 for $\beta>.999971$. In particular, for $c>2.774$, $G_{n,\frac c n}$ has no homomorphism to $C_{2\ell+1}$ for $2\ell+1\geq 1,427,583$. \end{proof} \section{Avoiding homomorphisms to $C_5$}\label{ah5} A homomorphism of $G=G_{n,p},p=\frac c n$ into $C_5$ induces a partition of $[n]$ into sets $V_i,i=0,1,\ldots,4$. As explained momentarily, this partition can be chosen so that the following hold: \begin{enumerate}[{\bf P1}] \item The sets $V_i,i=0,1,\ldots,4$ are all independent sets. \item There are no edges between $V_i$ and $V_{i+2}\cup V_{i-2}$. Here addition and subtraction in an index are taken to be modulo 5. \item Every $v\in V_i,i=1,2,3,4$ has a neighbor in $V_{i-1}$. \item Every $v\in V_2$ has a neighbor in $V_3$. \end{enumerate} Conditions {\bf P1,P2} are what is required for a homomorphism to $C_5$. For {\bf P3} we observe that if $v\in V_i$ has no neighbor in $V_{i-1}$ then we can move $v$ to $V_{i+2}$ and still maintain {\bf P1,P2}. As argued in Hatami \cite{Hat}, Lemma 2.1, applying this repeatedly eventually leads to {\bf P1,P2,P3} holding. Given {\bf P1,P2,P3}, if $v\in V_2$ has no neighbors in $V_3$ then we can move $v$ from from $V_2$ to $V_0$ and still have a homomorphism. Furthermore, this move does not upset {\bf P1,P2,P3}; thus we may assume \textbf{P4} as well. We let $|V_i|=n_i$ for $i=0,1,\ldots,4$. For a fixed partition we then have \beq{P12} \Pr({\bf P1\wedge P2})=(1-p)^S\text{ where }S=\binom{n}{2}-\sum_{i=0}^4n_in_{i+1}. \eeq \beq{P3} \Pr({\bf P3\mid P1\wedge P2})=\prod_{i=1}^4(1-(1-p)^{n_{i-1}})^{n_i}. \eeq \beq{P4} \Pr({\bf P4\mid P1\wedge P2\wedge P3})\leq \brac{1-\brac{1-\frac{1}{n_2}}^{n_3}(1-p)^{n_3}}^{n_2} \eeq Equations \eqref{P12} and \eqref{P3} are self evident, but we need to justify \eqref{P4}. Consider the bipartite subgraph $\G$ of $G_{n,p}$ induced by $V_2\cup V_3$. {\bf P3} tells us that each $v\in V_3$ has a neighbor in $V_2$. Denote this event by $\cA$. We will now describe the construction of a random bipartite graph $\G'$ on $V_2,V_3$ such that we can couple $\G,\G'$ so that $\G\subseteq \G'$. The RHS of \eqref{P4} is the probability that {\bf P4} holds using $\G'$ and the coupling implies that this bounds the probability of {\bf P4} in $\G$. To construct $\G'$ we choose a random mapping $\f$ from $V_3$ to $V_2$. We then create a bipartite graph $\G'$ with edge set $E_1\cup E_2$. Here $E_1=\set{\set{x,y}:x\in V_3,y=\f(x)}$ and $E_2$ is obtained by independently including each of the $n_2n_3$ possible edges between $V_2$ and $V_3$ with probability $p$. We now prove that we can couple $\G,\G'$ so that $\G\subseteq \G'$. Event $\cA$ can be construed as follows: A vertex in $v\in V_3$ chooses $B_v$ neighbors in $V_2$ where $B_v$ is distributed as a binomial $Bin(n_2,p)$, conditioned to be at least one. The neighbors of $v$ in $V_2$ will then be a random $B_v$ subset of $V_2$. We only have to prove then that if $v$ chooses $B_v'$ random neighbors in $\G'$ then $B_v'$ stochastically dominates $B_v$. Here $B_v'$ is one plus $Bin(n_2-1,p)$ and domination is easy to confirm. We have $n_2-1$ instead of $n_2$, since we do not wish to count the edge $v$ to $\f(v)$ twice. Note also, included in the estimate in the RHS of \eqref{P4} is the fact that the set of events $\set{v \text{ is not chosen as an image of }\f}$ for $v\in V_2$, are negatively correlated. We now write $n_i=\a_in$ for $i=0,\ldots,4$. We are particularly interested in the case where $c=4$. Now \eqref{e.bipartite} implies that $G_{n,\frac 4 n}$ has no induced bipartite subgraph of size $\beta n$ for $\beta >0.94$. Thus we may assume that $\alpha_i\geq0.06$ for $i=0,\ldots,4$. In which case we can write \begin{multline*} \Pr({\bf P1\wedge P2\wedge P3\wedge P4})\leq \\ e^{o(n)}\times \exp\set{-c\brac{\frac 1 2-\sum_{i=0}^4\a_i\a_{i+1}}n}\times \brac{\prod_{i=1}^4(1-e^{-c\a_{i-1}})^{\a_i}}^n\times\\ (1-e^{-\a_3/\a_2}e^{-c\a_3})^{\a_2n}. \end{multline*} The number of choices for $V_0,\ldots,V_4$ with these sizes is $$\binom{n}{n_0,n_1,n_2,n_3,n_4}=e^{o(n)}\times \bfrac{1}{\prod_{i=0}^4\a_i^{\a_i}}^n\leq 5^n.$$ Putting $\al_4=1-\al_0-\al_1-\al_2-\al_3$ and \begin{multline*} b=b(c,\al_0,\al_1,\al_2,\al_3)= \frac{1}{ {\al_0}^{\al_0} {\al_1}^{\al_1} {\al_2}^{\al_2} {\al_3}^{\al_3} {\al_4}^{\al_4}}\\ e^{c(\al_0\al_4-\frac 1 2)} (e^{c \al_0}-1)^{\al_1} (e^{c \al_1}-1)^{\al_2} (e^{c \al_2}-1)^{\al_3} (e^{c \al_3}-1)^{\al_4} (1-e^{-\al_3/\al_2}e^{-c \al_3})^{\al_2}, \end{multline*} we see that since there are $O(n^4)$ choices for $n_0,\ldots,n_4$ we have \beq{bound} \Pr(\exists \text{ a homomorphism from $G_{n,\frac4n}$ to $C_5$})\leq e^{o(n)}\brac{\max_{\substack{\a_0+\cdots+\a_3\leq 0.94\\\a_0,\ldots,\a_3\geq 0.06}}b(4,\al_0,\al_1,\al_2,\al_3)}^n. \eeq In the next section, we describe a numerical procedure for verifying that the maximum in \eqref{bound} is less than 1. This will complete the proof of Theorem \ref{t.l4}. \section{Bounding the function.} Our aim now is to bound the partial derivatives of $b(4.0,\al_0,\al_1,\al_2,\al_3)$, to translate numerical computations of the function on a grid to a rigorous upper bound. Before doing this we verify that w.h.p. $G_{n,p=\frac4 n}$ has no independent set $S$ of size $s=3n/5$ or more. Indeed, $$\Pr(\exists S)\leq 2^n(1-p)^{\binom{s}{2}}\leq 2^ne^{-18n/25}e^{12/5}=o(1).$$ In the calculations below we will make use of the following bounds: They assume that $0.06\leq \a_i\leq 0.6$ for $i\geq 0$. $$\log(\a_i)>-2.82;\quad-1.31<\log(e^{4\a_i}-1)<2.31;\quad\frac{e^{4\a_i}}{e^{4\a_i}-1}<4.69$$ $$\frac{1}{e^{4\a_i}-1}<3.69;\quad\log(e^{\al_3/\al_2+4\al_3}-1)>-0.91;\quad\frac{1+4\al_2}{e^{\al_3/\al_2}e^{4\al_3}-1}<8.40.$$ We now use these estimates to bound the absolute values of the $\frac{1}{b}\cdot\frac {\partial b}{\partial \al_i}$. Our target value for these is 30. We will be well within these bounds except for $i=2$ Taking logarithms to differentiate with respect to $\al_0$, we find \begin{multline} \frac {\partial b}{\partial \al_0}=b(c,\al_0,\al_1,\al_2,\al_3)\times \\ \left(c\left(-\al_0+\al_1+\frac{\al_1}{e^{\al_0 c}-1}+\al_4\right) -\log (\al_0)+\log (\al_4)-\log(e^{\al_3 c}-1)\right). \end{multline} In particular, for $c=4$, \begin{align*} \frac{1}{b}\cdot\frac {\partial b}{\partial \al_0}&\geq-4\a_0+\log(\a_4)-\log(e^{4\a_3}-1)>-2.4-2.82-2.31,\\ \frac{1}{b}\cdot\frac {\partial b}{\partial \al_0}&\leq4\brac{\a_1+\frac{\al_1}{e^{\al_0 c}-1}+\al_4}-\log(\a_0)-\log(e^{4\a_3}-1)<4\times 4.69+2.82+1.31. \end{align*} % Similarly, we find \begin{multline} \frac {\partial b}{\partial \al_1}=b(c,\al_0,\al_1,\al_2,\al_3)\times\\ \left(c\left(-\al_0+\al_2+\frac{\al_2}{e^{\al_1 c}-1}\right) -\log (\al_1)+\log (\al_4)+\log\bfrac{e^{\al_0 c}-1}{e^{\al_3 c}-1}\right), \end{multline} and so for $c=4$, \begin{align*} \frac{1}{b}\cdot\frac {\partial b}{\partial \al_1}&\geq-4\a_0+\log(\a_4)+\log(e^{4\a_0}-1)-\log(e^{4\a_3}-1)>-2.4-2.82-3.62,\\ \frac{1}{b}\cdot\frac {\partial b}{\partial \al_1}&\leq4\brac{\a_2+\frac{\al_2}{e^{4\al_1}-1}}-\log(\a_1)-\log(e^{4\a_3}-1)<2.4\times 4.69+2.82+1.31. \end{align*} % We next find that \begin{multline} \frac {\partial b}{\partial \al_2}=b(c,\al_0,\al_1,\al_2,\al_3)\times\\ c\left(-\al_0+\al_3+\frac{\al_3}{e^{\al_2 c}-1}\right)-\frac{\al_3/\al_2}{e^{\al_3/\al_2+c\al_3}-1}+\\\log\al_4-\log \al_2 +\log(e^{\al_1 c}-1)-\log(e^{\al_3 c}-1)-\frac {\al_3}{\al_2}-c\al_3-\log(e^{\al_3/\al_2+c \al_3}-1); \old{= \log\left(\frac{\al_4\al_1 }{\al_2 \al_3^2 c + \al_3^2}\right)-\frac{\al_3/\al_2}{e^{\al_3/\al_2+c\al_3}-1} +\ee(c(K+1))} \end{multline} and so for $c=4$, \begin{align*} \frac{1}{b}\cdot\frac {\partial b}{\partial \al_2}\geq&-4\a_0-\frac{\al_3}{\al_2}\frac{e^{\al_3/\al_2+c\al_3}}{e^{\al_3/\al_2+c\al_3}-1}-\log(e^{\al_3/\al_2+c \al_3}-1)+\log(\a_4)+\log\bfrac{e^{4\a_1}-1}{e^{4\a_3}-1}\\ \noalign{We need to be a little careful here. Now $\a_3/\a_2\leq 10$ and if $\a_3/\a_2\geq 9$ then $\a_3\geq 0.54$ and then $\a_i\leq 0.46-3\times.06=0.28$ for $i\neq 3$. We bound $-\frac{1}{b}\cdot\frac {\partial b}{\partial \al_i}$ for both possibilities. Continuing we get} \frac{\a_3}{\a_2}\geq 9:&\frac{1}{b}\cdot\frac {\partial b}{\partial \al_2}>-1.12-10.01-12.4-2.82-3.62=-29.97,\\ \frac{\a_3}{\a_2}\leq 9:&\frac{1}{b}\cdot\frac {\partial b}{\partial \al_2}>-2.4-9.01-11.4-2.82-3.62,\\ \frac{1}{b}\cdot\frac {\partial b}{\partial \al_2} &\leq 4\brac{\a_3+\frac{\al_3}{e^{4\al_2}-1}}-\log(\a_2)+\log\bfrac{e^{4\a_1}-1}{e^{4\a_3}-1}-\log(e^{\al_3/\al_2+c \al_3}-1)\\ &< 2.4\times 3.69+2.82+3.62+0.91. \end{align*} % Finally, we find that \begin{multline} \frac {\partial b}{\partial \al_3}=b(c,\al_0,\al_1,\al_2,\al_3)\times\\ c\left(-\al_0+\al_4\frac{e^{c \al_3}}{e^{c \al_3}-1}\right)+\frac{1+c \al_2}{e^{\al_3/\al_2}e^{c \al_3}-1}+\log(\al_4)-\log(\al_3)+\log\bfrac{e^{\al_2 c}-1}{e^{\al_3 c}-1} \end{multline} and so for $c=4$ \begin{align*} \frac1b\cdot\frac {\partial b}{\partial \al_3}&\geq-4\a_0+\log(\a_4) +\log(e^{4\al_2}-1)-\log(e^{4\al_3}-1)>-2.4-2.82-3.62,\\ \frac1b\cdot\frac {\partial b}{\partial \al_3}&\leq 4\al_4\frac{e^{4\al_3}}{e^{4\al_3}-1}+\frac{1+4\al_2}{e^{\al_3/\al_2}e^{4 \al_3}-1}-\log(\a_3)+\log\bfrac{e^{4\al_2}-1}{e^{4\al_3}-1}\\ &<2.4\times 4.69+8.40+2.82+3.62. \end{align*} \newcommand{\bal}{\boldsymbol\alpha} We see that $|\frac1b\cdot\frac{\partial b}{\partial \al_i}|<30$ for all $0\leq i\leq 3$. Thus, if we know that $b(c,\al_0,\al_1,\al_2,\al_3)\leq B$ for some $B$, this means that we can bound $b(4,\al_0,\al_1,\al_2,\al_3)<\rho$ by checking that $b(4,\al_0,\al_1,\al_2,\al_3)<\rho-\ep$ on a grid with step-size $\delta\leq \ep/(2\cdot B\cdot 30)$. The C++ program in Appendix \ref{code} checks that $b(4,\al_0,\al_1,\al_2,\al_3)<.949$ on a grid with step-size $\delta=.0008$ (it completes in around an hour or less on a standard desktop computer, and is available for download from the authors' websites). Suppose now that $B\geq 1$ is the supremum of $b(4,\al_0,\al_1,\al_2,\al_3)$ in the region of interest. For $\ep=60 \delta B=0.048B$, we must have at some $\delta$-grid point that $b(4,\al_0,\al_1,\al_2,\al_3)\geq B-\ep=.962B\geq .962$. This contradicts the computer-assisted bound of $<.949$ on the grid, completing the proof of Theorem \ref{t.l4}.\qed \subsection*{Acknowledgement} We thank the anonymous referee for a timely and useful pair of reviews. \begin{thebibliography}{99} \bibitem{AcFr} D.~Achlioptas and E.~Friedgut, A sharp threshold for $k$-colorability, {\em Random Structures and Algorithms} 14 (1999) 63-70. \bibitem{AM} D.~Achlioptas and C. Moore, Almost all Graphs with Average Degree 4 are 3-colorable, {\em Journal of Computer and System Science} 67 (2003) 441-471. \bibitem{AN} D. Achlioptas and A. Naor, The two possible values of the chromatic number of a random graph, {\em Annals of Mathematics} 162 (2005), 1333-1349. \bibitem{AFP} J. Aronson, A. Frieze and B. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, {\em Random Structures and Algorithms} {\bf 12} (1998), 111-178. \bibitem{Boll} B. Bollob\'as, A probabilistic proof of an asymptotic formula for the number of labeled graphs, {\em European Journal on Combinatorics} 1(1980) 311-316. \bibitem{B85} B. Bollob\'as, Random Graphs, First Edition, Academic Press, London 1985, Second Edition, Cambridge University Press, 2001. \bibitem{Fried} E. Friedgut, Sharp Thresholds of Graph Properties, and the $k$-sat Problem, {\em Journal of the American Mathematical Society} 12 (1999) 1017-1054. \bibitem{Hat} H. Hatami, Random cubic graphs are not homomorphic to the cycle of size 7, {\em Journal of Combinatorial Theory B} 93 (2005) 319-325. \bibitem{JLR00} S. Janson, M.J. Luczak and A. Ruci\'nski, Random Graphs, John Wiley and Sons, New York, 2000. \bibitem{Lu} T. {\L}uczak, A note on the sharp concentration of the chromatic number of random graphs, {\em Combinatorica} 11 (1991) 295-297. \bibitem{Pit} B. Pittel, On Tree Census and the Giant Component in Sparse Random Graphs, {\em Random Structures and Algorithms} 1 (1990) 311-342. \bibitem{zhu} X. Zhu, Circular chromatic number: a survey, {\em Discrete Mathematics} 229 (2001) 371--410. \end{thebibliography} \newpage \appendix \section{C++ code to check function bound} \label{code} \vspace*{-\baselineskip} \begin{verbatim} #include #include #include using namespace std; int main(int argc, char* argv[]){ double delta=.0008; //step size double maxIndSet=.6; //no independent sets larger than this fraction double minClass=.06; //all color classes larger than this fraction double val=0; double maxval=0; double maxa0,maxa1,maxa2,maxa3; //to record the coordinates of max value maxa0=maxa1=maxa2=maxa3=0; double A23,A,B,C; //For precomputing parts of the function double c=4; for (double a3=minClass; a3 + 4*minClass<1; a3+=delta){ B=exp(c*a3)-1; for (double a2=minClass; a3 + a2 + 3*minClass<1; a2+=delta){ A23=1/(pow(a2,a2)*pow(a3,a3)) * exp(-c/2) * pow(exp(c*a2)-1,a3) * pow(1-exp(-a3/a2)*exp(-c*a3),a2); for (double a1=minClass; a3+a1maxval){ maxval=val; maxa0=a0; maxa1=a1; maxa2=a2; maxa3=a3; } } } } } cout << "Max is "<