{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T04:27:08Z","timestamp":1728448028118},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T00:00:00Z","timestamp":1708041600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For graphs <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline1.png\"\/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline2.png\"\/><jats:tex-math>\n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the Ramsey number <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline3.png\"\/><jats:tex-math>\n$r(G,H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the smallest positive integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline4.png\"\/><jats:tex-math>\n$N$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that any red\/blue edge colouring of the complete graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline5.png\"\/><jats:tex-math>\n$K_N$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains either a red <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline6.png\"\/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or a blue <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline7.png\"\/><jats:tex-math>\n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A book <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline8.png\"\/><jats:tex-math>\n$B_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a graph consisting of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline9.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> triangles all sharing a common edge.<\/jats:p><jats:p>Recently, Conlon, Fox, and Wigderson conjectured that for any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline10.png\"\/><jats:tex-math>\n$0\\lt \\alpha \\lt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the random lower bound <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline11.png\"\/><jats:tex-math>\n$r(B_{\\lceil \\alpha n\\rceil },B_n)\\ge (\\sqrt{\\alpha }+1)^2n+o(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is not tight. In other words, there exists some constant <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline12.png\"\/><jats:tex-math>\n$\\beta \\gt (\\sqrt{\\alpha }+1)^2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline13.png\"\/><jats:tex-math>\n$r(B_{\\lceil \\alpha n\\rceil },B_n)\\ge \\beta n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for all sufficiently large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline14.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This conjecture holds for every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline15.png\"\/><jats:tex-math>\n$\\alpha \\lt 1\/6$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by a result of Nikiforov and Rousseau from 2005, which says that in this range <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline16.png\"\/><jats:tex-math>\n$r(B_{\\lceil \\alpha n\\rceil },B_n)=2n+3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for all sufficiently large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline17.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>We disprove the conjecture of Conlon, Fox, and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline18.png\"\/><jats:tex-math>\n$1\/4\\leq \\alpha \\leq 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Moreover, we show that for any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline19.png\"\/><jats:tex-math>\n$1\/6\\leq \\alpha \\le 1\/4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline20.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline21.png\"\/><jats:tex-math>\n$r(B_{\\lceil \\alpha n\\rceil }, B_n)\\le \\left (\\frac 32+3\\alpha \\right ) n+o(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where the inequality is asymptotically tight when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline22.png\"\/><jats:tex-math>\n$\\alpha =1\/6$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline23.png\"\/><jats:tex-math>\n$1\/4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also give a lower bound of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline24.png\"\/><jats:tex-math>\n$r(B_{\\lceil \\alpha n\\rceil }, B_n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000026_inline25.png\"\/><jats:tex-math>\n$1\/6\\le \\alpha \\lt \\frac{52-16\\sqrt{3}}{121}\\approx 0.2007$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox, and Wigderson holds in this interval.<\/jats:p>","DOI":"10.1017\/s0963548324000026","type":"journal-article","created":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T11:22:09Z","timestamp":1708082529000},"page":"432-445","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On a conjecture of Conlon, Fox, and Wigderson"],"prefix":"10.1017","volume":"33","author":[{"given":"Chunchao","family":"Fan","sequence":"first","affiliation":[]},{"given":"Qizhong","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Yuanhui","family":"Yan","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,2,16]]},"reference":[{"key":"S0963548324000026_ref15","first-page":"399","volume-title":"Probl\u00e8mes Combinatories et th\u00e9orie des graphs, (Colloq, Internat. CNRS, Univ. Orsay, Orsay","volume":"1976","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548324000026_ref18","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-13580-4_11","article-title":"Regularity lemmas for graphs, in: Fete of Combinatorics and Computer Science","volume":"20","author":"R\u00f6dl","year":"2010","journal-title":"Bolyai Soc. Math. Stud"},{"key":"S0963548324000026_ref9","first-page":"49","volume-title":"Surveys in Combinatorics","volume":"424","author":"Conlon","year":"2015"},{"key":"S0963548324000026_ref12","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1017\/S0963548322000360","article-title":"Off-diagonal book Ramsey numbers","volume":"32","author":"Conlon","year":"2023","journal-title":"Combin. Probab. Comput"},{"key":"S0963548324000026_ref7","doi-asserted-by":"crossref","first-page":"335","DOI":"10.2140\/pjm.1972.41.335","article-title":"Generalized Ramsey theory for graphs. III, small off-diagonal numbers","volume":"41","author":"Chv\u00e1tal","year":"1972","journal-title":"Pacific J. Math"},{"key":"S0963548324000026_ref16","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/3-540-45878-6_3","volume-title":"Theoretical Aspects of Computer Science","volume":"2292","author":"Koml\u00f3s","year":"2002"},{"key":"S0963548324000026_ref14","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/rsa.20081","article-title":"Book Ramsey numbers I","volume":"27","author":"Nikiforov","year":"2005","journal-title":"Ran Struc. Algor."},{"volume-title":"Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization","year":"2000","author":"Janson","key":"S0963548324000026_ref20"},{"key":"S0963548324000026_ref4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1002\/jgt.3190020110","article-title":"On Ramsey numbers for books","volume":"2","author":"Rousseau","year":"1978","journal-title":"J. Graph Theory"},{"key":"S0963548324000026_ref19","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie [in Hungarian], Math Fiz","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Lapok"},{"key":"S0963548324000026_ref11","first-page":"21","article-title":"Ramsey goodness of books revisited","volume":"4","author":"Fox","year":"2023","journal-title":"Adv. Combin."},{"key":"S0963548324000026_ref17","first-page":"295","volume-title":"Combinatorics, Paul Erd\u0151s is eighty","volume":"2","author":"Koml\u00f3s","year":"1996"},{"key":"S0963548324000026_ref13","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1002\/jgt.22815","article-title":"Ramsey numbers of large books","volume":"101","author":"Chen","year":"2022","journal-title":"J. Graph Theory"},{"key":"S0963548324000026_ref6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00493-021-4409-9","article-title":"Ramsey number of books and quasirandomness","volume":"42","author":"Conlon","year":"2022","journal-title":"Combinatorica"},{"key":"S0963548324000026_ref2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02018930","article-title":"The size Ramsey number","volume":"9","author":"Erd\u0151s","year":"1978","journal-title":"Period Math. Hungar"},{"key":"S0963548324000026_ref3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0195-6698(82)80038-3","article-title":"On finite Ramsey numbers","volume":"3","author":"Thomason","year":"1982","journal-title":"European J. Combin"},{"key":"S0963548324000026_ref8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/jgt.3190070106","article-title":"Generalizations of a Ramsey-theoretic result of Chv\u00e1tal","volume":"7","author":"Burr","year":"1983","journal-title":"J. Graph Theory"},{"key":"S0963548324000026_ref5","first-page":"12","article-title":"The Ramsey number of books","volume":"3","author":"Conlon","year":"2019","journal-title":"Adv. Combin."},{"key":"S0963548324000026_ref1","unstructured":"[1] Campos, M. , Griffiths, S. , Morris, R. and Sahasrabudhe, J. (2023) An exponential improvement for diagonal Ramsey. arXiv: 2303.09521v1, 2023."},{"key":"S0963548324000026_ref10","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s00493-009-2409-2","article-title":"Ramsey goodness and beyond","volume":"29","author":"Nikiforov","year":"2009","journal-title":"Combinatorica"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:08:26Z","timestamp":1728403706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000026\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,16]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0963548324000026"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000026","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,2,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}