On a Hypergraph Matching Problem
On a Hypergraph Matching Problem
复制标题
关于超图匹配问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
N. Alon;R. Yuster
设H=(V，E)是r-一致超图，且H的匹配M是(α，)-完美的，如果对每个F∈，F的至少α|F|点被M覆盖。我们的主要结果是一个定理，给出了r-一致超图有-完美匹配的充分条件。作为我们定理的一个特例，我们得到了如下结果。设K(n，r)表示n个顶点的完全r-一致超图。设t和r是固定的正整数，其中t≥r≥2，则K(n，r)可以被K(t，r)的边不相交的副本所填充，使得每个顶点只与O(nr−1)条未打包的边关联。这推广了Rödl[9]的一个结果。
Let H = (V, E) be an r-uniform hypergraph and let A matching M of H is (α, )-perfect if for each F ∈ , at least α|F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a -perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t≥r≥2. Then, K(n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(nr−1) unpacked edges. This extends a result of Rödl [9].