{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:21:54Z","timestamp":1777425714789,"version":"3.51.4"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"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":"Abstract<\/jats:title>We show that for every \n$\\eta \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> every sufficiently large \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex oriented graph \n$D$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of minimum semidegree exceeding \n$(1+\\eta )\\frac k2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains every balanced antidirected tree with \n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges and bounded maximum degree, if \n$k\\ge \\eta n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs.<\/jats:p>Further, we show that in the same setting, \n$D$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains every \n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length \n$1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or \n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> span a forest. As a special case, we can find all antidirected cycles of length at most \n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomass\u00e9 for antidirected trees in digraphs. We show that this conjecture is asymptotically true in \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548324000038","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T07:18:30Z","timestamp":1709709510000},"page":"446-466","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Antidirected subgraphs of oriented graphs"],"prefix":"10.1017","volume":"33","author":[{"given":"Maya","family":"Stein","sequence":"first","affiliation":[]},{"given":"Camila","family":"Z\u00e1rate-Guer\u00e9n","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"key":"S0963548324000038_ref17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.jctb.2022.04.007","article-title":"Spanning trees in dense directed graphs","volume":"156","author":"Kathapurkar","year":"2022","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000038_ref26","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02579379","article-title":"Degree and local connectivity in digraphs","volume":"5","author":"Mader","year":"1985","journal-title":"Combinatorica"},{"key":"S0963548324000038_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jctb.2021.10.002","article-title":"Dichromatic number and forced subdivisions","volume":"153","author":"Gishboliner","year":"2022","journal-title":"J. Comb. Theory, Ser. B"},{"key":"S0963548324000038_ref2","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1016\/j.disc.2013.01.011","article-title":"Oriented trees in digraphs","volume":"313","author":"Addario-Berry","year":"2013","journal-title":"Discr. Math."},{"key":"S0963548324000038_ref21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.jctb.2009.08.002","article-title":"Cycles of given length in oriented graphs","volume":"100","author":"Kelly","year":"2010","journal-title":"J. Comb. Theory Ser. B"},{"key":"S0963548324000038_ref31","unstructured":"[31] Szemer\u00e9di, E. (1978) Regular partitions of graphs. Probl\u00e9mes Combinatoires et Th\u00e9orie des Graphes Colloques Internationaux CNRS 260, 399\u2013401."},{"key":"S0963548324000038_ref3","unstructured":"[3] Ajtai, M. , Koml\u00f3s, J. and Szemer\u00e9di, E. (1995) On a Conjecture of Loebl. In: Proceedings of the 7th International Conference on Graph Theory, Combinatorics, and Algorithms. Wiley, New York, pp. 1135\u20131146."},{"key":"S0963548324000038_ref14","doi-asserted-by":"crossref","first-page":"329","DOI":"10.4153\/CMB-1970-063-1","article-title":"On subtrees of directed graphs with no path of length exceeding one","volume":"13","author":"Graham","year":"1970","journal-title":"Canad. Math. Bull."},{"key":"S0963548324000038_ref32","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/S0195-6698(85)80025-1","article-title":"Even cycles in directed graphs","volume":"6","author":"Thomassen","year":"1985","journal-title":"Eur. J. Combin."},{"key":"S0963548324000038_ref4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/j.jcss.2004.04.008","article-title":"Testing subgraphs in directed graphs","volume":"69","author":"Alon","year":"2004","journal-title":"J. Comput. Syst. Sci."},{"key":"S0963548324000038_ref5","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1137\/18M1210861","article-title":"Degree conditions for embedding trees","volume":"33","author":"Besomi","year":"2019","journal-title":"SIAM J. Discr. Math."},{"key":"S0963548324000038_ref19","doi-asserted-by":"crossref","first-page":"P186","DOI":"10.37236\/673","article-title":"Arbitrary Orientations of Hamilton Cycles in Oriented Graphs","volume":"18","author":"Kelly","year":"2011","journal-title":"Electron. J. Comb."},{"key":"S0963548324000038_ref7","unstructured":"[7] Burr, S. (1980) Subtrees of Directed Graphs and Hypergraphs. In:Proceedings of the Eleventh South- eastern Conference on Combinatorics, Graph Theory and Combinatorics Florida Atlantic University, Boca Raton, FL, pp. 227\u2013239."},{"key":"S0963548324000038_ref16","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1006\/eujc.1998.0231","article-title":"Extremal digraph results for topological complete tournaments","volume":"19","author":"Jagger","year":"1998","journal-title":"Eur. J. Combin."},{"key":"S0963548324000038_ref29","first-page":"459","volume-title":"Discrete Mathematics and Applications","author":"Stein","year":"2021"},{"key":"S0963548324000038_ref23","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1017\/S0963548300001620","article-title":"Proof of a packing conjecture of Bollob\u00e1s","volume":"4","author":"Koml\u00f3s","year":"1995","journal-title":"Comb. Prob. Comp."},{"key":"S0963548324000038_ref27","unstructured":"[27] Mycroft, R. and Naia, T. (2020) Trees and tree-like structures in dense digraphs. arXiv preprint: 2012.09201."},{"key":"S0963548324000038_ref11","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.jctb.2020.09.006","article-title":"Subdivisions of digraphs in tournaments","volume":"146","author":"Gir\u00e3o","year":"2021","journal-title":"J. Comb. Theory, Ser. B"},{"key":"S0963548324000038_ref1","doi-asserted-by":"crossref","first-page":"P3.19","DOI":"10.37236\/6521","article-title":"Sub- divisions in digraphs of large out-degree or large dichromatic number","volume":"26","author":"Aboulker","year":"2019","journal-title":"Elect. J. Comb."},{"key":"S0963548324000038_ref22","doi-asserted-by":"crossref","unstructured":"[22] Klimo\u0161ov\u00e1, T. and Stein, M. (2022) Antipaths in oriented graphs(In preparation).","DOI":"10.1016\/j.disc.2023.113515"},{"key":"S0963548324000038_ref25","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01364272","article-title":"Homomorphieeigenschaften und mittlere Kantendichte von Graphen","volume":"174","author":"Mader","year":"1967","journal-title":"Math. Ann."},{"key":"S0963548324000038_ref10","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF02024498","article-title":"On maximal paths and circuits of graphs","volume":"10","author":"Erd\u0151s","year":"1959","journal-title":"Act Math Acad Sci Hung"},{"key":"S0963548324000038_ref8","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1002\/jgt.22360","article-title":"Subdivisions of oriented cycles in digraphs with large chromatic number","volume":"89","author":"Cohen","year":"2018","journal-title":"J. Graph Theor."},{"key":"S0963548324000038_ref30","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1002\/jgt.23020","article-title":"Subdivisions with congruence constraints in digraphs of large chromatic number","volume":"105","author":"Steiner","year":"2024","journal-title":"J. Graph Thr."},{"key":"S0963548324000038_ref24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.20255","article-title":"A note on complete subdivisions in digraphs of large outdegree","volume":"57","author":"K\u00fchn","year":"2008","journal-title":"J. Graph Theor."},{"key":"S0963548324000038_ref9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","article-title":"Some theorems on abstract graphs","volume":"s3","author":"Dirac","year":"1952","journal-title":"Proc. London Math. Soc."},{"key":"S0963548324000038_ref15","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/jgt.3190050204","article-title":"Long paths and cycles in oriented graphs","volume":"5","author":"Jackson","year":"1981","journal-title":"J. Graph Theor."},{"key":"S0963548324000038_ref28","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1006\/eujc.2000.0406","article-title":"Subdivisions of Transitive Tournaments","volume":"21","author":"Scott","year":"2000","journal-title":"Eur. J. Combin."},{"key":"S0963548324000038_ref20","first-page":"689","article-title":"A Dirac type result on Hamilton cycles in oriented graphs","volume":"17","author":"Kelly","year":"2008","journal-title":"Comb. Prob. Comp."},{"key":"S0963548324000038_ref6","doi-asserted-by":"crossref","first-page":"2108","DOI":"10.1137\/19M1277667","article-title":"Maximum and minimum degree conditions for embedding trees","volume":"34","author":"Besomi","year":"2020","journal-title":"SIAM J. Discr. Math."},{"key":"S0963548324000038_ref18","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1112\/jlms\/jdn065","article-title":"An exact minimum degree condition for Hamilton cycles in oriented graphs","volume":"79","author":"Keevash","year":"2009","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548324000038_ref13","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1007\/s00493-021-4750-z","article-title":"Oriented cycles in digraphs of large outdegree","volume":"42","author":"Gishboliner","year":"2022","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\/S0963548324000038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:08:24Z","timestamp":1728403704000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000038\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,6]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0963548324000038"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000038","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,6]]},"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"}}]}}