Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-25T02:22:57.858Z Has data issue: false hasContentIssue false
  • English
  • Français

The Multiple-Orientability Thresholds for Random Hypergraphs†

Part of: Graph theory Theory of computing Algorithms - Computer Science

Published online by Cambridge University Press:  28 December 2015

NIKOLAOS FOUNTOULAKIS ,
MEGHA KHOSLA  and
KONSTANTINOS PANAGIOTOU
NIKOLAOS FOUNTOULAKIS
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, B15 2TT, UK (e-mail: fountoun@bham.ac.uk)
MEGHA KHOSLA
Affiliation:
Max Planck Institute for Informatics, Campus E1 4, 66123 Saarbrücken, Germany (e-mail: mkhosla@mpi-inf.mpg.de)
KONSTANTINOS PANAGIOTOU
Affiliation:
Mathematics Institute, University of Munich, Theresienstr. 39, 80333 München, Germany (e-mail: kpanagio@math.lmu.de)
Get access Rights & Permissions [Opens in a new window]

Abstract

A k-uniform hypergraph H = (V, E) is called ℓ-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 ℓ edges. Let Hn,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 ℓ-orientability of Hn,m,k for all k ⩾ 3 and ℓ ⩾ 2, that is, we determine a critical quantity c*k,ℓ such that with probability 1 − o(1) the graph Hn,cn,k has an ℓ-orientation if c < c*k,ℓ, but fails to do so if c > c*k,ℓ.

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.

MSC classification

Primary: 68Q25: Analysis of algorithms and problem complexity
Secondary: 05C80: Random graphs 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) 68W20: Randomized algorithms 05C65: Hypergraphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 6 , November 2016 , pp. 870 - 908
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

An extended abstract of this work appeared in the Proceedings of the 22nd ACM–SIAM Symposium on Discrete Algorithms: SODA'11.

References

[1] Bender, E. A. and Canfield, E. R. (1978) The asymptotic number of labelled graphs with given degree sequence. J. Combin. Theory Ser. A 24 296–307.Google Scholar
[2] Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin. 1 311–316.Google Scholar
[3] Cain, J. A., Sanders, P. and Wormald, N. (2007) The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation. In Proc. 18th Annual ACM–SIAM Symposium on Discrete Algorithms: SODA 2007, pp. 469–476.Google Scholar
[4] Cooper, C. (2004) The cores of random hypergraphs with a given degree sequence. Random Struct. Alg. 25 353–375.Google Scholar
[5] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M. (2010) Tight thresholds for cuckoo hashing via XORSAT. In Proc. 37th International Colloquium on Automata, Languages and Programming: ICALP 2010, Vol. 6198 of Lecture Notes in Computer Science, Springer, pp. 213–225.Google Scholar
[6] Ellis, R. (2006) Entropy, Large Deviations, and Statistical Mechanics, Classics in Mathematics. Springer.Google Scholar
[7] Fernholz, D. and Ramachandran, V. (2007) The k-orientability thresholds for Gn,p . In Proc. 18th Annual ACM–SIAM Symposium on Discrete Algorithms: SODA 2007, pp. 459–468.Google Scholar
[8] Fotakis, D., Pagh, R., Sanders, P. and Spirakis, P. (2003) Space efficient hash tables with worst case constant access time. In Proc. 20th Annual Symposium on Theoretical Aspects of Computer Science: STACS 2003, Vol. 2607 of Lecture Notes in Computer Science, Springer, pp. 271–282.Google Scholar
[9] Fountoulakis, N. and Panagiotou, K. (2010) Orientability of random hypergraphs and the power of multiple choices. In Proc. 37th International Colloquium on Automata, Languages and Programming: ICALP 2010, Vol. 6198 of Lecture Notes in Computer Science, Springer, pp. 348–359.Google Scholar
[10] Fountoulakis, N. and Panagiotou, K. (2012) Sharp load thresholds for cuckoo hashing. Random Struct. Alg. 41 306–333.Google Scholar
[11] Frieze, A. and Melsted, P. (2012) Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Struct. Alg. 41 334–364.Google Scholar
[12] Gao, P. and Wormald, N. C. (2010) Load balancing and orientability thresholds for random hypergraphs. In Proc. 42nd ACM Symposium on Theory of Computing: STOC 2010, pp. 97–104.CrossRefGoogle Scholar
[13] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.Google Scholar
[14] Kim, J. H. (2004) Poisson cloning model for random graphs. Manuscript.Google Scholar
[15] Leconte, M., Lelarge, M. and Massoulié, L. (2013) Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. In Proc. 24th ACM–SIAM Symposium on Discrete Algorithms: SODA 2013, pp. 35–46.CrossRefGoogle Scholar
[16] Lelarge, M. (2012) A new approach to the orientation of random hypergraphs. In Proc. 23th ACM–SIAM Symposium on Discrete Algorithms: SODA 2012, pp. 251–264.Google Scholar
[17] Molloy, M. (2005) Cores in random hypergraphs and boolean formulas. Random Struct. Alg. 27 124–135.CrossRefGoogle Scholar
[18] Pagh, R. and Rodler, F. F. (2001) Cuckoo hashing. In Proc. 9th Annual European Symposium on Algorithms: ESA 2001, pp. 121–133.Google Scholar
[19] Sanders, P., Egner, S. and Korst, J. (1999) Fast concurrent access to parallel disks. In Proc. 11th Annual ACM–SIAM Symposium on Discrete Algorithms: SODA 1999, pp. 849–858.Google Scholar