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,[1] though mathematicians had previously investigated many Ramsey-Turán-type problems.[2]

Ramsey's theorem and Turán's theorem

edit

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   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:[3]

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 ith color?

General problem

edit

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

edit

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.[2]

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:[1]   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:[4]   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

edit
  1. ^ a b Erdős, Paul; Sós, Vera T. (1970). Some remarks on Ramsey's and Turán's theorem. Combinatorial theory and its applications, Balatonfüred, 1969. Vol. II. North-Holland. pp. 395–404.
  2. ^ a b Simonovits, Miklós; T. Sós, Vera (2001-02-28). "Ramsey–Turán theory". Discrete Mathematics. 229 (1): 293–340. doi:10.1016/S0012-365X(00)00214-4. ISSN 0012-365X.
  3. ^ Andrásfal, B. (1964). "Graphentheoretische Extremalprobleme". Acta Mathematica Academiae Scientiarum Hungaricae. 15 (3–4): 413–438. doi:10.1007/bf01897150. ISSN 0001-5954. S2CID 189783307.
  4. ^ Erdős, Paul; Hajnal, András; Sós, Vera T.; Szemerédi, Endre (1983). "More results on Ramsey—Turán type problems". Combinatorica. 3 (1): 69–81. doi:10.1007/bf02579342. ISSN 0209-9683. S2CID 14815278.