# DIMACS Focus on Discrete Probability Seminar

## Title:

Tournament Certificates

## Speaker:

- Jeong-Han Kim
- Bell Labs

## Place:

- Hill Center, Room 525
- Busch Campus, Rutgers University

## Time:

- 3:30 - 4:30 PM
- Thursday, December 5, 1996

**Abstract:**
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)

Document last modified on November 27, 1996