The Multiple-Orientability Thresholds for Random Hypergraphs

DOI10.1017/S0963548315000334MaRDI QIDQ5366923zbMATH OpenFDO

Authors Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548315000334

Mathematics Subject Classification ID

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

Recommendations

• The multiple-orientability thresholds for random hypergraphs
• Orientability Thresholds for Random Hypergraphs
• Orientability of random hypergraphs and the power of multiple choices
• A new approach to the orientation of random hypergraphs
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• Load balancing and orientability thresholds for random hypergraphs
• On the k-orientability of random graphs
• scientific article; zbMATH DE number 3931058
• Orientation Ramsey thresholds for cycles and cliques
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Cores in random hypergraphs and Boolean formulas
• Entropy, large deviations, and statistical mechanics.
• scientific article; zbMATH DE number 1962820 (Why is no real title available?)
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Orientability of random hypergraphs and the power of multiple choices
• Sharp load thresholds for cuckoo hashing
• The asymptotic number of labeled graphs with given degree sequences
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(16)

• On the k-orientability of random graphs
• Thresholds for extreme orientability
• 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
• Dense peelable random uniform hypergraphs
• Orientability Thresholds for Random Hypergraphs
• The multiple-orientability thresholds for random hypergraphs
• A new approach to the orientation of random hypergraphs
• Matching recovery threshold for correlated random graphs
• Towards an analysis of quadratic probing
• 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

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 Q5366923)