Search

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 fH(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) fH(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 fk(G). Determining fk(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 fk(G) \leq s(G) k + 1 (assume that s(G) geq k 1). Our main result is that for all sufficiently large s = s(G), there are k-partite tournaments for which fk(G) = s(G) k + 1. In fact, much more can be said: A random k-partite tournament G satisfies fk(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, fk(G) = lfloor nkrfloor k +1 almost surely, where G is a random orientation of the Tur'an graph T(n, k). [ABSTRACT FROM AUTHOR]