Short certificates for tournaments

Noga Alon ; Miklós Ruszinkó

The electronic journal of combinatorics, Tome 4 (1997) no. 1

Résumé

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.

Détail

DOI : 10.37236/1297

Classification : 05C20
Mots-clés : isomorphism certificate, labeled tournament, reconstruction, score certificate