Ramsey with purple edges Thomas Lesgourgues, Anita Liebenau, Nye Taylor Abstract Motivated by a question of Angell, we investigate a variant of Ramsey numbers where some edges are coloured simultaneously red and blue, which we call purple. Specifically, we are interested in the largest number g = g ⁡ ( n , s , t ) g=g(n;s,t) , for some s s and t t and n < R ⁡ ( s , t ) n0 small enough, we have g(n;s,cn)=(1-o(1))\;\mathrm{{\bf RT}}_{s}(n,cn). Our next theorem centres on triangles, where we explore the behaviour of g(n;3,t) for a broader range of t . Let us first recall what is known about \mathrm{{\bf RT}}_{s}(n,cn) when s=3 . It follows from Mantel’s theorem that \mathrm{{\bf RT}}_{3}(n,cn)=\lfloor n^{2}/4\rfloor for any c\geq 1/2 , while Brandt’s work [ 11 ] covers the range c<1/3 asymptotically. In the intermediate range, Andrásfai proved that certain blow-ups of C_{5} are extremal constructions for \mathrm{{\bf RT}}_{3}(n,cn) when c\in[2/5,1/2] , and conjectured that similar constructions should provide extremal examples for the remaining range of c . Łuczak, Polcyn, and Reiher [ 31 , 33 ] confirmed this conjecture for c\in[4/11,2/5] and recently announced a proof of the conjecture. We refer the reader to Subsection 2.2 , for a detailed presentation of these results and the Andrásfai Conjecture. Using these, we give an almost complete picture of g(n;3;t) , showing first that 1.1 is asymptotically correct when t=cn for every c for which the Andrásfai Conjecture holds. We also bound g(n;3,t) in terms of Ramsey-Turán numbers when t is sublinear. Theorem 1.4 . (i) For all c\in\left(0,1\right]\setminus\left(\frac{1}{3},\frac{4}{11}\right) we have g(n;3,cn)=(1-o(1))\;\mathrm{{\bf RT}}_{3}(n,cn). (1.2) Moreover, assuming the Andrásfai Conjecture, we obtain that the same result holds also for c\in\left(\frac{1}{3},\frac{4}{11}\right) . (ii) For every \varepsilon>0 there exists \delta>0 such that for sufficiently large n and t=(1+\varepsilon)\sqrt{2n\log n} , we have g(n;3,t)\geq\delta\cdot\mathrm{{\bf RT}}_{3}(n,t). Moreover, if t\gg\sqrt{n\log n} , we have g(n;3,t)\geq\Big({\frac{1}{2}-o(1)}\Big)\;\mathrm{{\bf RT}}_{3}(n,t). We remark that, even without assuming the Andrásfai Conjecture, Theorem 1.4 (i) for c=1/3 implies that g(n;3,c^{\prime}n) is at least 0.91\,\mathrm{{\bf RT}}_{3}(n,c^{\prime}n) for c^{\prime} in the gap range c^{\prime}\in\left(1/3,4/11\right) . Next we note that the lower bound on t in Theorem 1.4 (ii) is essentially best possible. Indeed, the current, best known bounds on R(3,t) are \left(\frac{1}{4}-o(1)\right)\,\frac{t^{2}}{\log t}\leq R(3,t)\leq(1+o(1))\,\frac{t^{2}}{\log t}, (1.3) due to Bohman and Keevash [ 8 ] , Fiz Pontiveros, Griffiths, and Morris [ 24 ] , and Shearer [ 44 ] . The upper bound implies that g(n;3,t) is undefined if t\leq\gamma\sqrt{n\log n} , for any \gamma<1/\sqrt{2} . Moreover, the lower bound in ( 1.3 ) is conjectured to be asymptotically tight in both [ 8 , 24 ] . If true, this would imply that g(n;3,t) is undefined if t\leq\gamma\sqrt{n\log n} , for any \gamma<\sqrt{2} , that is, Theorem 1.4 (ii) would cover practically the full range of t . Finally, we observe that we cannot expect the constant \delta in Theorem 1.4 (ii) to be close to 1 when t is within a constant factor of \sqrt{n\log n} . Indeed, we have the following. Observation 1.5 . Let \gamma and \delta be real numbers satisfying 0<\delta<1/(2\gamma^{2})<1 . Then there exists an integer n_{0} such that for all n\geq n_{0} and t=\gamma\sqrt{n\log n} we have that g(n;3,t)<(1-\delta)\cdot\mathrm{{\bf RT}}_{3}(n,t), assuming g(n;3,t) is well-defined. We would like to thank Anastos, Das, Morris and Rathke [ 2 ] for pointing this fact out to us, which is a simple consequence of Shearer’s proof of the lower bound in ( 1.3 ). We provide the details in Section 4 . To discuss smaller ranges of t , define the inverse Ramsey number , denoted by R^{-1}(s,n) , to be the minimum independence number of a K_{s} -free graph on n vertices. Observe that g(n;s,t) is defined if and only if R^{-1}(s,n)0 such that for any fixed s\geq 3 , for n large enough and any t\in\left[R^{-1}(s,n)\log n,n\right] , we have p\cdot\mathrm{{\bf RT}}_{s}(n,t/\log n)\leq g(n;s,t). To compare this general lower bound with the upper bound in ( 1.1 ), it is useful to understand the behaviour of the Ramsey-Turán numbers \mathrm{{\bf RT}}_{s}(n,t) and \mathrm{{\bf RT}}_{s}(n,t^{\prime}) when t and t^{\prime} are not too far apart. For example, Theorem 1.10 in [ 25 ] implies that \mathrm{{\bf RT}}_{4}(n,t)\geq n^{2}/8+o(n^{2}) if t=n/(\log n)^{K} , for any constant K>1 . Thus, Theorem 1.6 implies that for t=n/(\log n)^{K-1} we have that g(n;s,t)=\Theta(n^{2}) . Sudakov proved that if t=e^{-\omega((\log n)^{1/2})}n then \mathrm{{\bf RT}}_{4}(n,t)=o(n^{2}) , from which we infer via ( 1.1 ) that g(n;4,t)=o(n^{2}) for such t . More generally, Balogh, Hu, and Simonovits [ 5 ] showed that \mathrm{{\bf RT}}_{s}(n,t)=o(n^{2}) when t=R^{-1}(s,n)n^{\varepsilon} for some \varepsilon\leq 1/s^{2} . They also gave a more precise range of t where a transition from \mathrm{{\bf RT}}_{s}(n,t)=\Theta(n^{2}) to \mathrm{{\bf RT}}_{s}(n,t)=o(n^{2}) occurs, assuming the following long-standing conjecture on Ramsey numbers. Conjecture 1.7 . For every integer s\geq 3 , there exist \vartheta=\vartheta(s)>0 such that for any t large enough R(s-1,t)t^{\vartheta}\leq R(s,t). Assuming this conjecture, it is proved in [ 5 ] that \mathrm{{\bf RT}}_{s}(n,R^{-1}(\ell,n)) is quadratic in n if \ell\leq\frac{s+1}{2} and sub-quadratic if \ell>\frac{s+1}{2} . Using this result and our probabilistic bound from Theorem 1.6 , we derive the following general behaviour of g(n;s,t) . Theorem 1.8 . For any s\geq 3 , assuming Conjecture 1.7 , (i) if t\geq R^{-1}\left(\frac{s+1}{2},n\right)\log n , then g(n;s,t)=\Theta(n^{2}) . (ii) if t\leq R^{-1}\left(\frac{s+3}{2},n\right) , then g(n;s,t)=o(n^{2}) . Organisation. In Section 2 we introduce notation and the key tool that will be used throughout the article. Section 3 is devoted to the proof of Theorem 1.4 (i) . Section 4 concludes the triangle case, proving Theorem 1.4 (ii) . In Section 5 , we present our results for general s proving Theorems 1.3 and 1.6 . We conclude the article with some computational results in Section 6 and discussions and open problems in Section 7 . 2 Preliminaries Notation. We use standard graph theoretic notation. In particular, given a graph G , we write V(G) for its vertex set and E(G) for its edge set, with v(G)=|V(G)| and e(G)=|E(G)| . We further write \alpha(G) , \omega(G) , and \delta(G) for the independence number, for the clique number, and for the minimum degree of G , respectively. Given graphs F and G , we say that G is F -free if G does not contain a subgraph that is isomorphic to F . A blow-up of an n -vertex graph G is a graph obtained by replacing each vertex i of G by an independent set V_{i} , and each edge ij of G by a complete bipartite graph between the parts V_{i} and V_{j} . A blow-up is called equitable if \big||V_{i}|-|V_{j}|\big|\leq 1 for all i,j . We often abuse notation identifying a graph with its edge set. For example, we write \alpha(R) for the independence number of the spanning subgraph of K_{n} induced on the edges of R , for a 3 -colouring R\cup B\cup P of K_{n} , and similarly for the clique number \omega(R) . Furthermore, for a subset S\subseteq V(K_{n}) , we write R[S] for the subgraph induced on the vertices of S and the edges in R . Unless stated otherwise, logarithms are in base 2 . We use the standard Landau symbols O , \Omega , \Theta , and o to denote the asymptotic behaviour of functions with respect to n , the number of vertices, tending to \infty , as well as f(n)\gg g(n) to denote g(n)=o(f(n)) . We say that an event A(n) holds with high probability if \lim_{n\to\infty}\mathbb{P}[A(n)]=1 . 2.1 Blow-up colouring We start with a general construction of a red/blue/purple colouring R\cup B\cup P of K_{n} that we will use throughout the article. Definition 2.1 (Blow-up colouring) . Let n\geq k\geq 1 be integers and let G be a graph on k vertices v_{1},\ldots,v_{k} . The n -blow-up colouring of G is a colouring R\cup B\cup P of K_{n} defined as follows. Let H be an equitable blow-up of G created by replacing every vertex v_{i}\in V(G) by a set of vertices V_{i} of size either \beta^{-}=\lfloor\frac{n}{k}\rfloor or \beta^{+}=\lceil\frac{n}{k}\rceil , such that \sum_{i}|V_{i}|=n , and replacing every edge v_{i}v_{j} of G by a complete bipartite graph between the sets V_{i} and V_{j} . For each i\in[k] , denote the vertices of V_{i} by \{u_{1}^{i},\ldots,u_{\beta^{-}}^{i}\} or \{u_{1}^{i},\ldots,u_{\beta^{+}}^{i}\} . For every edge v_{i}v_{j} of G , and for every \ell\in[\beta^{+}] , colour the edge u_{\ell}^{i}u_{\ell}^{j} of H , if it exists, red. Colour all other edges of H purple. Finally, colour all edges in the complement of H blue. Let R be the set of all red edges, B the set of all blue edges, and P the set of all purple edges. An illustration of a 10 -blow-up colouring of the cycle graph C_{4} can be found in Figure 2.1 . We remark that n -blow-up colourings are not uniquely defined, as their definition is up to the choice of vertices being replaced by sets of size \beta^{+} or \beta^{-} . However, in every n -blow-up colouring of a graph G , the red edges form \beta^{-} vertex-disjoint copies of G , and possibly a vertex-disjoint copy of an induced subgraph of G . R P Figure 2.1: This is an example of red and purple edges in a 10-blow-up colouring of C_{4} . The following proposition captures the core properties of blow-up colourings. Proposition 2.2 . Let G be a graph on k vertices and n\geq k be an integer. Each n -blow-up colouring R\cup B\cup P of G satisfies (i) \omega(R\cup P)=\omega(G) , (ii) \alpha(R)=\omega(B\cup P)\leq\left\lceil n/k\right\rceil\,\alpha(G) , (iii) \big||P|-e(G)\,n^{2}/k^{2}\big|\leq e(G)3n/k, and (iv) |R|\leq e(G)\,(n/k+1) . Proof. Let R\cup B\cup P be an n -blow-up colouring of G . Trivially, any edge in R\cup P corresponds to an edge in G , while for any two vertices u,v\in V_{i} for some i , we have uv\not\in R\cup P . Therefore \omega(R\cup P)=\omega(G) , verifying (i) . The red graph R consists of \left\lceil\frac{n}{k}\right\rceil vertex-disjoint copies of induced subgraphs of G that cover all n vertices. Therefore, \alpha(R)\leq\alpha(G)\,\left\lceil\frac{n}{k}\right\rceil , proving (ii) . To verify (iii) and (iv) , let m=\left\lfloor\frac{n}{k}\right\rfloor and note that R^{-}\subseteq R\subseteq R^{+},\qquad P^{-}\subseteq P\subseteq P^{+}, where R^{-}\cup B^{-}\cup P^{-} is an (mk) -blow-up colouring of G , and where R^{+}\cup B^{+}\cup P^{+} is an ((m+1)k) -blow-up colouring of G . We then obtain e(G)(m^{2}-m)\leq|P|\leq e(G)\big((m+1)^{2}-(m+1)\big), hence e(G)\Big(\frac{n^{2}}{k^{2}}-\frac{3n}{k}+1\Big)\leq|P|\leq e(G)\Big(\frac{n^{2}}{k^{2}}+\frac{n}{k}+1\Big), and \left\lvert|P|-e(G)\,\frac{n^{2}}{k^{2}}\right\rvert\leq e(G)\frac{3n}{k}.\qed 2.2 Ramsey-Turán theory In this subsection, we summarise results on Ramsey-Turán numbers that we utilise in this paper. We start with Turán’s Theorem. For non-negative integers s and n , denote by T_{n,s} the equitable blow-up of K_{s} on n vertices. Theorem 2.3 (Turán [ 52 ] ) . For s\geq 3 , the maximal number of edges among all n -vertex K_{s} -free graphs is obtained uniquely by T_{n,s-1} . Since the independence number of T_{n,s-1} is equal to \lceil n/(s-1)\rceil , we obtain immediately that \displaystyle\mathrm{{\bf RT}}_{s}(n,t) \displaystyle=e(T_{n,s-1})=\frac{1}{2}\Big(1-\frac{1}{s-1}\Big)n^{2}+O(n) (2.1) for all t>n/(s-1) . It is clear that the red/purple subgraph R\cup P of an n -blow-up colouring of K_{s-1} is exactly the Turán graph T_{n,s-1} and therefore, Proposition 2.2 implies that g(n;s,t) is asymptotically equal to \mathrm{{\bf RT}}_{s}(n,t) when t>n/(s-1) . Corollary 2.4 . For any s\geq 3 , and c>1/(s-1) , we have g(n;s,cn)=\big(1-O(1/n)\big)\,\mathrm{{\bf RT}}_{s}(n,cn). Proof. Let R\cup B\cup P be an n -blow-up colouring of K_{s-1} for some large enough n . The graph R\cup P is the Turán graph T_{n,s-1} which is K_{s} -free and has independence number n/(s-1)0 . Let d,k be integers such that c-\eta<\frac{d}{k}\frac{n^{2}}{2}(c-\eta). Since \eta>0 can be chosen arbitrarily small, we obtain the desired result. ∎ Recall that Conjecture 2.6 asserts that for every integer t\in(n/3,n/2) , canonical blow-ups of Andrásfai graphs are extremal for \mathrm{{\bf RT}}_{s}(n,t) . We now prove that these graphs yield a lower bound for g(n;3,t) up to some linear error term. Theorem 3.2 . For every c\in\left(\frac{1}{3},\frac{1}{2}\right) and positive integer n , we have g(n;3,t+1)\geq e(\Gamma(n;k,t))-O(n), where t=\lceil cn\rceil and k is the unique integer such that kn/(3k-1)\leq t<(k-1)n/(3k-4) . Proof. Fix c\in(1/3,1/2) , and let k\geq 2 be the unique integer such that k/(3k-1)\leq c<(k-1)/(3k-4) . Let n be large enough, in particular such that t:=\lceil cn\rceil satisfies kn/(3k-1)\leq t<(k-1)n/(3k-4) . Let \Gamma(n;k,t) be the canonical blow-up of the Andrásfai graph \Gamma_{k} defined in Subsection 2.2 . Label the vertices of \Gamma(n;k,t) as \displaystyle V(\Gamma(n;k,t))= \displaystyle\big\{\{u_{1}^{i},\ldots,u_{3t-n}^{i}\}\colon i\in[3k-1]\setminus\{1,k,2k\}\big\} \displaystyle\cup \displaystyle\big\{\{u_{1}^{i},\ldots,u_{(k-1)n-(3k-4)t}^{i}\}\colon i\in\{1,k,2k\}\big\}. We note that the canonical blow-up is composed of (3k-4) “large” sets of (3t-n) vertices, and 3 sets of size (k-1)n-(3k-4)t . We define an edge colouring R\cup B\cup P of K_{n} in an analogous fashion to the blow-up colourings from Definition 2.1 , but using the canonical blow-up \Gamma(n;k,t) instead of an equitable one. For any i,j\in[3k-1] and any \ell\in[3t-n] , if u_{i}^{\ell}u_{j}^{\ell} is an edge of \Gamma(n;k,t) , then colour that edge red. Colour all other edges of \Gamma(n;k,t) in purple. Colour all edges not in \Gamma(n;k,t) in blue. Similarly to blow-up colourings, the red edges form (3t-n) vertex-disjoint copies of either \Gamma_{k} or a subgraph of \Gamma_{k} , hence |R|\leq(3t-n)e(\Gamma_{k})\leq 3k^{2}n . Observe that R\cup P is a triangle-free graph since \Gamma_{k} is. We now study the independence number of R . The red edges can be decomposed into (3t-n) vertex-disjoint graphs R_{\ell} , \ell\in[3t-n] , where R_{\ell} is a copy of \Gamma_{k} if \ell\leq(k-1)n-(3k-4)t , and a copy of \Gamma_{k}\setminus\{1,k,2k\} otherwise. It is not hard to see that every independent set of \Gamma_{k} of size k contains a vertex from \{1,k,2k\} . Therefore \alpha(R_{\ell})\leq k-1 if \ell>(k-1)n-(3k-4)t , and \alpha(R_{\ell})\leq k otherwise. It follows that \alpha(R)\leq\bigcup_{\ell\in[3t-n]}\alpha(R_{\ell})\leq(3t-n)\cdot(k-1)+[(k-1)n-(3k-4)t]\cdot 1=t, and therefore g(n;3,cn+1)=g(n;3,t+1)\geq|P|=e(\Gamma(n;k,t))-|R|\geq e(\Gamma(n;k,t))-3k^{2}n. We obtain the desired result as k depends only on c . ∎ We are now ready to prove Theorem 1.4 (i) , that is g(n;3,cn)=(1-o(1))\mathrm{{\bf RT}}_{3}(n,cn) when c\in\left(0,1\right]\setminus\left(\frac{1}{3},\frac{4}{11}\right) . Proof of Theorem 1.4 (i) . Recall that, for c\geq 1/2 , the theorem statement is a simple consequence of Turán’s theorem and the blow-up colouring, see Corollary 2.4 . When c\leq 1/3 , Theorem 1.4 (i) follows immediately by combining Theorems 3.1 , 1.1 and 2.5 . For the remaining range, let k\geq 2 be the unique integer such that k/(3k-1)\leq c<(k-1)/(3k-4) . Let n be large enough, in particular, such that t:=\lceil cn\rceil satisfies kn/(3k-1)\leq t0 , there exists k_{0} such that for all k\geq k_{0} there exists a triangle-free graph G=G(k,\varepsilon) on k vertices satisfying \alpha(G)\leq(1+\varepsilon)\sqrt{2k\log k},\quad\text{ and }\quad e(G)\geq\frac{1}{2\sqrt{2}}(1-\varepsilon)k^{3/2}\sqrt{\log k}. We split the proof of Theorem 1.4 (ii) into two subcases. First, when t is sufficiently larger than 4\sqrt{n\log n} , we use the graph produced by Theorem 4.1 as a black box. Then, for smaller t we slightly modify the triangle-free process to produce a desired colouring. For both subcases, we prove a stronger statement, relating g(n;3,t) to nt/2 instead of \mathrm{{\bf RT}}_{3}(n,t) . The results follow immediately by 2.2 . Theorem 4.2 . For every \gamma>4 there exist n_{0}\geq 1 and \delta\in(0,1/2) such that for all n\geq n_{0} and t=\gamma\sqrt{n\log n} we have g(n;3,t)\geq\delta\,\frac{nt}{2}. Furthermore, if t\gg\sqrt{n\log n} then g(n;3,t)\geq\Big(\frac{1}{2}-o(1)\Big)\,\frac{nt}{2}. Proof. We prove the first part of the theorem by showing that for any constant \gamma>4 , there exist \delta<1/2 , \varepsilon\in(0,1) , \zeta>2 and n_{0}\geq 1 such that the following holds for any n\geq n_{0} . There exists an integer k\approx n/\zeta^{2} such that the n -blow-up colouring of the triangle-free-process G=G(k,\varepsilon) as guaranteed by Theorem 4.1 yields a colouring R\cup B\cup P such that \alpha(R)<\gamma\sqrt{n\log n},\quad\text{ and }\quad|P|\geq\delta\cdot\frac{\gamma\;n^{3/2}\sqrt{\log n}}{2}. Let \gamma>4 , and let \varepsilon>0 be sufficiently small such that \varepsilon<\frac{1}{4},\text{ and }\qquad\gamma>\frac{4(1+\varepsilon)}{1-\varepsilon}. Let \zeta>2 be such that \gamma=\sqrt{2}\;\frac{1+\varepsilon}{1-\varepsilon}\Big(\zeta+\frac{1}{\zeta}\Big). (4.1) We note that \gamma>4(1+\varepsilon)/(1-\varepsilon) implies that such a choice of \zeta is always possible, that \zeta is increasing with \gamma , and that we indeed have \zeta>2 . Let n be large enough, t=\gamma\sqrt{n\log n} , and let k be the smallest integer such that n\leq\zeta^{2}k . Then \zeta^{2}(k-1)3 , by 4.2 and since \varepsilon<1/4 and \zeta>2 . It follows that |P|\geq\delta tn/2 for some \delta=\delta(\gamma,\zeta)>0. For the second part, when t\gg\sqrt{n\log n} , we reason similarly, with some adjustments since we need more precise estimates on \delta . Observe that we can assume that t=o(n) as otherwise the result follows from Theorem 1.4 (i) . Let \varepsilon>0 , let n be large enough and let \gamma=t/\sqrt{n\log n} . Recall that here we assume \gamma\to\infty as n\to\infty . Define \zeta by \gamma=\sqrt{2}\;\frac{(1+\varepsilon)^{2}}{1-\varepsilon}\Big(\zeta+\frac{1}{\zeta}\Big)\Big(1-\frac{2\log\zeta}{\log n}\Big)^{1/2}. Note that \zeta=\Theta(\gamma) , and thus our assumptions on t imply that 1\ll\zeta\ll\sqrt{n/\log n}. Again, let k be the smallest integer such that n\leq\zeta^{2}k . Then k\leq(n/\zeta^{2})^{(1+\varepsilon)^{2}} for n large enough, and thus, \sqrt{\log k}\leq(1+\varepsilon)\sqrt{\log n}\cdot\Big(1-\frac{2\log\zeta}{\log n}\Big)^{1/2}. The computations of \alpha(R) and |P| are now similar to the first case. From Propositions 2.2 and 4.3 we deduce that \displaystyle\alpha(R)\leq(1+\varepsilon)\sqrt{2k\log k}\left\lceil\frac{n}{k}\right\rceil\leq\frac{(1+\varepsilon)^{2}}{1-\varepsilon}\sqrt{2n\log n}\Big(\zeta+\frac{1}{\zeta}\Big)\Big(1-\frac{2\log\zeta}{\log n}\Big)^{1/2}=\gamma\sqrt{n\log n}, and \displaystyle|P| \displaystyle\geq e(G)\Big(\frac{n^{2}}{k^{2}}-\frac{3n}{k}\Big)\geq\frac{1-\varepsilon}{2\sqrt{2}}\,k^{3/2}\sqrt{\log k}\,\frac{n^{2}}{k^{2}}(1-o(1)) \displaystyle=\frac{1-\varepsilon}{\gamma\sqrt{2}}\,\Big(\frac{n\log k}{k\log n}\Big)^{1/2}\,\frac{\gamma n^{3/2}\sqrt{\log n}}{2}(1-o(1)), (4.4) where we used that k=o(n) in this case. Now n/k\geq\zeta^{2}(1-1/k)=\zeta^{2}(1-o(1)) and \sqrt{\log k}\geq\sqrt{\log n}\cdot\Big(1-\frac{2\log\zeta}{\log n}\Big)^{1/2}, by definition of k . Thus, 4.4 implies that \displaystyle|P| \displaystyle\geq(1-o(1))\frac{(1-\varepsilon)\zeta}{\gamma\sqrt{2}}\,\Big(1-\frac{2\log\zeta}{\log n}\Big)^{1/2}\,\frac{tn}{2} (4.5) \displaystyle=(1-o(1))\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)^{2}}\,\frac{tn}{4}, (4.6) by definition of \zeta and since \zeta\to\infty . The theorem follows since \varepsilon>0 is arbitrary. ∎ To cover the remaining range of t , that is t=\gamma\sqrt{n\log n} for \sqrt{2}<\gamma\leq 4 , we need a much more refined analysis of the triangle-free process. Recall that we denote by G_{i} the random graph obtained from the triangle-free process after adding i edges. Furthermore, for a given \varepsilon>0 we let m^{*}(\varepsilon):=\Big(\frac{1}{2\sqrt{2}}-\varepsilon\Big)n^{3/2}\sqrt{\log n}. (4.7) Fiz Pontiveros, Griffiths, and Morris [ 24 ] defined a sequence of good events, denoted here by \mathcal{E}(m) for simplicity, such that if \mathcal{E}(m) holds then there are still free edges that do not close a triangle with G_{m} , implying that the triangle-free process has not stopped yet. They proved the following proposition. Theorem 4.3 (Fiz Pontiveros, Griffiths, and Morris [ 24 ] Theorems 6.9 and 7.2) . For every sufficiently small constant \varepsilon>0 , and every n large enough, let m=m^{*}(\varepsilon) . Then, (i) \mathcal{E}(m) holds with probability at least 1-n^{-\log n} . (ii) With probability at least 1-e^{-\sqrt{n}} either \mathcal{E}(m) fails or \alpha(G_{m})<\left(\sqrt{2}+10\sqrt{\varepsilon}\right)\sqrt{n\log n} . We remark that [ 24 , Proposition 7.2] is stated in terms of G_{n,\triangle} , that is the final random graph produced by the triangle-free process. However, the stronger statement of Theorem 4.3 (ii) is easily extracted from the proof in [ 24 , Section 7.7] . We use these results to prove the following theorem which, together with 2.2 , concludes the proof of Theorem 1.4 (ii) . Theorem 4.4 . For every \varepsilon>0 , there exists a constant \delta>0 such that for n large enough and t=(\sqrt{2}+\varepsilon)\sqrt{n\log n} we have g(n;3,t)\geq\delta nt/2. Proof. Observe that, by monotonicity, it is sufficient to prove the statement for \varepsilon small enough. Therefore let \varepsilon>0 be small enough and n be large enough such that Theorem 4.3 holds. Let \varepsilon_{1}:=\varepsilon^{2}/100 , and fix a real number \varepsilon_{2}\in(0,\varepsilon_{1}) . Let m_{1}=m^{*}(\varepsilon_{1}) and m_{2}=m^{*}(\varepsilon_{2}) as given by 4.7 . Our goal is to follow the triangle-free process up to m_{2} , colouring all m_{1} first edges in red, and then the remaining m_{2}-m_{1} edges in purple. We first condition the triangle-free process on \mathcal{E}(m_{2}) holding. Because we have m_{2}>m_{1} , we know that \mathcal{E}(m_{1}) holds, and therefore by Theorem 4.3 , \mathbb{P}[\alpha(G_{m_{1}})\geq t\,|\,\mathcal{E}(m_{2})]\leq\frac{e^{-\sqrt{n}}}{1-n^{-\log n}}=o(1). We therefore select an outcome of the triangle-free process such that \mathcal{E}(m_{2}) holds and \alpha(G_{m_{1}})0 . Let d,k be non-negative integers such that (c-\eta)\ell<\frac{d}{k}\frac{n^{2}}{2\ell}(c-\eta), and |R|\leq e(G)\frac{n/\ell+k}{k}=O(n). We define a colouring R^{\prime}\cup B^{\prime}\cup P^{\prime} of F\cong K_{n} as follows. We partition the vertices of F into \ell disjoint sets V_{1},\ldots,V_{\ell} of size n/\ell . For each i\in[\ell] , we embed a copy of the colouring R\cup B\cup P on the vertices V_{i} . For each i\neq j\in[\ell] we colour the edges between V_{i},V_{j} in red and purple (with no blue edges) such that the resulting R^{\prime} will be isomorphic to the so-called strong product R\boxtimes K_{\ell} . Specifically, for i\neq j , v_{i}\in V_{i} and v_{j}\in V_{j} , colour the edge v_{i}v_{j} • red if v_{i} and v_{j} are copies of the same vertex of the colouring R\cup B\cup P ; • red if v_{i} and v_{j} are copies of distinct vertices u,w in R\cup B\cup P such that the edge uw is in R ; and • purple otherwise. First note that R^{\prime}\cup P^{\prime} is K_{2\ell+1} -free, since (R^{\prime}\cup P^{\prime})[V_{i}] is a triangle-free graph for every i\in\ell . Next, it is not hard to see that \alpha(R^{\prime})\leq\alpha(R) . Indeed, every U\subseteq V(F) that is independent in R^{\prime} can contain at most one copy of u , for each u\in V(R\cup B\cup P) . Thus, U=\{u_{1}^{j_{1}},\ldots,u_{h}^{j_{h}}\} , where u_{1},\ldots,u_{h} are distinct vertices of V(R\cup B\cup P) , and u_{i}^{j_{i}} is the copy of u_{i} in V_{j_{i}} for every 1\leq i\leq h . But this set U is independent in R^{\prime} if and only if the set of vertices \{u_{1},\ldots,u_{h}\} is an independent set in R . Therefore, \alpha(R^{\prime})\leq\alpha(R)0 can be chosen arbitrarily small, we obtain the desired result. ∎ We now turn our attention to the case of even cliques. Modifying the Bollobás–Erdős construction [ 9 ] for the study of \mathrm{{\bf RT}}_{4}(n,t) , Fox, Loh, and Zhao [ 25 ] proved the existence of the following graph. Theorem 5.2 (Fox, Loh, and Zhao [ 25 ] ) . For every 0\delta>0 be arbitrarily small constants. Let n be large enough, and without loss of generality, divisible by 3\ell-2 . Let k=2\lfloor\log\log n\rfloor,\quad\varepsilon=\frac{4(\log\log k)^{3/2}}{\log^{1/2}k},\quad a=\frac{(3\ell-2)}{4}(c-\eta). For n large enough, observe that a\geq\frac{1}{\varepsilon k}+\varepsilon . Therefore, there exists a K_{4} -free graph G_{4} be on k vertices such that e(G_{4})\geq\frac{1}{2}\Big(\frac{1}{4}+a-a^{2}-2\varepsilon\Big)k^{2}\quad\text{and}\quad\alpha(G_{4})\leq ak, by Theorem 5.2 . Let R_{4}\cup B_{4}\cup P_{4} be a (4n)/(3\ell-2) -blow-up colouring of G_{4} . It follows from Proposition 2.2 that R_{4}\cup P_{4} is a K_{4} -free graph such that \displaystyle\alpha(R_{4})\leq\left\lceil\frac{4n}{k(3\ell-2)}\right\rceil\alpha(G_{4})\leq\frac{4na}{(3\ell-2)}+ak=(c-\eta)n+ak<(c-\delta)n, (5.1) for n large enough. We also obtain from Propositions 2.2 and 5.2 that the number of purple edges is given by \displaystyle|P_{4}| \displaystyle\geq e(G_{4})\Big(\frac{(4n)^{2}}{k^{2}(3\ell-2)^{2}}-\frac{12n}{k(3\ell-2)}\Big)\geq\frac{1}{2}\Big(\frac{1}{4}+a-a^{2}-o(1)\Big)\frac{(4n)^{2}}{(3\ell-2)^{2}} \displaystyle=\frac{n^{2}}{2}\Big(\frac{4}{(3\ell-2)^{2}}+\frac{4(c-\eta)}{(3\ell-2)}-(c-\eta)^{2}-o(1)\Big). (5.2) Observe that if \ell=2 , we have 3\ell-2=4 and we are done since \eta is arbitrarily small. Assume now that \ell>2 , and let d , h be integers such that \frac{(3\ell-2)}{3}(c-\eta)<\frac{d}{h}<\frac{(3\ell-2)}{3}(c-\delta)<\frac{1}{3} and such that Theorem 2.5 guarantees the existence of a triangle-free d -regular graph G_{3} on h vertices with independence number d . Let R_{3}\cup B_{3}\cup P_{3} be a (3n)/(3\ell-2) -blow-up colouring of G_{3} . It follows from Proposition 2.2 that for n large enough, R_{3}\cup P_{3} is a triangle-free graph with \alpha(R_{3})\leq\left\lceil\frac{3n}{h(3\ell-2)}\right\rceil\alpha(G_{3})\leq\Big(\frac{3d}{h(3\ell-2)}+\frac{d}{n}\Big)n<(c-\delta)n, (5.3) and |P_{3}|\geq e(G_{3})\Big(\frac{(3n)^{2}}{h^{2}(3\ell-2)^{2}}-\frac{9n}{h(3\ell-2)}\Big)\geq\frac{3(c-\eta)}{2(3\ell-2)}n^{2}. (5.4) We now define a colouring R\cup B\cup P of F\cong K_{n} as follows. Informally, we take a copy of R_{4}\cup B_{4}\cup P_{4} and (\ell-2) vertex-disjoint copies of R_{3}\cup B_{3}\cup P_{3} . The edges between any two of these copies are coloured red randomly, with probability p , and purple with probability 1-p . We show that the independence number of R is not much larger than the one of each R_{i} . More formally, partition the vertices of F into one set V_{1} of size (4n)/(3\ell-2) and \ell-2 sets V_{2},\ldots,V_{\ell-1} of size (3n)/(3\ell-2) each. Embed a copy of the colouring R_{4}\cup B_{4}\cup P_{4} into F[V_{1}] , and for each i\in\{2,\ldots,\ell-1\} , embed a copy of R_{3}\cup B_{3}\cup P_{3} in F[V_{i}] . Let p\in(0,1) be such that 1/n\ll p\ll 1 , and for i,j\in\binom{[\ell-1]}{2} , colour each edge between V_{i} and V_{j} in red independently at random with probability p , and purple otherwise. Claim 5.4 . For every \mu>0 , the following properties are satisfied with probability 1-o(1) as n\to\infty . (P1) There are o(n^{2}) red edges between any two distinct sets V_{i} and V_{j} . (P2) For all sets X\subseteq V_{i} and Y\subseteq V_{j} , with i\neq j , such that |X||Y|\geq\mu n^{2} , there exists a red edge between X and Y . Proof. (P1) is true for p\ll 1 by standard concentration results on the number of edges in the binomial random graph. Fix two sets X\subseteq V_{i} and Y\subseteq V_{j} such that |X||Y|\geq\mu n^{2} . The probability that there is no red edge between X and Y is (1-p)^{|X||Y|}\leq\exp\left(-\mu pn^{2}\right) . There are at most 2^{2n} choices of sets X,Y . (P2) follows immediately from the union bound. ∎ Fix a colouring satisfying (P1) and (P2) . Observe that any set of 2\ell vertices in F contains either 3 vertices from V_{i} for some i\in\{2,\ldots,\ell-1\} or 4 vertices from V_{1} . Given that (R\cup P)[V_{i}] is K_{4} -free if i=1 and K_{3} -free if i\in\{2,\ldots,\ell-1\} , we obtain that R\cup P is K_{2\ell} -free. Assume now that \alpha(R)\geq cn , and so there exists a set of vertices I with |I|\geq cn and no red edges in F[I] . By the pigeonhole principle, there exists i\in[\ell-1] such that X=I\cap V_{i} contains at least cn/(\ell-1) vertices. Fix such an i . Now \alpha(R[V_{i}])<(c-\delta)n , by 5.1 and 5.3 . Therefore, I contains at least \delta n vertices not in V_{i} . Once again, by the pigeonhole principle there exists j\in[\ell-1]\setminus\{i\} such that Y=I\cap V_{j} has size at least \delta n/(\ell-2) . By (P2) there exists a red edge between the two sets X,Y , contradicting the fact that F[I] contains no red edges. Finally, to bound the total number of purple edges in P from below, observe that (P1) implies that the number of purple edges between V_{i} and V_{j} , for i,j\in[\ell-1] with i\neq j , is at least |V_{i}||V_{j}|-o(n^{2}) . Given that any purple edge in P is either between V_{i} and V_{j} for some distinct i,j\in[\ell-1] , in P_{4} , or in one of the \ell-2 copies of P_{3} , we obtain from 5.2 and 5.4 that \displaystyle|P| \displaystyle\geq|P_{4}|+(\ell-2)|P_{3}|+\binom{\ell-2}{2}\frac{9n^{2}}{(3\ell-2)^{2}}+(\ell-2)\frac{12n^{2}}{(3\ell-2)^{2}}-o(n^{2}) \displaystyle\geq\frac{1}{2}\Big(\frac{3\ell-5}{3\ell-2}+(c-\eta)-(c-\eta)^{2}-o(1)\Big)n^{2}, and the result follows as \eta is arbitrarily small. ∎ We note that, in Claim 5.4 , we could use the better estimate \Theta(pn^{2}) for red edges in the random colourings between V_{i} ’s and V_{j} ’s, and hence increase the second order term in |P| . However, the error term \varepsilon from Theorem 5.2 used for P_{4} leads to an error term in |P| that is at least of order \Theta\left(n^{2}/\sqrt{\log n}\right) . 5.2 A probabilistic bound In this section, we prove Theorem 1.6 and show that for any s , the behaviour of g(n;s,t) closely follows \mathrm{{\bf RT}}_{s}(n,t) up to some logarithmic offset in the function t . Proof of Theorem 1.6 . For some absolute constant 00 , p\cdot\mathrm{{\bf RT}}_{s}(n,t/\log n)\leq g(n;s,t)\leq\mathrm{{\bf RT}}_{s}(n,t). Applying Theorem 5.5 we obtain g(n;s,t)=\Theta(n^{2}) . The second point follows similarly, by observing that if \ell\geq\frac{s+3}{2} , then \frac{s-1}{\ell-1}<2 and Theorem 5.5 yield that \mathrm{{\bf RT}}_{s}(n,R^{-1}(\ell,n))=o(n^{2}) . ∎ 6 Computational results In this section, we present some computational results obtained at the start of this project, which might be of interest for future work. Angell’s Problem 1.1 asks to prove that every red/blue/purple colouring of K_{8} , in which the purple edges form a perfect matching, contains a red/purple copy of K_{3} or a blue/purple copy of K_{4} . It is not hard to prove that three purple matching edges are sufficient, while two are not. More generally, let us denote by g_{M}(n;s,t) the largest m such that there exists a red/blue/purple colouring of K_{n} with a matching of exactly m purple edges that has neither a red/purple copy of K_{s} nor a blue/purple copy of K_{t} . If, for example, g_{M}(n;s,t)=0 , then a single purple edge is sufficient to guarantee a red/purple K_{s} or a blue/purple K_{t} . For all s,t for which R(s,t) is known, McKay’s webpage [ 36 ] provides the list \mathcal{L}(n;s,t) of all graphs on n=R(s,t)-1 vertices, with no clique of size s , and no independent set of size t , that is, the list of red graphs in (s,t) -free red/blue colourings of K_{n} . A crucial observation is that if R\cup B\cup P is a red/blue/purple colouring that with no red/purple copy of K_{s} and no blue/purple copy of K_{t} , then every recolouring of the purple edges by either red or blue produces a red graph in \mathcal{L}(n;s,t) . Observation 6.1 . Fix n>s,t\geq 3 . If g_{M}(n;s,t)\geq k , then there exist a graph R in \mathcal{L}(n;s,t) and a matching P in K_{n}\setminus R of size k such that R\cup P^{\prime} is in \mathcal{L}(n;s,t) for every subset P^{\prime}\subseteq P . We remark further that it is sufficient to check that R and R\cup P are in \mathcal{L}(n;s,t) , as this trivially implies that R\cup P^{\prime} is in \mathcal{L}(n;s,t) for every subset P^{\prime}\subseteq P . Using SageMath [ 50 ] and Nauty [ 37 ] , we profit from these remarks, and several other optimisations beyond brute force, to compute g_{M}(n;s,t) for all triples s,t,n where n=R(s,t)-1 is known. For completeness, we include pseudocode in Appendix A . Table 1 contains all computational results obtained for g_{M}(n;s,t) , where (\dagger) denotes the assumption that the list \mathcal{L}(42;5,5) is complete, which is conjectured in [ 39 ] . If true, this would imply that R(5,5)=43 , since none of the colourings in \mathcal{L}(42;5,5) extend to a (5,5) -free colouring on 43 vertices, see [ 39 ] for details. t=3 t=4 t=5 s=3 g_{M}(5;3,3)=0 g_{M}(8;3,4)=2 g_{M}(13;3,5)=0 s=4 g_{M}(17;4,4)=0 g_{M}(24;4,5)=12 s=5 g_{M}(42;5,5)=6^{(\dagger)} t=6 t=7 t=8 t=9 s=3 g_{M}(17;3,6)=2 g_{M}(22;3,7)=6 g_{M}(27;3,8)=7 g_{M}(35;3,9)=0 Table 1: Values of g_{M}(R(s,t)-1;s,t) . We note that some of these results do not require computer aid. For example, g_{M}(5,3,3)=0 can be deduced from the fact that C_{5} is self-complementary and the unique triangle-free graph on 5 vertices with no independent set of size 3 . Similarly, the Paley graph on 17 vertices is self-complementary and the unique K_{4} -free graph on 17 vertices with no independent set of size 4 , which directly implies that g_{M}(17,4,4)=0 . Some other results have simple proofs using pigeonhole arguments. We also obtained the value of g(n;s,t) for the same values of n , s and t , that is, the parameter studied extensively in this article, where purple edges do not necessarily form a matching. In most cases we obtain g(n;s,t)=g_{M}(n;s,t) , with the following exceptions: \displaystyle g(27;3,8)=9,\qquad g(24;4,5)=14,\qquad g(42;5,5)=7. We mentioned in the introduction that a perfect matching of purple edges in K_{24} is not sufficient to find a red/purple copy of K_{4} or a blue/purple copy of K_{5} . Therefore, the fact that g(24;4,5)>g_{M}(24;4,5) is not too surprising. The other two cases are somewhat more surprising. For (s,t)=(3,8) , for example, we have R(3,8)=28 , and we determined above that g_{M}(27;3,8)=7 . However, there is a graph P with nine edges and a (K_{3},K_{8}) -free red/blue/purple colouring R\cup B\cup P of K_{27} . Here, we may take P to be the graph consisting of vertex-disjoint copies of the 3-edge path, the 2-edge path and four pairwise disjoint edges, for example. A similar behaviour is observed for (s,t)=(5,5) and n=42 , assuming that \mathcal{L}(42;5,5) is complete, as mentioned above. Here, g_{M}(42;5,5)=6 , while there is a (K_{5},K_{5}) -free red/blue/purple colouring R\cup B\cup P of K_{42} , where P consists of a 3-edge path and four vertex-disjoint edges, that is P has 7 edges. These two cases exemplify that a purple matching is not necessarily optimal if we wish to maximise |P| while maintaining \omega(R\cup P)(\log n)/2 . The results of Nagy [ 40 ] imply that g(n;c\log n)\geq(1-\varepsilon_{1})\binom{n}{2} for every c>2 , and that g(n;c\log n)\leq(1-\varepsilon_{2})\binom{n}{2} for every c>3/5 , where \varepsilon_{1}\approx 2/c and \varepsilon_{2}\approx 1/(5c) . It would be interesting to improve these bounds, and extend them to determine g(n;s) when s=c\log n , for any c>1/2 . Appendix A Pseudocodes We now present the pseudocodes used to compute results presented in Section 6 . A Ramsey (s,t) -graph is a graph with no clique of size s , and no independent set of size t . Algorithm 1 below takes as input a Ramsey (s,t) -graph G , and outputs the largest k such that a matching of size k in G can be deleted without creating an independent set of size t . Algorithm 2 determines g_{M}(n;s,t) by looping through all Ramsey (s,t) -graphs, using several optimisations to cut down on runtime. Algorithm 1 Given a Ramsey (s,t) -graph G , returns the largest k such that \alpha(G-M) Max_size then 8: Max_size = |E(G)| 9: end if 10: end for 11: Edge_bound = Max_size - Min_size + 1 12: Max_k = 0 13: for G in All_critical_graphs do 14: if |E(G)| - Max_k < Min_size then 15: continue (to next graph) 16: end if 17: k = Find_k ( G , s , t ) 18: if k=\lfloor n/2\rfloor then 19: return \lfloor n/2\rfloor 20: end if 21: if k> Max_k then 22: Max_k = k 23: end if 24: if Max_k = Edge_bound then - 1 25: break 26: end if 27: end for 28: return Max_k 29: end procedure