---
OA_place: repository
OA_type: green
_id: '22170'
abstract:
- lang: eng
  text: "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.\r\nWe 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.\r\nWe 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."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, Wigderson Y. Ramsey multiplicity and the Turán coloring. <i>Advances
    in Combinatorics</i>. 2023. doi:<a href="https://doi.org/10.19086/aic.2023.2">10.19086/aic.2023.2</a>
  apa: Fox, J., &#38; Wigderson, Y. (2023). Ramsey multiplicity and the Turán coloring.
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals. <a
    href="https://doi.org/10.19086/aic.2023.2">https://doi.org/10.19086/aic.2023.2</a>
  chicago: Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.”
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
    <a href="https://doi.org/10.19086/aic.2023.2">https://doi.org/10.19086/aic.2023.2</a>.
  ieee: J. Fox and Y. Wigderson, “Ramsey multiplicity and the Turán coloring,” <i>Advances
    in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
  ista: Fox J, Wigderson Y. 2023. Ramsey multiplicity and the Turán coloring. Advances
    in Combinatorics.
  mla: Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.”
    <i>Advances in Combinatorics</i>, Alliance of Diamond Open Access Journals, 2023,
    doi:<a href="https://doi.org/10.19086/aic.2023.2">10.19086/aic.2023.2</a>.
  short: J. Fox, Y. Wigderson, Advances in Combinatorics (2023).
date_created: 2026-06-29T10:55:46Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2026-07-14T08:45:53Z
day: '01'
doi: 10.19086/aic.2023.2
extern: '1'
external_id:
  arxiv:
  - '2207.07775'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2207.07775
month: '01'
oa: 1
oa_version: Preprint
publication: Advances in Combinatorics
publication_identifier:
  eissn:
  - 2517-5599
publication_status: published
publisher: Alliance of Diamond Open Access Journals
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey multiplicity and the Turán coloring
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...