Lower bounds for the size of random maximal \(H\)-free graphs (Q1010905)

Summary: We consider the following random process for generating a maximal \(H\)-free graph: Given a fixed graph \(H\) and an integer \(n\), start by taking a uniformly random permutation of the edges of the complete \(n\)-vertex graph \(K_n\). Then, traverse the edges of \(K_n\) according to the order imposed by the permutation and add each traversed edge to an (initially empty) evolving \(n\)-vertex graph - unless its addition creates a copy of \(H\). The result of this process is a maximal \(H\)-free graph \({\mathbb M}_n(H)\). [This process was introduced by \textit{P.Erdős}, \textit{S. Suen}, and {P. Winkler}, ``On the size of a random maximal graph'', Random Struct. Algorithms 6, No.\,2-3, 309--318 (1995; Zbl 0820.05054).] Our main result is a new lower bound on the expected number of edges in \({\mathbb M}_n(H)\), for \(H\) that is regular, strictly 2-balanced. As a corollary, we obtain new lower bounds for Turán numbers of complete, balanced bipartite graphs. Namely, for fixed \(r \geq 5\), we show that ex\((n, K_{r,r}) = \Omega(n^{2-2/(r+1)}(\ln\ln n)^{1/(r^2-1)})\). This improves an old lower bound of \textit{P. Erdős} and \textit{J. Spencer} [Probabilistic methods in combinatorics, Budapest: Akademiai Kiado (1974; Zbl 0308.05001)]. Our result relies on giving a non-trivial lower bound on the probability that a given edge is included in \({\mathbb M}_n(H)\), conditioned on the event that the edge is traversed relatively (but not trivially) early during the process.