The sub-exponential transition for the chromatic generalized Ramsey numbers (Q2322506): Difference between revisions

Define, for positive integers \(p\), \(q\), \(r\) with \(p\geq 3\) and \(2\leq q\leq \binom{p}{2}\) \(F_{\chi} (r,p,q)\) to be the smallest integer \(n\) for which every edge-colouring of \(K_{n}\) with \(r\) colours contains a \(p\)-chromatic subgraph receiving at most \(q-1\) colours on its edges. One can check that this is well-defined, e.g. because \(F_{\chi}(r,p,q)\) is bounded above by the so-called generalised Ramsey number \(F(r,p,q)\). Similarly say that an edge-colouring of a complete graph is \((p,q)\)-chromatic if the union of every \(q-1\) colour classes has chromatic number at most \(p-1\): then it is clear that \(F_{\chi}(r,p,q)\) is the smallest \(n\) for which there does not exist a chromatic \((p,q)\)-colouring of \(K_{n}\).\par If there is a chromatic \((p,q)\)-colouring of \(K_{n}\) with \(r\) colours, by partitioning the \(r\) colours into \(\lceil r/(q-1) \rceil\) sets of size at most \(q-1\), noting that each induces a \(p-1\) chromatic graph, and then using the product formula for chromatic numbers, we obtain the exponential upper bound \(F_{\chi}(r,p,q)\leq (p-1)^{\lceil r/(q-1) \rceil}\). Sometimes this crude-looking bound is tight: for example, one can show that \(F_{\chi}(r,2^{q}+1,q+1)=2^{r}+1\) whenever \(q\) divides \(r\). \textit{D. Conlon} et al. [Int. Math. Res. Not. 2015, No. 17, 8052--8084 (2015; Zbl 1342.05123)], in earlier work on this topic, asked if by contrast \(F_{\chi}(r,2^{q},q+1)=2^{o(r)}\) for \(q\geq 2\) and the main result of the paper under review is to prove this fact, which can be regarded as saying that there is a threshold for \(F_{\chi}(r,p,q)\) to be exponential in \(r\). Indeed, they prove a somewhat more precise statement about the \(2^{o(r)}\) term: one can show that \(F_{\chi}(r,p,q)\leq e^{Cr^{1-1/q}(\log(r)^{q})}\).