Integer and fractional packings in dense 3‐uniform hypergraphs
Integer and fractional packings in dense 3‐uniform hypergraphs
复制标题
稠密 3 均匀超图中的整数和分数堆积
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
P. Haxell;B. Nagle;V. Rödl
让？0是任何固定的3一致超图。对于一个3一致超图，我们定义ν？ 0（整数）是的一组成对三重不相交副本的最大大小？0在中国。我们说一个函数从集合的副本？0在整数到[0，1]中是分数吗？如果∑？e对于每个三重e，都≤ 1。那么v呢？ 0*（∑）定义为∑？∈（？ 0）（？）在所有的分数？0个包装的包装盒。我们证明了ν？ 0*（）− ν？ 0（0）= 0（|V（V）|3）对于所有的3-一致超图，这扩展了由Haxell和Rödl（2001）证明的图的类似结果，并且需要大量关于3一致超图的正则性的新理论。特别是，我们证明了一个结果，我们称之为扩展定理。这表明如果一个k部3一致超图是正则的[在Frankl和Rödl（2002）的超图正则引理的意义上]，那么几乎每个三元组都是在K k（3）（具有k个顶点的完全3一致超图）的相同数量的副本中。© 2003 Wiley Periodicals，Inc.随机结构算法，22：248-310，2003
Let ?0 be any fixed 3‐uniform hypergraph. For a 3‐uniform hypergraph ℋ︁ we define ν ? 0 (ℋ︁) to be the maximum size of a set of pairwise triple‐disjoint copies of ?0 in ℋ︁. We say a function ψ from the set of copies of ?0 in ℋ︁ to [0, 1] is a fractional ?0‐packing of ℋ︁ if ∑?∋e ψ(?) ≤ 1 for every triple e of ℋ︁. Then ν ? 0* (ℋ︁) is defined to be the maximum value of ∑ ?∈( ? 0ℋ︁) ψ(?) over all fractional ?0‐packings ψ of ℋ︁. We show that ν ? 0* (ℋ︁) − ν ? 0 (ℋ︁) = o(|V(ℋ︁)| 3) for all 3‐uniform hypergraphs ℋ︁. This extends the analogous result for graphs, proved by Haxell and Rödl (2001), and requires a significant amount of new theory about regularity of 3‐uniform hypergraphs. In particular, we prove a result that we call the Extension Theorem. This states that if a k‐partite 3‐uniform hypergraph is regular [in the sense of the hypergraph regularity lemma of Frankl and Rödl (2002)], then almost every triple is in about the same number of copies of K k(3) (the complete 3‐uniform hypergraph with k vertices). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 248–310, 2003