Combinatorics Seminar
When: Sunday, May 20, 10am
Where: Schreiber 309
Speaker: Zur Luria, Hebrew University
Title: Upper bounds on the number of Steiner triple
systems and 1-factorizations
Abstract:
A 1-factorization of the complete graph Kn is a partition of its edges
into n-1 perfect matchings. A Steiner triple system on [n] = {1,...,n}
is a collection T of triples such that each pair in [n] is contained in
a unique triple.
We will discuss the connections between these (and other) objects,
and present previously known bounds on their number. We'll show that
the number of 1-factorizations of Kn is at most ((1+o(1)) n/e^2)^(n^2/2)
and that the number of Steiner triple systems on [n] is at most ((1+o(1))
n/e^2)^(n^2/6).
The proofs make use of the entropy method, the basic idea of which is
to estimate the cardinality of a set X by sampling uniformly from that
set and then estimating the entropy of this process using tools from
the field of information entropy.
Joint work with Nati Linial.