2016/05/25 by Fabricio S. Benevides, Fabrício Benevides, Benevides, Fabricio S. +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1605.08013
23 pages, including appendix, 2 figures
openalex publication_date 2016/05/25 · arxiv created 2016/05/27 · arxiv updated 2016/05/30 · openalex created_date 2022/09/25 · openalex updated_date 2026/07/28
Given a graph F and an integer r ≥ 2, a partition \widehatF of the edge set of F into at most r classes, and a graph G, define c_r, \widehatF(G) as the number of r-colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F. We think of \widehatF as the pattern of coloring that should be avoided. The main question is, for a large enough n, to find the (extremal) graph G on n vertices which maximizes c_r, \widehatF(G). This problem generalizes a question of Erd\H os and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition \widehatF contains a single class). We use Hölder's Inequality together with Zykov's Symmetrization to prove that, for any r ≥ 2, k ≥ 3 and any pattern \widehatKk of the clique Kk, there exists a complete multipartite graph that is extremal. Furthermore, if the pattern \widehatKk has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r=3 and \widehatF is a rainbow triangle (that is, where F=K3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r=3, we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.