[{"publication_status":"published","quality_controlled":"1","extern":"1","publication":"Advances in Combinatorics","title":"Ramsey multiplicity and the Turán coloring","author":[{"last_name":"Fox","full_name":"Fox, Jacob","first_name":"Jacob"},{"id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval","last_name":"Wigderson","full_name":"Wigderson, Yuval"}],"date_published":"2023-01-01T00:00:00Z","article_type":"original","date_updated":"2026-07-14T08:45:53Z","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."}],"month":"01","oa_version":"Preprint","publication_identifier":{"eissn":["2517-5599"]},"type":"journal_article","citation":{"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>","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>","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>.","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.","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>.","ista":"Fox J, Wigderson Y. 2023. Ramsey multiplicity and the Turán coloring. Advances in Combinatorics.","short":"J. Fox, Y. Wigderson, Advances in Combinatorics (2023)."},"article_processing_charge":"No","status":"public","_id":"22170","year":"2023","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2207.07775"}],"date_created":"2026-06-29T10:55:46Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"external_id":{"arxiv":["2207.07775"]},"language":[{"iso":"eng"}],"OA_place":"repository","scopus_import":"1","doi":"10.19086/aic.2023.2","arxiv":1,"publisher":"Alliance of Diamond Open Access Journals","day":"01","OA_type":"green"},{"OA_place":"repository","language":[{"iso":"eng"}],"external_id":{"arxiv":["2109.09205"]},"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-06-29T10:58:11Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2109.09205"}],"year":"2023","day":"29","OA_type":"green","publisher":"Alliance of Diamond Open Access Journals","arxiv":1,"doi":"10.19086/aic.2023.4","scopus_import":"1","date_published":"2023-07-29T00:00:00Z","author":[{"last_name":"Fox","full_name":"Fox, Jacob","first_name":"Jacob"},{"full_name":"He, Xiaoyu","last_name":"He","first_name":"Xiaoyu"},{"first_name":"Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval","last_name":"Wigderson"}],"title":"Ramsey goodness of books revisited","publication":"Advances in Combinatorics","extern":"1","quality_controlled":"1","publication_status":"published","_id":"22176","status":"public","article_processing_charge":"No","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>","short":"J. Fox, X. He, Y. Wigderson, Advances in Combinatorics (2023).","ista":"Fox J, He X, Wigderson Y. 2023. Ramsey goodness of books revisited. Advances in Combinatorics.","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.","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>."},"type":"journal_article","publication_identifier":{"eissn":["2517-5599"]},"oa_version":"Preprint","month":"07","abstract":[{"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","lang":"eng"}],"date_updated":"2026-07-14T09:05:44Z","article_type":"original"}]