A new approach to the orientation of random hypergraphs

Details A new approach to the orientation of random hypergraphs A new approach to the orientation of random hypergraphs

2012-01-25

arxiv.org/abs/1201.5335v1

Mathematics

Probability

27 pages, preliminary version appeared at SODA 2012

Scientific paper

A h-uniform hypergraph H=(V,E) is called (l,k)-orientable if there exists an assignment of each hyperedge e to exactly l of its vertices such that no vertex is assigned more than k hyperedges. Let H_{n,m,h} be a hypergraph, drawn uniformly at random from the set of all h-uniform hypergraphs with n vertices and m edges. In this paper, we determine the threshold of the existence of a (l,k)-orientation of H_{n,m,h} for k>=1 and h>l>=1, extending recent results motivated by applications such as cuckoo hashing or load balancing with guaranteed maximum load. Our proof combines the local weak convergence of sparse graphs and a careful analysis of a Gibbs measure on spanning subgraphs with degree constraints. It allows us to deal with a much broader class than the uniform hypergraphs.

Affiliated with

Also associated with

No associations

Rating

A new approach to the orientation of 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 A new approach to the orientation of random hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new approach to the orientation of random hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-683728