Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 829.05033
Autor: Chen, Hang; Schwenk, Allen J.; Erdös, Paul
Title: Tournaments that share several common moments with their complements. (In English)
Source: Bull. Inst. Comb. Appl. 4, 65-89 (1992).
Review: The k-th moment of a tournament T is the sum of the k-th powers of its scores, that is, Mk(T) = sumni = 1 tki. A tournament T and its complement Tc are said to share the k-th moment if Mk(T) = Mk (Tc). We define the common moment set of T and Tc as P = {k in N | Mk(T) = Mk (Tc)}. Some tournaments have self complementary score sequences, which forces P = N. But, when the sequence is not self complementary, P is a finite subset of N. For any tournament, 1, 2 in P. In fact, P = {1,2,...,2p} \cup A where A \subset {2p+1, 2p+2,...} with 2p+1, 2p+2 \notin A. For every even integer 2p, we explicitly construct a tournament which shares the first 2p common moments with its complement, and furthermore, we seek the smallest such tournament. This can be achieved with cp2 ln p vertices. Paul Erdös asked whether any tournament and its complement yield a nonempty set A. For a long time we could not find any example with A nonempty. In this paper, we now show that nonempty sets A can occur provided they have a certain low ``initial density''. Furthermore, we characterize the sets A that can occur and thus we also characterize sets P which can be the common moment set of T and Tc. We also give explicit examples of tournaments attaining P for a few small sets P.
Classif.: * 05C20 Directed graphs (digraphs)
11B75 Combinatorial number theory
Keywords: moment; tournament; common moment set; complementary score sequences
Citations: Zbl.786.05085
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag