Big News: Existence of designs

Vuhavan's Blog

To start, let us introduce Steiner (1796-1863)  system with parameters $latex (n, r, t)$. There is a set of $latex n$ elements, and one would like to find a collection $latex F$ of subsets of size $latex r$ so that every $latex t$-tuple of elements appear in exactly one member of the collection. Since each $latex r$-tuple contains $latex {r \choose t}$ $latex t$-tuples, it is clear that $latex {r \choose t}$ must divide ${n \choose t}$. More generally, for any $latex 0 \le i \le t$,  $latex {r -i \choose t-i}$ must divide $latex {n -i \choose t-i}$ (exercise). Is this necessary divisibility condition sufficient ?

A famous related problem was posted by Kirkman (1850)  known as the “15 school girls problem”: There is a class of 15 students in a private girl school. The girls want to walk in groups of three every day of the week, but…

View original post 1,075 more words

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s