Almost all Steiner triple systems have perfect matchings
From MaRDI portal
Publication:3389173
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)
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.
Recommendations
Cited in
(22)- New bounds for Ryser’s conjecture and related problems
- 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
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)
