Abstract | ||
---|---|---|
A h-uniform hypergraph H = (V, E) is called (l, k)-orientable if there exists an assignment of each hyper-edge e ε to exactly l of its vertices v ε e such that no vertex is assigned more than k hyperedges. Let Hn,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 Hn,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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.5555/2095116.2095139 | Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms |
Keywords | DocType | Volume |
guaranteed maximum load,load balancing,h l,h-uniform hypergraphs,gibbs measure,h-uniform hypergraph h,k hyperedges,broader class,new approach,vertices v,uniform hypergraphs,random hypergraphs | Conference | abs/1201.5335 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 14 | 0.79 |
References | Authors | |
11 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
M. Lelarge | 1 | 20 | 1.99 |