Name
Abstract | ||
|---|---|---|
For 0 < γ ≤ 1 and graphs G and H , we write G [formula] H if any γ-proportion of the edges of G span at least one copy of H in G . As customary, we write C k for a cycle of length k . We show that, for every fixed integer l ≥ 2 and real γ > 0, there exists constant C = C ( l , γ) > 0 such that almost every random graph G n, p with p = p ( n ) ≥ Cn −1 + 1/(2 l − 1) satisfies G n,p [formula] C 2 l . In particular, for any fixed l ≥ 2 and γ > 0, this result implies the existence of very sparse graphs G with G [formula] C 2 l . |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1006/jctb.1995.1035 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
random graph,extremal problem,satisfiability | Journal | 64 |
Issue | ISSN | Citations |
2 | Journal of Combinatorial Theory, Series B | 23 |
PageRank | References | Authors |
2.05 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. E. Haxell | 1 | 212 | 26.40 |
| Yoshiharu Kohayakawa | 2 | 172 | 22.74 |
| T. Łuczak | 3 | 124 | 13.68 |