Triangle‐free subgraphs in the triangle‐free process

Consider the triangle‐free process, which is defined as follows. Start with G (0), an empty graph on n vertices. Given G ( i ‐ 1), let G ( i ) = G ( i ‐ 1) ∪{ g ( i )}, where g ( i ) is an edge that is chosen uniformly at random from the set of edges that are not in G ( i − 1) and can be added to G ( i ‐ 1) without creating a triangle. The process ends once a maximal triangle‐free graph has been created. Let H be a fixed triangle‐free graph and let X H ( i ) count the number of copies of H in G ( i ). We give an asymptotically sharp estimate for ( X H ( i )), for every \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}1 \ll i \le 2^{-5} n^{3/2} \sqrt{\ln n}\end{align*} \end{document} , at the limit as n → ∞ . Moreover, we provide conditions that guarantee that a.a.s. X H ( i ) = 0, and that X H ( i ) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011