Orientation of Random Hypergraphs and the Load Balancing Problem

size $h$. A constant 0<w<h is given. A hyperedge is said to be
w-oriented if exactly w distinct vertices in it are designated
to be positive with respect to the edge, and the rest negative. If
all hyperedges are w-oriented, the indegree of a vertex v is
defined to be the number of edges for which v is positive. A
(w,k)-orientation of H is a w-orientation of all hyperedges
of H, such that each vertex has indegree at most k. Study of the
(w,k)-orientation of a hypergraph is motivated by the general load
balancing problem. Assume that we want to assign m jobs to n
machines, such that each job can be allocated to w out of h
machines chosen randomly from the n machines. How large can m
be so that there exists an allocation such that each machine receives at most $k$ jobs?
For the graph case, namely h=2 and w=1, Cain, Sanders, and Wormald recently showed that the k-orientability threshold of a random graph in G(n,m) coincides with the threshold at which the (k+1)-core has mean degree at most 2k. Fernholz and Ramachandran showed the same result with a more concise proof.

In this talk, we explain why it is hard to extend the method used in the graph case to the hypergraph case. We determine the threshold function f(n) for the (w,k)-orientability of H when k is large enough. The threshold is analogous to the one conjectured by Karp and Saks for the random graph case. We derive the proof for the hypergraph case, which is more complicated, using a completely different approach from the previous work on the graph case.
The analysis consists of two phases. The first phase analyses a randomized algorithm that partially orients H and the second phase proves that with high probability the partial orientation derived from the first phase can be extended to a (w,k)-orientation of H. Our approach also gives a significantly simpler proof for the graph case comparing to the previous ones.