{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:36Z","timestamp":1787322996710,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We study two extremal problems about subgraphs excluding a family $\\mathcal{F}$ of graphs: (i) Among all graphs with $m$ edges, what is the smallest size $f(m,\\mathcal{F})$ of a largest $\\mathcal{F}$-free subgraph? (ii) Among all graphs with minimum degree $\\delta$ and maximum degree $\\Delta$, what is the smallest minimum degree $h(\\delta,\\Delta,\\mathcal{F})$ of a spanning $\\mathcal{F}$-free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $\\mathcal{F}$ is composed of all even cycles of length at most 2r, $r\\geq 2$. In this case, we give bounds on $f(m,\\mathcal{F})$ and $h(\\delta,\\Delta,\\mathcal{F})$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$, we show the existence of subgraphs with arbitrarily high girth and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.<\/jats:p>","DOI":"10.1137\/140954416","type":"journal-article","created":{"date-parts":[[2015,1,6]],"date-time":"2015-01-06T12:26:18Z","timestamp":1420547178000},"page":"65-78","source":"Crossref","is-referenced-by-count":12,"title":["Large Subgraphs without Short Cycles"],"prefix":"10.1137","volume":"29","author":[{"given":"F.","family":"Foucaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Perarnau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,6]]},"reference":[{"key":"atypb1","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 3rd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 2008."},{"key":"atypb2","unstructured":"B. Bolloba\u0301s,\n                      Extremal Graph Theory\n                      , Academic Press, New York, 1978."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-036-2"},{"key":"atypb5","unstructured":"D. Conlon, J. Fox, and B. Sudakov,\n                      Large Subgraphs Without Complete Bipartite Graphs\n                      , preprint, arXiv:1401.6711, 2014."},{"key":"atypb6","first-page":"135","author":"D","year":"1992","journal-title":"Amsterdam"},{"key":"atypb7","first-page":"623","volume":"7","author":"Erdo\u0308s P.","year":"1962","journal-title":"Magyar Tud. Akad. Mat. Kutato\u0301 Int. Ko\u0308zl."},{"key":"atypb8","first-page":"215","volume":"1","author":"Erdo\u0308s P.","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"atypb9","first-page":"51","volume":"1","author":"Erdo\u0308s P.","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Z. Fu\u0308redi and M. Simonovits,\n                      The History of Degenerate (Bipartite) Extremal Graph Problems\n                      , arXiv:1306.5167, 2013.","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00184-7"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01195001"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0010-2"},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"N5","DOI":"10.37236\/1972","volume":"12","author":"Lam T.","year":"2005","journal-title":"Electron. J. Combin."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00569-0"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)90107-3"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed,\n                      Graph Colouring and the Probabilistic Method\n                      , Springer, New York, 2002.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007029"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020254"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90067-9"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140954416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:34Z","timestamp":1787319394000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140954416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140954416"],"URL":"https:\/\/doi.org\/10.1137\/140954416","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}