Short certificates for tournaments

Noga Alon, Miklós Ruszinkó

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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 log2 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 ∈ > 0 so that any tournament on n vertices contains a score certificate with at most (1/2 - ∈)n2 edges.

Original languageEnglish (US)
Article numberR12
Pages (from-to)1-6
Number of pages6
JournalElectronic Journal of Combinatorics
Volume4
Issue number1 R
DOIs
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Short certificates for tournaments'. Together they form a unique fingerprint.

  • Cite this