Online vertex-coloring games in random graphs (Q532126)

A fixed graph \(F\) is chosen. A random graph \(G(n,p(n))\) with \(n\) vertices and each edge included independently of all other edges with probability \(p(n)\) is generated. Then the vertices of the random graph are put in some order and revealed one by one (`online\') to a player Painter, together with all edges linking the newly exposed vertex to an earlier vertex in the order. Painter has a fixed number \(r\) of colours and has to assign one of these to each vertex immediately it is revealed. The objective for Painter is to avoid creating a monochromatic copy of \(F\): if she can avoid this still when all \(n\) vertices are coloured, she wins. We are concerned with when Painter can win the game a.a.s., i.e, with probability tending to 1 as \(n\rightarrow\infty\). More precisely, for a large class of graphs \(F\) including cliques and cycles, and any fixed number \(r\) of colours, we obtain an explicit function \(p_{0}=p_{0}(F,r,n)\) such that, by judicious choice of strategy, Painter a.a.s. succeeds in colouring the entire random graph if \(p=o(p_{0})\) but if \(p=\omega(p_{0})\), no matter what strategy Painter uses she fails. To state the main result, we need some notation about densities of subgraphs. For a graph \(H\) let \(v_{H}\), denote its number of vertices and \(e_{H}\) its number of edges. For any graph \(F\), define \[ m_{1}(F)=\max_{H\subseteq F}e_{H}/(v_{H}-1) \] and \[ \overline{m}_{1}^{r}(F)=\begin{cases} \max_{H\subseteq F} \frac{e_{H}}{v_{H}} & \text{if}\;r=1,\cr \max_{H\subseteq F}\frac{e_{H}+\overline{m}_{1}^{r-1}(F)} {v_{H}} & \text{if}\;r\geq 2.\end{cases} \] Now suppose \(F\) is a non-empty graph with an induced subgraph on \(v_{F}-1\) vertices, \(F^{\circ}\), such that \[ m_{1}(F^{\circ})\leq \overline{m}_{1}^{2}(F). \] Though this `precondition\'\, is only used in the upper bound proof (but cannot be totally avoided). The main result is now that, for any \(r\geq 1\), the threshold for the online \(F\)-avoidance vertex colouring game with \(r\) colours is \[ p_{0}(F,r,n)=n^{-1/\overline{m}_{1}^{r}(F)}. \] This is easily seen to imply that, e.g., when \(F=K_{\ell}\) a complete graph of order \(\ell\), we get \(p_{0}(K_{\ell},r,n)=n^{-2/(\ell (1-\ell^{-r}))}\) for \(\ell\geq 2\) and, when \(\ell\geq 3\) and \(F=C_{\ell}\) is a cycle of length \(\ell\), then \(p_{0}(C_{\ell},r,n)=n^{-(\ell-1)/(\ell(1-\ell^{-r}))}\). Note that this online game threshold will inevitably be at least as large as the threshold for there to be a copy of \(F\) in \(G(n,p)\) at all, and at most the threshold for the offline version of the game found by \textit{T. Łuczak, A. Ruciński} and \textit{B. Voigt} [``Ramsey properties of random graphs,'' J. Comb. Theory, Ser. B 56, No.\,1, 55--68 (1992; Zbl 0711.05041)]. In fact, the paper shows that the online threshold approaches the offline one as \(r\) grows. The techniques used include various density measure calculations, devising (inductively) a suitable strategy for the lower bound and using the Janson inequalities to obtain the upper bound.