Title: The existence of designs
Abstract: A Steiner Triple System on a set X is
a collection T of 3-element subsets of X such
that every pair of elements of X is contained
in exactly one of the triples in T. An example
considered by Plücker in 1835 is the affine
plane of order three, which consists of 12
triples on a set of 9 points.
Plücker observed that a necessary condition for
the existence of a Steiner Triple System on a
set with n elements is that n be congruent to
1 or 3 mod 6. In 1846, Kirkman showed that this
necessary condition is also sufficient. In 1853,
Steiner posed the natural generalisation of the
question: given integers q and r, for which n is
it possible to choose a collection Q of q-element
subsets of an n-element set X such that any r
elements of X are contained in exactly one of
the sets in Q?
There are some natural necessary divisibility
conditions generalising the necessary conditions
for Steiner Triple Systems. The Existence
Conjecture states that for all but finitely many
n these divisibility conditions are also sufficient
for the existence of general Steiner systems (and
more generally designs). We prove the Existence
Conjecture, and more generally, we show that the
natural divisibility conditions are sufficient for
clique decompositions of simplicial complexes that
satisfy a certain pseudorandomness condition.