\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
 {\bf  B\'ela Bollob\'as and Oliver Riordan}
\medskip
\noindent {\bf Constrained graph processes }

 \vskip.5cm

\noindent 
Let $\cal Q$ be a monotone decreasing property of graphs
$G$ on $n$ vertices.
Erd\H os, Suen and Winkler [5] introduced the following
natural way of choosing a random maximal graph in $\cal Q$:
start with $G$ the empty graph on $n$ vertices.
Add edges to $G$ one at a time, each time choosing
uniformly from all $e\in G^c$ such that $G+e\in \cal Q$.
Stop when there are no such edges, so the graph $G_\infty$
reached is maximal in $\cal Q$.
Erd\H os, Suen and Winkler asked how many edges the resulting
graph typically has, giving good bounds for $\cal Q=\{$%
bipartite graphs$\}$ and $\cal Q=\{$triangle free graphs$\}$.
We answer this question
for $C_4$-free graphs and for $K_4$-free graphs, by considering
a related question about standard random graphs
$G_p\in {\cal G}(n,p)$.


The main technique we use is the `step by step' approach of~[3].
We wish to show that $G_p$ has a certain property with high probability.
For example, for $K_4$ free graphs the property is that
every `large' set $V$ of vertices
contains a triangle not sharing an edge with any $K_4$ in $G_p$.
We would like to apply a standard Martingale inequality, but the
complicated dependence involved is not of the right form.
Instead we examine $G_p$ one step at a time in such a way that the
dependence on what has gone before
can be split into `positive' and `negative' parts, using the notions
of up-sets and down-sets.
The relatively simple positive part is then estimated directly.
The much more complicated negative part can simply be ignored, as shown
in [3].

\bye




.