The Reverse H-free Process for Strictly 2-Balanced Graphs

被引:5
作者
Makai, Tamas [1 ]
机构
[1] Univ London, Royal Holloway Coll, Egham TW20 0EX, Surrey, England
关键词
random graphs; random graph processes; THRESHOLD FUNCTIONS; ASYMPTOTIC PACKING; DENSE SUBGRAPHS; SIZE;
D O I
10.1002/jgt.21821
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:125 / 144
页数:20
相关论文
共 34 条
[1]   The early evolution of the H-free process [J].
Bohman, Tom ;
Keevash, Peter .
INVENTIONES MATHEMATICAE, 2010, 181 (02) :291-336
[2]   The triangle-free process [J].
Bohman, Tom .
ADVANCES IN MATHEMATICS, 2009, 221 (05) :1653-1677
[3]   THRESHOLD FUNCTIONS FOR SMALL SUBGRAPHS [J].
BOLLOBAS, B .
MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1981, 90 (SEP) :197-206
[4]  
Bollobás B, 2009, BOLYAI SOC MATH STUD, V18, P15
[5]   GRAPH THEORY AND PROBABILITY .2. [J].
ERDOES, P .
CANADIAN JOURNAL OF MATHEMATICS, 1961, 13 (02) :346-&
[6]  
ERDOS P, 1960, B INT STATIST INST, V38, P343
[7]   ON THE SIZE OF A RANDOM MAXIMAL GRAPH [J].
ERDOS, P ;
SUEN, S ;
WINKLER, P .
RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (2-3) :309-318
[8]  
ERDOS P, 1990, RANDOM STRUCT ALGOR, V1, P245
[9]  
Gerke S, 2011, ELECTRON J COMB, V18
[10]  
Janson S, 1998, RANDOM STRUCT ALGOR, V13, P467, DOI 10.1002/(SICI)1098-2418(199810/12)13:3/4<467::AID-RSA15>3.0.CO