hide
Free keywords:
Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM
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.
