Avoiding anti-monotone graph properties in a random graph
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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?
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 |