\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Noga Alon and Mikl\'os Ruszink\'o, Short Certificates for Tournaments

An {\it 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 {\it 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.



\bye