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