**
**

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

Item Type: | Journal article |
---|---|

Faculties: | Mathematics, Computer Science and Statistics > Mathematics |

Subjects: | 500 Science > 510 Mathematics |

URN: | urn:nbn:de:bvb:19-epub-47315-5 |

ISSN: | 0963-5483 |

Alliance/National Licence: | This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively. |

Language: | English |

Item ID: | 47315 |

Date Deposited: | 27. Apr 2018, 08:12 |

Last Modified: | 04. Nov 2020, 13:24 |