Orientability of Random Hypergraphs and the Power of Multiple Choices
Orientability of Random Hypergraphs and the Power of Multiple Choices
复制标题
随机超图的可定向性和多重选择的力量
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
K. Panagiotou
中科院分区：
文献类型：
--
作者：
N. Fountoulakis;K. Panagiotou
如果超图H = （V，E）的每条边E∈E与其中一个顶点V∈E的赋值使得每个顶点的赋值不超过s条边，则该超图H = （V，E）称为s可定向的。设Hn，m，k是一个超图，从所有k个有n个顶点和m条边的一致超图集合中随机绘制。本文建立了所有k≥3时，图Hn，m，k具有1取向性的阈值，即我们确定了一个临界值ck*，使得图Hn，cn，k有1- 0(1)的概率具有1取向性。
A hypergraph H = (V,E) is called s-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 s 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 1-orientability of Hn,m,k for all k ≥ 3, i.e., we determine a critical quantity ck* such that with probability 1 - o(1) the graph Hn,cn,k has a 1-orientation if c ck*.
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 ≥ 3 we prove that with probability 1 - o(1) the maximum number of elements that can be hashed is (1 - o(1))ck*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.
关于使用带有简单通用哈希类的布谷鸟哈希的风险
DOI：
10.1137/1.9781611973068.87
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Ulf Schellbach
通讯作者：
Ulf Schellbach