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 

Ramsey's theorem for two colors and the complete graph, proved in its original form in 1930, states that for any positive integer  there exists an integer  large enough that for any coloring of the edges of the complete graph  using two colors has a monochoromatic copy of . More generally, for any graphs , there is a threshold  such that if  and the edges of  are colored arbitrarily with  colors, then for some  there is a  in the th color. Turán's theorem, proved in 1941, characterizes the graph with the maximal number of edges on  vertices which does not contain a . Specifically, the theorem states that for all positive integers , the number of edges of an -vertex graph which does not contain  as a subgraph is at most  and that the maximum is attained uniquely by the Turán graph . 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 , let  be an -vertex graph not containing  and having independence number . 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  be fixed graphs. What is the maximum number of edges an -edge colored graph on  vertices can have under the condition that it does not contain an  in the th color? General problem 

The backbone of Ramsey-Turán theory is the common generalization of the above problems. Problem 3: Let  be fixed graphs. Let  be an -edge-colored -vertex graph satisfying  (1)  (2) the subgraph  defined by the th color contains no . What is the maximum number of edges  can have? We denote the maximum by . 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 , which reduces to the classic Ramsey problem. There is the "intermediate" case, where  for a fixed . Lastly, there is the  case, which contains the richest problems. The most basic nontrivial problem in the  range is when  and  Erdős and Sós determined the asymptotic value of the Ramsey-Turán number in this situation in 1969:  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:  Note that in both cases, the problem can be viewed as adding the extra condition to Turán's theorem that . In both cases, it can be seen that asymptotically, the effect is the same as if we had excluded  instead of  or . References 

Graph theory