---
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'
...
---
OA_place: repository
OA_type: green
_id: '22176'
abstract:
- lang: eng
  text: "The Ramsey number r(G,H) is the minimum N such that every graph on N vertices
    contains G as a subgraph or its complement contains H as a subgraph. For integers
    n≥k≥1, the k-book Bk,n is the graph on n vertices consisting of a copy of Kk,
    called the spine, as well as n−k additional vertices each adjacent to every vertex
    of the spine and non-adjacent to each other. A connected graph H on n vertices
    is called p-good if r(Kp,H)=(p−1)(n−1)+1. Nikiforov and Rousseau proved that if
    n is sufficiently large in terms of p and k, then Bk,n is p-good. Their proof
    uses Szemerédi's regularity lemma and gives a tower-type bound on n. We give a
    short new proof that avoids using the regularity method and shows that every Bk,n
    with n≥2k10p is p-good.\r\nUsing Szemerédi's regularity lemma, Nikiforov and Rousseau
    also proved much more general goodness-type results, proving a tight bound on
    r(G,H) for several families of sparse graphs G and H as long as |V(G)|<δ|V(H)|
    for a small constant δ>0. Using our techniques, we prove a new result of this
    type, showing that r(G,H)=(p−1)(n−1)+1 when H=Bk,n and G is a complete p-partite
    graph whose first p−1 parts have constant size and whose last part has size δn,
    for some small constant δ>0. Again, our proof does not use the regularity method,
    and thus yields double-exponential bounds on δ.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, He X, Wigderson Y. Ramsey goodness of books revisited. <i>Advances in
    Combinatorics</i>. 2023. doi:<a href="https://doi.org/10.19086/aic.2023.4">10.19086/aic.2023.4</a>
  apa: Fox, J., He, X., &#38; Wigderson, Y. (2023). Ramsey goodness of books revisited.
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals. <a
    href="https://doi.org/10.19086/aic.2023.4">https://doi.org/10.19086/aic.2023.4</a>
  chicago: Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey Goodness of Books Revisited.”
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
    <a href="https://doi.org/10.19086/aic.2023.4">https://doi.org/10.19086/aic.2023.4</a>.
  ieee: J. Fox, X. He, and Y. Wigderson, “Ramsey goodness of books revisited,” <i>Advances
    in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
  ista: Fox J, He X, Wigderson Y. 2023. Ramsey goodness of books revisited. Advances
    in Combinatorics.
  mla: Fox, Jacob, et al. “Ramsey Goodness of Books Revisited.” <i>Advances in Combinatorics</i>,
    Alliance of Diamond Open Access Journals, 2023, doi:<a href="https://doi.org/10.19086/aic.2023.4">10.19086/aic.2023.4</a>.
  short: J. Fox, X. He, Y. Wigderson, Advances in Combinatorics (2023).
date_created: 2026-06-29T10:58:11Z
date_published: 2023-07-29T00:00:00Z
date_updated: 2026-07-14T09:05:44Z
day: '29'
doi: 10.19086/aic.2023.4
extern: '1'
external_id:
  arxiv:
  - '2109.09205'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2109.09205
month: '07'
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 goodness of books revisited
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...