tailieunhanh - Báo cáo toán học: "5-sparse Steiner Triple Systems of Order n Exist for Almost All Admissible n"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: 5-sparse Steiner Triple Systems of Order n Exist for Almost All Admissible n. | 5-sparse Steiner Triple Systems of Order n Exist for Almost All Admissible n Adam Wolfe Department of Mathematics The Ohio State University Columbus OH USA water@ Submitted Aug 5 2003 Accepted Nov 7 2005 Published Dec 5 2005 Mathematics Subject Classification 05B07 Abstract Steiner triple systems are known to exist for orders n 1 3 mod 6 the admissible orders. There are many known constructions for infinite classes of Steiner triple systems. However Steiner triple systems that lack prescribed configurations are harder to find. This paper gives a proof that the spectrum of orders of 5-sparse Steiner triple systems has arithmetic density 1 as compared to the admissible orders. 1 Background Let v 2 N and let V be a v-set. A Steiner triple system of order v abbreviated STS v is a collection B of 3-sets of V called blocks or triples such that every distinct pair of elements of V lies in exactly one triple of B. An STS v exists exactly when v 1 or 3 mod 6 the admissible orders. Wilson 13 showed that the number of non-isomorphic Steiner triple systems of order n is asymptotically at least e-5n n 6. Much less is known about the existence of Steiner triple systems that avoid certain configurations. An reconfiguration of a system is a set of r distinct triples whose union consists of no more than r 2 points. A Steiner triple system that lacks r-configurations is said to be r-sparse. In other words a Steiner triple system where the union of every r distinct triples has at least r 3 points is r -sparse. In 1976 Paul Erdos conjectured that for any r 1 there exists a constant Nr such that whenever v Nr and v is an admissible order an r-sparse STS v exists 4 . The statement is trivial for r 2 3. For r 4 there is only one type of 4-configuration a Pasch. Paschs have the form a b c a d e f b d f c e 1 Thanks to the editors of this journal for considering this for publication. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R68 1 In this paper Paschs are written .