ASYMPTOTIC-BEHAVIOR OF THE CHROMATIC INDEX FOR HYPERGRAPHS
ASYMPTOTIC-BEHAVIOR OF THE CHROMATIC INDEX FOR HYPERGRAPHS
复制标题
DOI：
10.1016/0097-3165(89)90074-5
复制
发表时间：
1989-05-01
影响因子：
1.1
通讯作者：
SPENCER, J
中科院分区：
文献类型：
--
作者：
PIPPENGER, N;SPENCER, J
我们证明了：如果一个超图集合（1）是一致的（对于某个固定的k，每条边恰好包含k个顶点），（2）最小度渐近于最大度，（3）最大余度（包含一对顶点的边的数目）渐近于最大度，则色指数渐近于最大度.这意味着边可以被划分为填充（或匹配），几乎所有的填充都是几乎完美的。我们还表明，边缘可以划分成覆盖，几乎所有的覆盖都是几乎完美的。这个结果加强和推广了Frankl和Rödl关于在类似情况下存在一个几乎完美填充或覆盖的结果。特别是，它表明，色指数的施泰纳三重系统的n点是渐近n 2，解决了一个长期存在的猜想。
We show that if a collection of hypergraphs (1) is uniform (every edge contains exactly k vertices, for some fixed k),(2) has minimum degree asymptotic to the maximum degree, and (3) has maximum codegree (the number of edges containing a pair of vertices) asymptotically negligible compared with the maximum degree, then the chromatic index is asymptotic to the maximum degree. This means that the edges can be partitioned into packings (or matchings), almost all of which are almost perfect. We also show that the edges can be partitioned into coverings, almost all of which are almost perfect. The result strengthens and generalizes a result due to Frankl and Rödl concerning the existence of a single almost perfect packing or covering under similar circumstances. In particular, it shows that the chromatic index of a Steiner triple-system on n points is asymptotic to n 2, resolving a long-standing conjecture.