Triangle-free subgraphs in the triangle-free process

DOI10.1002/RSA.20378MaRDI QIDQ5388974zbMATH OpenOpenAlexFDO

Authors Guy Wolfovitz

Publication date 24 April 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphsubgraph counttriangle-free process

Mathematics Subject Classification ID

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

Abstract: We consider the triangle-free process: given an integer n, start by taking a uniformly random ordering of the edges of the complete n-vertex graph K_n. Then, traverse the ordered edges and add each traversed edge to an (initially empty) evolving graph - unless its addition creates a triangle. We study the evolving graph at around the time where Theta(n^{3/2 + epsilon}) edges have been traversed for any fixed epsilon in (0,10^{-10}). At that time and for any fixed triangle-free graph F, we give an asymptotically tight estimation of the expected number of copies of F in the evolving graph. For F that is balanced and have density smaller than 2 (e.g., for F that is a cycle of length at least 4), our argument also gives a tight concentration result for the number of copies of F in the evolving graph. Our analysis combines Spencer's original branching process approach for analysing the triangle-free process and the semi-random method.

Recommendations

• No dense subgraphs appear in the triangle-free graph process
• Dynamic concentration of the triangle‐free process
• Dynamic concentration of the triangle-free process
• The early evolution of the \(H\)-free process
• The triangle-free process

Cites work

• The early evolution of the \(H\)-free process
• The triangle-free process

Cited in

(16)

• The triangle-free process
• A triangle process on regular graphs
• Packing nearly optimal Ramsey R(3,t) graphs
• The \(Q_2\)-free process in the hypercube
• The sum-free process
• A note on the random greedy independent set algorithm
• The diamond-free process
• Generating random networks without short cycles
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Large girth approximate Steiner triple systems
• The reverse \(H\)-free process for strictly 2-balanced graphs
• When does the \(K_{4}\)-free process stop?
• Dynamic concentration of the triangle-free process
• The C_ℓ‐free process
• Dynamic concentration of the triangle‐free process
• No dense subgraphs appear in the triangle-free graph process

This page was built for publication: Triangle-free subgraphs in the triangle-free process

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