Short certificates for tournaments (Q1378501)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Short certificates for tournaments |
scientific article |
Statements
Short certificates for tournaments (English)
0 references
12 February 1998
0 references
Summary: 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 \(\varepsilon >0\) so that any tournament on \(n\) vertices contains a score certificate with at most \( ({1/2}-\varepsilon)n^2\) edges.
0 references
isomorphism certificate
0 references
labeled tournament
0 references
reconstruction
0 references
score certificate
0 references