An upper bound on the number of Steiner triple systems. Issue 4 (5th March 2013) - Linial, Nathan
Abstract Richard Wilson conjectured in 1974 the following asymptotic formula for the number of n ‐vertex Steiner triple systems: \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*} STS(n) = \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}\end{align*}\end{document} . Our main result is that \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*} STS(n) \leq \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}. \end{align*}\end{document} The proof is based on the entropy method. As a prelude to this proof we consider the number F(n) of 1 ‐factorizations of the complete graph on n vertices. Using the Kahn‐Lovász theorem it can be shown that \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*} F(n) \leq \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{2}}. \end{align*}\end{document} We show how to derive this bound using the entropy method. Both bounds are conjectured to be sharp. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 399–406, 2013