{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:46:27Z","timestamp":1758476787985},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2015,12,28]],"date-time":"2015-12-28T00:00:00Z","timestamp":1451260800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p>A<jats:italic>k<\/jats:italic>-uniform hypergraph<jats:italic>H<\/jats:italic>= (<jats:italic>V, E<\/jats:italic>) is called \u2113-orientable if there is an assignment of each edge<jats:italic>e<\/jats:italic>\u2208<jats:italic>E<\/jats:italic>to one of its vertices<jats:italic>v<\/jats:italic>\u2208<jats:italic>e<\/jats:italic>such that no vertex is assigned more than \u2113 edges. Let<jats:italic>H<jats:sub>n,m,k<\/jats:sub><\/jats:italic>be a hypergraph, drawn uniformly at random from the set of all<jats:italic>k<\/jats:italic>-uniform hypergraphs with<jats:italic>n<\/jats:italic>vertices and<jats:italic>m<\/jats:italic>edges. In this paper we establish the threshold for the \u2113-orientability of<jats:italic>H<jats:sub>n,m,k<\/jats:sub><\/jats:italic>for all<jats:italic>k<\/jats:italic>\u2a7e 3 and \u2113 \u2a7e 2, that is, we determine a critical quantity<jats:italic>c*<jats:sub>k,\u2113<\/jats:sub><\/jats:italic>such that with probability 1 \u2212<jats:italic>o<\/jats:italic>(1) the graph<jats:italic>H<jats:sub>n,cn,k<\/jats:sub><\/jats:italic>has an \u2113-orientation if<jats:italic>c<\/jats:italic>&lt;<jats:italic>c*<jats:sub>k,\u2113<\/jats:sub><\/jats:italic>, but fails to do so if<jats:italic>c<\/jats:italic>&gt;<jats:italic>c*<jats:sub>k,\u2113<\/jats:sub><\/jats:italic>.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1017\/s0963548315000334","type":"journal-article","created":{"date-parts":[[2015,12,28]],"date-time":"2015-12-28T05:10:16Z","timestamp":1451279416000},"page":"870-908","source":"Crossref","is-referenced-by-count":9,"title":["The Multiple-Orientability Thresholds for Random Hypergraphs"],"prefix":"10.1017","volume":"25","author":[{"given":"NIKOLAOS","family":"FOUNTOULAKIS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MEGHA","family":"KHOSLA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KONSTANTINOS","family":"PANAGIOTOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,12,28]]},"reference":[{"key":"S0963548315000334_ref8","first-page":"271","volume-title":"Lecture Notes in Computer Science","author":"Fotakis","year":"2003"},{"key":"S0963548315000334_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"S0963548315000334_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"S0963548315000334_ref18","doi-asserted-by":"crossref","unstructured":"Pagh R. and Rodler F. F. (2001) Cuckoo hashing. In Proc. 9th Annual European Symposium on Algorithms: ESA 2001, pp. 121\u2013133.","DOI":"10.1007\/3-540-44676-1_10"},{"key":"S0963548315000334_ref9","first-page":"348","volume-title":"Lecture Notes in Computer Science","author":"Fountoulakis","year":"2010"},{"key":"S0963548315000334_ref5","first-page":"213","volume-title":"Lecture Notes in Computer Science","author":"Dietzfelbinger","year":"2010"},{"key":"S0963548315000334_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"S0963548315000334_ref14","unstructured":"Kim J. H. (2004) Poisson cloning model for random graphs. Manuscript."},{"key":"S0963548315000334_ref13","doi-asserted-by":"crossref","unstructured":"Janson S. , \u0141uczak T. and Ruci\u0144ski A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.","DOI":"10.1002\/9781118032718"},{"key":"S0963548315000334_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548315000334_ref7","unstructured":"Fernholz D. and Ramachandran V. (2007) The k-orientability thresholds for Gn,p . In Proc. 18th Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA 2007, pp. 459\u2013468."},{"key":"S0963548315000334_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20426"},{"key":"S0963548315000334_ref19","unstructured":"Sanders P. , Egner S. and Korst J. (1999) Fast concurrent access to parallel disks. In Proc. 11th Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA 1999, pp. 849\u2013858."},{"key":"S0963548315000334_ref16","doi-asserted-by":"crossref","unstructured":"Lelarge M. (2012) A new approach to the orientation of random hypergraphs. In Proc. 23th ACM\u2013SIAM Symposium on Discrete Algorithms: SODA 2012, pp. 251\u2013264.","DOI":"10.1137\/1.9781611973099.23"},{"key":"S0963548315000334_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29060-5"},{"key":"S0963548315000334_ref3","unstructured":"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\u2013SIAM Symposium on Discrete Algorithms: SODA 2007, pp. 469\u2013476."},{"key":"S0963548315000334_ref12","doi-asserted-by":"crossref","unstructured":"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\u2013104.","DOI":"10.1145\/1806689.1806705"},{"key":"S0963548315000334_ref15","doi-asserted-by":"crossref","unstructured":"Leconte M. , Lelarge M. and Massouli\u00e9 L. (2013) Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. In Proc. 24th ACM\u2013SIAM Symposium on Discrete Algorithms: SODA 2013, pp. 35\u201346.","DOI":"10.1137\/1.9781611973105.3"},{"key":"S0963548315000334_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20427"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T20:11:09Z","timestamp":1567455069000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000334\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,28]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["S0963548315000334"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000334","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,28]]}}}