zbMATH — the first resource for mathematics

A variant of the classical Ramsey problem. (English) Zbl 0910.05034
The following quantity is estimated. Let \(f(n,p,q)\) be the minimum number of colors needed to color all edges of \(K_n\) such that every \(K_p\) gets at least \(q\) colors. A general upper bound is given using the Lovász local lemma. If \(q={p\choose 2}-p+3\) then \(f(n,p,q)\) is linear while \(f(n,p,q-1)\) is sublinear. If \(q={p\choose 2}-\lfloor{p\over 2}\rfloor+2\) then \(f(n,p,q)=\Omega(n^2)\) while \(f(n,p,q-1)=O(n^{2-{4\over p}})\) but is \(\Omega(n^{{4\over 3}})\) for \(p\geq 7\). \(f(n,p,p)=\Omega(n^{{1\over{p-2}}})\). Also, \({5\over 6}(n-1)\leq f(n,4,5)\) and \(f(n,9,34)={n\choose 2}-o(n^2)\).

05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)
05D10 Ramsey theory
05C55 Generalized Ramsey theory
Full Text: DOI
[1] W. G. Brown, P. Erdos, V. T. Sós: Some extremal problems onr-graphs, inNew directions in the theory of Graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, 53–63, Academic Press, New York, 1973.
[2] W. G. Brown, P. Erdos, V. T. Sós: On the existence of triangulated spheres in 3-graphs and related problems,Periodica Mathematica Hungarica,3 (1973), 221–228. · Zbl 0269.05111 · doi:10.1007/BF02018585
[3] P. Erdos: Solved and unsolved problems in combinatorics and combinatorial number theory,Congressus Numerantium,32 (1981), 49–62.
[4] P. Erdos: Extremal problems in graph theory, inTheory of Graphs and its Applications (M. Fiedler, ed.), Academic Press, New York, 1964, 29–36.
[5] P. Erdos, D. J. Kleitman: On coloring graphs to maximize the proportion of multicoloredk-edges,J. of Combinatorial Theory,5 (1968), 164–169. · Zbl 0167.22302 · doi:10.1016/S0021-9800(68)80051-1
[6] P. Erdos, L. Lovász: Problems and results on 3-chromatic hypergraphs and some related problems, in:Infinite and Finite sets, Colloquia Math. Soc. J. Bolyai vol. 10 (A. Hajnal et al eds.) North-Holland, Amsterdam, 609–617 1995.
[7] P. Erdos, V. T. Sós: personal communication, 1994.
[8] P. C. Fishburn: personal communication, 1995.
[9] A. Gyárfás, J. Lehel: Linear Sets with Five Distinct Differences among any Four Elements,J. of Combinatorial Theory B,64 (1995), 108–118. · Zbl 0830.05061 · doi:10.1006/jctb.1995.1028
[10] I. Z. Ruzsa, E. Szemerédi: Triple systems with no six points carrying three triangles, inCombinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II. 939–945.
[11] W. D. Wallis: Combinatorial Designs, Monographs and Textbooks inPure and Applied Mathematics, Vol. 118, Marcel Dekker, Inc. 1988.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.