A note on the random greedy triangle-packing algorithm

DOI10.4310/JOC.2010.V1.N4.A5zbMATH Open1244.05213arXiv1004.2418OpenAlexW2963656439MaRDI QIDQ547873FDOQ547873

Authors: Tom Bohman, Eyal Lubetzky, Alan Frieze 

Publication date: 27 June 2011

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

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 $$.

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

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

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)

Cited In (14)

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

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)