\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Guy Wolfovitz}
%
%
\medskip
\noindent
%
%
{\bf Lower Bounds for the Size of Random Maximal $H$-Free Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
We consider the next random process for generating a maximal $H$-free
graph: Given a fixed graph $H$ and an integer $n$, start by taking a
uniformly random permutation of the edges of the complete $n$-vertex
graph $K_n$. Then, traverse the edges of $K_n$ according to the order
imposed by the permutation and add each traversed edge to an (initially
empty) evolving $n$-vertex graph - unless its addition creates a copy of
$H$. The result of this process is a maximal $H$-free graph ${\Bbb M}_n(H)$.
Our main result is a new lower bound on the expected number of edges in
${\Bbb M}_n(H)$, for $H$ that is regular, strictly $2$-balanced.
As a corollary, we obtain new lower bounds for Tur\'{a}n numbers of
complete, balanced bipartite graphs.  Namely, for fixed $r \ge 5$, we
show that ex$(n, K_{r,r}) = \Omega(n^{2-2/(r+1)}(\ln\ln n)^{1/(r^2-1)})$.
This improves an old lower bound of Erd\H{o}s and Spencer.

Our result relies on giving a non-trivial lower bound on the probability
that a given edge is included in ${\Bbb M}_n(H)$, conditioned on the event
that the edge is traversed relatively (but not trivially) early during
the process.

\bye