Media type: E-Article Title: The diamond‐free process Contributor: Picollelli, Michael E. Published: Wiley, 2014 Published in: Random Structures & Algorithms, 45 (2014) 3, Seite 513-551 Language: English DOI: 10.1002/rsa.20517 ISSN: 1042-9832; 1098-2418 Keywords: Applied Mathematics ; Computer Graphics and Computer-Aided Design ; General Mathematics ; Software Origination: Footnote: Description: <jats:title>Abstract</jats:title><jats:p>Let <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20517-math-0001.gif" xlink:title="urn:x-wiley::media:rsa20517:rsa20517-math-0001" /> denote the diamond graph, formed by removing an edge from the complete graph <jats:italic>K</jats:italic><jats:sub>4</jats:sub>. We consider the following random graph process: starting with <jats:italic>n</jats:italic> isolated vertices, add edges uniformly at random provided no such edge creates a copy of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20517-math-0002.gif" xlink:title="urn:x-wiley::media:rsa20517:rsa20517-math-0002" />. We show that, with probability tending to 1 as <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20517-math-0003.gif" xlink:title="urn:x-wiley::media:rsa20517:rsa20517-math-0003" />, the final size of the graph produced is <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20517-math-0004.gif" xlink:title="urn:x-wiley::media:rsa20517:rsa20517-math-0004" />. Our analysis also suggests that the graph produced after <jats:italic>i</jats:italic> edges are added resembles the uniform random graph, with the additional condition that the edges which do not lie on triangles form a random‐looking subgraph. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 513–551, 2014</jats:p>