×

Turán-Ramsey theorems and simple asymptotically extremal structures. (English) Zbl 0774.05050

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 2a construction of B. Bollobás and 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.

MSC:

05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
05C38 Paths and cycles

Citations:

Zbl 0337.05134
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Bollobás:Extremal graph theory, Academic Press, London, 1978.
[2] B. Bollobás andP. Erdos: On a Ramsey-Turán type problem,Journal of Combinatorial Theory, B21 (1976), 166–168. · Zbl 0337.05134
[3] W. G. Brown, P. Erdos andM. Simonovits: Extremal problems for directed graphs,Journal of Combinatorial Theory,15B(1) (1973), 77–93. · Zbl 0253.05124
[4] W. G. Brown, P. Erdos andM. Simonovits: Multigraph extremal problems, in:Problemes Combinatoires et Théorie des Graphes (ed. J. Bermond et al.), CNRS Paris, 1978.
[5] W. G. Brown, P. Erdos, andM. Simonovits: Inverse extremal digraph problems,Finite and Infinite Sets, Colloq. Math. Soc. J. Bolyai37 Eger 1981, Akad. Kiadó, Budapest (1985), 119–156.
[6] W. G. Brown, P. Erdos, andM. Simonovits: Algorithmic Solution of Extremal Digraph Problems,Trans. Amer. Math. Soc. 292 (1985), 421–449. · Zbl 0607.05040
[7] S. Burr, P. Erdos andL. Lovász: On graphs of Ramsey type,Ars Combinatoria,1 (1976), 167–190.
[8] P. Erdos: On some new inequalities concerning extremal properties of graphs,Theory of Graphs, Proc. Coll. Tihany, Hungary (ed. P. Erdos and G. Katona), Acad. Press., N. Y. 1968, 77–81.
[9] P. Erdos Remarks on a theorem of Ramsey,Bull. Res. Conne. Israel 7 (1957), 21–24.
[10] P. Erdos, A. Hajnal, Vera T.Sós andE. Szemerédi More results on Ramsey-Turán type problem Ramsey-Turán type problems,Combinatorica 3 (1983), 69–82. · Zbl 0526.05031
[11] P. Erdos, A. Meir, Vera T. Sós andP. Turán: On some applications of graph theory I,Discrete Math. 2 (1972), (3) 207–228. · Zbl 0236.05119
[12] P. Erdos, A. Meir, Vera T. Sós andP. Turán: On some applications of graph theory II.Studies in Pure Mathematics (presented to R. Rado) Academic Press, London, 1971, 89–99.
[13] P. Erdos, A. Meir, Vera T. Sós andP. Turán: On some applications of graph theory III,Canadian Math. Bulletin 15 (1972), 27–32. · Zbl 0232.05003
[14] P. Erdos andC. A. Rogers: The construction of certain graphs,Canadian Journal of Math 1962.; or Art of Counting MIT PRESS. · Zbl 0194.25304
[15] P. Erdos andVera T. Sós: Some remarks on Ramsey’s and Turán’s theorems, in:Combin. Theory and Appl. (P. Erdos et al eds) Colloq. Math. Soc. J. Bolyai4 (1969), 395–404.
[16] P. Erdos andA. H. Stone: On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946), 1089–1091. · Zbl 0063.01277
[17] P. Frankl andV. Rödl: Some Ramsey-Turán type results for hypergraphs,Combinatorica 8 (1988), 323–332. · Zbl 0658.05041
[18] Motzkin, E. G. Straus: Maxima for graphs and a new proof of a theorem of Turán,Canadian Journal of Math. 17 (1965), 533–540. · Zbl 0129.39902
[19] F. P. Ramsey On a problem of formal logic,Proc. London Math. Soc. 2nd Series,30 (1930), 264–286. · JFM 55.0032.04
[20] M. Simonovits: A method for solving extremal problems in graph theory, in:Theory of graphs, Proc. Coll. Tihany, (1966), (Ed. P. Erdos and G. Katona) Acad. Press, N.Y., 1968, 279–319.
[21] M. Simonovits: Extremal Graph Theory, in:Selected Topics in Graph Theory (eds Beineke and Wilson) Academic Press, London, New York, San Francisco, 161–200. (1983).
[22] Vera T. Sós: On extremal problems in graph theory, in:Proc. Calgary International Conf. on Combinatorial Structures and their Application, (1969), 407–410.
[23] E. Szemerédi: On graphs containing no complete subgraphs with 4 vertices (in Hungarian),Mat. Lapok 23 (1972), 111–116.
[24] E. Szemerédi: On regular partitions of graphs, in:Problemes Combinatoires et Théorie des Graphes (ed. J. Bermond et al.), CNRS Paris, 1978, 399–401.
[25] P. Turán On an extremal problem in graph theory,Matematikai Lapok 48 (1941), 436–452 (in Hungarian), (see also [30]).
[26] P. Turán: On the theory of graphs,Colloq. Math. 3 (1954), 19–30, (see also [30]). · Zbl 0055.17004
[27] P. Turán: Applications of graph theory to geometry and potential theory, in:Proc. Calgary International Conf. on Combinatorial Structures and their Application, (1969), 423–434, (see also [30]).
[28] P. Turán: Constructive theory of functions, in:Proc. Internat. Conference in Varna, Bulgaria, 1970 Izdat. Bolgar Akad. Nauk, Sofia, 1972, (see also [30]). · Zbl 0272.05119
[29] P. Turán: A general inequality of potential theory,Proc. Naval Research Laboratory, Washington, (1970), 137–141, (see also [30]). · Zbl 0286.31001
[30] Collected works of Paul Turán, Akadémiai Kiadó, Budapest, 1989.
[31] A. A. Zykov: On some properties of linear complexes, Mat Sbornik, 24 (1949), 163–188; Amer. Math. Soc. Translations79, 1952.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.