The Multiple-Orientability Thresholds for Random Hypergraphs

Source abstract

A k -uniform hypergraph H = ( V, E ) is called ℓ-orientable if there is an assignment of each edge e ∈ E to one of its vertices v ∈ e such that no vertex is assigned more than ℓ edges. Let H n,m,k be a hypergraph, drawn uniformly at random from the set of all k -uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the ℓ-orientability of H n,m,k for all k ⩾ 3 and ℓ ⩾ 2, that is, we determine a critical quantity c* k,ℓ such that with probability 1 − o (1) the graph H n,cn,k has an ℓ-orientation if c < c* k,ℓ , but fails to do so if c > c* k,ℓ . Our result has various applications, including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.