ON THE CHROMATIC INDEX OF RANDOM UNIFORM HYPERGRAPHS

摘要

Let H-(k) (n, N), where k >= 2, be a random hypergraph on the vertex set [n] = {1, 2, ... , n} with N edges drawn independently with replacement from all subsets of [n] of size k. For (d) over bar = kN and any epsilon > 0 we show that if k = o(ln((d) over bar /ln n)) and k = o(ln(n/ln (d) over bar)), then with probability 1 - o(1) a random greedy algorithm produces a proper edge coloring of H-(k) (n, N) with at most (d) over bar (1 + epsilon) colors. This yields the asymptotic chromatic number of the corresponding uniform random intersection graph.