# The multiple-orientability thresholds for random hypergraphs

Research output: Contribution to journal › Article › peer-review

## Standard

**The multiple-orientability thresholds for random hypergraphs.** / Fountoulakis, Nikolaos; Khosla, Megha ; Panagiotou, Konstantinos .

Research output: Contribution to journal › Article › peer-review

## Harvard

*Combinatorics, Probability and Computing*, vol. 25, no. 6, pp. 870-908. https://doi.org/10.1017/S0963548315000334

## APA

*Combinatorics, Probability and Computing*,

*25*(6), 870-908. https://doi.org/10.1017/S0963548315000334

## Vancouver

## Author

## Bibtex

}

## RIS

TY - JOUR

T1 - The multiple-orientability thresholds for random hypergraphs

AU - Fountoulakis, Nikolaos

AU - Khosla, Megha

AU - Panagiotou, Konstantinos

PY - 2015/12/28

Y1 - 2015/12/28

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

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

KW - random hypergraphs

KW - orientability

KW - core

U2 - 10.1017/S0963548315000334

DO - 10.1017/S0963548315000334

M3 - Article

VL - 25

SP - 870

EP - 908

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 6

ER -