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.

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.

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.

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.

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.

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.

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.

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.

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.

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?

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.

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.

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.

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.

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.

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.)

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.