Ramsey multiplicity and the Turán coloring

Fox J, Wigderson Y. 2023. Ramsey multiplicity and the Turán coloring. Advances in Combinatorics.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Abstract
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.
Publishing Year
Date Published
2023-01-01
Journal Title
Advances in Combinatorics
Publisher
Alliance of Diamond Open Access Journals
eISSN
IST-REx-ID

Cite this

Fox J, Wigderson Y. Ramsey multiplicity and the Turán coloring. Advances in Combinatorics. 2023. doi:10.19086/aic.2023.2
Fox, J., & Wigderson, Y. (2023). Ramsey multiplicity and the Turán coloring. Advances in Combinatorics. Alliance of Diamond Open Access Journals. https://doi.org/10.19086/aic.2023.2
Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.” Advances in Combinatorics. Alliance of Diamond Open Access Journals, 2023. https://doi.org/10.19086/aic.2023.2.
J. Fox and Y. Wigderson, “Ramsey multiplicity and the Turán coloring,” Advances in Combinatorics. Alliance of Diamond Open Access Journals, 2023.
Fox J, Wigderson Y. 2023. Ramsey multiplicity and the Turán coloring. Advances in Combinatorics.
Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.” Advances in Combinatorics, Alliance of Diamond Open Access Journals, 2023, doi:10.19086/aic.2023.2.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Metadata Export

Sources

arXiv 2207.07775

Search this title in

Google Scholar