2-PARTITION-TRANSITIVE TOURNAMENTS

Given a tournament score sequence s(1) greater than or equal to s(2) g reater than or equal to ... greater than or equal to s(n), we prove th at there exists a tournament T on vertex set {1, 2,...., n} such that the degree of any vertex i is s(i) and the subtournaments of Ton both the even and the odd vertices are transitive in the given order. This means that i beats j whenever i < j and i = j (mod 2). For any score s equence, we give an algorithm to construct a tournament of the above f orm, i.e. it is transitive on evens and odds in the given order. This algorithm fixes half of the edges of the tournament and then is simila r to the algorithm for constructing a tournament given its score seque nce. Another consequence provides asymptotics for the maximum number o f edges in score unavoidable digraphs. From a result of Ryser, it is p ossible to get From any tournament to this special tournament by a seq uence of triangle reversals. We show that n(2)/2 reversals are always enough and that in some cases (l-o(1)) n(2)/32 are required. We also s how that such a sequence of triangle reversals can be found in O(n(2)) time. (C) 1998 Academic Press.