##
**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, M_{k}(T) = **sum**^{n}_{i = 1} t^{k}_{i}. A tournament T and its complement T^{c} are said to share the k-th moment if M_{k}(T) = M_{k} (T^{c}). We define the common moment set of T and T^{c} as P = **{**k in **N** | M_{k}(T) = M_{k} (T^{c})**}**. 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 cp^{2} 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 T^{c}. 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