Constrainted graph processes (Q1972678)

Summary: Let \(\mathcal Q\) be a monotone decreasing property of graphs \(G\) on \(n\) vertices. \textit{P. Erdős, S. Suen} and \textit{P. Winkler} [Random Struct. Algorithms 6, No. 2-3, 309-318 (1995; Zbl 0820.05054)]\ introduced the following natural way of choosing a random maximal graph in \(\mathcal 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 \mathcal Q\). Stop when there are no such edges, so the graph \(G_\infty\) reached is maximal in \(\mathcal Q\). Erdős, Suen and Winkler asked how many edges the resulting graph typically has, giving good bounds for \(\mathcal Q=\) \{bipartite graphs\} and \(\mathcal 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 \mathcal G(n,p)\). The main technique we use is the `step by step' approach of our paper [(*) Colorings generated by monotone properties, Random Struct. Algorithms 12, No. 1, 1-25 (1998; Zbl 0894.05043)]. 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 (*).