Avoiding anti-monotone graph properties in a random graph

Let us call a property \( P\) of graphs anti-monotone if deleting edges always preserves property \( P\).

Problem (proposed by Erdös, Suen, and Winkler [1])
Start with \(n\) vertices and add edges one by one at random, subject to the condition that the anti-monotone property P continues to hold. Stop when no more edges can be added. How many edges can such a graph have?

The cases when \( P\) denotes "triangle-free", "bipartite", or "disconnected" were considered by Erdös, Suen and Winkler [1].

The property "maximum degree bounded by \( k\)" was examined by Rucínski and Wormald [2].

The case when \( P\) denotes"planar'' was considered by Gerke, Schlatter, Steger, and Taraz [3]

The cases when \( P\) denotes "\( C_4\)-free" and "\( K_4\)-free were examined by Bollobás and Riordan [4].

The more general case of "\( H\)-free", where \( H\) is a graph obeying certain density conditions (including the cases \( H\) is a cycle or \( K_r\)), was explored by Osthus and Taraz [5].


Bibliography
1 P. Erdös, S. Suen and P. Winkler, On the size of a random maximal graph, Random Structures and Algorithms 6 (1995), 309-318.
2 A. Rucínski and N. C. Wormald, Random graph processes with degree restrictions, Combinatorics, Probability and Computing 1 (1992), 169-180.
3 S. Gerke, The random planar graph process. Random structures and algorithms. 32(2)(2008) ,236-.
4 B Bollobas and O Riordan, Constrained graph processes ,The Electronic Journal of Combinatorics, 2000
5 D Osthus, Anusch Taraz, Random maximal H-free graphs, Random Structures and Algorithms 18 (1) (2000) 61 - 82