Geodesic
Ramsey multiplicity and the Turán coloring
Advances in Combinatorics (2023) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

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.
Publié le : 
@article{ADVC_2023_a5,
     author = {Jacob Fox and Yuval Wigderson},
     title = {Ramsey multiplicity and the {Tur\'an} coloring},
     journal = {Advances in Combinatorics},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADVC_2023_a5/}
}
TY  - JOUR
AU  - Jacob Fox
AU  - Yuval Wigderson
TI  - Ramsey multiplicity and the Turán coloring
JO  - Advances in Combinatorics
PY  - 2023
UR  - http://geodesic.mathdoc.fr/item/ADVC_2023_a5/
LA  - en
ID  - ADVC_2023_a5
ER  - 
%0 Journal Article
%A Jacob Fox
%A Yuval Wigderson
%T Ramsey multiplicity and the Turán coloring
%J Advances in Combinatorics
%D 2023
%U http://geodesic.mathdoc.fr/item/ADVC_2023_a5/
%G en
%F ADVC_2023_a5
Jacob Fox; Yuval Wigderson. Ramsey multiplicity and the Turán coloring. Advances in Combinatorics (2023). http://geodesic.mathdoc.fr/item/ADVC_2023_a5/