The Multiple-Orientability Thresholds for Random Hypergraphs

Nikolaos Fountoulakis, M. Khosla, Konstantinos Panagiotou

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


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 G 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*k,ℓ, but fails doing 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
Title of host publicationProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms (SODA'11
EditorsDana Randall
Publication statusPublished - 2011
Externally publishedYes
EventACM-SIAM symposium on Discrete algorithms -
Duration: 23 Jan 201125 Jan 2011
Conference number: 22

Publication series

NameCombinatorics, Probability and Computing


ConferenceACM-SIAM symposium on Discrete algorithms
Abbreviated titleSODA'11


Dive into the research topics of 'The Multiple-Orientability Thresholds for Random Hypergraphs'. Together they form a unique fingerprint.

Cite this