The Multiple-Orientability Thresholds for Random Hypergraphs

Nikolaos  Fountoulakis; M. Khosla; Konstantinos  Panagiotou

The Multiple-Orientability Thresholds for Random Hypergraphs

Nikolaos Fountoulakis, M. Khosla, Konstantinos Panagiotou

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

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 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 language	English
Title of host publication	Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms (SODA'11
Editors	Dana Randall
Pages	1222-1236
Volume	25
Edition	6
Publication status	Published - 2011
Externally published	Yes
Event	ACM-SIAM symposium on Discrete algorithms - Duration: 23 Jan 2011 → 25 Jan 2011 Conference number: 22

Publication series

Name	Combinatorics, Probability and Computing

Conference

Conference	ACM-SIAM symposium on Discrete algorithms
Abbreviated title	SODA'11
Period	23/01/11 → 25/01/11

Cite this

@inproceedings{b4b17b4495ee4c288eea3748f9d2553b,

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

author = "Nikolaos Fountoulakis and M. Khosla and Konstantinos Panagiotou",

year = "2011",

language = "English",

isbn = "978-0-89871-993-2",

volume = "25",

series = "Combinatorics, Probability and Computing",

pages = "1222--1236",

editor = "Dana Randall",

booktitle = "Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms (SODA'11",

edition = "6",

note = "ACM-SIAM symposium on Discrete algorithms, SODA'11 ; Conference date: 23-01-2011 Through 25-01-2011",

}

The Multiple-Orientability Thresholds for Random Hypergraphs. / Fountoulakis, Nikolaos ; Khosla, M.; Panagiotou, Konstantinos.
Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms (SODA'11. ed. / Dana Randall. Vol. 25 6. ed. 2011. p. 1222-1236 (Combinatorics, Probability and Computing).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - The Multiple-Orientability Thresholds for Random Hypergraphs

AU - Fountoulakis, Nikolaos

AU - Khosla, M.

AU - Panagiotou, Konstantinos

N1 - Conference code: 22

PY - 2011

Y1 - 2011

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

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

M3 - Conference contribution

SN - 978-0-89871-993-2

VL - 25

T3 - Combinatorics, Probability and Computing

SP - 1222

EP - 1236

BT - Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms (SODA'11

A2 - Randall, Dana

T2 - ACM-SIAM symposium on Discrete algorithms

Y2 - 23 January 2011 through 25 January 2011

ER -

The Multiple-Orientability Thresholds for Random Hypergraphs

Abstract

Publication series

Conference

Fingerprint

Cite this