Fountoulakis, Nikolaos; Panagiotou, Konstantinos Orientability of random hypergraphs and the power of multiple choices. (English) Zbl 1288.05186 Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 348-359 (2010). Summary: A hypergraph \(H = (V, E)\) is called \(s\)-orientable, if there is an assignment of each edge \(e \in E\) to one of its vertices \(v \in 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\)-uniform hypergraphs with \(n\) vertices and \(m\) edges. In this paper we establish the threshold for the 1-orientability of \(H _{n,m,k }\) for all \(k \geq 3\), i.e., we determine a critical quantity \(c_k^*\) such that with probability \(1 - o(1)\) the graph \(H _{n,cn,k }\) has a 1-orientation if \(c < c_k^*\), but fails doing so if \(c > c_k^*\). We present two applications of this result that involve the paradigm of multiple choices. First, we show how it implies sharp load thresholds for cuckoo hash tables, where each element chooses \(k\) out of \(n\) locations. Particularly, for each \(k \geq 3\) we prove that with probability \(1 - o(1)\) the maximum number of elements that can be hashed is \((1 - o(1))c_k^* n\), and more items prevent the successful allocation. Second, we study random graph processes, where in each step we have the choice among any edge connecting \(k\) random vertices. Here we show the existence of a phase transition for avoiding a giant connected component, and quantify precisely the dependence on \(k\).For the entire collection see [Zbl 1194.68005]. Cited in 7 Documents MSC: 05C65 Hypergraphs 05C80 Random graphs (graph-theoretic aspects) 68P05 Data structures 68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) 68R10 Graph theory (including graph drawing) in computer science PDFBibTeX XMLCite \textit{N. Fountoulakis} and \textit{K. Panagiotou}, Lect. Notes Comput. Sci. 6198, 348--359 (2010; Zbl 1288.05186) Full Text: DOI