Random Structures and Algorithms · 1997 · 52 citations · 12 references
Natural SciencesMathematicsCombinatoricsDiscrete MathematicsProbability TheoryDirected Acyclic GraphsGraph AlgorithmsGraph TheoryProbabilistic CombinatoricsRamsey TheoryRamsey GraphsRamsey PropertyRamsey's TheoremRamsey-type TheoremsRandom Graph ModelsRandom Graph TheorySparse Random GraphsThreshold Functions
We consider the binomial random graph Gp and determine a sharp threshold function for the edge-Ramsey propertyfor all l1,…,lr, where Cl denotes the cycle of length l. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 245–276, 1997
12
Endre Szemerédi · Defense Technical Information Center (DTIC) · 1975 · 806 citations
Poisson approximation for large deviations
Svante Janson · Random Structures and Algorithms · 1990 · 215 citations
OnK 4-free subgraphs of random graphs
Yoshiharu Kohayakawa, Tomasz Łuczak, V. Rödl · COMBINATORICA · 1997 · 122 citations · Full text