The multiple-orientability thresholds for random hypergraphs

Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
220 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)870-908
Number of pages38
JournalCombinatorics, Probability and Computing
Volume25
Issue number6
Early online date28 Dec 2015
DOIs
Publication statusE-pub ahead of print - 28 Dec 2015

Keywords

  • random hypergraphs
  • orientability
  • core

Fingerprint

Dive into the research topics of 'The multiple-orientability thresholds for random hypergraphs'. Together they form a unique fingerprint.

Cite this