More Web Proxy on the site http://driver.im/

research-article

The multiple-orientability thresholds for random hypergraphs

Authors:

Nikolaos Fountoulakis,

Konstantinos PanagiotouAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 1222 - 1236

Published: 23 January 2011 Publication History

Abstract

A k-uniform hypergraph H = (V, E) is called l-orientable, if there is an assignment of each edge e ε E to one of its vertices v ε e such that no vertex is assigned more than l edges. Let H_n,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the l-orientability of H_n,m,k for all k ≥ 3 and l ≥ 1, i.e., we determine a critical quantity c*_k,l such that with probability 1 − o(1) the graph H_n,cn,k has an l-orientation if c < c*_k,l, but fails doing so if c > c*_k,l.

Our result has various applications including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.

References

[1]

E. A. Bender and E. R. Canfield. The asymptotic number of labelled graphs with given degree sequence. J. Combin. Theory Ser. A, 24(3):296--307, 1978.

[2]

B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin, 1:311--316, 1980.

[3]

J. A. Cain, P. Sanders, and N. Wormald. The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In SODA '07, pages 469--476, 2007.

Digital Library

[4]

C. Cooper. The cores of random hypergraphs with a given degree sequence. Random Structures & Algorithms, 25(4):353--375, 2004.

Digital Library

[5]

M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh, and M. Rink. Tight thresholds for cuckoo hashing via XORSAT. In ICALP'10, volume 6198 of Lecture Notes in Computer Science, pages 213--225. 2010.

Digital Library

[6]

R. Ellis. Entropy, large deviations, and statistical mechanics. Classics in Mathematics. Springer-Verlag, Berlin, 2006.

[7]

D. Fernholz and V. Ramachandran. The k-orientability thresholds for G _n,p. In SODA '07, pages 459--468, 2007.

Digital Library

[8]

D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis. Space efficient hash tables with worst case constant access time. In STAGS '03, volume 2607 of Lecture Notes in Computer Science, pages 271--282. 2003.

Digital Library

[9]

N. Fountoulakis and K. Panagiotou. Orientability of random hypergraphs and the power of multiple choices. In ICALP'10, volume 6198 of Lecture Notes in Computer Science, pages 348--359. 2010.

Digital Library

[10]

A. Frieze and P. Melsted. Maximum matchings in random bipartite graphs and the space utilization of cuckoo hashtables. arXiv:0910.5535v3 {cs.DS} (29 Oct 2009), 2009.

[11]

P. Gao and N. C. Wormald. Load balancing and orientability thresholds for random hypergraphs. In STOC '10, pages 97--104, 2010.

Digital Library

[12]

S. Janson, T. Luczak, and A. Ruciński. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.

[13]

J. H. Kim. Poisson cloning model for random graphs. Manuscript, 2006.

[14]

M. Molloy. Cores in random hypergraphs and boolean formulas. Random Structures & Algorithms, 27(1):124--135, 2005.

Digital Library

[15]

R. Pagh and F. F. Rodler. Cuckoo hashing. In ESA '01, pages 121--133, 2001.

Digital Library

Cited By

Ren KZheng QArulraj JGibson G(2017)SlimDBProceedings of the VLDB Endowment10.14778/3151106.315110810:13(2037-2048)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.14778/3151106.3151108
Sun YHua YFeng DYang LZuo PCao SGuo Y(2017)A Collision-Mitigation Cuckoo Hashing Scheme for Large-Scale Storage SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.259476328:3(619-632)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2594763
Gao PPérez-Giménez XSato CChekuri C(2014)Arboricity and spanning-tree packing in random graphs with an application to load balancingProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634097(317-326)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634097
Show More Cited By

The multiple-orientability thresholds for random hypergraphs
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Mathematics of computing

Recommendations

Load balancing and orientability thresholds for random hypergraphs
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Let h>w>0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To 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)-...
Tiling multipartite hypergraphs in quasi-random hypergraphs
Abstract
Given k ≥ 2 and two k-graphs (k-uniform hypergraphs) F and H, an F-factor in H is a set of vertex disjoint copies of F that together covers the vertex set of H. Lenz and Mubayi studied the F-factor problems in quasi-random k-graphs with minimum ...
Orientability of random hypergraphs and the power of multiple choices
ICALP'10: Proceedings of the 37th international colloquium conference on Automata, languages and programming

A hypergraph H = (V,E) is called s-orientable, if there is an assignment of each edge e ∈ E to one of its vertices v ∈ e such that no vertex is assigned more than s edges. Let H_n,m,k be a hypergraph, drawn uniformly at random from the set of all k-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ren KZheng QArulraj JGibson G(2017)SlimDBProceedings of the VLDB Endowment10.14778/3151106.315110810:13(2037-2048)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.14778/3151106.3151108
Sun YHua YFeng DYang LZuo PCao SGuo Y(2017)A Collision-Mitigation Cuckoo Hashing Scheme for Large-Scale Storage SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.259476328:3(619-632)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2594763
Gao PPérez-Giménez XSato CChekuri C(2014)Arboricity and spanning-tree packing in random graphs with an application to load balancingProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634097(317-326)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634097
Fan BAndersen DKaminsky MMitzenmacher MSeneviratne ADiot CKurose JChaintreau ARizzo L(2014)Cuckoo FilterProceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies10.1145/2674005.2674994(75-88)Online publication date: 2-Dec-2014
https://dl.acm.org/doi/10.1145/2674005.2674994
Leconte MLelarge MMassoulié LKhanna S(2013)Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancingProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627820(35-46)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627820
Lelarge M(2012)A new approach to the orientation of random hypergraphsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095139(251-264)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095139
Dietzfelbinger MMitzenmacher MRink M(2011)Cuckoo hashing with pagesProceedings of the 19th European conference on Algorithms10.5555/2040572.2040639(615-627)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040639

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents