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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page