Load balancing and orientability thresholds for random hypergraphs

DOI10.1145/1806689.1806705zbMATH Open1293.05245arXiv1009.5489OpenAlexW2008159222MaRDI QIDQ2875136FDOQ2875136

Nicholas Wormald, Pu Gao

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: Let $h>w>0$ be two fixed integers. Let $orH$ be a random hypergraph whose hyperedges are all of cardinality $h$. To {em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to the hyperedge, and the rest negative. A $(w,k)$-orientation of $orH$ consists of a $w$-orientation of all hyperedges of $orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when $h=2$ and $w=1$, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, which settled a conjecture of Karp and Saks.

Full work available at URL: https://arxiv.org/abs/1009.5489

zbMATH Keywords

load balancingcoreshypergraph orientationorientability thresholds

Mathematics Subject Classification ID

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

Cited In (10)

• The densest subgraph problem in sparse random graphs
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Thresholds for extreme orientability
• Load balancing for Markov chains with a specified directed graph
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Sandwiching a densest subgraph by consecutive cores
• Matching recovery threshold for correlated random graphs
• Orientability Thresholds for Random Hypergraphs
• A new approach to the orientation of random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs

This page was built for publication: Load balancing and orientability thresholds for random hypergraphs

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