Name
Abstract | ||
|---|---|---|
Random Intersection Graphs, G"n","m","p, is a class of random graphs introduced in Karonski (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=@?n^@a@?, for any real @a different than one, we establish here, for the first time, a sharp threshold for the graph property ''Contains a Hamilton cycle''. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2010.06.022 | Theor. Comput. Sci. |
Keywords | Field | DocType |
edge dependency,random graph,n vertex,random subset,graph property,p and G n,Stochastic order relation between G n,m,universal set,m element,chosen element,Random intersection graph,Hamilton cycles,p,Hamilton cycle,random intersection graph model,sharp threshold,Sharp threshold | Discrete mathematics,Graph,Combinatorics,Random graph,Vertex (geometry),Mathematics,Universal set | Journal |
Volume | Issue | ISSN |
411 | 40-42 | Theoretical Computer Science |
Citations | PageRank | References |
8 | 0.49 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charilaos Efthymiou | 1 | 209 | 15.44 |
| Paul G. Spirakis | 2 | 2222 | 299.05 |