{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T12:25:17Z","timestamp":1706185517492},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>For a directed graph <jats:italic>G<\/jats:italic> without loops or parallel edges, let \u03b2(<jats:italic>G<\/jats:italic>) denote the size of the smallest feedback arc set, <jats:italic>i.e.<\/jats:italic>, the smallest subset <jats:italic>X<\/jats:italic> \u2282 <jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) such that <jats:italic>G<\/jats:italic> \u2216 <jats:italic>X<\/jats:italic> has no directed cycles. Let \u03b3(<jats:italic>G<\/jats:italic>) be the number of unordered pairs of vertices of <jats:italic>G<\/jats:italic> which are not adjacent. We prove that every directed graph whose shortest directed cycle has length at least <jats:italic>r<\/jats:italic> \u2265 4 satisfies \u03b2(<jats:italic>G<\/jats:italic>) \u2264 <jats:italic>c<\/jats:italic>\u03b3(<jats:italic>G<\/jats:italic>)\/<jats:italic>r<\/jats:italic><jats:sup>2<\/jats:sup>, where <jats:italic>c<\/jats:italic> is an absolute constant. This is tight up to the constant factor and extends a result of Chudnovsky, Seymour and Sullivan.<\/jats:p><jats:p>This result can also be used to answer a question of Yuster concerning almost given length cycles in digraphs. We show that for any fixed 0 &lt; \u03b8 &lt; 1\/2 and sufficiently large <jats:italic>n<\/jats:italic>, if <jats:italic>G<\/jats:italic> is a digraph with <jats:italic>n<\/jats:italic> vertices and \u03b2(<jats:italic>G<\/jats:italic>) \u2265 \u03b8<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>, then for any 0 \u2264 <jats:italic>m<\/jats:italic> \u2264 \u03b8<jats:italic>n<\/jats:italic> \u2212 <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>) it contains a directed cycle whose length is between <jats:italic>m<\/jats:italic> and <jats:italic>m<\/jats:italic> + 6\u03b8<jats:sup>\u22121\/2<\/jats:sup>. Moreover, there is a constant <jats:italic>C<\/jats:italic> such that either <jats:italic>G<\/jats:italic> contains directed cycles of every length between <jats:italic>C<\/jats:italic> and \u03b8<jats:italic>n<\/jats:italic> \u2212 <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>) or it is close to a digraph <jats:italic>G<\/jats:italic>\u2032 with a simple structure: every strong component of <jats:italic>G<\/jats:italic>\u2032 is periodic. These results are also tight up to the constant factors.<\/jats:p>","DOI":"10.1017\/s0963548309990460","type":"journal-article","created":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T08:43:43Z","timestamp":1254386623000},"page":"285-301","source":"Crossref","is-referenced-by-count":5,"title":["Directed Graphs Without Short Cycles"],"prefix":"10.1017","volume":"19","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PETER","family":"KEEVASH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,10,1]]},"reference":[{"key":"S0963548309990460_ref9","first-page":"295","volume-title":"Combinatorics: Paul Erd\u0151s is Eighty","author":"Koml\u00f3s","year":"1996"},{"key":"S0963548309990460_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2331-z"},{"key":"S0963548309990460_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"S0963548309990460_ref13","unstructured":"[13] Sullivan B. (2008) Extremal problems in digraphs. PhD thesis, Princeton University."},{"key":"S0963548309990460_ref12","volume-title":"The Logical Design of Operating Systems","author":"Shaw","year":"1974"},{"key":"S0963548309990460_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759032"},{"key":"S0963548309990460_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"S0963548309990460_ref3","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"Bang-Jensen","year":"2001"},{"key":"S0963548309990460_ref4","unstructured":"[4] Caccetta L. and H\u00e4ggkvist R. (1978) On minimal digraphs with given girth. In Proc. 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton 1978), Congress. Numer. XXI 181\u2013187."},{"key":"S0963548309990460_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"},{"key":"S0963548309990460_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0769-1"},{"key":"S0963548309990460_ref6","unstructured":"[6] Christofides D. , Keevash P. , K\u00fchn D. and Osthus D. Finding Hamilton cycles in robustly expanding digraphs. Submitted."},{"key":"S0963548309990460_ref11","unstructured":"[11] Nathanson M. B. The Caccetta\u2013H\u00e4ggkvist conjecture and additive number theory. AIM Preprint 2006-10: www.aimath.org\/preprints.html."},{"key":"S0963548309990460_ref14","unstructured":"[14] Sullivan B. A summary of results and problems related to the Caccetta\u2013H\u00e4ggkvist conjecture. AIM Preprint 2006-13: www.aimath.org\/preprints.html."},{"key":"S0963548309990460_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990460","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T20:32:29Z","timestamp":1556483549000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990460\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,1]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["S0963548309990460"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990460","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,1]]}}}