The threshold of k-orientability in G_{n, m, h}
by
Jane (Pu) Gao
University of Waterloo
Coauthors: Nick Wormald

An instance of the orientation problem of a graph, is to orient every edge of the graph, such that the maximum in-degree of the graph is minimized. If there exists an orientation, such that the maximum in-degree is at most k, then we say that the graph is k-orientable. Fernholz and Ramachandran showed that the k-orientability threshold of a random graph in G_{n, p} coincides with the threshold at which that (k+1)-core has mean degree 2k. Cain, Sanders, and Wormald proved the same threshold in G_{n, m} by analyzing a linear time algorithm that finds a k-orientation. The application of k-orientability problem refers to the off-line load balancing problem. We want to assign m jobs to n machines, such that each machine receives at most k jobs. Each job can be allocated to one of two machines chosen randomly from the n machines. How large m could be so that there exists such an allocation? Naturally, we may consider that the choice is not out of two but from h, such that h is any constant integer. If we consider distributed computation, such that each job is assigned to a few, say w < h machines, then would there exist a threshold such that this generalized problem is k-orientable? In this talk, I will show that this threshold exists, for any given h and w < h, and that k is large enough. The approach, though, is quite different from previous work. We will see that the technique in Fernholz and Ramachandran can not apply in hypergraph case, and the algorithm used by Cain, Sanders and Wormald is already very complicated for analysis even for graph case. We proved, without giving an algorithm of finding an orientation, the existence of the threshold of random hypergraphs in G_{n, m, h}, in which every hypergraph contains n vertices, m edges, whose sizes are uniformly h.

Date received: March 31, 2008