Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub-tournaments
✍ Scribed by Richard A. Brualdi; Jian Shen
- Publisher
- John Wiley and Sons
- Year
- 2001
- Tongue
- English
- Weight
- 106 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Ao and Hanson, and
Guiduli, Gya  rfa  s, Thomasse  and Weidl independently, proved the following result: For any tournament score sequence S (s 1 , s 2 ,F F F,s n ) with s 1 s 2 Á Á Á s n , there exists a tournament T on vertex set f1Y 2Y F F F Y ng such that the score of each vertex i is s i and the sub-tournaments of T on both the even and the odd indexed vertices are transitive in the given order; that is, i dominates j whenever i b j and i j (mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satis®es a set of inequalities which are individually stronger ÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐ Contract grant sponsor: NSERC.