An upper bound on the number of Steiner triple systems. Issue 4 (5th March 2013)

• Record Type: Journal Article
• Authors: Linial, Nathan; Luria, Zur
• Is Part Of: Random structures & algorithms. Volume 43:Issue 4(2013)
• Page Start: 399
• Page End: 406
• Publication Date: 2013-03-05
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20487
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Richard Wilson conjectured in 1974 the following asymptotic formula for the number of <italic>n</italic> ‐vertex Steiner triple systems:</p> <p> <tex-math notation="LaTeX"><![CDATA[\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}]]></tex-math> <inline-graphic xlink:href="ark:/27927/pgg3qnzxng0" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. Our main result is that <disp-formula content-type="mathematics" id="di-ueqn-2"><alternatives><graphic position="anchor" mimetype="image" xlink:href="ark:/27927/pgg3qnzxnhj" orientation="portrait" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math notation="LaTeX"><![CDATA[\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}]]></tex-math></alternatives></disp-formula></p> <p>The proof is based on the entropy method.</p> <p>As a prelude to this proof we consider the number <italic>F</italic>(<italic>n</italic>) of 1 ‐factorizations of the complete graph on <italic>n</italic> vertices. Using the Kahn‐Lovász theorem it can be shown that <disp-formula content-type="mathematics" id="di-ueqn-3"><alternatives><graphic position="anchor" mimetype="image" xlink:href="ark:/27927/pgg3qnzxnj3" orientation="portrait" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math notation="LaTeX"><![CDATA[\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}]]></tex-math></alternatives></disp-formula> 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</p> </abstract>