A003141 Minimal number of arcs whose reversal yields a transitive tournament.

0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20, 22, 28

Offset: 0

Author

N. J. A. Sloane

Keywords

• hard
• more
• nonn
• nice

Comments

This is the "minimum feedback arc set" problem.

The minimal number of arcs you need to delete to make a directed graph acyclic (maxed over all n-vertex directed graphs) is the same as the minimal number of arcs you need to reverse to make a tournament acyclic (maxed over all n-player tournaments).

References

• Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25.
• J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]
• I. Charon and O. Hudry, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Ann. Oper. Res. 175 (2010), 107-158
• Don Coppersmith, Lisa Fleischer and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, SODA 2006: 776-782.
• Robert A. Laird and Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547-552.
• Range Voting Yahoo Group, Range Voting.
• Range Voting Yahoo Group, Introduction. [Cached copy]
• RangeVoting.org, Group Website.
• K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.
• W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs [Has much more information]
• Index entries for sequences related to tournaments

Crossrefs

Equals C(n, 2) - A001225.

a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond]

Formula

The asymptotics for large n are (n+1)*n/4 - C*n^(3/2) <= F(n) <= (n+1)*n/4 - K*n^(3/2) for all sufficiently large n and certain constants C, K > 0. - Warren D. Smith, Sep 14 2006

Extensions

More terms from Irène Charon and Olivier Hudry

Terms a(12) and a(13) from Christian Stricker, Jan 14 2017