Premium
Threshold functions for asymmetric Ramsey properties involving cycles
Author(s) -
Kohayakawa Y.,
Kreuter B.
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199710)11:3<245::aid-rsa3>3.0.co;2-0
Subject(s) - ramsey's theorem , mathematics , combinatorics , property (philosophy) , random graph , ramsey theory , binomial (polynomial) , graph , discrete mathematics , function (biology) , enhanced data rates for gsm evolution , statistics , computer science , telecommunications , philosophy , epistemology , evolutionary biology , biology
We consider the binomial random graph G p and determine a sharp threshold function for the edge‐Ramsey property $$G_p\rightarrow (C^{l_1},\ldots,C^{l_r})$$ for all l 1 ,…, l r , where C l 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