
arXiv: 0903.1756
AbstractConsider 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 XH(i) count the number of copies of H in G(i). We give an asymptotically sharp estimate for 𝔼(XH(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. XH(i) = 0, and that XH(i) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
triangle-free process, 05C80, Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), subgraph count, random graph
triangle-free process, 05C80, Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), subgraph count, random graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
