Sharp Ramsey thresholds for large books

MaRDI QIDQ6426199zbMATH OpenFDO

Authors Qizhong Lin, Ye Wang

Publication date 11 February 2023

Abstract: For graphs $G$ and $H$, let $GoH$ signify that any red/blue edge coloring of $G$ contains a monochromatic $H$. Let $G(N,p)$ be the random graph of order $N$ and edge probability $p$. The sharp thresholds for Ramsey properties seemed out of hand until a general technique was introduced by Friedgut ({em J. AMS} 12 (1999), 1017--1054). In this paper, we obtain the sharp Ramsey threshold for the book graph $B_n^{(k)}$, which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$. In particular, for every fixed integer $kge1$ and for any real $c>1$, let $N=c{2}^{k}n$. Then for any real $gamma>0$, [ lim_{n o infty} Pr(G(N,p) o B_n^{(k)})= left{ �egin{array}{cl} 0 & mbox{if $plefrac1c^{1/k}(1-gamma)$,} \ 1 & mbox{if $pgefrac1c^{1/k}(1+gamma)$}. end{array} ight. ] The sharp Ramsey threshold $frac1c^{1/k}$ for $B_n^{(k)}$, e.g. a star, is positive although its edge density tends to zero.

This page was built for publication: Sharp Ramsey thresholds for large books

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426199)