On Tournament Inversion Article Swipe
Related Concepts
Raphael Yuster
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1002/jgt.23251
· OA: W4409741553
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1002/jgt.23251
· OA: W4409741553
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 .
Related Topics
Finding more related topics…