Landaus Theorem Revisited

Abstract

Two new elementary proofs are given of Landaus Theorem on necessary and sufficient conditions for a sequence of integers to be the score sequence for some tournament. The first is related to existing proofs by majorization, but it avoids depending on any facts about majorization. The second is natural and direct, but a bit more basic than existing proofs. Both proofs are constructive, so they each provide an algorithm for obtaining a tournament realizing a sequence satisfying Landaus conditions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1998
Accession Number
AD1000112

Entities

People

  • Jerrold R. Griggs
  • K. B. Reid

Organizations

  • University of South Carolina

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Department Of Defense
  • Governments
  • Graph Theory
  • Inequalities
  • Information Operations
  • Mathematics
  • Military Research
  • New York
  • Numbers
  • Real Numbers
  • Sequences
  • South Carolina
  • United States
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Linear Algebra