TY - JOUR

T1 - The number of edge colorings with no monochromatic cliques

AU - Alon, Noga

AU - Balogh, József

AU - Keevash, Peter

AU - Sudakov, Benny

N1 - Funding Information:
The first author’s research was supported in part by a State of New Jersey grant, by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. The second author’s research was supported in part by OTKA grant T34475. The fourth author’s research was supported in part by NSF grants DMS-0106589 and CCR-9987845 and by the State of New Jersey.

PY - 2004/10

Y1 - 2004/10

N2 - Let F(n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of Kk. It is shown that for every fixed k and all n > n0(k), F(n, 2, k) = 2tk-1(n) and F(n, 3, k) = 3tk-1(n), where tk-1(n) is the maximum possible number of edges of a graph on n vertices with no Kk (determined by Turán's theorem). The case r = 2 settles an old conjecture of Erdos and Rothschild, which was also independently raised later by Yuster. On the other hand, for every fixed r > 3 and k > 2, the function F(n, r, k) is exponentially bigger than rtk-1(n). The proofs are based on Szemerédi's regularity lemma together with some additional tools in extremal graph theory, and provide one of the rare examples of a precise result proved by applying this lemma.

AB - Let F(n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of Kk. It is shown that for every fixed k and all n > n0(k), F(n, 2, k) = 2tk-1(n) and F(n, 3, k) = 3tk-1(n), where tk-1(n) is the maximum possible number of edges of a graph on n vertices with no Kk (determined by Turán's theorem). The case r = 2 settles an old conjecture of Erdos and Rothschild, which was also independently raised later by Yuster. On the other hand, for every fixed r > 3 and k > 2, the function F(n, r, k) is exponentially bigger than rtk-1(n). The proofs are based on Szemerédi's regularity lemma together with some additional tools in extremal graph theory, and provide one of the rare examples of a precise result proved by applying this lemma.

UR - http://www.scopus.com/inward/record.url?scp=7544235824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=7544235824&partnerID=8YFLogxK

U2 - 10.1112/S0024610704005563

DO - 10.1112/S0024610704005563

M3 - Article

AN - SCOPUS:7544235824

SN - 0024-6107

VL - 70

SP - 273

EP - 288

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

IS - 2

ER -