论文标题
Ramsey多重性和Turán着色
Ramsey multiplicity and the Turán coloring
论文作者
论文摘要
Burr和Rosta扩展了ErdőS的早期猜想，猜想在完整图的所有边缘的所有两色中，均匀的随机着色渐近地将任何固定图$ H $的单色副本数量最小化。 Sidorenko和Thomason独立反驳了这一猜想。第一作者后来使用Turán着色发现了更Quantitiit的反例，其中两种颜色涵盖了平衡的完整多片图。 我们证明，对于无限的图表，Turán着色是极端的，它是独特的极端颜色。这产生了burr- rosta猜想失败的图的Ramsey多重性常数的首次确定。 我们还证明了类似的三色结果。在这种情况下，我们的结果是基于对两色拉姆齐数字的行为的某种自然猜想的条件。
Extending an earlier conjecture of Erdős, Burr and Rosta conjectured that among all two-colorings of the edges of a complete graph, the uniformly random coloring asymptotically minimizes the number of monochromatic copies of any fixed graph $H$. This conjecture was disproved independently by Sidorenko and Thomason. The first author later found quantitatively stronger counterexamples, using the Turán coloring, in which one of the two colors spans a balanced complete multipartite graph. We prove that the Turán coloring is extremal for an infinite family of graphs, and that it is the unique extremal coloring. This yields the first determination of the Ramsey multiplicity constant of a graph for which the Burr--Rosta conjecture fails. We also prove an analogous three-color result. In this case, our result is conditional on a certain natural conjecture on the behavior of two-color Ramsey numbers.
