The multiple-orientability thresholds for random hypergraphs

MaRDI QIDQ5365112zbMATH OpenFDO

Authors Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1309.6772, http://dl.acm.org/citation.cfm?id=2133129

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A $k$-uniform hypergraph $H=(V,E)$ is called $ell$-orientable, if there is an assignment of each edge $einE$ to one of its vertices $vine$ such that no vertex is assigned more than $ell$ edges. Let $H_{n,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 $ell$-orientability of $H_{n,m,k}$ for all $kge3$ and $ellge2$, i.e., we determine a critical quantity $c_{k,ell}^{\ast }$ such that with probability $1-o(1)$ the graph $H_{n,cn,k}$ has an $ell$-orientation if $c<c_{k,ell}^{\ast }$, but fails doing so if $c>c_{k,ell}^{\ast }$. 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.

Recommendations

• The Multiple-Orientability Thresholds for Random Hypergraphs
• Orientability of random hypergraphs and the power of multiple choices
• A new approach to the orientation of random hypergraphs
• Load balancing and orientability thresholds for random hypergraphs
• Orientability Thresholds for Random Hypergraphs

Cited in

(17)

• On the k-orientability of random graphs
• Thresholds for extreme orientability
• The densest subgraph problem in sparse random graphs
• Load balancing and orientability thresholds for random hypergraphs
• Mixed hypergraphs for linear-time construction of denser hashing-based data structures
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• Orientability of random hypergraphs and the power of multiple choices
• scientific article; zbMATH DE number 3931058 (Why is no real title available?)
• Monotone paths in random hypergraphs
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Dense peelable random uniform hypergraphs
• Load thresholds for cuckoo hashing with double hashing
• Orientability Thresholds for Random Hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• A new approach to the orientation of random hypergraphs
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks

This page was built for publication: The multiple-orientability thresholds for random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365112)