{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T09:14:30Z","timestamp":1655370870067},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the <jats:italic>triangle-free lemma<\/jats:italic>, states that for each <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline1.png\" \/><jats:tex-math>\n$\\epsilon&gt;0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> there exists <jats:italic>M<\/jats:italic> such that every triangle-free graph <jats:italic>G<\/jats:italic> has an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline2.png\" \/><jats:tex-math>\n$\\epsilon$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-approximate homomorphism to a triangle-free graph <jats:italic>F<\/jats:italic> on at most <jats:italic>M<\/jats:italic> vertices (here an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline3.png\" \/><jats:tex-math>\n$\\epsilon$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:italic>-approximate homomorphism<\/jats:italic> is a map <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline4.png\" \/><jats:tex-math>\n$V(G) \\to V(F)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> where all but at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline5.png\" \/><jats:tex-math>\n$\\epsilon \\left\\lvert{V(G)}\\right\\rvert^2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges of <jats:italic>G<\/jats:italic> are mapped to edges of <jats:italic>F<\/jats:italic>). One consequence of our results is that the least possible <jats:italic>M<\/jats:italic> in the triangle-free lemma grows faster than exponential in any polynomial in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000572_inline6.png\" \/><jats:tex-math>\n$\\epsilon^{-1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.<\/jats:p>","DOI":"10.1017\/s0963548321000572","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T07:12:06Z","timestamp":1643008326000},"page":"721-736","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Removal lemmas and approximate homomorphisms"],"prefix":"10.1017","volume":"31","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[]},{"given":"Yufei","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"S0963548321000572_ref25","doi-asserted-by":"crossref","unstructured":"[25] Pebody, L. (2018) Proof of a conjecture of Kleinberg-Sawin-Speyer. Discrete Anal., Paper No. 13, 7.","DOI":"10.19086\/da.3733"},{"key":"S0963548321000572_ref16","doi-asserted-by":"crossref","unstructured":"[16] Green, B. (2021) Lower bounds for corner-free sets. New Zealand J. Math. 51 1\u20132.","DOI":"10.53733\/86"},{"key":"S0963548321000572_ref31","unstructured":"[31] Tao, T. Entropy and rare events, blog post https:\/\/terrytao.wordpress.com\/2015\/09\/20\/entropy-and-rare-events\/."},{"key":"S0963548321000572_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-015-0324-9"},{"key":"S0963548321000572_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000048"},{"key":"S0963548321000572_ref19","doi-asserted-by":"crossref","unstructured":"[19] Kleinberg, R. , Speyer, D. E. and Sawin, W. (2018) The growth of tri-colored sum-free sets. Discrete Anal., Paper No. 12, 10.","DOI":"10.19086\/da.3734"},{"key":"S0963548321000572_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.12.003"},{"key":"S0963548321000572_ref30","unstructured":"[30] Szemer\u00e9di, E. (1978) Regular partitions of graphs. In Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloquium International CNRS, Vol. 260, CNRS, Paris, pp. 399\u2013401."},{"key":"S0963548321000572_ref3","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"S0963548321000572_ref6","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.7"},{"key":"S0963548321000572_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2018.06.004"},{"key":"S0963548321000572_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.09.037"},{"key":"S0963548321000572_ref14","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"S0963548321000572_ref4","doi-asserted-by":"crossref","unstructured":"[4] Blasiak, J. , Church, T. , Cohn, H. , Grochow, J. A. , Naslund, E. , Sawin, W. F. and Umans, C. (2017) On cap sets and the group-theoretic approach to matrix multiplication. Discrete Anal., Paper No. 3, 27.","DOI":"10.19086\/da.1245"},{"key":"S0963548321000572_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2320-x"},{"key":"S0963548321000572_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02789444"},{"key":"S0963548321000572_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"S0963548321000572_ref11","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rny240"},{"key":"S0963548321000572_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0080-y"},{"key":"S0963548321000572_ref23","doi-asserted-by":"publisher","DOI":"10.1112\/plms.12223"},{"key":"S0963548321000572_ref27","unstructured":"[27] Ruzsa, I. Z. and Szemer\u00e9di, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Vol. 18 of Colloquia Mathematica Societatis J\u00c1nos Bolyai, North-Holland, Amsterdam-New York, pp. 939\u2013945."},{"key":"S0963548321000572_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548321000572_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2019.47"},{"key":"S0963548321000572_ref28","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdp076"},{"key":"S0963548321000572_ref22","unstructured":"[22] Linial, N. and Shraibman, A. (2021) Larger corner-free sets from better NOF exactly-N protocols. Discrete Anal., Paper No. 19, 9."},{"key":"S0963548321000572_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"S0963548321000572_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0509-8"},{"key":"S0963548321000572_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_39"},{"key":"S0963548321000572_ref7","first-page":"339","article-title":"On large subsets of","volume":"185","author":"Ellenberg","year":"2017","journal-title":"Ann. Math. (2)"},{"key":"S0963548321000572_ref1","first-page":"9","article-title":"Sets of lattice points that form no squares","volume":"9","author":"Ajtai","year":"1974","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548321000572_ref8","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"S0963548321000572_ref13","unstructured":"[13] Fu, H. and Kleinberg, R. (2014) Improved lower bounds for testing triangle-freeness in Boolean functions via fast matrix multiplication. In Approximation, Randomization, and Combinatorial Optimization, Vol. 28 of LIPIcs. Leibniz International Proceedings in Informatics, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 669\u2013676."},{"key":"S0963548321000572_ref17","doi-asserted-by":"crossref","unstructured":"[17] Hell, P. and Ne\u0161etril, J. (1992) The Core of a Graph, Vol. 109 of Algebraic Graph Theory (Leibnitz, 1989), pp. 117\u2013126.","DOI":"10.1016\/0012-365X(92)90282-K"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T08:44:50Z","timestamp":1655282690000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000572\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S0963548321000572"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000572","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}