Portal de Periódicos da CAPES

The Final Size of the C 4 -Free Process

2011; Cambridge University Press; Volume: 20; Issue: 6 Linguagem: Inglês

10.1017/s0963548311000368

1469-2163

Michael E. Picollelli,

Advanced Graph Theory Research

We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of C 4 . We show that, with probability tending to 1 as n → ∞, the final graph produced by this process has maximum degree O (( n log n ) 1/3 ) and consequently size O ( n 4/3 (log n ) 1/3 ), which are sharp up to constants. This confirms conjectures of Bohman and Keevash and of Osthus and Taraz, and improves upon previous bounds due to Bollobás and Riordan and Osthus and Taraz.