Ramsey-Turán theory

{{See also|Ramsey's theorem|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 {{math|k}} there exists an integer {{math|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,\backslash dots,L\_r$, there is a threshold $R=R(L\_1,\backslash dots,L\_k)$ such that if $n\; \backslash geq\; R$ and the edges of $K\_n$ are colored arbitrarily with $r$ colors, then for some $1\; \backslash leq\; i\; \backslash 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 $$\backslash bigg(1\; -\; \backslash frac\{1\}\{r\}\backslash bigg)\; \backslash 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:{{Cite journal |last=Andrásfal |first=B. |date=1964 |title=Graphentheoretische Extremalprobleme |url=http://dx.doi.org/10.1007/bf01897150 |journal=Acta Mathematica Academiae Scientiarum Hungaricae |volume=15 |issue=3–4 |pages=413–438 |doi=10.1007/bf01897150 |s2cid=189783307 |issn=0001-5954}}

Problem 1: For a given positive integer $m$, let $G$ be an $n$-vertex graph not containing $K\_\{r+1\}$ 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 $L\_1,\backslash 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 {{math|i}}th color?

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

Problem 3: Let $L\_1,\backslash dots,\; L\_r$ be fixed graphs. Let $G$ be an $r$-edge-colored $n$-vertex graph satisfying

(1)

(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 $\backslash mathbf\{RT\}(n;L\_1,\backslash 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.

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

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:{{Cite conference |last1=Erdős |first1=Paul |author-link=Paul Erdős |last2=Sós |first2=Vera T. |author-link2=Vera T. Sós |date=1970 |title=Some remarks on Ramsey's and Turán's theorem |conference=Combinatorial theory and its applications, Balatonfüred, 1969 |publisher=North-Holland |volume=II |pages=395{{endash}}404}} $$\backslash mathbf\{RT\}(n;K\_\{2k+1\},o(n))\; =\; \backslash bigg(1-\backslash frac\{1\}\{k\}\backslash bigg)\backslash 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:{{Cite journal |last1=Erdős |first1=Paul |author-link=Paul Erdős |last2=Hajnal |first2=András |author-link2=András Hajnal |last3=Sós |first3=Vera T. |author-link3=Vera T. Sós |last4=Szemerédi |first4=Endre |author-link4=Endre Szemerédi |date=1983 |title=More results on Ramsey—Turán type problems |url=http://dx.doi.org/10.1007/bf02579342 |journal=Combinatorica |volume=3 |issue=1 |pages=69–81 |doi=10.1007/bf02579342 |s2cid=14815278 |issn=0209-9683}} $$\backslash mathbf\{RT\}(n;K\_\{2k\},o(n))\; =\; \backslash frac\{6k-10\}\{6k-4\}\backslash 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 . 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\}$.

{{reflist}}

Category:Extremal graph theory