Week 2 Topic: Tournaments
Joergen Bang-JensenUniversity of Southern DenmarkConnectivity of Tournament-like digraphsWe survey recent results on connectivity and the structure of digraphs
that are either
tournaments or ``tournament-like'' that is they have a structure which
is related to that of tournaments. Such classes of digraphs include
locally semicomplete digraphs, quasi-transitive digraphs, path-mergeable
digraphs and
semicomplete multipartite digraphs. We will
discuss results on hamiltonian paths and cycles as well as finding
small spanning subdigraphs which preserve the degree of arc-strong
connectivity in these classes of
digraphs. We will also discuss recent results on decompositions of
tournaments and results on increasing the connectivity of tournaments by
adding new arcs or by reversing existing arcs. Finally we will pose a number of open problems and conjectures in the
area. Much more information about directed graphs in general and paths and
cycle in particular can be found in the book ``Digraphs: Theory,
Algorithms and Applications'', Bang-Jensen and Gutin, Springer
Monographs in Mathematics, 2000. Erol BarbutUniversity of IdahoScores for Hypertournaments Let $n$ and $k$ be positive integers with $n>k$. A $k$-{\it
hypertournament} is a generalization of a tournament
consisting of a pair ($V$, $A$) where $A$ is a set of $k$- tuples
of $n$ vertices in $V$, called {\it arcs}, such that for any
$k$-subset $S$ of $V$, $A$ contains exactly one of the $k!$
$k$-tuples whose entries belong to $S$. The $i$-{\it score} of a
vertex $v$ for $i=1,\ldots k$ is the number of $k$-subsets
in which $v$ appears in the $i$th place. The main question
addressed in this talk is for what given $i$-scores
of the vertices one can construct a $k$-tournament having those
$i$-scores. We survey some answers to this question since the 1953
paper by H.G. Landau which completely solves the problem for $k$=2,
including results on rotational and regular hypertournaments by E. Barbut and Arie
Bialostocki (1989,1992), as well as recent results of Zhou, Yao and Zhang (2000) that generalize Landau's theorem. Gregory GutinRoyal Holloway, University of LondonDomination analysis for the TSPThe domination number of a heuristic A for the TSP is the maximum integer d(n) such that, for evey instance I of the TSP on n vertices, A produces a tour T which is not worse than at least d(n) tours in I including T itself. Observe that an exact algorithm for the Asymmetric TSP (Symmetric TSP) has domination number (n-1)! ((n-1)!/2). The aim of the talk is to discuss exact values and bounds obtained for the domination numbers of TSP heuristics by S. Kabadi, F. Margot, A. Punnen, A. Yeo, A. Zverovich and the speaker. The heuristics include the greedy and nearest neighbor algorithms, vertex insertion and parching heuristics, as well as 2-Opt and 3-Opt. Olivier HudryEcole Nationale Superieure des TelecommunicationsLinks Between Some Tournament SolutionsConsider a competition organized in such a way that each competitor plays
once against each one of the other competitors. If we assume that ties
cannot occur, then the result of this pairwise comparison is a tournament
T: the vertices of T are the competitors and there is an arc from x to y if
x defeats y. Then, a "tournament solution" S can be defined as a way to choose, from
the set X of vertices of any tournament T = (X, U), a subset S(X) of X
whose elements can be considered as better than the others: the "winners"
of T according to S. It may happen that, in the competition, there is a player (a vertex) who
defeated all the other ones; such a player is called a "Condorcet winner"
and can reasonably be considered as the unique winner for any tournament
solution S. But it may happen also that there is no Condorcet winner in T.
Then answering the question "who are the best players" is no longer an easy
task. In this talk, we recall the definition of and the links between several
tournament solutions, namely: - the Copeland solution, based on the out-degrees of the vertices;
- a solution based on the maximum eigenvalue of the matrix associated with the tournament;
- a Markovian solution;
- the Slater solution, based on linear orders at minimum distance;
- the Banks solution, based on maximal transitive subtournaments;
- the tournament equilibrium set (TEQ);
- solutions based on covering relations.
Stephen KirklandUniversity of ReginaExtremizing Algebraic Properties of Tournament MatricesA tournament matrix is the (0,1) adjacency matrix of a
tournament, and there is a growing body of work on the algebraic features
of such matrices. In this talk, I will survey some results on problems of
the following type: select an algebraic quantity associated with a matrix
(for example spectral radius, determinant, largest singular value) and
extremize that quantity over the class of nxn tournament matrices. Brenda J. LatkaDepartment of Mathematics, Lafayette CollegeAntichains of subtournamentsAn antichain of subtournaments is a set of subtournaments of a tournament so
that no element of the set embeds in any other element. An antichain is
maximal if no proper superset is also an antichain. The maximum antichain
cardinality (MACC) of a tournament T is the maximum number of elements in a
maximal antichain of subtournaments. A MACC antichain is one with this
number of elements. The tournaments whose MACC is 1 or 2 are given
explicitly. For any integer k, tournaments with MACC k can have
arbitrarily large order. On the other hand, the MACC can grow exponentially with the
order of a tournament. Several open questions are presented. Gary MacGillivrayUniversity of VictoriaRe-Orienting Tournaments by Pushing VerticesLet D be a directed graph. When a subset X of vertices of D is "pushed",
the orientation of every arc with exactly one end in X is reversed. A
considerable amount of attention has recently been devoted to questions
concerning when the push operation can be used to transform a given
directed graph into one with certain prescribed properties, e.g.,
k-connected, hamiltonian, or acyclic. While most of these problems are
NP-complete, there are often nice theorems, leading to efficient
algorithms, for tournaments. A survey of these results will be presented. Jozsef MalaBudapest University of Economic Sciences and Public AdministrationLambda-MAJORITY VOTING PARADOXESWe consider a finite set of voters and a finite set of alternatives,
called A. The preferences of the voters are linear orders on A and
an m-tuple of linear orders ( m is the number of voters ) is called
a profile. A profile induces the so-called majority relation M on A: - aMb iff at least half of the voters prefer a to b.
The well known result of McGarvey in social choice theory says that if
T is a tournament on A then there exists a profile on A (with
sufficiently many voters) such that the corresponding majority is T. If \lambda is between 0 and 1 then the relation M_lambda is
defined by: - a M_lambda b iff at least lambda-proportion of the voters prefer a to b.
It can be proved that for each 1/2 < lambda <1 there exists a
tournament T (on the set A with sufficiently many alternatives)
such that it does not coincide with the M_lambda of
any profile. In other words, if lambda(T) is the least upper bound of
the lambda such that T=M_lambda (by McGarvey's theorem
lambda(T)> 1/2) then for each lambda
strictly between 1/2 and 1 there exists a tournament T with
lambda(T)< \lambda (in fact, most of the tournaments are such). The
lambda(D) can be defined for every oriented graph D as well. The
following
extension of the above results is obtained: for each 1/2 < lambda <1
there exists an oriented graph D containing
only large cycles with lambda(D) < lambda. We can also obtain bounds for
lambda(T) if T is a composite tournament. Sarah MerzThe University of the PacificDomination Parameters and Alpha Domination in Digraphs and TournamentsDomke, Dunbar, and Markus proved several Gallai-type theorems for graphs.
For example, they relate the minimum size of a dominating set, maximum
degree and number of vertices. We apply these ideas to digraphs and
tournaments. Dunbar, Hoffman, Laskar, and Markus introduced alpha
domination in a graph. Let alpha be a real number greater than 0 and less
than or equal to 1. We say a set of vertices S is an alpha dominating set
of a digraph provided that for all x not in S, the size of the
intersection of the inset of x and S is greater than or equal to alpha
times the size of the inset of x. While domination in tournaments has
been studied, less has been done in regard to alpha domination and
tournaments (or digraphs). We consider these ideas and pose some open
problems. T. S. MichaelUnited States Naval AcademyTournaments, Ranks, and GamesWe discuss two current joint research projects of the speaker. 1. How small can the rank of a tournament matrix be over a finite
field? 2. What are the optimal mixed strategies in the two-person, zero-sum
node-selection game played on an oriented graph (e.g. tournament),
where the arcs between nodes determine the winner of each round? Darren A. NarayanRochester Institute of TechnologyReversing Numbers and a Min/Max Relation for TournamentsA minimum feedback arc set of a digraph is a smallest sized set of
arcs that when reversed makes the resulting digraph acyclic. Given an
acyclic digraph D, we seek a smallest sized tournament T, that has D as a
minimum feedback arc set. The reversing number of a digraph is defined to
be r(D) = |V(T)| -| V(D)|. We use methods from integer programming to
obtain partial results where D is a power of a directed Hamiltonian path. In addition, we connect these ideas to another problem involving
tournaments. We will investigate the relationship between a minimum sized
feedback arc set and a maximum sized collection of arc disjoint cycles. K. Brooks ReidCalifornia State UniversityTournaments: Four Theorems / Four ThemesThis talk is an expository talk, in four parts, intended to illustrate the
diversity of results that have appeared in the research literature on
tournaments. Since the literature on tournaments has developed quite
broadly, only a sampling of topics on tournaments can be presented in a
single talk such as this. However, research talks during this conference
promise to explore these and other important topics in greater depth. At
the outset of the talk we introduce tournaments, present some basic
terminology, and briefly mention several applications that will be
referenced later in the talk. In each part of the talk we take as our
point of departure a very basic theorem, a result that is suitable for
high school use. Then we discuss a few substantial topics related to the
basic result. Much of the talk will likely be new to most of the high
school teachers present, so we intentionally aim much of the discussion at
tournament novices. However, we hope that even the tournament experts
present will leave the talk having learned something new. Fred RobertsRutgers UniversityBioconsensusAn old problem in the social sciences is to find a consensus
given different opinions or preferences or votes. The social science
methods developed over the years for dealing with this problem are
beginning to find novel and important applications in information
technology. This talk will briefly describe the use of such methods
in meta-search (finding the results from multiple search engines),
image processing, collaborative filtering, and software measurement
and then concentrate on the application of such methods to the large
databases of molecular biology. Specifically, we will discuss the
problem of finding a single molecular sequence that is in some sense
the consensus of a collection of molecular sequences obtained by
different subjective or objective methods or different investigators. Peter J. SlaterUniversity of Alabama in HuntsvilleDigraph Realization Based on Distance Criteria in a GraphGiven a set C of candidates and a set V of voters, one
can construct a digraph with vertex set C in which (u,v)
is an arc if more voters in V prefer u to v than prefer
v to u. Questions involving the realizability of a given
digraph D when V must be a set of vertices in a graph
and voter preference is determined by relative distance
considerations will be discussed. Meike TewesT-Nova TechnologiezentrumExtending cycles in in-tournamentsAn in-tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. This talk deals with the extendability of cycles in a strong in-tournament D. In particular, the existence of a pancyclic ordering is considered, where we ask D to have a cycle of length 3 that can be extended successively by adding single vertices to end up with a Hamiltonian cycle of D. A sharp lower bound for the minimum indegree is given ensuring the existence of a pancyclic ordering in a strong in-tournament. Stephan ThomasseUniversite Claude BernardMedian Orders of TournamentsIn a digraph D, a feedback arc set is a minimal set S of arcs
such that D-S is acyclic. Dually, a median order of a
tournament T=(V,A) is a transitive tournament L=(V,B) maximizing
the intersection of A and B. Feedback
arc sets and median orders are well-studied for their own sake since they
provide a way of ranking a tournament, but they are also
powerful tools when used for proofs. The crucial fact is that if L is a
median order of T, and U is an
interval of L, the restriction of L to U is a median order of T
restricted to U. Thus one can apply induction on couples (T,L). I will present in this talk four short proofs making use of median
orders. Precisely I will show that: - 1) Every finite digraph has a quasi-kernel. (Well-known result. One line proof with median order as a warm up.)
- 2) Every finite tournament has a vertex whose first neighborhood is no greater than its second neighborhood. (with F. Havet. This was known as Dean's conjecture until Fisher proved it.)
- 3) Every finite tournament on 4n vertices contains every oriented tree of n vertices. (with F. Havet. Sumner's conjecture, posed around 1972, asserts that every tournament of order 2n contains every oriented tree of order n, 4n was known asymptotically following the work of Haggkvist and Thomason, in fact the median order argument gives 7n/2, with a longer proof.)
- 4) Every finite 2-colored tournament has an absorbing vertex. (Well-known result of Sands, Sauer and Woodrow, I will provide an explicit construction of such a vertex, again using median orders.)
Anders YeoUniversity of AarhusArc-Disjoint Strong Spanning Subgraphs of K-Arc-Strong TournamentsJoint work with Jorgen Bang-Jensen A tournament, is an orientation of a complete graph. k-arc-strong means
that the digraph is strong (i.e. there is an (x,y)-path and a (y,x)-path
for all distinct vertices x and y) whenever we delete at most k-1 arcs.
We will talk about the following conjecture and results (n denotes the
number of vertices): 1. We conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. 2. If D=(V,A) is a 2-arc-strong semicomplete digraph, then it
contains 2 arc-disjoint spanning strong subdigraphs except for
one digraph on 4 vertices. 3. Every k-arc-strong tournament with minimum in- and out-degree
at least 37k contains k arc-disjoint strong spanning subdigraphs. 4. Every k-arc-strong tournament contains a spanning k-arc-strong
subdigraph with no more than nk+280k*k arcs. Note that any k-arc-strong
digraph has at least nk arcs, as every vertex has at least k arcs
out of it. Furthermore we give a construction which shows that for each k>1 there are k-arc-strong tournaments on n vertices such that every k-arc-strong spanning subdigraph of T contains at least nk+k(k-1)/2 arcs. Note that the conjecture mentioned in 1, would imply the well-known Kelly-conjecture. The result in 2 implies that the conjecture in 1 is true for k=2. We will furthermore state a number of useful lemmas, and a number of conjectures. And we will talk about how the above results relate to out- and in-branchings
in tournaments. |

Page last updated June 22, 2001