Short score certificates for upset tournaments (Q1386146)

The score certificate number of a labelled tournament \(T\) is the size \(\text{sc} (T)\) of the smallest set \(D\) of arcs with the property that every tournament containing the arcs of \(D\) and having the same score list as \(T\) is identical to \(T\). A tournament \(T_n\) with \(n\geq 4\) nodes is an upset tournament if its score list is \(\{1,1,2,3, \dots, n-3, n-2, n-2\}\); an example of such a tournament is the nearly transitive tournament \(N_n\) with arcs \(\nu_1 \nu_n\) and \(\nu_i \nu_j\) for all other \(\nu_i\) and \(\nu_j\) with \(i>j\). The authors show, among other things, that \(\text{sc} (T_n)\leq 2n-3\) for all upset tournaments \(T_n\) and that \(\text{sc} (N_n)= n+3\) when \(n\geq 10\).