Logo Logo
Help
Contact
Switch Language to German

Fountoulakis, Nikolaos; Khosla, Megha and Panagiotou, Konstantinos (2016): The Multiple-Orientability Thresholds for Random Hypergraphs. In: Combinatorics Probability & Computing, Vol. 25, No. 6: pp. 870-908 [PDF, 275kB]

Abstract

A k-uniform hypergraph H = (V, E) is called l-orientable if there is an assignment of each edge e is an element of E to one of its vertices v is an element of e such that no vertex is assigned more than l edges. Let H-n,H-m,H-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 l-orientability of H-n,H-m,H-k for all k >= 3 and l >= 2, that is, we determine a critical quantity c(*)k,l such that with probability 1-o(1) the graph H-n,H-cn,(k) has an l-orientation if c < c(k,l)(*) , but fails to do so if c > c(k,l)(*) . 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.

Actions (login required)

View Item View Item