论文标题
四倍体的显式Baranyai分区，第一部分：四倍体结构
Explicit Baranyai Partitions for Quadruples, Part I: Quadrupling Constructions
论文作者
论文摘要
众所周知，每当$ k $划分$ n $时，$ n $顶点上的完整$ k $均匀的超图可以分为脱节的完美匹配。同等地，可以将$ n $ set的$ k $ -subset分配到并行类中，以便每个并行类都是$ n $ set的分区。该结果称为Baranyai定理，它保证存在\ emph {baranyai partitions}。不幸的是，Baranyai定理的证据使用网络流参数，这使得该结果不明确。特别是，没有已知的方法可以在时间和空间中生成与超图中的Hyperedges数量线性缩放的时间和空间分区。希望某些应用具有在线性时间内生成Baranyai分区的明确结构。这种高效的结构以$ k = 2 $而闻名，$ k = 3 $。在本文中，我们提出了$ k = 4 $和$ n = 4t $的明确递归四倍构建，其中$ t \ equiv 0,3,4,6,8,9〜（\ text {mod} 〜12）$。在后续文件（第二部分）中，将考虑〜$ t $的其他值，即$ t \ equiv 1,2,5,7,10,11〜（\ text {mod} 〜12）$。
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 $t \equiv 0,3,4,6,8,9 ~(\text{mod}~12)$. In a follow-up paper (Part II), the other values of~$t$, namely $t \equiv 1,2,5,7,10,11 ~(\text{mod}~12)$, will be considered.
