Fountoulakis, Nikolaos; Khosla, Megha; Panagiotou, Konstantinos
(2016):
The MultipleOrientability Thresholds for Random Hypergraphs.
In: Combinatorics Probability & Computing, Vol. 25, No. 6: pp. 870908

Preview 

275kB 
Abstract
A kuniform hypergraph H = (V, E) is called lorientable 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 Hn,Hm,Hk be a hypergraph, drawn uniformly at random from the set of all kuniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the lorientability of Hn,Hm,Hk for all k >= 3 and l >= 2, that is, we determine a critical quantity c(*)k,l such that with probability 1o(1) the graph Hn,Hcn,(k) has an lorientation 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.