Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Landau’s and Rado’s Theorems and Partial Tournaments. | Landau s and Rado s Theorems and Partial Tournaments Richard A. Brualdi and Kathleen Kiernan Department of Mathematics University of Wisconsin Madison WI 53706 brualdi kiernan @ Submitted Sep 30 2008 Accepted Jan 18 2009 Published Jan 23 2009 Mathematics Subject Classifications 05C07 05C20 05C50. Abstract Using Rado s theorem for the existence of an independent transversal of family of subsets of a set on which a matroid is defined we give a proof of Landau s theorem for the existence of a tournament with a prescribed degree sequence. A similar approach is used to determine when a partial tournament can be extended to a tournament with a prescribed degree sequence. Mathematics Subject Classifications 05C07 05C20 05C50. 1 Introduction A tournament of order n is a digraph obtained from the complete graph Kn of order n by giving a direction to each of its edges. Thus a tournament T of order n has n directed edges. The sequence n r2 rn of outdegrees of the vertices 1 2 . ng of T ordered so that r1 r2 rn is called the score sequence of T. The sequence of indegrees of the vertices of T is given by s1 n 1 r1 s2 n 1 r2 . sn n 1 rn and satisfies s1 s2 sn. In the tournament T0 obtained from T by reversing the direction of each edge the indegree sequence and outdegree sequence are interchanged the score vector of T0 equals s1 s2 . sn with the s in nonincreasing order. 2 Landau s theorem from Rado s theorem Landau s theorem characterizes score vectors of tournaments. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N2 1 Theorem Landau s theorem The sequence r1 r2 rn of integers is the score sequence of a tournament of order n if and only if k ik r. Q k 1 2 . n 1 with equality for k n. Note that 1 is equivalent to Xr. 1 K c 1 2 . n . 2 i2K There are several known short proofs of Landau s theorem see 2 3 4 7 8 . In this section we give a short proof of Landau s theorem using Rado s theorem see 5 6 for the existence of an independent transversal of a finite family
