Mathematics – Combinatorics
Scientific paper
2011-08-08
Mathematics
Combinatorics
17 pages, 2 figures
Scientific paper
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^{2- \frac{1}{2 \sqrt{2}}+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.
Bohman Tom
Frieze Alan
Lubetzky Eyal
No associations
LandOfFree
Random greedy triangle-packing beyond the 7/4 barrier does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random greedy triangle-packing beyond the 7/4 barrier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random greedy triangle-packing beyond the 7/4 barrier will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-190686