tailieunhanh - Báo cáo toán học: "n Random Greedy Triangle Packing"

OTuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: n Random Greedy Triangle Packing. | On Random Greedy Triangle Packing David A. Grable Institut fur Informatik Humboldt-Universitat zu Berlin D-10099 Berlin Germany Submitted August 5 1996 Accepted February 26 1997 Abstract The behaviour of the random greedy algorithm for constructing a maximal packing of edge-disjoint triangles on n points a maximal partial triple system is analysed with particular emphasis on the final number of unused edges. It is shown that this number is at most n7 4 o 1 halfway from the previous best-known upper bound o n2 to the conjectured value n3 2 o 1 . The more general problem of random greedy packing in hypergraphs is also considered. 1 Introduction Consider the following simple algorithm for constructing a maximal collection of pair-disjoint triples in a set of n points repeatedly pick a triple uniformly at random from among all triples which do not share a pair with any previously picked triple until there are no more candidate triples. It is perhaps mildly surprising that such a simple random greedy procedure almost always results in a collection of triples which cover almost all of the pairs 13 12 . In this paper we obtain significantly tighter bounds on the number of uncovered pairs. In particular we show that the number of uncovered pairs is almost always no more than n7 4 o 1 where o 1 is a function going to 0 as n goes to infinity. This problem is expressed nicely in the language of design theory. A partial triple system on n points a PTS n for short is a collection of 3-element subsets triples of 1 . ng such that each 2-element subset pair is contained in covered by at most one triple. Of considerable interest are partial triple systems in which every pair is covered by exactly one triple. Such systems are called Steiner triple systems. The reader is referred to 3 for more background on design theory. A partial triple system is maximal if no triple can be added without covering some pair more than once. It is obvious but worth noting that Steiner triple systems .