The Reverse H‐free Process for Strictly 2‐Balanced Graphs |
| |
Authors: | Tamás Makai |
| |
Affiliation: | ROYAL HOLLOWAY COLLEGE, UNIVERSITY of LONDON, EGHAM, UNITED KINGDOM |
| |
Abstract: | Consider the random graph process that starts from the complete graph on n vertices. In every step, the process selects an edge uniformly at random from the set of edges that are in a copy of a fixed graph H and removes it from the graph. The process stops when no more copies of H exist. When H is a strictly 2‐balanced graph we give the exact asymptotics on the number of edges remaining in the graph when the process terminates and investigate some basic properties namely the size of the maximal independent set and the presence of subgraphs. |
| |
Keywords: | random graphs random graph processes |
|
|