An upper bound on the number of Steiner triple systems

DOI10.1002/RSA.20487MaRDI QIDQ2868080zbMATHOpenAlexFDO

Authors Nathan Linial, Zur Luria

Publication date 23 December 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.5042

zbMATH Keywords

asymptoticsentropy methodSteiner triple systemscombinatorial enumeration

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Triple systems (05B07)

Abstract: Let STS(n) denote the number of Steiner triple systems on n vertices, and let F(n) denote the number of 1-factorizations of the complete graph on n vertices. We prove the following upper bound. STS(n) <= ((1 + o(1)) (n/e^2))^(n^2/6) F(n) <= ((1 + o(1)) (n/e^2))^(n^2/2) We conjecture that the bound is sharp. Our main tool is the entropy method.

Recommendations

• Counting designs
• Counting Steiner triple systems
• scientific article; zbMATH DE number 4014740
• A new extremal property of Steiner triple-systems
• Threshold for Steiner triple systems

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• A generalisation of \(t\)-designs
• An entropy proof of Bregman's theorem
• An entropy proof of the Kahn-Lovász theorem
• Nonisomorphic Steiner triple systems
• The maximum number of perfect matchings in graphs with a given degree sequence

Cited in

(25)

• Enumerating matroids and linear spaces
• On the number of 1-factorizations of a complete graph
• On the maximum number of Latin transversals
• Enumerating extensions of mutually orthogonal Latin squares
• An Entropy-Based Proof for the Moore Bound for Irregular Graphs
• The number of \(n\)-queens configurations
• Permanents of multidimensional matrices: properties and applications
• Thresholds versus fractional expectation-thresholds
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Counting Steiner triple systems
• Number of 1-factorizations of regular high-degree graphs
• Counting \(r\)-graphs without forbidden configurations
• scientific article; zbMATH DE number 1228449 (Why is no real title available?)
• The number of partial Steiner systems and d-partitions
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Counting designs
• Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• On the numbers of 1-factors and 1-factorizations of hypergraphs
• Efficient, local and symmetric Markov chains that generate one-factorizations
• A proof of Tomescu's graph coloring conjecture
• Smoothed counting of 0–1 points in polyhedra
• Threshold for Steiner triple systems
• On the upper embedding of Steiner triple systems and Latin squares

This page was built for publication: An upper bound on the number of Steiner triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868080)