Explicit Baranyai partitions for quadruples, Part I: Quadrupling constructions

DOI10.1002/JCD.21776MaRDI QIDQ6145733zbMATH OpenOpenAlexFDO

Authors Yeow Meng Chee, Tuvi Etzion, Han Mao Kiah, Alexander Vardy, Chengmin Wang

Publication date 2 February 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

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

zbMATH Keywords

Baranyai partitionsBaranyai's theoremnear-one-factorizationone-factorization

Mathematics Subject Classification ID

Partitions of sets (05A18) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: It is well known that, whenever $k$ divides $n$, the complete $k$-uniform hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings. Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into parallel classes so that each parallel class is a partition of the $n$-set. This result is known as Baranyai's theorem, which guarantees the existence of emph{Baranyai partitions}. Unfortunately, the proof of Baranyai's theorem uses network flow arguments, making this result non-explicit. In particular, there is no known method to produce Baranyai partitions in time and space that scale linearly with the number of hyperedges in the hypergraph. It is desirable for certain applications to have an explicit construction that generates Baranyai partitions in linear time. Such an efficient construction is known for $k=2$ and $k=3$. In this paper, we present an explicit recursive quadrupling construction for $k=4$ and $n=4t$, where $tequiv0,3,4,6,8,9(extmod12)$. In a follow-up paper (Part II), the other values of~$t$, namely $tequiv1,2,5,7,10,11(extmod12)$, will be considered.

Recommendations

• Some remarks on Baranyai's theorem
• Perfect matching and Hamilton cycle decomposition of complete balanced \(( k + 1 )\)-partite \(k\)-uniform hypergraphs
• scientific article; zbMATH DE number 4174938
• Connected Baranyai's theorem
• Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Cites work

• A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems
• A course in combinatorics.
• A new existence proof for large sets of disjoint Steiner triple systems
• Connected Baranyai's theorem
• Detachments of hypergraphs I: The Berge-Johnson problem
• Enumerative source encoding
• scientific article; zbMATH DE number 3683587 (Why is no real title available?)
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• scientific article; zbMATH DE number 979131 (Why is no real title available?)
• Max flows in O(nm) time, or better
• Maximal Flow Through a Network
• On almost-regular edge colourings of hypergraphs
• On large sets of disjoint Steiner triple systems. I
• On large sets of disjoint Steiner triple systems. IV
• On Quadruple Systems
• Resolvable Steiner Quadruple Systems for the Last 23 Orders
• The existence of resolvable Steiner quadruple systems
• Towards a Large Set of Steiner Quadruple Systems

This page was built for publication: Explicit Baranyai partitions for quadruples, Part I: Quadrupling constructions

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