The multiple-orientability thresholds for random hypergraphs

Research output: Contribution to journalArticlepeer-review

Standard

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

In: Combinatorics, Probability and Computing, Vol. 25, No. 6, 28.12.2015, p. 870-908.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Fountoulakis, Nikolaos ; Khosla, Megha ; Panagiotou, Konstantinos . / The multiple-orientability thresholds for random hypergraphs. In: Combinatorics, Probability and Computing. 2015 ; Vol. 25, No. 6. pp. 870-908.

Bibtex

@article{708508709d8747f792f180d7468a60eb,
title = "The multiple-orientability thresholds for random hypergraphs",
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.",
keywords = "random hypergraphs, orientability, core",
author = "Nikolaos Fountoulakis and Megha Khosla and Konstantinos Panagiotou",
year = "2015",
month = dec,
day = "28",
doi = "10.1017/S0963548315000334",
language = "English",
volume = "25",
pages = "870--908",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "6",

}

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 -