A new approach to the orientation of random hypergraphs
From MaRDI portal
(Redirected from Publication:5743396)
Abstract: A h-uniform hypergraph H=(V,E) is called (l,k)-orientable if there exists an assignment of each hyperedge e to exactly l of its vertices such that no vertex is assigned more than k hyperedges. Let H_{n,m,h} be a hypergraph, drawn uniformly at random from the set of all h-uniform hypergraphs with n vertices and m edges. In this paper, we determine the threshold of the existence of a (l,k)-orientation of H_{n,m,h} for k>=1 and h>l>=1, extending recent results motivated by applications such as cuckoo hashing or load balancing with guaranteed maximum load. Our proof combines the local weak convergence of sparse graphs and a careful analysis of a Gibbs measure on spanning subgraphs with degree constraints. It allows us to deal with a much broader class than the uniform hypergraphs.
Recommendations
- Orientability Thresholds for Random Hypergraphs
- On the k-orientability of random graphs
- Orientability of random hypergraphs and the power of multiple choices
- The multiple-orientability thresholds for random hypergraphs
- The Multiple-Orientability Thresholds for Random Hypergraphs
- On the orientation of graphs and hypergraphs
- A note on orientations of the infinite random graph
- Acyclic orientations of random graphs
- On the structure of random hypergraphs
Cites work
- A new approach to the orientation of random hypergraphs
- A simple solution to the k‐core problem
- Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
- Fast concurrent access to parallel disks
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 2042286 (Why is no real title available?)
- scientific article; zbMATH DE number 1875412 (Why is no real title available?)
- Information, Physics, and Computation
- Load balancing and orientability thresholds for random hypergraphs
- Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
- Orientability of random hypergraphs and the power of multiple choices
- Processes on unimodular random networks
- Recurrence of distributional limits of finite planar graphs
- The \(k\)-orientability thresholds for \(G_{n,p}\)
- The multiple-orientability thresholds for random hypergraphs
- The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
- The rank of diluted random graphs
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
- Towards a theory of negative dependence.
- Weighted enumeration of spanning subgraphs with degree constraints
Cited in
(23)- Dynamic space efficient hashing
- Thresholds for extreme orientability
- A faster algorithm for cuckoo insertion and bipartite matching in large graphs
- An average study of hypergraphs and their minimal transversals
- Load balancing and orientability thresholds for random hypergraphs
- Orientability of random hypergraphs and the power of multiple choices
- Matchings on infinite graphs
- Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Dense peelable random uniform hypergraphs
- Load thresholds for cuckoo hashing with double hashing
- Counting restricted orientations of random graphs
- Orientability Thresholds for Random Hypergraphs
- The multiple-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
- scientific article; zbMATH DE number 7740865 (Why is no real title available?)
- Sharp threshold for rigidity of random graphs
- Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
- ShockHash: near optimal-space minimal perfect hashing beyond brute-force
- Insertion time of random walk cuckoo hashing below the peeling threshold
- Ribbon: fast succinct static retrieval and approximate membership
This page was built for publication: A new approach to the orientation of random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743396)
