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)\).
Reviewer: Péter Komjáth (Budapest)
MSC:
05C35 | Extremal problems in graph theory |
05C80 | Random graphs (graph-theoretic aspects) |
05D10 | Ramsey theory |
05C55 | Generalized Ramsey theory |
Citations:
Zbl 0910.05035References:
[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. 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.