Orientability Thresholds for Random Hypergraphs

DOI10.1017/S096354831400073XMaRDI QIDQ5364256zbMATH OpenFDO

Authors Pu Gao, Nicholas Wormald

Publication date 4 October 2017

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

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The multiple-orientability thresholds for random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• A new approach to the orientation of random hypergraphs
• Orientability of random hypergraphs and the power of multiple choices
• On the k-orientability of random graphs
• Load balancing and orientability thresholds for random hypergraphs
• Orientation Ramsey thresholds for cycles and cliques
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• On the orientation of graphs and hypergraphs
• Acyclic orientations of random graphs

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Almost all graphs with 1.44n edges are 3-colorable
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Balanced Allocations
• Balanced allocations: the heavily loaded case
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Differential equations for random processes and random graphs
• Efficient PRAM simulation on a distributed memory machine
• Encores on cores
• Exploiting storage redundancy to speed up randomized shared memory simulations
• Fast concurrent access to parallel disks
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• Load balancing and orientability thresholds for random hypergraphs
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• On the degrees of the vertices of a directed graph
• Probability Inequalities for Sums of Bounded Random Variables
• Sharp load thresholds for cuckoo hashing
• Sudden emergence of a giant k-core in a random graph
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(8)

• On the k-orientability of random graphs
• Thresholds for extreme orientability
• Load balancing and orientability thresholds for random hypergraphs
• Orientability of random hypergraphs and the power of multiple choices
• The multiple-orientability thresholds for random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• Equitable hypergraph orientations
• A new approach to the orientation of random hypergraphs

This page was built for publication: Orientability Thresholds for Random Hypergraphs

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