Orientability thresholds for random hypergraphs
arXiv:1009.5489 · doi:10.1017/S096354831400073X
Abstract
Let be two fixed integers. Let $\orH$ be a random hypergraph whose hyperedges are all of cardinality . To {\em -orient} a hyperedge, we assign exactly of its vertices positive signs with respect to the hyperedge, and the rest negative. A -orientation of $\orH$ consists of a -orientation of all hyperedges of $\orH$, such that each vertex receives at most positive signs from its incident hyperedges. When is large enough, we determine the threshold of the existence of a -orientation of a random hypergraph. The -orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when and , was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, which settled a conjecture of Karp and Saks.
47 pages, 1 figures, the journal version of [16]