Paper Info
Title
Random greedy triangle-packing beyond the 7/4 barrier
Abstract
The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. 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 out of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph, and a longstanding open problem is to estimate the final number of edges, or equivalently the time it takes the process to conclude. The intuition that the edge distribution is roughly uniform at all times led to a folklore conjecture that the final number of edges is $n^{3/2+o(1)}$ with high probability, whereas the best known upper bound is $n^{7/4+o(1)}$. It is no coincidence that various methods break precisely at the exponent 7/4 as it corresponds to the inherent barrier where co-degrees become comparable to the variations in their values that arose earlier in the process. In this work we significantly improve upon the previous bounds by establishing that w.h.p. the number of edges in the final graph is at most $ n^{5/3+o(1)} $. Our approach relies on a system of martingales used to control key graph parameters, where the crucial new idea is to harness the self-correcting nature of the process in order to control these parameters well beyond the point where their early variation matches the order of their expectation.
Year
Venue
Keywords
2011
CoRR
steiner triple system,data structure,upper bound,complete graph,stochastic process,greedy algorithm
Field
DocType
Volume
Pseudoforest,Discrete mathematics,Strength of a graph,Random regular graph,Combinatorics,Multigraph,Cycle graph,Multiple edges,Mathematics,Path graph,Complement graph
Journal
abs/1108.1781
Citations 
PageRank 
References 
2
0.40
5
Authors
3
Name
Order
Citations
PageRank
Tom Bohman125033.01
Alan M. Frieze24837787.00
Eyal Lubetzky335528.87