From: Eugene Subject: Steiner Sysrems Date: Wed, 12 Jan 2000 19:13:53 +0200 Newsgroups: sci.math Summary: [missing] Hello, Steiner systems represent special solutions to an extremal set problem – satisfying a condition containing the words “exactly ones” is an extreme case for both “at most one” or “at least one”. I will place two examples for small Steiner triple systems: If I denote STS(a,b,n) as a Steiner system then STS(2,3,n) is called Steiner triple system of order n. Such a triple system does exist if and only if Mod [n,6] = = 1 or 3 Example for STS(7): STS(7) means there is (A,B) such that A = {1,2,3,4,5,6,7} B = {{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}}, then (A,B) is a Steiner triple system because each 2-subsets of 7 set A is contained in exactly one triple of B. Example for STS(9): A = Range[9] B = {{1,2,3},{1,4,7},{1,5,9},{1,6,8},{2,4,9},{2,5,8},{2,6,7},{3,4,8},{3,5,7},{3,6,9},{4,5,6},{7,8,9}} Here is the expression for number of words in STS(a,b,n): | STS(a,b,n) | = n * (n-1) / b * (b-1) *** My question is: Does someone know a recursive way to construct Steiner systems from smaller ones? Thank you for you time. Eugene ============================================================================== From: gmg@maths.may.ie (Gary McGuire) Subject: Steiner Systems Date: 13 Jan 2000 10:29:52 -0500 Newsgroups: sci.math You stated a theorem - that Steiner triple systems on n points exist if and only if n is 1 or 3 mod 6. You ask if there is a recursive construction of Steiner triple systems. The answer is yes. The proof of this theorem uses recursive constructions. It can be found in some books, for example, "A course in combinatorics" by J. H. van Lint and R. M. Wilson (chapter 19). -Gary McGuire ============================================================================== From: Chip Eastham Subject: Non-computer proof of 4 Color Theorem Date: Sat, 14 Oct 2000 00:34:29 GMT Newsgroups: sci.math,alt.math.recreational There is a nicely presented approach to proving the Four Color Theorem without any computer help at the following Yahoo! Geocities Web site: http://www.geocities.com/dharwadker/index.html The hard part of the idea is to show that a planar map requiring N colors implies the existence of a Steiner system S(N+1,2N,6N), and the easy part is that this is impossible for N > 4 because of Tit's inequality on the parameters of a Steiner system. [A Steiner system S(k,v,t) is an organization of k points into v "blocks" such that any t points uniquely determines a block.] I'm no combinatorialist, and in any case the hard part of the proof goes far afield in showing the existence of the Steiner system, but it seems well enough written to repay one's study. Regards, Chip Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Chip Eastham Subject: Re: Non-computer proof of 4 Color Theorem Date: Sun, 15 Oct 2000 16:34:27 GMT Newsgroups: sci.math,alt.math.recreational In article <8sbg8r$la8$1@news8.svr.pol.co.uk>, "martin" wrote: > > > this is impossible for N > 4 because of Tit's > > inequality on the parameters of a Steiner system. > > > Is that really his name? > Sure you don't need Bum's theorem for this? > Yes, really (though I'm not enough of a linguist to know how well the wordplay might translate back into French). The proof is brief enough to give here. Van Lint and Wilson (A Course in Cominatorics, Cambridge Univ. Press, 1992) reference J. Tits (1964), Sur les systemes de Steiner associes aux trois 'grands' groupes de Mathieu, Rend. Math. e Appl. (5) 23, 166- 184, in regard to the following: Thm. 19.5 In any nontrivial Steiner system S(t,k,v): v >= (t + 1)(k - t + 1) Proof: A Steiner system S(t,k,v) consists of v points organized into "blocks" (sets) of size k such that any t points uniquely determines one block containing them. A Steiner system is "trivial" if k = v (all points in one block) or if k = t (the blocks are simply all the subsets of size t). Thus a nontrivial Steiner system has more than one block and k > t. In a nontrivial Steiner system, take t points from one block and another point not in that block. This is a set S of t+1 points not contained in any block (since such a block would share t points with the first block yet be distinct from it by containing the last point). Now there are t+1 subsets T of S of size t, and each determines a unique block B(T) containing T. How many points are in the union over these B(T)? Aside from the t+1 points in S which are surely covered by this union, consider the points in some B(T) that do not belong to S. Since there are t points that do belong to S, there must be exactly k - t points that do not. Further, since distinct blocks B(T),B(T') share t - 1 points in S through their inclusion of T intersect T' they cannot share any other points. Thus the size of the union over the blocks B(T) is: (t+1) points in S + (t+1)(k-t) points not in S The desired inequality then follows: v >= (t + 1)(k - t + 1) QED If we apply this inequality to the Dharwadker's putative Steiner system S(N+1,2N,6N), it tells us that: 6N >= (N + 2)N N^2 - 4N <= 0 This clearly fails for N > 4, so the "easy part" of his proof is easily verified. Regards, Chip Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Chip Eastham Subject: Re: Non-computer proof of 4 Color Theorem Date: Sun, 15 Oct 2000 16:34:27 GMT Newsgroups: sci.math,alt.math.recreational In article <8sbg8r$la8$1@news8.svr.pol.co.uk>, "martin" wrote: > > > this is impossible for N > 4 because of Tit's > > inequality on the parameters of a Steiner system. > > > Is that really his name? > Sure you don't need Bum's theorem for this? > Yes, really (though I'm not enough of a linguist to know how well the wordplay might translate back into French). The proof is brief enough to give here. Van Lint and Wilson (A Course in Cominatorics, Cambridge Univ. Press, 1992) reference J. Tits (1964), Sur les systemes de Steiner associes aux trois 'grands' groupes de Mathieu, Rend. Math. e Appl. (5) 23, 166- 184, in regard to the following: Thm. 19.5 In any nontrivial Steiner system S(t,k,v): v >= (t + 1)(k - t + 1) Proof: A Steiner system S(t,k,v) consists of v points organized into "blocks" (sets) of size k such that any t points uniquely determines one block containing them. A Steiner system is "trivial" if k = v (all points in one block) or if k = t (the blocks are simply all the subsets of size t). Thus a nontrivial Steiner system has more than one block and k > t. In a nontrivial Steiner system, take t points from one block and another point not in that block. This is a set S of t+1 points not contained in any block (since such a block would share t points with the first block yet be distinct from it by containing the last point). Now there are t+1 subsets T of S of size t, and each determines a unique block B(T) containing T. How many points are in the union over these B(T)? Aside from the t+1 points in S which are surely covered by this union, consider the points in some B(T) that do not belong to S. Since there are t points that do belong to S, there must be exactly k - t points that do not. Further, since distinct blocks B(T),B(T') share t - 1 points in S through their inclusion of T intersect T' they cannot share any other points. Thus the size of the union over the blocks B(T) is: (t+1) points in S + (t+1)(k-t) points not in S The desired inequality then follows: v >= (t + 1)(k - t + 1) QED If we apply this inequality to the Dharwadker's putative Steiner system S(N+1,2N,6N), it tells us that: 6N >= (N + 2)N N^2 - 4N <= 0 This clearly fails for N > 4, so the "easy part" of his proof is easily verified. Regards, Chip Sent via Deja.com http://www.deja.com/ Before you buy.