Short certificates for tournaments (Q1378501)

Summary: An isomorphism certificate of a labeled tournament \(T\) is a labeled subdigraph of \(T\) which together with an unlabeled copy of \(T\) allows the errorless reconstruction of \(T\). It is shown that any tournament on \(n\) vertices contains an isomorphism certificate with at most \(n \log_2 n\) edges. This answers a question of Fishburn, Kim and Tetali. A score certificate of \(T\) is a labeled subdigraph of \(T\) which together with the score sequence of \(T\) allows its errorless reconstruction. It is shown that there is an absolute constant \(\varepsilon >0\) so that any tournament on \(n\) vertices contains a score certificate with at most \( ({1/2}-\varepsilon)n^2\) edges.