Turán-Ramsey theorems and simple asymptotically extremal structures
Let \(L_1,\) \(L_2,\dots,L_r\) be given graphs (``forbidden graphs), and let \(n\) be a positive integer and \(f\) a given function; \(\alpha(G)\) denotes the maximum number of independent vertices in a graph \(G\); \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\) denotes the maximum number of edges in a graph \(G_n\) on \(n\) vertices, having \(\alpha(G_n)\leq f(n)\), whose edges may be coloured in \(r\) colours so that the subgraph of the \(i\)th colour contains no \(L_i\) \((i=1,2,\dots,r)\); the results of this paper generally apply to the case \(f(n)=o(n)\), and the maximum is usually denoted by \(\text{RT}(n,L_1,L_2,\dots,L_r,o(n))\). A sequence \((S_n)\) of graphs for which \(\alpha(S_n)\leq f(n)\) and \(S_n\) has \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))+o(n^2)\) edges, is asymptotically extremal for \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\) if the edges of \(S_n\) may be \(r\)-coloured so that the subgraph of the \(i\)th colour contains no \(L_i\) \((i=1,\dots,r)\). In Theorem 2\ a construction of \textit{B. Bollobás} and \textit{P. Erdős} [On a Ramsey-Turán type problem, J. Comb. Theory, Series B 21, 166-168 (1976; Zbl 0337.05134)] used to prove that \(\text{RT}(n,K_4,o(n))\geq{1\over 8}n^2-o(n^2)\) is generalized to prove the existence of a sequence of graphs that is asymptotically extremal for \(\text{RT}(n,K_{k_1},K_{k_2},\dots,K_{k_r},o(n^2))\), where \(k_1\), \(k_2,\dots,k_r\) are integers each exceeding 2. Let \(\vartheta(L_1,L_2,\dots,L_r)\) denote the minimum real number such that \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\leq\vartheta(L_1,L_2,\dots,L_r)n^2+o(n^2)\); in Theorem 3 the values of \(\vartheta(K_3,K_3)\), \(\vartheta(K_3,K_4)\), \(\vartheta(K_3,K_5)\), \(\vartheta(K_4,K_4)\) are determined, as well as an asymptotically extremal sequence for each case; it is shown that the distance between two such sequences - - i.e. the minimum number of edge additions/deletions needed to transform one such sequence into another -- is \(o(n^2)\) in each case. Theorem 4: If \(p\) and \(q\) are odd integers, then \(\text{RT}(n,C_p,C_q,o(n))={1\over 4}n^2+o(n^2)\). The paper concludes with a list of open problems.
- Algorithmic Solution of Extremal Digraph Problems
- Extremal problems for directed graphs
- scientific article; zbMATH DE number 3427399 (Why is no real title available?)
- scientific article; zbMATH DE number 3448930 (Why is no real title available?)
- Maxima for Graphs and a New Proof of a Theorem of Turán
- More results on Ramsey-Turán type problems
- On a Ramsey-Turán type problem
- On Some Applications of Graph Theory III
- On some applications of graph theory. I
- On the structure of linear graphs
- On the theory of graphs
- Some Ramsey-Turán type results for hypergraphs
- The Construction of Certain Graphs
- On the Turán properties of infinite graphs
- Two path extremal graphs and an application to a Ramsey-type problem
- A few remarks on Ramsey--Turán-type problems
- Turán-Ramsey problems
- Two results on Ramsey-Turán theory
- Phase transitions in Ramsey-Turán theory
- A hierarchy of randomness for graphs
- scientific article; zbMATH DE number 412246 (Why is no real title available?)
- Short proofs of some extremal results. II.
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Mean Ramsey–Turán numbers
- On the connectivity of extremal Ramsey graphs
- scientific article; zbMATH DE number 3655979 (Why is no real title available?)
- scientific article; zbMATH DE number 3765840 (Why is no real title available?)
- scientific article; zbMATH DE number 16113 (Why is no real title available?)
- scientific article; zbMATH DE number 19174 (Why is no real title available?)
- Turán-Ramsey Theorems and Kp-Independence Numbers
- Two Conjectures in Ramsey--Turán Theory
- The critical window for the classical Ramsey-Turán problem
- On two problems in Ramsey-Turán theory
- Explicit constructions of triple systems for Ramsey–Turán problems
- Ramsey-Turán theory
- More results on Ramsey-Turán type problems
- Two-colored Ramsey-Turán densities involving triangles
- Geometric constructions for Ramsey-Turán theory
- The next case of Andrásfai's conjecture
- The number of edge colorings with small independence number and no monochromatic H
- Remarques sur deux problèmes extrémaux. (Remarks on two extremal problems)
- An extremal problem on v-partite graphs
This page was built for publication: Turán-Ramsey theorems and simple asymptotically extremal structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367441)
