Premium
Asymmetric Ramsey properties of random graphs involving cliques and cycles
Author(s) -
Liebenau Anita,
Mattos Letícia,
Mendonça Walner,
Skokan Jozef
Publication year - 2023
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/rsa.21106
Subject(s) - conjecture , combinatorics , colored , mathematics , statement (logic) , property (philosophy) , brooks' theorem , discrete mathematics , chordal graph , graph , 1 planar graph , philosophy , materials science , epistemology , political science , law , composite material
We say thatG → ( F , H ) $$ G\to \left(F,H\right) $$ if, in every edge coloringc : E ( G ) → { 1 , 2 } $$ c:E(G)\to \left\{1,2\right\} $$ , we can find either a 1‐colored copy ofF $$ F $$ or a 2‐colored copy ofH $$ H $$ . The well‐known Kohayakawa‐Kreuter conjecture states that the threshold for the propertyG ( n , p ) → ( F , H ) $$ G\left(n,p\right)\to \left(F,H\right) $$ is equal ton − 1 / m 2 ( F , H )$$ {n}^{-1/{m}_2\left(F,H\right)} $$ , wherem 2 ( F , H ) $$ {m}_2\left(F,H\right) $$ is given bym 2 ( F , H ) : = maxe ( J ) v ( J ) − 2 + 1 / m 2 ( H ): J ⊆ F , e ( J ) ≥ 1 ,$$ {m}_2\left(F,H\right):= \max \left\{\frac{e(J)}{v(J)-2+1/{m}_2(H)}:J\subseteq F,e(J)\ge 1\right\}, $$ for any pair of graphsF $$ F $$ andH $$ H $$ withm 2 ( F ) ≥ m 2 ( H ) $$ {m}_2(F)\ge {m}_2(H) $$ . In this article, we show the 0‐statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques.