No dense subgraphs appear in the triangle-free graph process

zbMATH Open1229.05249arXiv1002.2316MaRDI QIDQ640423FDOQ640423

Authors: Stefanie Gerke, Tamás Makai 

Publication date: 18 October 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Consider the triangle-free graph process, which starts from the empty graph on $n$ vertices and a random ordering of the possible $nchoose2$ edges; the edges are added in this ordering provided the graph remains triangle free. We will show that there exists a constant $c$ such that no copy of any fixed finite triangle-free graph on $k$ vertices with at least $ck$ edges asymptotically almost surely appears in the triangle-free graph process.

Full work available at URL: https://arxiv.org/abs/1002.2316

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Triangle-free subgraphs in the triangle-free process
• Triangle-free subgraphs of random graphs
• Triangle-free subgraphs of random graphs
• Dense subgraphs in the \(H\)-free process
• On the Structure of Dense Triangle-Free Graphs
• Graphs without large triangle free subgraphs
• On triangle-free random graphs
• Triangle-free graphs without forbidden subgraphs
• On the edge distribution in triangle-free graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cited In (10)

• The \(Q_2\)-free process in the hypercube
• The diamond-free process
• Dense subgraphs in the \(H\)-free process
• Dynamic concentration of the triangle‐free process
• The C_ℓ‐free process
• When does the \(K_{4}\)-free process stop?
• A note on the random greedy independent set algorithm
• Triangle-free subgraphs in the triangle-free process
• The reverse \(H\)-free process for strictly 2-balanced graphs
• A sequence of triangle-free pseudorandom graphs

This page was built for publication: No dense subgraphs appear in the triangle-free graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640423)