Orientability Thresholds for Random Hypergraphs

Source abstract

Let h > w > 0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h . To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative signs. A ( w,k )-orientation of H consists of a w -orientation of all hyperedges of H , such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a ( w,k )-orientation of a random hypergraph. The ( w,k )-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h = 2 and w = 1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran. This settled a conjecture of Karp and Saks.