\documentclass[12pt]{article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R19\hfill}
\thispagestyle{empty}
\usepackage{amsmath,latexsym}
\oddsidemargin 0pt % Left margin on odd-numbered pages.
\evensidemargin 0pt % Left margin on even-numbered pages.
\marginparwidth 40pt % Width of marginal notes.
\marginparsep 10pt % Horizontal space between outer margin and
% marginal note
% VERTICAL SPACING:
\topmargin 0pt % Nominal distance from top of page to top of
% box containing running head.
\headsep 20pt % Space between running head and text.
% DIMENSION OF TEXT:
\textheight 8.5in %Height of text(including footnotes and figures,
% excluding running head and foot).
\textwidth 6in % Width of text line.
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\la{\lambda}
\def\K{\Kappa}
\def\z{\zeta}
\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\gp{G_{n,p}}
\def\whp{{\bf whp}}
\def\whps{{\bf whp } }
\def\cE{{\cal E}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{ack}{Acknowledgment} \renewcommand{\theack}{}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{problem}[lemma]{Problem}
\newtheorem{fact}[lemma]{Fact}
\newtheorem{observation}[lemma]{Observation}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{remark}[lemma]{Remark}
\def\gk{{\overline{G}}}
\newcommand{\qed}{$\Box$\medskip}
\newcommand{\comment}[1]{}
\renewcommand{\baselinestretch}{1.3}
\newcommand{\ratio}[2]{\mbox{$\frac{#1}{#2}$}}
\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\begin{document}
\makeatletter
\title{A Note on Sparse Random Graphs and Cover Graphs\thanks{Keywords:
random graph, cover graph, poset
\hfil\break\indent Proposed running head:
Sparse Cover Graphs\hfil\break\indent 1991 Mathematics Subject
Classification: 05C80, 06A07}}
\author {
Tom Bohman\thanks{Supported in part by NSF Grant DMS-9627408.}
\and
Alan Frieze\thanks{Supported in part by NSF grant CCR-9530974.}
\and
Mikl\'os Ruszink\'o\thanks{Permanent Address
Computer and Automation Research Institute of the Hungarian Academy of
Sciences, Budapest, P.O.Box 63, Hungary-1518. Supported in part by
OTKA Grants T 030059 and T 29074 FKFP 0607/1999.}
\and
Lubos Thoma\thanks{Supported in part by
NSF grant DMS-9970622.}
\\
Department of Mathematical Sciences\\ Carnegie Mellon University\\
Pittsburgh, PA 15213, USA\\
{\small\texttt{tbohman@andrew.cmu.edu}},\
{\small\texttt{alan@random.math.cmu.edu}}\\
{\small\texttt{ruszinko@andrew.cmu.edu}},\
{\small\texttt{thoma@qwes.math.cmu.edu}}\\
Submitted: December, 1999; Accepted: March 24, 2000. }
\date{}
\maketitle
\makeatother
\begin{abstract}
{It is shown in this note that with high probability it is enough to
destroy all triangles in order to get a cover graph from a random graph
$G_{n,p}$
with $p\le \k\log n/n$ for any constant $\k<2/3$. On the other hand, this
is not true for
somewhat higher densities: If
$p\ge \lambda (\log n)^3 / (n\log\log n)$ with $\lambda > 1/8$
then with high probability we need to delete more
edges than one from every triangle. Our result has a natural algorithmic
interpretation.}
\end{abstract}
\section{Cover Graphs}
The (Hasse) diagram of the finite poset ${\cal P}=(V,\prec)$ is the
directed graph $\vec G=(V,A)$, where $(u,v)\in A$ iff $u\prec v$ and
there is no $z\in V$ such that $u\prec z\prec v$. The finite
undirected graph $G=(V,E)$ is a {\em cover} graph iff there exists an
orientation of its edges $\vec E$ such that $\vec G=(V,\vec E)$ is a
diagram of some poset ${\cal P}=(V,\prec)$. Clearly, $\vec G=(V,A)$ is
the diagram of a poset iff it contains no directed cycles and no directed
quasicycles. A directed {\it quasicycle} is a cycle with oriented edges
in which the reversal of the orientation of a single edge creates
a directed cycle.
The relationship between cover graphs
and graph parameters has been investigated in several papers.
B. Descartes \cite{D47} (as noted in \cite{B77}) showed
that there are cover graphs with arbitrarily large chromatic number
and this was strenghtened by B. Bollob\'as \cite{B77} who showed that
for every integer $k$ there is a lattice whose
diagram has chromatic number at least $k$.
Furthermore, it was proved by Ne\v set\v ril
and R\"odl \cite{NR78} that there exist graphs which are not cover
graphs and have arbitrarily large girth.
The triangle is not a cover graph, since every orientation of
its edges results in either a directed cycle or quasicycle. However, after
deleting
an edge from it, we get a path of length two, which is
already a cover graph. Obviously, if we delete sufficiently many edges
from an arbitrary graph $G$ it will become a cover graph. Therefore,
it is reasonable to ask, what is the minimum number $c(G)$ such that
after deleting $c(G)$ edges from $G$ it will be a cover graph. This
parameter was introduced by Bollob\'as, Brightwell, and Ne{\v s}et{\v r}il
\cite{BBN86}.
First consider dense random graphs.
It is shown in \cite{BBN86} that for arbitrary
integer $l\ge 2$ and
$\displaystyle{p=p(n)=o\left(n^{(l-2)/(l-1)}\right)}$,
$c(G_{n,p})\le (1+\delta)pn^2/2l$ \whp\footnote{A sequence of events
$\cE_n$ occurs {\em with high probability,} \whp, if $\Pr(\cE_n)=1-o(1)$
as $n\to\infty$}.
Moreover, if $\displaystyle{p=p(n)=n^{-1+\eta (n)}}$, where $0<
\eta_0\le\eta (n)\le 1$, then
\whps one needs to delete a positive proportion of edges from $G_{n,p}$ in
order
to get a cover graph. The auhors of \cite{BBN86} also
conjectured that if $pn^{(l-2)/(l-1)}\to 0$ and
$pn^{(l-1)/l}\to\infty,$ then their upper bound gives the right
constant, i.e., \whp\ $c(G_{n,p})\sim pn^2/2l.$ This has been
recently proved by R\"odl and Thoma \cite{RT99}.
For sparse random graphs, the authors of \cite{BBN86} show that \whp\
$c(\gp) = o(e(\gp))$. Namely they prove the following two bounds.
For every $c\ge 1$ there is a $b, b > c\log(1+b),$ such that if
$p = p(n) \le \frac{c\log n}{n},$ then $c(\gp) \le \frac{pn^2}{2}\cdot
\frac{b}{c\log n}$. Further, for every $\delta>0$ and for every function
$\omega = \omega(n),$ with $\omega \to\infty$ and $\omega = o(n^{\nu})$
for every $\nu>0,$ if $p = p(n)\le \frac{\omega\log n}{n},$ then
$c(\gp)\le (1+\delta) \cdot\frac{pn^2}{2}\cdot\frac{\log\omega}{\log n}$.
For a graph $G$ let $\t(G)$ denote the
minimum number of edges that must be deleted in order to get a
triangle-free graph.
In this note we focus on the graph property $c(G) = \tau(G)$.
Since a cover graph may contain no
triangles $\t(G)\le c(G)$ always holds.
We will show in this note, that for any constant $\k< 2/3$ and $p\le \k\log
n/n$,
$c(\gp) = \t(\gp)$ \whp\ (Theorem~\ref{th1}) while for any constant
$\l>1/8$ and
$p\ge \l(\log n)^3/(n\log\log n), $
$c(\gp) > \t(\gp)$ \whp\ (Theorem~\ref{th2}).
We may interpret our results in an algorithmic way.
Consider a simple algorithm which takes a graph $G$ as input and
deletes edges in copies of triangles as long as $G$ is not triangle-free.
Then Theorem \ref{th1} implies that if the algorithm takes as input
$\gp, p\le \k\log n/n$ for a constant $\k<2/3,$ then it outputs a cover
graph \whp.
Note that the output graph will have \whps girth equal to $4$.
On a related note we point to \cite{P91}
which surveys constructions of non cover graphs with a given girth.
It is an open problem to construct small examples of non cover graphs
with girth greater then $4$.
We will prove the following theorems:
\begin{theorem}\label{th1}
If $\k< 2/3$ is constant and $p\le \k\log n/n$ then $c(G)=\t(G)$ \whp.
\end{theorem}
\begin{theorem} \label{th2}
If $\l>1/8$ is constant and $p\geq \l(\log n)^3/(n\log\log n)$ then
$c(\gp)>\t(\gp)$ \whp.
\end{theorem}
For $p=c/n$, $c$ constant we know that the distribution of the
number of triangles in $G_{n,p}$
is asymptotically Poisson with mean $c^3/6$, \cite{ER}. So as an immediate
corollary we get that if $p=c_n/n$ then
\begin{corollary}
$$\lim_{n\to\infty}\Pr(G_{n,p}\mbox{ is a cover graph})=
\left\{\begin{array}{ll}1&c_n\to-\infty\\e^{-c^3/6}&c_n\to c\\0&c_n\to\infty
\end{array}\right.$$
\end{corollary}
Theorem \ref{th2} follows from the following stronger theorem:
\begin{theorem}\label{th3}
Suppose $\l>1/8$ is constant and $p\geq \l(\log n)^3/(n\log\log n)$ and
$g\leq \frac{\log n}{4\log\log n}$. Let $H$
be obtained from $\gp$ by deleting all vertices which lie on a cycle of
length at most $g$.
Then \whp\ $H$ is not a cover graph.
\end{theorem}
\begin{remark}
{\rm
Part of the results of \cite{RT99} is based on a detailed analysis of the
expansion
properties of the random graph $\gp$. Using the same analysis
of the expansion properties provides the same bound on $p$ in Theorem
\ref{th3}.
}
\end{remark}
\section{Triangle-free graphs: proof of Theorem \ref{th1}}
We will need the following lemma. Let $\chi=\chi(G)$ be the chromatic
number of $G$. We will call a cycle of $G$ {\em short} if it contains $\le
\chi (G)$ vertices and {\em long} otherwise. As usual the distance between
two sets $V_1$ and $V_2$ of
vertices in $G$ is the length of the shortest path between $u\in V_1$
and $v\in V_2$.
\begin{lemma}\label{lem1}
Let $G$ having the following properties:
\begin{description}
\item[(a)] The distance between any two short cycles is at least $\chi +1$.
\item[(b)] No short cycle shares an edge with a cycle of length $\leq 2\chi$.
\end{description}
Then $c(G)=\t(G)$.
\end{lemma}
\proofstart Let $G^\prime= (V,E^\prime)$ be a triangle-free subgraph of
$G$ which we get after deleting one edge of each triangle of $G$.
Let $V_1,\dots ,V_\chi$ be a proper coloring of $G^\prime$ with $\chi$
colours. Define the orientation ${\vec{G^\prime}}= (V,{\vec{E^\prime}})$
as follows. If $u\in V_i$, $v\in V_j$ and $i