Combinatorics, Probability and Computing

Paper

The Final Size of the C4-Free Process

MICHAEL E. PICOLLELLIa1

a1 Department of Electrical and Computer Engineering, University of Delaware, Newark, DE, USA (e-mail: mpicolle@udel.edu)

Abstract

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 C4. We show that, with probability tending to 1 as n → ∞, the final graph produced by this process has maximum degree O((nlogn)1/3) and consequently size O(n4/3(logn)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.

(Received October 10 2010)

(Revised August 07 2011)

(Online publication September 05 2011)