Packing and covering tetrahedra
Packing and covering tetrahedra
复制标题
DOI：
10.1016/j.dam.2010.05.027
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
S. Ghosh;P. Haxell
中科院分区：
文献类型：
--
作者：
S. Ghosh;P. Haxell
设H是d-一致超图，在Rd中有几何实现。证明了H的边集C满足完全子超图Kd+1din H的所有副本|C|≤(⌈D2⌉+1)ν(H)，其中ν(H)表示Kd+1din H的一组两两边不相交的副本的最大尺寸。对于d=3，我们还证明了任意3-一致超图上同一命题的两个分式弱化。
Let H be a d-uniform hypergraph that has a geometric realization in Rd. We show that there is a set C of edges of H that meets all copies of the complete subhypergraph Kd+1din H with |C|≤(⌈d2⌉+1)ν(H), where ν(H) denotes the maximum size of a set of pairwise edge-disjoint copies of Kd+1din H. This generalizes a result of Tuza on planar graphs. For d=3 we also prove two fractional weakenings of the same statement for arbitrary 3-uniform hypergraphs.