Ramsey-Turán theory

Ramsey-Turán theory is a subfield of extremal graph theory. It studies common generalizations of Ramsey's theorem and Turán's theorem. In brief, Ramsey-Turán theory asks for the maximum number of edges a graph which satisfies constraints on its subgraphs and structure can have. The theory organizes many natural questions which arise in extremal graph theory. The first authors to formalize the central ideas of the theory were Erdős and Sós in 1969, though mathematicians had previously investigated many Ramsey-Turán-type problems.

Ramsey's theorem and Turán's theorem

See also: Ramsey's theorem and Turán's theorem

Ramsey's theorem for two colors and the complete graph, proved in its original form in 1930, states that for any positive integer k there exists an integer n large enough that for any coloring of the edges of the complete graph $K_{n}$ using two colors has a monochoromatic copy of $K_{k}$. More generally, for any graphs $L_{1},\dots ,L_{r}$, there is a threshold $R=R(L_{1},\dots ,L_{k})$ such that if $n\geq R$ and the edges of $K_{n}$ are colored arbitrarily with $r$ colors, then for some $1\leq i\leq r$ there is a $L_{i}$ in the $i$th color.

Turán's theorem, proved in 1941, characterizes the graph with the maximal number of edges on $n$ vertices which does not contain a $K_{r+1}$. Specifically, the theorem states that for all positive integers $r,n$, the number of edges of an $n$-vertex graph which does not contain $K_{r+1}$ as a subgraph is at most $${\bigg (}1-{\frac {1}{r}}{\bigg )}{\frac {n^{2}}{2}}$$ and that the maximum is attained uniquely by the Turán graph $T_{n,r}$.

Both of these classic results ask questions about how large a graph can be before it possesses a certain property. There is a notable stylistic difference, however. The extremal graph in Turán's theorem has a very strict structure, having a small chromatic number and containing a small number of large independent sets. On the other hand, the graph considered in Ramsey problems is the complete graph, which has large chromatic number and no nontrivial independent set. A natural way to combine these two kinds of problems is to ask the following question, posed by Andrásfai:

Problem 1: For a given positive integer $m$, let $G$ be an $n$-vertex graph not containing $K_{r+1}$ and having independence number $\alpha (G)<m$. What is the maximum number of edges such a graph can have?

Essentially, this question asks for the answer to the Turán problem in a Ramsey setting; it restricts Turán's problem to a subset of graphs with less orderly, more randomlike structure. The following question combines the problems in the opposite direction:

Problem 2: Let $L_{1},\dots ,L_{r}$ be fixed graphs. What is the maximum number of edges an $r$-edge colored graph on $n$ vertices can have under the condition that it does not contain an $L_{i}$ in the ith color?

General problem

The backbone of Ramsey-Turán theory is the common generalization of the above problems.

Problem 3: Let $L_{1},\dots ,L_{r}$ be fixed graphs. Let $G$ be an $r$-edge-colored $n$-vertex graph satisfying

(1) $\alpha (G)<m$

(2) the subgraph $G_{i}$ defined by the $i$th color contains no $L_{i}$.

What is the maximum number of edges $G$ can have? We denote the maximum by $\mathbf {RT} (n;L_{1},\dots ,L_{r},m)$.

Ramsey-Turán-type problems are special cases of problem 3. Many cases of this problem remain open, but several interesting cases have been resolved with precise asymptotic solutions.

Notable results

Problem 3 can be divided into three different cases, depending on the restriction on the independence number. There is the restriction-free case, where $m=n$, which reduces to the classic Ramsey problem. There is the "intermediate" case, where $m=cn$ for a fixed $0<c<1$. Lastly, there is the $m=o(n)$ case, which contains the richest problems.

The most basic nontrivial problem in the $m=o(n)$ range is when $r=1$ and $L_{1}=K_{2k+1}.$ Erdős and Sós determined the asymptotic value of the Ramsey-Turán number in this situation in 1969: $$\mathbf {RT} (n;K_{2k+1},o(n))={\bigg (}1-{\frac {1}{k}}{\bigg )}{\frac {n^{2}}{2}}+o(n^{2}).$$ The case of the complete graph on an even number of vertices is much more challenging, and was resolved by Erdős, Hajnal, Sós and Szemerédi in 1983: $$\mathbf {RT} (n;K_{2k},o(n))={\frac {6k-10}{6k-4}}{\frac {n^{2}}{2}}+o(n^{2}).$$ Note that in both cases, the problem can be viewed as adding the extra condition to Turán's theorem that $\alpha (G)<o(n)$. In both cases, it can be seen that asymptotically, the effect is the same as if we had excluded $K_{k}$ instead of $K_{2k+1}$ or $K_{2k}$.