Abstract | ||
---|---|---|
Let c be a positive constant. Suppose that r =o(n5/12) and the members of $({{[n]}\atopr})$ are chosen sequentially at random to form an intersectinghypergraph ${\cal H}$. We show that whp (A sequence ofevents ${\cal E}_1,\ldots,{\cal E}_n,\ldots$ is said to occurwith high probability (whp)$\lim_{n\to\infty}\Pr({\cal E}_n)=1$.) ${\cal H}$ consists of asimple hypergraph ${\cal S}$ of size˜(r/n1/3), a distinguishedvertex v and all r-sets that contain v andmeet every edge of ${\cal S}$. This is a continuation of the studyof such random intersecting systems started in (Bohman et al.,Electronic J Combinatorics (2003) R29) where the case r =O(n1/3) was considered. To obtain thestated result we continue to investigate this question in the rangeÉ(n1/3) d r do(n5/12). © 2006 Wiley Periodicals,Inc. Random Struct. Alg., 2007 |
Year | DOI | Venue |
---|---|---|
2007 | 10.1002/rsa.v30:1/2 | Random Structures and Algorithms |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Vertex (geometry),Constraint graph,Hypergraph,Mathematics | Journal | 30 |
Issue | Citations | PageRank |
1-2 | 4 | 0.77 |
References | Authors | |
5 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Alan M. Frieze | 2 | 4837 | 787.00 |
Ryan Martin | 3 | 144 | 14.43 |
M. Ruszinkó | 4 | 230 | 35.16 |
Cliff Smyth | 5 | 64 | 4.92 |