An upper bound on the number of Steiner triple systems

DOI10.1002/RSA.20487zbMATH Open1278.05030arXiv1108.5042OpenAlexW2592640058MaRDI QIDQ2868080FDOQ2868080

Authors: Nathan Linial, Zur Luria 

Publication date: 23 December 2013

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

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.

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

Recommendations

• Counting designs
• Counting Steiner triple systems
• scientific article
• A new extremal property of Steiner triple-systems
• Threshold for Steiner triple systems

zbMATH Keywords

asymptoticsentropy methodSteiner triple systemscombinatorial enumeration

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• An entropy proof of Bregman's theorem
• A generalisation of \(t\)-designs
• The maximum number of perfect matchings in graphs with a given degree sequence
• Nonisomorphic Steiner triple systems
• An entropy proof of the Kahn-Lovász theorem

Cited In (24)

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

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)