Short Certificates for Tournaments

Noga Alon, Miklós Ruszinkó

Abstract


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 $\epsilon >0$ so that any tournament on $n$ vertices contains a score certificate with at most $ ({1/2}-\epsilon)n^2$ edges.


Full Text: PDF