2023/12/04 by Raphael Yuster, Yuster, Raphael · 1 citation
Engineering · #05C35 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2312.01910
openalex publication_date 2023/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An \it inversion of a tournament T is obtained by reversing the direction of all edges with both endpoints in some set of vertices. Let \rm invk(T) be the minimum length of a sequence of inversions using sets of size at most k that result in the transitive tournament. Let \rm invk(n) be the maximum of \rm invk(T) taken over n-vertex tournaments. It is well-known that \rm inv2(n)=(1+o(1))n2/4 and it was recently proved by Alon et al. that \rm inv(n):=\rm invn(n)=n(1+o(1)). In these two extreme cases (k=2 and k=n), random tournaments are asymptotically extremal objects. It is proved that the random tournament \em does not asymptotically attain \rm invk(n) when k ≥ k0 and conjectured that \rm inv3(n) is (only) attained by (quasi) random tournaments. It is further proved that (1+o(1))\rm inv3(n)/n2 ∈ [(1)/(12), 0.0992) and (1+o(1))\rm invk(n)/n2 ∈ [(1)/(2k(k-1))+δk, (1)/(2 \lfloor k2/2 \rfloor)-εk] where εk > 0 for all k ≥ 3 and δk > 0 for all k ≥ k0.