On Tournament Inversion
Raphael Yuster · Journal of Graph Theory · 2025
ABSTRACT An inversion of a tournament is obtained by reversing the direction of all edges with both endpoints in some set of vertices. Let be the minimum length of a sequence of inversions using sets of size at most that result in the transitive tournament. Let be the maximum of taken over ‐vertex tournaments. It is well known that and it was recently proved by Alon et al. that . In these two extreme cases ( and ), random tournaments are extremal objects. It is proved that is not attained by random tournaments when and conjectured that is (only) attained by (quasi)random tournaments. It is further proved that and , where for all and for all .