{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T20:58:29Z","timestamp":1774472309306,"version":"3.50.1"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,11,10]],"date-time":"2020-11-10T00:00:00Z","timestamp":1604966400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Erd\u0151s\u2013Simonovits stability theorem states that for all <jats:italic>\u03b5<\/jats:italic> &gt; 0 there exists <jats:italic>\u03b1<\/jats:italic> &gt; 0 such that if <jats:italic>G<\/jats:italic> is a <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r+<\/jats:italic>1<\/jats:sub>-free graph on <jats:italic>n<\/jats:italic> vertices with <jats:italic>e<\/jats:italic>(<jats:italic>G<\/jats:italic>) &gt; ex(<jats:italic>n<\/jats:italic>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic>+1<\/jats:sub>)\u2013 <jats:italic>\u03b1 n<\/jats:italic><jats:sup>2<\/jats:sup>, then one can remove <jats:italic>\u03b5n<\/jats:italic><jats:sup>2<\/jats:sup> edges from <jats:italic>G<\/jats:italic> to obtain an <jats:italic>r<\/jats:italic>-partite graph. F\u00fcredi gave a short proof that one can choose <jats:italic>\u03b1<\/jats:italic> = <jats:italic>\u03b5<\/jats:italic>. We give a bound for the relationship of <jats:italic>\u03b1<\/jats:italic> and <jats:italic>\u03b5<\/jats:italic> which is asymptotically sharp as <jats:italic>\u03b5<\/jats:italic> \u2192 0.<\/jats:p>","DOI":"10.1017\/s0963548320000590","type":"journal-article","created":{"date-parts":[[2020,11,10]],"date-time":"2020-11-10T08:01:32Z","timestamp":1604995292000},"page":"609-618","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Making <i>K<\/i><sub><i>r<\/i>+1<\/sub>-free graphs <i>r<\/i>-partite"],"prefix":"10.1017","volume":"30","author":[{"given":"J\u00f3zsef","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix Christian","family":"Clemen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Lavrov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Lidick\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Pfender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,11,10]]},"reference":[{"key":"S0963548320000590_ref11","unstructured":"[11] Hu, P. , Lidick\u00fd, B. , Martins, T. , Norin, S. and Volec, J. Large multipartite subgraphs in H-free graphs. Manuscript."},{"key":"S0963548320000590_ref1","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1654"},{"key":"S0963548320000590_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.001"},{"key":"S0963548320000590_ref18","doi-asserted-by":"publisher","DOI":"10.37236\/4717"},{"key":"S0963548320000590_ref4","unstructured":"[4] Brouwer, A. E. (1981) Some Lotto Numbers From an Extension of Tur\u00e1n\u2019s Theorem, Vol. 152 of Afdeling Zuivere Wiskunde [Department of Pure Mathematics]. Mathematisch Centrum, Amsterdam."},{"key":"S0963548320000590_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90057-3"},{"key":"S0963548320000590_ref5","first-page":"249","article-title":"On the graph theorem of Tur\u00e1n","volume":"21","author":"Erd\u0151s","year":"1970","journal-title":"Mat. Lapok"},{"key":"S0963548320000590_ref12","first-page":"12","article-title":"Maximum Kr+1-free graphs which are not r-partite","volume":"24","author":"Kang","year":"2005","journal-title":"Mat. Stud."},{"key":"S0963548320000590_ref7","unstructured":"[7] Erd\u0151s, P. , Gyr\u0151i, E. and Simonovits, M. (1992) How many edges should be deleted to make a triangle-free graph bipartite? In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 239\u2013263. North-Holland."},{"key":"S0963548320000590_ref3","first-page":"6439","article-title":"Trans. Amer.Math","volume":"368","author":"Balogh","year":"2016","journal-title":"Soc."},{"key":"S0963548320000590_ref8","first-page":"51","article-title":"A limit theorem in graph theory","volume":"1","author":"Erd\u0151s","year":"1966","journal-title":"Studia Sci. Math. Hungar"},{"key":"S0963548320000590_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548320000590_ref14","first-page":"141","volume-title":"Series","author":"Nikiforov","year":"2011"},{"key":"S0963548320000590_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.07.004"},{"key":"S0963548320000590_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2238-0"},{"key":"S0963548320000590_ref10","first-page":"159","article-title":"k-saturated graphs of chromatic number at least k","volume":"31","author":"Hanson","year":"1991","journal-title":"Ars Combin."},{"key":"S0963548320000590_ref17","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548320000590_ref13","unstructured":"[13] Kor\u00e1ndi, D. , Roberts, A. and Scott, A. (2020) Exact stability for Tur\u00e1n\u2019s theorem. arXiv:2004.10685"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T14:34:36Z","timestamp":1623335676000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000590\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000590"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000590","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,10]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. 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 (http:\/\/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"}]}}