Turán-Ramsey theorems and simple asymptotically extremal structures (Q2367441)

Let \(L_1,\) \(L_2,\dots,L_r\) be given graphs (``forbidden'' graphs), and let \(n\) be a positive integer and \(f\) a given function; \(\alpha(G)\) denotes the maximum number of independent vertices in a graph \(G\); \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\) denotes the maximum number of edges in a graph \(G_n\) on \(n\) vertices, having \(\alpha(G_n)\leq f(n)\), whose edges may be coloured in \(r\) colours so that the subgraph of the \(i\)th colour contains no \(L_i\) \((i=1,2,\dots,r)\); the results of this paper generally apply to the case \(f(n)=o(n)\), and the maximum is usually denoted by \(\text{RT}(n,L_1,L_2,\dots,L_r,o(n))\). A sequence \((S_n)\) of graphs for which \(\alpha(S_n)\leq f(n)\) and \(S_n\) has \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))+o(n^2)\) edges, is asymptotically extremal for \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\) if the edges of \(S_n\) may be \(r\)-coloured so that the subgraph of the \(i\)th colour contains no \(L_i\) \((i=1,\dots,r)\). In Theorem 2\ a construction of \textit{B. Bollobás} and \textit{P. Erdős} [On a Ramsey-Turán type problem, J. Comb. Theory, Series B 21, 166-168 (1976; Zbl 0337.05134)] used to prove that \(\text{RT}(n,K_4,o(n))\geq{1\over 8}n^2-o(n^2)\) is generalized to prove the existence of a sequence of graphs that is asymptotically extremal for \(\text{RT}(n,K_{k_1},K_{k_2},\dots,K_{k_r},o(n^2))\), where \(k_1\), \(k_2,\dots,k_r\) are integers each exceeding 2. Let \(\vartheta(L_1,L_2,\dots,L_r)\) denote the minimum real number such that \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\leq\vartheta(L_1,L_2,\dots,L_r)n^2+o(n^2)\); in Theorem 3 the values of \(\vartheta(K_3,K_3)\), \(\vartheta(K_3,K_4)\), \(\vartheta(K_3,K_5)\), \(\vartheta(K_4,K_4)\) are determined, as well as an asymptotically extremal sequence for each case; it is shown that the distance between two such sequences - - i.e. the minimum number of edge additions/deletions needed to transform one such sequence into another -- is \(o(n^2)\) in each case. Theorem 4: If \(p\) and \(q\) are odd integers, then \(\text{RT}(n,C_p,C_q,o(n))={1\over 4}n^2+o(n^2)\). The paper concludes with a list of open problems.