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.