# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Orientability Thresholds for Random Hypergraphs

##### 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: http://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.