{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:12Z","timestamp":1787323152759,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1082\/16"],"award-info":[{"award-number":["1082\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>What must one do in order to make acyclic a given oriented graph? Here we look at the structures that must be removed (or reversed) in order to make acyclic a given oriented graph. For a directed acyclic graph $H$ and an oriented graph $G$, let $f_H(G)$ be the maximum number of pairwise disjoint copies of $H$ that can be found in all feedback arc sets of $G$. In particular, to make $G$ acyclic, one must at least remove (or reverse) $f_H(G)$ pairwise disjoint copies of $H$. Perhaps most intriguing is the case where $H$ is a $k$-clique, in which case the parameter is denoted by $f_k(G)$. Determining $f_k(G)$ for arbitrary $G$ seems challenging. Here we essentially answer the problem, precisely, for the family of $k$-partite tournaments. Let $s(G)$ denote the size of the smallest vertex class of a $k$-partite tournament $G$. It is not difficult to show that $f_k(G) \\le s(G)-k+1$ (assume that $s(G) \\ge k-1$). Our main result is that for all sufficiently large $s=s(G)$, there are $k$-partite tournaments for which $f_k(G) = s(G)-k+1$. In fact, much more can be said: A random $k$-partite tournament $G$ satisfies $f_k(G) = s(G)-k+1$ almost surely (i.e., with probability tending to $1$ as $s(G)$ goes to infinity). In particular, as the title states, $f_k(G) = \\lfloor n\/k\\rfloor-k+1$ almost surely, where $G$ is a random orientation of the Tur\u00e1n graph $T(n,k)$.<\/jats:p>","DOI":"10.1137\/20m1356506","type":"journal-article","created":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T12:24:11Z","timestamp":1624364651000},"page":"1460-1477","source":"Crossref","is-referenced-by-count":0,"title":["All Feedback Arc Sets of a Random Tur\u00e1n Tournament Have $\\lfloor {n}\/{k}\\rfloor-{k}+1$ Disjoint ${k}$-Cliques (and This Is Tight)"],"prefix":"10.1137","volume":"35","author":[{"given":"Safwat","family":"Nassar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.01.011"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"atypb3","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , John Wiley & Sons, New York, 2004."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.02.002"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000642"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"J. Bang-Jensen and G. Z. Gutin,\n                      Digraphs: Theory, Algorithms and Applications\n                      , Springer-Verlag, Berlin, 2008.","DOI":"10.1007\/978-1-84800-998-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90060-6"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90007-7"},{"key":"atypb9","unstructured":"J. Fox, M. Kwan, and B. Sudakov,\n                      Acyclic Subgraphs of Tournaments with High Chromatic Number\n                      , preprint, arXiv:1912.07722, 2019."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.10.003"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003106"},{"key":"atypb12","first-page":"11","volume":"75","author":"Nassar S.","year":"2019","journal-title":"J. Combin. Theory Ser. B"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02412090"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.10.002"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010204"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1356506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:45:03Z","timestamp":1787319903000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1356506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1356506"],"URL":"https:\/\/doi.org\/10.1137\/20m1356506","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}