An {\em isomorphism certificate} of a labeled tournament $T$ is a labeled subdigraph of $T$ which together with the unlabeled copy of $T$ allows errorless reconstruction of $T$. Similarly, a {\em score certificate} for a labeled tournament $T$ is a labeled subdigraph of $T$ which together with the score sequence of $T$ allows errorless reconstruction of $T$. Here the score sequence of a tournament means its out-degree sequence.
In this talk we give upper and lower bounds on sizes of (minimum) certificates. In particular, we will discuss the following theorem.
{\em Except for the regular tournaments on 3 and 5 vertices, every tournament $T$ on $n$ vertices requires at least $n-1$ arcs in a score certificate for $T$.}
This is best possible since every transitive tournament on $n$ vertices has a score certificate with exactly $n-1$ arcs. The same question for an isomorphism certificate is open.
(joint work with P. Fishburn and P. Tetali)