DIMACS DCI '01 Week 2 Topic: Tournaments July 16 - 20, 2001 Abstracts Joergen Bang-Jensen University of Southern Denmark Connectivity of Tournament-like digraphs We 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 Barbut University of Idaho Scores 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 Gutin Royal Holloway, University of London Domination analysis for the TSP The 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 Hudry Ecole Nationale Superieure des Telecommunications Links Between Some Tournament Solutions Consider 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 Kirkland University of Regina Extremizing Algebraic Properties of Tournament Matrices A 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. Latka Department of Mathematics, Lafayette College Antichains of subtournaments An 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 MacGillivray University of Victoria Re-Orienting Tournaments by Pushing Vertices Let 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 Mala Budapest University of Economic Sciences and Public Administration Lambda-MAJORITY VOTING PARADOXES We 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 Merz The University of the Pacific Domination Parameters and Alpha Domination in Digraphs and Tournaments Domke, 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. Michael United States Naval Academy Tournaments, Ranks, and Games We 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. Narayan Rochester Institute of Technology Reversing Numbers and a Min/Max Relation for Tournaments A 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 Reid California State University Tournaments: Four Theorems / Four Themes This 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 Roberts Rutgers University Bioconsensus An 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. Slater University of Alabama in Huntsville Digraph Realization Based on Distance Criteria in a Graph Given 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 Tewes T-Nova Technologiezentrum Extending cycles in in-tournaments An 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 Thomasse Universite Claude Bernard Median Orders of Tournaments In 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 Yeo University of Aarhus Arc-Disjoint Strong Spanning Subgraphs of K-Arc-Strong Tournaments Joint 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