×

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].

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
Full Text: DOI