Name
Abstract | ||
|---|---|---|
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*, but fails doing so 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14165-2_30 | ICALP |
Keywords | Field | DocType |
graph hn,n vertex,critical quantity ck,multiple choice,hypergraph h,c ck,n location,random graph process,m edge,vertices v,k random vertex,random hypergraphs,phase transition,hash table,random graph,connected component | Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Hypergraph,Orientability,Constraint graph,Giant component,Degree (graph theory),Connected component,Mathematics | Conference |
Volume | ISSN | ISBN |
6198 | 0302-9743 | 3-642-14164-1 |
Citations | PageRank | References |
12 | 0.84 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikolaos Fountoulakis | 1 | 185 | 18.04 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |