Almost all Steiner triple systems have perfect matchings

DOI10.1112/PLMS.12373zbMATH Open1462.05045arXiv1611.02246OpenAlexW3100797722MaRDI QIDQ3389173FDOQ3389173

Authors: Matthew Kwan 

Publication date: 10 May 2021

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

Abstract: We show that for any n divisible by 3, almost all order-n Steiner triple systems have a perfect matching (also known as a parallel class or resolution class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. Our methods can also be adapted to other types of designs; for example, we sketch a proof of the theorem that almost all Latin squares have transversals.

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

Recommendations

• Almost all Steiner triple systems are almost resolvable
• Nearly perfect matchings in regular simple hypergraphs
• New bounds for Ryser’s conjecture and related problems
• Threshold for Steiner triple systems
• Counting Steiner triple systems

zbMATH Keywords

3-uniform hypergraphtriangle-decomposition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of block designs (05B05) Orthogonal arrays, Latin squares, Room squares (05B15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Triple systems (05B07)

Cited In (22)

• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• From one to many rainbow Hamiltonian cycles
• Hamilton transversals in random Latin squares
• Dirac-type theorems in random hypergraphs
• Steiner triple systems of order 21 with subsystems
• Covering cycles in sparse graphs
• Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Substructures in Latin squares
• The growth rate of multicolor Ramsey numbers of 3-graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Threshold for Steiner triple systems
• Constructing random Steiner triple systems: an experimental study
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Almost all Steiner triple systems are almost resolvable
• Partitioning problems via random processes
• Enumerating matroids and linear spaces
• Transversals in quasirandom latin squares
• Large deviations in random latin squares
• Packing paths in Steiner triple systems
• New bounds for Ryser’s conjecture and related problems

This page was built for publication: Almost all Steiner triple systems have perfect matchings

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