论文标题
三种颜色和多种禁止图案的Erdős-Hajnal猜想
The Erdős-Hajnal conjecture for three colors and multiple forbidden patterns
论文作者
论文摘要
Ramsey定理的Erdős和Szekeres的定量版本断言，在n个顶点上的任何完整的图形都用两种颜色边缘颜色具有至少1/2log（n）顶点的单色集团。著名的Erdős-Hajnal猜想断言，禁止固定颜色模式可确保更大的单色集团。具体而言，它声称，对于任何固定的整数k和k Vertices上的任何集团k，带有两种颜色的边缘颜色，有一个正常数a，因此，在任何完整的n-vertex Graph Gragh edge the the clique clique中，至少在n^a vertices上都有单色clique。 我们考虑具有三种颜色的边缘色。对于一个三角形的家族，每种颜色都带有{r，b，y}，forb（n，h）的颜色，表示完整的N-vertex的边缘色，使用{r，b，y}的颜色的颜色，并表示H.的最大值（n，h）的颜色最大。 颜色。我们为H_2（N，H）提供了所有由三角形组成的家庭的界限。对于他们中的大多数人来说，我们的界限在渐近上很紧。这扩展了Fox，Grinshpun和Pach的结果，他们确定了由彩虹三角形组成的H的H_2（N，H），并确认了这些模式集的多色Erdős-Hajnal构想。
Erdős and Szekeres's quantitative version of Ramsey's theorem asserts that any complete graph on n vertices that is edge-colored with two colors has a monochromatic clique on at least 1/2log(n) vertices. The famous Erdős-Hajnal conjecture asserts that forbidding fixed color patterns ensures larger monochromatic cliques. Specifically, it claims that for any fixed integer k and any clique K on k vertices edge-colored with two colors, there is a positive constant a such that in any complete n-vertex graph edge-colored with two colors that does not contain a copy of K, there is a monochromatic clique on at least n^a vertices. We consider edge-colorings with three colors. For a family H of triangles, each colored with colors from {r, b, y}, Forb(n,H) denotes a family of edge-colorings of the complete n-vertex graph using colors from {r, b, y} and containing none of the colorings from H. Let h_2(n, H) be the maximum q such that any coloring from Forb(n, H) has a clique on at least q vertices using at most two colors. We provide bounds on h_2(n, H) for all families H consisting of at most three triangles. For most of them, our bounds are asymptotically tight. This extends a result of Fox, Grinshpun, and Pach, who determined h_2(n, H) for H consisting of a rainbow triangle, and confirms the multicolor Erdős-Hajnal conjecture for these sets of patterns.
