English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Orientability Thresholds for Random Hypergraphs

MPS-Authors
/persons/resource/persons44475

Gao,  Pu
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1009.5489.pdf
(Preprint), 478KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Gao, P., & Wormald, N. (2010). Orientability Thresholds for Random Hypergraphs. doi:10.1017/S096354831400073X.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0028-4CC6-E
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.