✦ LIBER ✦

Transitive partitions in realizations of tournament score sequences

✍ Scribed by Arthur H. Busch; Guantao Chen; Michael S. Jacobson

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 121 KB
Volume: 64
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20438

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A tournament is an oriented complete graph, and one containing no
directed cycles is called transitive. A tournament
T=(V, A) is called m‐partition
transitive if there is a partition
such that the subtournaments induced by each X~i~ are all transitive, and T is m‐partition k‐transitive if max|X~i~|=k. Two tournaments are equivalent if they have the same out‐degree sequence. We show that for any m and k, T is equivalent to an m‐partition k‐transitive tournament T′ whenever T is equivalent to any tournament which contains a transitive subtournament of order at least k. This generalizes results of Guiduli et al. and Acosta et al., who proved the claim for m=2 and k=⌈n/2⌉, and m>2 and k⩽⌈n/2⌉, respectively. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 52–62, 2010

📜 SIMILAR VOLUMES

Some special realizations of partition m

Some special realizations of partition matrix sequences

✍ Z. Majcher 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 997 KB

Asymptotic Enumeration of Tournaments wi

Asymptotic Enumeration of Tournaments with a Given Score Sequence

✍ Brendan D. McKay; Xiaoji Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 560 KB

We obtain the asymptotic number of labeled trounaments with a given score sequence in the case where each score is nÂ2+O(n 3Â4+= ) for sufficiently small =>0. Some consequences for the score sequences of random tournaments are also noted. The method used is integration in n complex dimensions.

Landau's inequalities for tournament sco

Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub-tournaments

✍ Richard A. Brualdi; Jian Shen 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

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 an

Asymptotic enumeration of tournaments wi

Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph

✍ Zhicheng Gao; Brendan D. McKay; Xiaoji Wang 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

This paper studies the probability that a random tournament with specified score sequence contains a specified subgraph. The exact asymptotic value is found in the case that the scores are not too far from regular and the subgraph is not too large. An ndimensional saddle-point method is used. As a s

Sequence of orientational phase transiti

Sequence of orientational phase transitions in solid C60

✍ K.H. Michel 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 217 KB

The high symmetry of the C6,, molecule and the symmetry of the cubic lattice site in solid ChO imply that in addition to the known orientational phase transition at 250 K, there is a sequence of transitions at lower T. These transitions correspond to a successive freezing of orientational degrees of

Collapse transitions in protein-like lat

Collapse transitions in protein-like lattice polymers: The effect of sequence patterns

✍ Andrzej Kolinski; Pawel Madziar 📂 Article 📅 1997 🏛 Wiley (John Wiley & Sons) 🌐 English ⚖ 138 KB 👁 2 views

The collapse transition of lattice protein-like heteropolymers has been studied by means of the Monte Carlo method. The protein model has been reduced to the a-carbon trace restricted to a high coordination lattice. The sequences of model heteropolymers contain two types of mers: hydrophobic/nonpola