The multiple-orientability thresholds for random hypergraphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

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

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 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.

Details

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

Keywords

  • random hypergraphs, orientability, core