{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T14:46:41Z","timestamp":1772376401786,"version":"3.50.1"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2017,6,6]],"date-time":"2017-06-06T00:00:00Z","timestamp":1496707200000},"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":[[2017,9]]},"abstract":"<jats:p>For an orientation <jats:italic>H<\/jats:italic> with <jats:italic>n<\/jats:italic> vertices, let <jats:italic>T<\/jats:italic>(<jats:italic>H<\/jats:italic>) denote the maximum possible number of labelled copies of <jats:italic>H<\/jats:italic> in an <jats:italic>n<\/jats:italic>-vertex tournament. It is easily seen that <jats:italic>T<\/jats:italic>(<jats:italic>H<\/jats:italic>) \u2265 <jats:italic>n<\/jats:italic>!\/2<jats:sup><jats:italic>e<\/jats:italic>(<jats:italic>H<\/jats:italic>)<\/jats:sup>, as the latter is the expected number of such copies in a random tournament. For <jats:italic>n<\/jats:italic> odd, let <jats:italic>R<\/jats:italic>(<jats:italic>H<\/jats:italic>) denote the maximum possible number of labelled copies of <jats:italic>H<\/jats:italic> in an <jats:italic>n<\/jats:italic>-vertex regular tournament. In fact, Adler, Alon and Ross proved that for <jats:italic>H<\/jats:italic>=<jats:italic>C<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, the directed Hamilton cycle, <jats:italic>T<\/jats:italic>(<jats:italic>C<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) \u2265 (<jats:italic>e\u2212o<\/jats:italic>(1))<jats:italic>n<\/jats:italic>!\/2<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>, and it was observed by Alon that already <jats:italic>R<\/jats:italic>(<jats:italic>C<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) \u2265 (<jats:italic>e\u2212o<\/jats:italic>(1))<jats:italic>n<\/jats:italic>!\/2<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>. Similar results hold for the directed Hamilton path <jats:italic>P<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results, and prove that they hold for a larger family of orientations <jats:italic>H<\/jats:italic> which includes all bounded-degree Eulerian orientations and all bounded-degree balanced orientations, as well as many others. One corollary of our method is that for any fixed <jats:italic>k<\/jats:italic>, every <jats:italic>k<\/jats:italic>-regular orientation <jats:italic>H<\/jats:italic> with <jats:italic>n<\/jats:italic> vertices satisfies <jats:italic>T<\/jats:italic>(<jats:italic>H<\/jats:italic>) \u2265 (<jats:italic>e<\/jats:italic><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>\u2212<jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic>!\/2<jats:sup><jats:italic>e<\/jats:italic>(<jats:italic>H<\/jats:italic>)<\/jats:sup>, and in fact, for <jats:italic>n<\/jats:italic> odd, <jats:italic>R<\/jats:italic>(<jats:italic>H<\/jats:italic>) \u2265 (<jats:italic>e<\/jats:italic><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>\u2212<jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic>!\/2<jats:sup><jats:italic>e<\/jats:italic>(<jats:italic>H<\/jats:italic>)<\/jats:sup>.<\/jats:p>","DOI":"10.1017\/s0963548317000153","type":"journal-article","created":{"date-parts":[[2017,6,6]],"date-time":"2017-06-06T03:22:53Z","timestamp":1496719373000},"page":"775-796","source":"Crossref","is-referenced-by-count":2,"title":["On the Maximum Number of Spanning Copies of an Orientation in a Tournament"],"prefix":"10.1017","volume":"26","author":[{"given":"RAPHAEL","family":"YUSTER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,6,6]]},"reference":[{"key":"S0963548317000153_ref11","unstructured":"Keevash P. (2014) The existence of designs. arXiv:1401.3665"},{"key":"S0963548317000153_ref5","first-page":"3","volume-title":"Handbook of Combinatorics","author":"Bondy","year":"1995"},{"key":"S0963548317000153_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.06.001"},{"key":"S0963548317000153_ref14","first-page":"223","article-title":"Kombinatorikai vizsg\u00e1latok az ir\u00e1nyitott teljes gr\u00e1ffal kapcsolatban","volume":"50","author":"Szele","year":"1943","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548317000153_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895727"},{"key":"S0963548317000153_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128667"},{"key":"S0963548317000153_ref3","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2016.v7.n2.a2"},{"key":"S0963548317000153_ref17","first-page":"647","article-title":"Decomposition of complete graphs into subgraphs isomorphic to a given graph","volume":"XV","author":"Wilson","year":"1975","journal-title":"Congress. Numer."},{"key":"S0963548317000153_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.030"},{"key":"S0963548317000153_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006863"},{"key":"S0963548317000153_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1010"},{"key":"S0963548317000153_ref16","first-page":"436","article-title":"On an extremal problem in graph theory (in Hungarian)","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548317000153_ref18","unstructured":"Wormald N. Tournaments with many Hamilton cycles. Manuscript."},{"key":"S0963548317000153_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80023-8"},{"key":"S0963548317000153_ref15","first-page":"159","article-title":"Hamilton circuits in regular tournaments","volume":"27","author":"Thomassen","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S0963548317000153_ref10","unstructured":"Gustavsson T. (1991) Decompositions of large graphs and digraphs with high minimum degree. PhD thesis, University of Stockholm."},{"key":"S0963548317000153_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008170"},{"key":"S0963548317000153_ref4","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"1978"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T19:59:00Z","timestamp":1555444740000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000153\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,6]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["S0963548317000153"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000153","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,6]]}}}