An Upper bound on the number of Steiner triple systems

2011/08/25 by Nathan Linial, Linial, Nathan, Zur Luria +1 · 3 citations
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.1108.5042

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²))^(n²/6) F(n) <= ((1 + o(1)) (n/e²))^(n²/2) We conjecture that the bound is sharp. Our main tool is the entropy method.

Cited by

• Entropy methods in combinatorics
• Parities in random Latin squares
• Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs

Related

• Enumerating Steiner Triple Systems
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Steiner Triple Systems of Order 21 with Subsystems
• Threshold for Steiner triple systems
• Algorithms and Complexity for Counting Configurations in Steiner Triple Systems