2-partition-transitive tournaments
type: Item
instance of: scholarly article
title: 2-partition-transitive tournaments
zbMATH Open document ID: 0914.05033
author: Barry Guiduli
author: András Gyárfás
author: Peter Weidl
author: Stéphan Thomassé
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-02-11T00:00:00Z
review text: Given a tournament score sequence \(s_1\geq s_2\geq\cdots\geq s_n\), we prove that there exists a tournament \(T\) on vertex set \(\{1,2,\dots, n\}\) such that the degree of any vertex \(i\) is \(s_i\) and the subtournaments of \(T\) on both the even and the odd vertices are transitive in the given order. This means that \(i\) beats \(j\) whenever \(i<j\) and \(i\equiv j\pmod 2\). For any score sequence, we give an algorithm to construct a tournament of the above form, i.e. it is transitive on evens and odds in the given order. This algorithm fixes half of the edges of the tournament and is similar to the algorithm for constructing a tournament given its score sequence. Another consequence provides asymptotics for the maximum number of edges in score unavoidable digraphs. From a result of Ryser, it is possible to get from any tournament to this special tournament by a sequence of triangle reversals. We show that \(n^2/2\) reversals are always enough and that in some cases \((1-o(1))n^2/32\) are required. We also show that such a sequence of triangle reversals can be found in \(O(n^2)\) time. \(\copyright\) Academic Press.
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1234259
zbMATH Keywords: tournament score sequence
MaRDI profile type: Publication
OpenAlex ID: W2006296146
cites work: Q4004078
cites work: Score vectors of tournaments
cites work: Q3927273
cites work: Q3872493
cites work: Q3346350
cites work: Q3883524
cites work: Upsets in Round Robin Tournaments
cites work: A theorem on flows in networks
cites work: A Constructive Solution to a Tournament Problem
cites work: Largest digraphs contained in all n-tournaments
cites work: On the Score Sequence of an N-Partite Tournament
cites work: Q5585195
cites work: Combinatorial Properties of Matrices of Zeros and Ones
cites work: Q5337210
DOI: 10.1006/JCTB.1997.1806
description: scientific article; zbMATH DE number 1234259