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 k there exists an integer n large enough that for any coloring of the edges of the complete graph K n {\displaystyle K_{n}} using two colors has a monochoromatic copy of K k {\displaystyle K_{k}} . More generally, for any graphs L 1 , … , L r {\displaystyle L_{1},\dots ,L_{r}} , there is a threshold R = R ( L 1 , … , L k ) {\displaystyle R=R(L_{1},\dots ,L_{k})} such that if n ≥ R {\displaystyle n\geq R} and the edges of K n {\displaystyle K_{n}} are colored arbitrarily with r {\displaystyle r} colors, then for some 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} there is a L i {\displaystyle L_{i}} in the i {\displaystyle i} th color. Turán's theorem, proved in 1941, characterizes the graph with the maximal number of edges on n {\displaystyle n} vertices which does not contain a K r + 1 {\displaystyle K_{r+1}} . Specifically, the theorem states that for all positive integers r , n {\displaystyle r,n} , the number of edges of an n {\displaystyle n} -vertex graph which does not contain K r + 1 {\displaystyle K_{r+1}} as a subgraph is at most ( 1 − 1 r ) n 2 2 {\displaystyle {\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 {\displaystyle 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 {\displaystyle m} , let G {\displaystyle G} be an n {\displaystyle n} -vertex graph not containing K r + 1 {\displaystyle K_{r+1}} and having independence number α ( G ) < m {\displaystyle \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 , … , L r {\displaystyle L_{1},\dots ,L_{r}} be fixed graphs. What is the maximum number of edges an r {\displaystyle r} -edge colored graph on n {\displaystyle n} vertices can have under the condition that it does not contain an L i {\displaystyle L_{i}} in the ith color?
General problem The backbone of Ramsey-Turán theory is the common generalization of the above problems.
… excerpt ends here. Continue reading the full article.
