A note on the random greedy triangle-packing algorithm

DOI10.4310/JOC.2010.V1.N4.A5MaRDI QIDQ547873zbMATHOpenAlexFDO

Authors Tom Bohman, Eyal Lubetzky, Alan Frieze

Publication date 27 June 2011

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

triangle-free graphedge removalSteiner triple system

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Triple systems (05B07)

Abstract: The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. We begin with a complete graph on $n$ vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random from the collection of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph. In this note we show that with high probability the number of edges in the final graph is at most $$.

Recommendations

• On random greedy triangle packing
• Random triangle removal
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Large triangle packings and Tuza's conjecture in sparse random graphs
• The triangle-free process

Cited in

(14)

• A natural barrier in random greedy hypergraph matching
• A note on the random greedy independent set algorithm
• Greedy triple systems
• Dynamic concentration of the triangle‐free process
• The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• On the random greedy linear uniform hypergraph packing
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Discrepancy of high-dimensional permutations
• Random triangle removal
• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
• A gentle introduction to the differential equation method and dynamic concentration
• Large girth approximate Steiner triple systems
• The sharp threshold for making squares

This page was built for publication: A note on the random greedy triangle-packing algorithm

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