Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-06T01:58:44.304Z Has data issue: false hasContentIssue false
  • English
  • Français

Orientability Thresholds for Random Hypergraphs

Part of: Graph theory

Published online by Cambridge University Press:  23 March 2015

PU GAO  and
NICHOLAS WORMALD
PU GAO
Affiliation:
Max-Planck-Institut für Informatik, 66123 Saarbrücken, Saarland, Germany and Department of Combinatorics and Optimization, University of Waterloo, Canada (e-mail: janegao@mpi-inf.mpg.de)
NICHOLAS WORMALD
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Canada (e-mail: nwormald@math.uwaterloo.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 signs. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, 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. This settled a conjecture of Karp and Saks.

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C85: Graph algorithms

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 5 , September 2015 , pp. 774 - 824
Copyright
Copyright © Cambridge University Press 2015 

References

REFERENCES

[1] Alon, N. and Spencer, J. (2008) The Probabilistic Method, third edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.CrossRefGoogle Scholar
[2] Azar, Y., Broder, A. Z., Karlin, A. R. and Upfal, E. (1999) Balanced allocations. SIAM J. Comput. 29 180–200.CrossRefGoogle Scholar
[3] Berenbrink, P., Czumaj, A., Steger, A. and Vőcking, B. (2000) Balanced allocations: The heavily loaded case. In 32nd Annual ACM Symposium on Theory of Computing, pp. 745–754.Google Scholar
[4] Bollobás, B. and Frieze, A. M. (1985) On matchings and Hamiltonian cycles in random graphs. In Random Graphs '83, Vol. 118 of North-Holland Mathematics Studies, North-Holland, pp. 23–46.Google Scholar
[5] Cain, J., Sanders, P. and Wormald, N. (2007) The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation. In Symposium on Discrete Algorithms: SODA, pp. 469–476.Google Scholar
[6] Cain, J. and Wormald, N. (2006) Encores on cores. Electron. J. Combin. 13 RP81.Google Scholar
[7] Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493–507.Google Scholar
[8] Chvátal, V. (1991) Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Alg. 2 11–28.CrossRefGoogle Scholar
[9] Cook, W. J., Cunningham, W. H., Pulleyblank, W. R. and Schrijver, A. (1998) Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.Google Scholar
[10] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M. (2012) Tight thresholds for cuckoo hashing via XORSAT. Automata, Languages and Programming, Lecture Notes in Computer Science 6198 213–225.Google Scholar
[11] Dietzfelbinger, M. and Meyer auf der Heide, F. (1993) Simple, efficient shared memory simulations. In 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 110–119.Google Scholar
[12] Fernholz, D. and Ramachandran, V. (2007) The k-orientability thresholds for Gn,p . In Proc. ACM–SIAM Symposium on Discrete Algorithms: SODA, pp. 459–468.Google Scholar
[13] Fountoulakis, N. and Panagiotou, K. (2012) Sharp load thresholds for cuckoo hashing. Random Structures & Algorithms 41 306–333.CrossRefGoogle Scholar
[14] Frieze, A. and Melsted, P. (2012) Maximum matchings in random bipartite graphs and the space utilization of cuckoo hashtables. Random Structures & Algorithms 41 334–364.Google Scholar
[15] Gao, P. Generation and properties of random graphs and analysis of randomized algorithms. PhD dissertation, Department of Combinatorics and Optimization, University of Waterloo. http://hdl.handle.net/10012/4987 Google Scholar
[16] Gao, P. and Wormald, N. C. (2010) Load balancing and orientability thresholds for random hypergraphs. In STOC'10, Cambridge, Massachusetts, USA. pp. 97–103.Google Scholar
[17] Hakimi, S. L. (1965) On the degrees of the vertices of a directed graph. J. Franklin Inst. 279 290–308.Google Scholar
[18] Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.Google Scholar
[19] Karp, R. M., Luby, M. and Meyer auf der Heide, F. (1992) Efficient PRAM simulation on a distributed memory machine. In 24th ACM Symposium on Theory of Computing, pp. 318–326.Google Scholar
[20] McKay, B. D. and Wormald, N. C. (1991) Asymptotic enumeration by degree sequence of graphs with degrees o(n 1/2). Combinatorica 11 369–382.Google Scholar
[21] Meyer auf der Heide, F., Scheideler, C. and Stemann, V. (1996) Exploiting storage redundancy to speed up randomized shared memory simulations. Theoret. Comput. Sci. 162 245–281.CrossRefGoogle Scholar
[22] Mitzenmacher, M., Richa, A. and Sitaraman, R. (2001) The power of two random choices: A survey of techniques and results. Chapter 9 of Handbook of Randomized Computing, Vol. I, Combinatorial Optimization, Kluwer, pp. 255–312.Google Scholar
[23] Pittel, B., Spencer, J. and Wormald, N. (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111–151.CrossRefGoogle Scholar
[24] Pittel, B. and Wormald, N. (2003) Asymptotic enumeration of sparse graphs with a minimum degree constraint. J. Combin. Theory Ser. A 101 249–263.Google Scholar
[25] Sanders, P., Egner, S. and Korst, J. (2003) Fast concurrent access to parallel disks. Algorithmica 35 21–55.Google Scholar
[26] Schrijver, A. (2003) Combinatorial Optimization: Polyhedra and Efficiency, Vol. B, Vol. 24 of Algorithms and Combinatorics, Springer.Google Scholar
[27] Wormald, N. C. (1995) Differential equations for random processes and random graphs. Ann. Appl. Probab. 5 1217–1235.CrossRefGoogle Scholar
[28] Wormald, N. C. (1999) The differential equation method for random graph processes and greedy algorithms. Lectures on Approximation and Randomized Algorithms (Karonski, M. and Prömel, H. J., eds), PWN, Warsaw, pp. 73–155.Google Scholar
[29] Wormald, N. C. (2004) Random graphs and asymptotics. Section 8.2 of Handbook of Graph Theory (Gross, J. L. and Yellen, J., eds), CRC, pp. 817–836.Google Scholar