

A003141


Minimal number of arcs whose reversal yields a transitive tournament.
(Formerly M2334)


5



0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20, 22, 28
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


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 nvertex directed graphs) is the same as the minimal number of arcs you need to reverse to make a tournament acyclic (maxed over all nplayer tournaments).


REFERENCES

SanchezFlores, NeumannLara and Bermond, Graphs & Combin 10 (1994) 363366 and 367376.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=0..13.
J.C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 525.
J.C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 525. [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), 107158
Don Coppersmith, Lisa Fleischer and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, SODA 2006: 776782.
Robert A. Laird, Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547552.
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), 261264.
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


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


CROSSREFS

Equals C(n, 2)  A001225.
a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond]
Sequence in context: A129819 A025032 A207524 * A284491 A284506 A157419
Adjacent sequences: A003138 A003139 A003140 * A003142 A003143 A003144


KEYWORD

hard,more,nonn,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Irène Charon and Olivier Hudry.
Terms a(12) and a(13) from Christian Stricker, Jan 14 2017


STATUS

approved



