The multiple-orientability thresholds for random hypergraphs

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • Max Planck Inst Informat
  • Department of Mathematics, University of Munich (LMU)


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 ℓ ≥ 2, that is, 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,ℓ , 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.


Original languageEnglish
Pages (from-to)870-908
Number of pages38
JournalCombinatorics, Probability and Computing
Issue number6
Early online date28 Dec 2015
Publication statusE-pub ahead of print - 28 Dec 2015


  • random hypergraphs, orientability, core