Short Score Certificates for Upset Tournaments

Abstract

A score certificate for a tournament, $T$, is a collection of arcs of $T$ which can be uniquely completed to a tournament with the same score-list as $T$'s, and the score certificate number of $T$ is the least number of arcs in a score certificate of $T$. Upper bounds on the score certificate number of upset tournaments are derived. The upset tournaments on $n$ vertices are in one–to–one correspondence with the ordered partitions of $n-3$, and are "almost" transitive tournaments. For each upset tournament on $n$ vertices a general construction of a score certificate with at most $2n-3$ arcs is given. Also, for the upset tournament, $T_{\lambda}$, corresponding to the ordered partition $\lambda$, a score certificate with at most $n+2k+3$ arcs is constructed, where $k$ is the number of parts of $\lambda$ of size at least 2. Lower bounds on the score certificate number of $T_{\lambda}$ in the case that each part is sufficiently large are derived. In particular, the score certificate number of the so-called nearly transitive tournament on $n$ vertices is shown to be $n+3$, for $n\geq 10$.