Orientability thresholds for random hypergraphs

Details Orientability thresholds for random hypergraphs Orientability thresholds for random hypergraphs

2010-09-28

arxiv.org/abs/1009.5489v1

Mathematics

Combinatorics

47 pages, 1 figures, the journal version of [16]

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Orientability thresholds for random hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Orientability thresholds for random hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orientability thresholds for random hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693472