Jan.27 Intro: basic definitions and questions.

Illustrated by Fano plane Pi_2 of 7 "points" and 7 "lines"
(diagram again; get properties from class, including):

-- Each line has _3_ points
-- Any _2_ points on a _unique_ line

That makes it a 2-(7,3,1) design.  In general:

  Def. 1.1 (p.1) A t-design with parameters (v,k,\lam), a.k.a. a
  t-(v,k,\lam) design, is a pair \D = (X,\B) where

    X is a set of v "points"
    B is a collection of k-element "blocks", each a subset of X
    any t points contained in exactly \lam blocks.

  E.g. Pi_2 is also a 1-(7,3,3) design, and Petersen is 1-(10,2,3);
  Trivial example: any collection of b blocks is a 0-(v,k,b) design.
  Is Pi_2 a 3-design?

  Even more trivial: If v<k or k<t then \lam=0 (and if v<t then \lam
  is undefined); we don't care about such examples, nor indeed of the
  example where \lam=0 because \B is empty.

We do care very much about the special case

  \lam=1 (as with Pi_2);

that's a

  _Steiner system_ (a.k.a. S(t,k,v)).

  Aim: describe all designs, up to equivalence.

  That's asking too much!
  
But can be done, with interesting results, for many particular cases,
some of which will appear shortly.  E.g. 2-(7,3,1) is unique.

Gets harder as t increases, with the exception of:

Only slightly less trivial: the set of _all_ Bin(v,k) subsets is
a trivial design: S_v acts transitively on t-element subsets,
so each is contained in the same number (namely Bin(v-t,k-t)).
That's a _complete block design_; we're interested in _incomplete_ ones.
The t-design condition says that the set of blocks is "balanced" among
all elements, pairs, ..., t-subsets.  This is sometimes called a

  BIBD: balanced incomplete block design.
  
  (At least when t>=2 -- t=1 is still too easy to satisfy without
  additional conditions.)

It's harder as t increases because

  Cor. 1.6 (p.3): a t-(v,k,\lam) design is automatically also an
  s-(v,k,\lam_s) design for each s \leq t, with \lam_s given by:

  Prop. 1.4: If S is a subset of X with s = |S| \in [0,t] then
  the number of blocks containing S is

    \lam_s := (Bin(v-s,t-s) / Bin(k-s,t-s)) \lam.
  
  Proof: double count pairs (B,T) where B is a block and
  S \subset T \subset X with |T|=t.

  Cor. 1.7: If a t-(v,k,\lam) design exists then

    Bin(k-s,t-s)  |  Bin(v-s,t-s) \lam
  
  for each s=0,1,...,t-1.

  Example:

    b := \lam_0 = # blocks and
    r := \lam_1 = # blocks containing a given point [if t>0...]
  
  satisfy

    bk=vr.
  
  Likewise if t=2 then we have

    r = (Bin(v-1,1)/Bin(k-1,1)) \lam = (v-1)/(k-1) \lam
  
  so  (v-1)\lam = r(k-1)  [p4, (1.9)].

Even for \lam=1, infinitely many examples known with t=2,3
but only finitely many for 4,5 (we'll see all the "classical" ones)
and none known with 6 or more!

What does "up to equivalence" mean?

  p.3 isomorphism from (X,B) to (X',B'): bijection f: X --> X'
  that takes B to B'.

  Automorphism of (X,B) = isomorphism (X,B) --> (X,B);
  these form a group.

  If G is t-transitive, or even transitive on t-subsets, then
  (X,B) is automatically a t-design.  Many t-designs explained 
  this way, including Pi_2 (and Petersen).

Finally (and a first appearance of linear algebra): why don't we work
with "designs with multiplicity", a.k.a. "t-structures" (see p.1)?
Even the bridges-of-Konigsberg graph has multiplicity...  But again
it's too easy to construct t-structures:

  Prop. 1.2 (p.2): If k \in (t,v-t) then there is a t-(v,k,\lam) structure
  for some \lam, in which not every k-set is incident with a block.

  Proof: more variables than Q-linear equations; clear denominators and
  add the smallest multiple of the all-1's vector.

  [another way to say this: the variables are the multiplicities m_B of the
  Bin(v,k) k-subsets, plus \lam itself; the equations are the Bin(v,t)
  conditions that each t-subset be contained in \lam blocks counted
  with multiplicity; so there's a >1 dimensional space of solutions,
  which includes the vector x_1 where all the m_B equal 1.  Let x_2
  be an independent vector; multiply by a common denominator to get
  all the coordinates of x_2 to be integers; and subtract m*x_1, where
  m is the minimal coordinate m_B of x_2, to get a nonzero solution where
  all the m_B are nonnegative and at least one vanishes.]