3 The Multiple-orientability Thresholds for Random Hypergraphs∗
Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou · 2011
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 Hn,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 Hn,m,k for all k ≥ 3 and ` ≥ 1, i.e., we determine a critical quantity c∗k, ` such that with probability 1 − o(1) the graph Hn,cn,k has an `-orientation 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. 1