Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00004125/00001
## Material Information- Title:
- Domination and matrix properties in tournaments and generalized tournaments
- Creator:
- Stewart, Dustin J
- Publication Date:
- 2005
- Language:
- English
- Physical Description:
- x, 202 leaves : ; 28 cm
## Subjects- Subjects / Keywords:
- Domination (Graph theory) ( lcsh )
Tournaments (Graph theory) ( lcsh ) Matrices ( lcsh ) Domination (Graph theory) ( fast ) Matrices ( fast ) Tournaments (Graph theory) ( fast ) - Genre:
- bibliography ( marcgt )
theses ( marcgt ) non-fiction ( marcgt )
## Notes- Bibliography:
- Includes bibliographical references (leaves 198-202).
- General Note:
- Department of Mathematical and Statistical Sciences
- Statement of Responsibility:
- by Dustin J. Stewart.
## Record Information- Source Institution:
- |University of Colorado Denver
- Holding Location:
- |Auraria Library
- Rights Management:
- All applicable rights reserved by the source institution and holding location.
- Resource Identifier:
- 62775256 ( OCLC )
ocm62775256 - Classification:
- LD1193.L622 2005d S73 ( lcc )
## Auraria Membership |

Full Text |

DOMINATION AND MATRIX PROPERTIES IN TOURNAMENTS AND
GENERALIZED TOURNAMENTS by Dustin J. Stewart B.S. Mathematics, University of the Pacific, 2001 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics This thesis for the Doctor of Philosophy degree by Dustin J. Stewart has been approved by Ellen Gethner Date K. Brooks Reid Stewart, Dustin J. (Ph.D., Applied Mathematics) Domination and Matrix Properties in Tournaments and Generalized Tourna- ments Thesis directed by Professor J. Richard Lundgren ABSTRACT In this thesis we examine several matrix properties of tournament matrices. In particular we look at how domination and related parameters in tournaments affect these properties in the corresponding matrices. We begin by examin- ing when a tournament can support an orthogonal matrix. To do so, we first look at the necessary condition of quadrangularity in tournaments. We classify tournaments with given properties which meet this necessary condition. We show how domination effects quadrangularity in regular tournaments and tour- naments with certain minimum degrees. We also determine for exactly which orders a quadrangular tournament exists. In chapter 3, we examine the stronger necessary condition for a digraph to support an orthogonal matrix of strong quadrangularity. We construct a class of tournaments which meet this condition. We also show that the 3-cycle is the unique tournament on ten or fewer vertices which supports an orthogonal matrix, and discuss a search conducted for a tournament matrix which supports an orthogonal matrix. In the following chapter we look at which tournament matrices are fully indecomposable and which are separable, as these properties m are related to a necessary condition for a (0, l)-matrix to support an orthogonal matrix. We use our classification to derive a number of matrix and graph theo- retic corollaries. As the domination graphs of tournaments play a central role in our classification of separable tournament matrices, we classify the domination graphs of complete paired comparison digraphs in chapter 5. Finally, we examine the Boolean, non-negative integer and real ranks of tournament matrices. We find new bounds for the Boolean rank using results on dominating sets and related parameters. We determine, for the first time, a class of tournament matrices in which the real rank is less than the Boolean rank. We also determine a set theoretic dual to the problem of finding the Boolean row rank of a tournament matrix, and give some results and conjectures related to the problem of finding the minimum Boolean rank over all tournament matrices of order n. This abstract accurately represents the content of the candidates thesis. I recommend its publication. Signed IV DEDICATION For Melissa, for my family, and for Albion. ACKNOWLEDGMENT There are several people in my life that deserve thanks for bringing me to this point. First, I want to thank my advisor, J. Richard Lundgren. Rich has made many things possible for me in the last four years, and has taught me a great deal about mathematics, teaching and life as an academic. I also owe many thanks my thesis committee Rich, Brooks Reid, Stan Payne, Bill Cherowitzo and Ellen Gethner. Each have been a great help and influence in their own way. Thank you as well to the faculty who I had the chance to work with at UCD. I want to thank the graduate committee and the mathematics department for the financial support, teaching assistantships and fellowships. None of this would have been possible without it. Thank you to Marcia Kelly, Liz Lhotka and Jennifer Thurston. I would not have survived without them. Thanks also to Lynn Bennethum and Bruce MacMillan for their help and advice on teaching. My thanks to the UOP mathematics department for preparing me for grad- uate school, especially to Sarah Merz, Coburn Ward and Vincent Panico. I also want to thank Sarah for introducing me to graph theory and starting me off researching in the field. I am also thankful for my fellow graduate students who have helped me through the last few years with teaching and research ideas, or by just being a good distraction. For this, I am happy to thank, among others, Nate, Art, Ryan, Kevin, Flink, Rob, Tessa, Hank, Sarah and Chris. Special thanks to my two amazing officemates, Jenny Cowel and Dave Brown, and to Carey Jenkins and Jeff Matsuo, helpful friends and great fishermen. I want to thank my parents for everything they have done for me. Especially for when they sent me to college and started this whole process. Finally, I want to thank Melissa Cyfers for all her love and support. I could not have asked for more. CONTENTS Figures ........................................................... ix 1. Introduction...................................................... 1 1.1 Background........................................................ 1 1.2 Graph and digraph basics.......................................... 4 1.3 Tournament basics................................................ 11 1.4 Domination basics ............................................... 19 1.5 Matrix basics.................................................... 23 2. Quadrangular Tournaments ........................................ 27 2.1 Definitions and background....................................... 27 2.2 Tournaments which are not strongly connected .................... 29 2.3 Tournaments with given minimum degrees........................... 34 2.4 Regular and rotational tournaments............................... 38 2.5 Known orders of quadrangular tournaments......................... 43 3. Strongly Quadrangluar Tournaments................................ 55 3.1 Definitions and background....................................... 55 3.2 A class of strongly quadrangular tournaments..................... 57 3.3 Nonexistence and searches........................................ 62 4. Fully Indecomposable Tournament Matrices......................... 69 4.1 Definitions and background ...................................... 69 4.2 Fully indecomposable matrices.................................... 72 vii 4.3 Separable matrices............................................... 74 4.4 Corollaries...................................................... 77 5. Domination Graphs of Complete Paired Comparison Digraphs .... 84 5.1 Definitions and background....................................... 84 5.2 Preliminary results.............................................. 85 5.3 Complete paired comparison digraphs with no arc weight .5 .... 90 5.4 Connected domination graphs...................................... 99 5.5 Domination graphs with no isolated vertices..................... 114 5.6 Isolated vertices in domination graphs ......................... 134 6. Ranks of Tournament Matrices ..................................... 137 6.1 Definitions and background...................................... 137 6.2 Rank and domination ............................................ 140 6.3 Boolean row rank................................................ 144 6.4 A conjecture about tournament codes............................. 152 6.5 A construction for a singular tournament matrix with full Boolean rank............................................................ 159 Appendix A. Extra Proofs...................................................... 184 A.l Normal tournament matrices...................................... 184 A. 2 Two new proofs of the real rank of a tournament matrix......... 185 B. C++ Code......................................................... 190 References........................................................... 198 viii FIGURES Figure 1.1 An example of a Markov model....................................... 3 1.2 A drawing of a graph............................................... 5 1.3 A drawing of a digraph............................................. 8 1.4 A 5-tournament.................................................... 11 1.5 An example of a spiked cycle and a caterpillar.................... 23 2.1 A Quadrangular Digraph ........................................... 28 2.2 The 2-tournament, the 3-cycle, and the transitive triple.......... 37 2.3 The four 4-tournaments with the strong 4-tournament on the far right. 45 3.1 The tree diagram for our algorithm................................ 66 4.1 A bigraph representation of M and M'.............................. 71 4.2 Different digraph representations for M and M'.................... 72 4.3 An example of a cycle factor in a digraph......................... 82 5.1 A pcd and its associated tournament............................... 92 5.2 The domination graphs of a pcd and its associated tournament . 93 5.3 NC7.............................................................. 100 5.4 The arcs with weight x........................................... 101 5.5 The chorded 4-cycle.............................................. 107 5.6 The bowtie....................................................... 107 5.7 An example of a spiked clique.................................... Ill IX 5.8 Some spiked bicliques .................................................. 122 6.1 A directed biclique partition............................................. 138 6.2 The network in our feasible flow problem.................................. 169 x 1. Introduction 1.1 Background The two main structures of interest in this thesis are tournaments and tour- nament matrices. Tournaments are a famous class of digraphs which originally arose from the model of a round robin competition in which each player plays against every other. Since this simple beginning, tournaments have been shown to have a great deal of interesting combinatorial structure, and the tournament matrix has proven to have many interesting algebraic properties. In this thesis we look at various problems which bring together these two aspects of tour- naments and tournament matrices. In chapter 5, we will also study a related structure, the complete paired comparison digraph (sometimes called a general- ized tournament). In chapters 2, 3, and 4, we study three properties which arise from the question of orthogonal support, and how these properties effect tournaments and tournament matrices. In chapter 6, we take a look at various matrix rank problems in tournament matrices. We find that domination plays a role in each of these problems. Particularly, the domination graphs of tournaments can be applied to the problems in chapter 2, and will give us our characterization in chapter 4. Because these play such an important role in some of these problems, especially in chapter 4, we characterize the domination graphs of complete paired comparison digraphs in chapter 5. 1 The first problem addressed in this thesis is that of orthogonal support. This problem comes from an application to quantum physics and quantum comput- ing. In physics the problem arises in modeling discrete quantum walks, and in computing it comes from writing quantum algorithms. In both cases, one sets up the model, much like a Markov chain, by repeatedly applying an orthogo- nal (or unitary) transition matrix to a state vector. The state vector gives the original state of the object we wish to model, and after a select number of mul- tiplications by the transition matrix we return the probable outcomes for our object. Underlying the transition matrix is a directed graph which maps out the movements of our object from state to state. We are interested in knowing if this underlying digraph can be a tournament. We give an example of a Markov model below. Suppose six school children are playing a game of catch. The digraph in Figure 1.1 shows the children as vertices, and the probability that child i will throw the ball to child j is given by the weight on arc (z, j). If we begin by giving the ball to child 1, then our model has the transition matrix /.6 .4 0 0 0 0 \ 0 0 .3.7 0 0 0 0 0 0 .4.6 M ~ 1 0 0 0 0 0 1 0 0 0 0 0 \0 1 0 0 0 0/ and state vector v = (1 0 0 0 0 0)T. We then repeatedly multiply v by M to determine possible outcomes. For example, if we wish to know the probability child 4 will end up with the ball after 12 throws, then we simply look at the 4th entry of M12v. For more on Markov chains, the reader is referred to [55]. 2 6 Figure 1.1: An example of a Markov model The nature of decoherence in quantum physics requires the transition matrix in the quantum version of these models to be orthogonal. We want to know when a tournament can be used in these models, and hence when a tournament is the digraph underlying an orthogonal matrix. We have three necessary conditions for a directed graph to be the digraph of an orthogonal matrix. In chapter 2 we study the first of our necessary conditions, quadrangularity. In chapter 3 we study the stronger condition of strong quadrangularity, and discuss some of our searches for tournaments which are the digraphs of orthogonal matrices. In chapter 4 we see that an orthogonal matrix needs to be written in a particular way, and see exactly when a tournament matrix can be written in this way. In chapter 4 we also characterize exactly which tournaments can be used in a 3 doubly stochastic Markov model. In chapter 5 we look at the domination graphs of complete paired compar- ison digraphs. This is one extension of the study of the domination graphs of tournaments. The domination graphs of tournaments were introduced by Merz, Fisher, Lundgren, and Reid, in [44], and have been characterized in a series of papers (see [31], [43], [44], [45], [46]). Domination graphs have been generalized to tournaments in which ties are allowed, and proper subdigraphs of tourna- ments by Factor and Factor in [24] and [25]. Another generalization, called ^-domination has also been studied by McKenna, Morton and Sneddon in [41]. We give a generalization of domination graphs for the context of complete paired comparison digraphs, and essentially characterize this class of graphs. In chapter 6 we examine some problems involving ranks of tournament ma- trices. We will look at relationships between the Boolean, non-negative integer, real, term, and minimal rank of tournament matrices. We see that, as domina- tion plays a role in the questions addressed in chapters 2, 3, and 4, it also acts in this context by giving us lower bounds for these ranks. We answer a question of Siewert [58], by constructing an infinite class of singular tournament matrices with full Boolean rank. We examine a dual to the Boolean row rank of a tour- nament matrix which is an extension of Schiittes problem, and also examine a dual to the problem of finding the Boolean rank of a tournament matrix. 1.2 Graph and digraph basics In this section we review the background and notation for graphs and di- rected graphs necessary for this thesis. Recall first that a graph G is a set of vertices V(G), together with a set E(G) of unordered pairs of vertices, called 4 edges. If G is a graph such that no edge occurs more than once, and G has no edge of the form [u,u] for some u G V(G), then G is typically referred to as a simple graph. In this thesis we have no need to distinguish between graphs and simple graphs, so we shall assume that all graphs are simple. We also have no need for infinite graphs, and so shall assume the vertex and edges sets of our graphs are finite. We typically represent a graph pictorially by representing the vertices with dots, and connecting two dots with a line segment if there is an edge joining the two vertices in the graph. For example, the graph G = (V(G), E(G)) with V(G) = {1,2,3,4,5,6,7} and E(G) = {[1,2], [1,3], [3,4], [5,6]} is shown in Figure 1.2. We now give some of the basic definitions necessary to study the structure of graphs. oo o 6 4o 6 o Figure 1.2: A drawing of a graph Let G be a graph. If [u,v] G E(G), then we say that u and v are adjacent in G. A vertex u and edge e of G are said to be incident if e = [u, v] for some vertex v. For a given v G V(G), we define the degree of v, d(v), to be the number of edges incident to v. Since we are assuming our graphs are simple, we can equivalently define the degree of v as the number of vertices adjacent to v. To study the structure of graphs it is sometimes useful to study related graphs, such as subgraphs and the complement of a graph. A subgraph of a 5 graph G, is a graph H with V(H) C V(G) and E(H) C E(G). Given a set S C V(G), the subgraph induced on S, G^S], is the graph with VXGfS1]) = S', and [it, v] G Â£(G'[S']) if and only if it, v G S' and [it, v] G -E'(G'). A graph H is called an induced subgraph of G if H = G'fS'] for some S' C V(G). The complement of a graph G is the graph G, with V(G) = V(G) and [it, v] G E(G) if and only if [u, i>] 0 E(G). A path between vertices it and v in a graph G (sometimes called a u,v- path) is an alternating sequence of vertices and edges of G, beginning with u and ending with v, such that no vertex or edge is repeated, and each vertex is incident with the edge immediately preceding and succeeding it in the sequence. For simplicity, we typically only list the vertices of a path. The length of a path is defined to be the number of edges in the path. The distance between vertices u and v is defined to be the length of a shortest u, i;-path. Also, a graph G is said to be connected if there exists a it, v-path for all distinct it, v G V(G). A graph G which is not connected is called disconnected, and the maximally connected subgraphs of G are called the connected components or components of G. A component of order 1 is referred to as an isolated vertex. Cycles and cliques are important graph structures that come up frequently in chapter 5. A cycle in a graph G is an alternating sequence of vertices and edges of G, beginning and ending with the same vertex, such that no edge is repeated, only the first vertex is repeated, and each vertex is incident to the edge immediately preceding and succeeding it. If all the vertices and edges of G are contained in a cycle, we call G a cycle. The length of a cycle is the number of edges occurring in the cycle, and a cycle of length n is called an n-cycle, 6 typically denoted by Cn. If the length of a cycle is odd or even, then we refer to the cycle as an odd cycle or even cycle respectively. A complete graph, or clique, on n vertices, written Kn, is a graph with n vertices, such that [u, v] G E(Kn) for all distinct u,v G V(Kn). Typically the term clique is reserved for a complete subgraph of some graph. Another important class of graphs which come up throughout the thesis are the bipartite graphs. A graph B is said to be bipartite if V(B) can be partitioned into two sets X and Y, called a bipartition, such that no two vertices of X are adjacent and no two vertices of Y are adjacent. A well known result on bipartite graphs, which proves useful in chapter 5, is that a graph is bipartite if and only if it contains no odd cycles. A complete bipartite graph, or biclique, is a bipartite graph B with bipartition X U Y so that [x, y] G E(B) for all x G X and y Gh If |A| = r and |yj = s, then we sometimes denote the biclique on XUY by KTtS. As with clique, the term biclique is typically reserved for a complete bipartite subgraph of some graph. Bicliques play an important role in chapter 6 because of their relationship with rank 1 matrices. We now turn our attention to directed graphs. A directed graph, or digraph, D is a set of vertices V(D), together with a set A(D) of ordered pairs of vertices, called arcs. An orientation of a graph G is a digraph D obtained from G by letting V(D) = V(G) and for each [u,v] G E(G), making exactly one of (u, v) or (v, u) an arc of D. Directed graphs are typically drawn in a manner analogous to graphs, in that each vertex is represented by a dot, and we draw an arrow from vertex u to vertex v if (u, v) is an arc of of the digraph. Figure 1.3 shows a drawing of the digraph D = (V(D), A(D)) where 7 V(D) = {1, 2,3,4, 5,6} and A(D) = {(2,3), (3,4), (5, 5), (4,1), (4,3), (5,6)}. We now give some of the necessary definitions and notation to study digraphs in this thesis. 1 O 60 Figure 1.3: A drawing of a digraph If (u, v) G A(D), then we typically say that u beats v or that u domi- nates v and write this as u v. We define the outset, Oo(v), of a vertex v in D to be the set of all vertices that v dominates. That is, 0D(v) = {ue V(D) : (v,u) G A{D)}. Similarly, the inset, Id{v), of a vertex v in D is the set of all vertices which dominate v. So, ID{v) = {uÂ£V(D):{u,v)eA(D)}. The closed outset and closed inset of a vertex v are defined by Od[v] = Od{v) U {u} and Id[v] I(v) U {n} respectively. If S C V(D), then we define the outset of S as the set of all vertices dominated by some vertex in S, written Od(S). Equivalently, we can define the outset of S by Od(S) = UvesOoiv). We denote by Od[S], the closed outset of S, defined by Od[S] Od(S)US. The 8 inset of S and closed inset of S are defined analogously as Id(S) = UvesHv) and Id[S] = I(S) U S respectively. When the context of which digraph we are referring to is clear we will drop the subscript. The out-degree of a vertex v in a digraph D, written df(v), is defined to be \Od(v)\. Similarly, the in-degree of v is dp(v) = \Io(v)\. Again, when the context is clear, we will drop the subscript. The minimum out-degree of a digraph D, denoted 8+(D), is defined to be 8+(D) = min{d+(u) : v Â£ V(D)}. Similarly, the minimum in-degree of D is 5~(D) = min{d~(u) : v Â£ V(D)}. We define the maximum out-degree and maximum in-degree of a digraph D to be the values A+(Z)) = max{d+(t>) : v Â£ V(D)} and A~{D) = max{d~(v) : v Â£ V(D)} respectively. Let D be a digraph. A subdigraph of D is a digraph D' such that V(D') C V(D) and A(D') C A(D). If S C V(D), then the subdigraph induced on S is the digraph D' with V(D') = S and (u,v) Â£ A(D') if and only if u,v S and (u, v) Â£ A(D). A digraph D' is called an induced subdigraph of D if there exists some S C V(D) which induces D'. A directed path in a digraph D is an alternating sequence of vertices and arcs of D, beginning and ending with vertices, so that no vertex or arc is repeated, and if (u, v) is an arc in the path, the vertex immediately preceding it must be u and the vertex immediately succeeding it must be v. A directed path which begins at a vertex u and ends at a vertex v is called a directed u, v-path. Similar to the undirected case, the length of a directed path is defined to be the number of arcs in the path. If D is a directed graph so that there is a directed u, u-path for every distinct u,v Â£ V(D), then we say D is strongly connected. If D is not 9 strongly connected, then the maximal strongly connected subdigraphs of D are called the strong components of D. A directed cycle in a digraph D is an alternating sequence of vertices and arcs of D which begin and end with the same vertex, repeat no vertices or edges, and if (u, v) is an arc in the cycle, then the vertex immediately preceding it must be u and the vertex immediately succeeding it must be v. Similar to undirected cycles, the length of a directed cycle is the number of arcs in the cycle. A directed cycle of length n is referred to as a directed n-cycle. Also, as before, an n-cycle is called a directed odd cycle or directed even cycle if n is odd or even respectively. If it is clear that we are dealing with a directed context, we will simply refer to directed cycles and directed paths as cycles and paths. To study the structure of graphs and digraphs, it is useful to have a concept of isomorphism in graphs and digraphs. An isomorphism of graphs G and H is a bijective function (j) : V(G) > V(H) such that [u, v] E E(G) if and only if [ ing bijection. We say that two graphs are isomorphic if there exists a graph isomorphism between them. Similarly, we define an isomorphism of digraphs D and D' to be a bijection 0 : V(D) V(D') such that (w, v) E A(D) if and only if ( preserving bijection. An isomorphism from a graph to itself (digraph to itself) is called a graph automorphism (digraph automorphism). We now look at the class of digraphs studied most in this thesis. 1.3 Tournament basics 10 In this section we review some of the basic terminology and properties of tournaments. A tournament T is a complete asymmetric digraph. That is, for every two distinct u,v E V(T), either (u,v) E A(T) or (v,u) an n-tournament. Equivalently, some define an n-tournament as an orientation of the complete graph Kn. An example of a 5-tournament is shown in Figure 1.4. Figure 1.4: A 5-tournament In studying tournament structure, we often want to look at subtournaments and the dual of a tournament. Given a tournament T, and S C V(T), a subtour- nament of T is the tournament T[S], with F(T[5]) = S, and (u, v) E A(T[S']) if and only if u, v E S and (u, v) E A(T). That is, T[S] is the subdigraph induced on S. Also, for a vertex v E V(T) or a set of vertices S, we define the subtour- naments T v and T S to be the tournaments T[V(T) {u}] and T[V(T) S] 11 respectively. The dual of T is the tournament Tr, with V(Tr) = V(T) and (u,v) A(Tr) if and only if (v,u) G A(T). We define the dual of a digraph in the same way, and use the same notation. One of the most famous results about tournaments is Landaus Theorem. The list of out-degrees of the vertices of a tournament is called its score sequence. In 1953 Landau characterized which lists of n positive integers could be the score sequence of some tournament. Theorem 1.1 (Landaus quence of positive integers, if and only if Theorem) Let si, S2, ,sn be a non-decreasing se- This list is the score sequence for some n-tournament for 1 < k < n 1 and The necessity in Landaus Theorem is easy to see. Any n-tournament must have an arc between every two vertices, and hence Q) arcs. Further, every sub- tournament of an n-tournament on k vertices will have (*) arcs. The argument follows by counting arcs in subtournaments in this way, and by counting them as the sum of the out-degrees of a subset of vertices. The sufficiency in Landaus Theorem has been proved in many ways, by many people. It has been proven by using classic combinatorial methods, using majorization of vectors, using posets, using network flows, and even using Halls Theorem. Some of the many authors of these proofs include Landau, Ryser, Reid, Thomassen, Fulkerson, and Bang and Sharp. For a full proof of Landaus Theorem the reader is referred to [50]. 12 Another classic theorem on tournaments involves Hamiltonian paths. Given a digraph D, a Hamiltonian path is a path which contains every vertex of D. By taking a path of maximum length in a tournament, one can show, via the complete asymmetry of the tournament, that there is no vertex not on the path and it is hence Hamiltonian. We discuss an analogous result about cycles in strong tournaments below. We now state this theorem. Theorem 1.2 Every tournament contains a Hamiltonian path. In this thesis, we are often concerned with when one set in a tournament completely dominates another. Let T be a tournament and S,S' C V(T). If for every u G S and v G S', u > v, then we write S => S'. In the case where S = {u} (S' = {u}), we write u => S' (S => v) rather than {u} => S' (S => {u}). A vertex s G V(T) such that s => V(T) {s} is called a transmitter. A vertex t V(T) such that V(T) {t} => t is called a receiver. The concept of one set completely dominating another plays an important part in our study of tournaments and tournament matrices, as it corresponds to large blocks of ones in the adjacency matrix. Tournaments with transmitters and receivers also play a part as special cases of some of our results. In particular, when studying tournaments which are not strongly connected, tournaments with transmitters or receivers are important special cases. As with digraphs, we define a tournament T to be strongly connected if for any two vertices u, v G V(T) there is a directed path in T from u to v and another from v to u, and a strong component of a tournament to be a maximal strongly connected subtournament. We sometimes refer to a strongly connected 13 tournament as a strong tournament. We note that a single vertex is trivially strongly connected, and that a 2-tournament has exactly one arc, and hence cannot be strongly connected. So, the smallest non-trivial strong component which a tournament could have is the 3-cycle. Strong tournaments have been characterized in terms of their score sequences by replacing the inequalities in Landaus Theorem with strict inequalities. The following two theorems are well known, useful results on tljp structure of tournaments. Theorem 1.3 Let T be a strong n-tournament, and let v G V(T). Then v is contained on a cycle of length k for k = 3,..., n. Theorem 1.4 Let T be a tournament which is not strongly connected. Then V(T) can be partitioned by the strong components of T, and these components can be labeled Ti, T2,..., Tm such that Ti => Tj if and only if i < j. The strong components T\ and Tm in the previous theorem are called the initial and terminal strong components of T respectively. The above result has also been stated as The condensation of a tournament is transitive. A tran- sitive tournament is one in which for all u,v,w G V(T), if u > v and v w, then u > w. There are several equivalencies for the definition of a transitive tournament. The two others we will most frequently use are that the vertices can be labeled V\,V2,... ,vn such that vl > Vj if and only if i < j, and that 0,1,2,... ,n 1 is the score sequence of T. We also note that the transitive tournament on n vertices is unique up to isomorphism. The condensation of a tournament T is typically defined to be the tourna- ment T' obtained by representing each strong component of T with a vertex of 14 T', and letting u v if and only if for the corresponding strong components Tu and Tv we have that Tu => Tv. Theorem 1.4 above, with this definition, may also be stated as The condensation of a tournament is always a transitive tour- nament. In this thesis we will adopt the following, more versatile definition of condensation. Let T be a tournament, and suppose we can partition the vertices of T as Si, S2, ) Sm such that for all i ^ j either S', =>- Sj or Sj => S,. We de- fine the condensation of T, with respect to this partition, to be the tournament V with V(T) = {ui, V2,. , um} with Vi Vj in T' if and only if S, => Sj in T. In the study of tournaments, the extreme examples of many problems tend to be transitive tournaments and regular tournaments. We discussed the transitive tournaments above. A regular tournament is one in which every vertex has the same out-degree. Consequently, every vertex in a regular tournament has the same in-degree. Thus, for every regular n-tournament, n is odd and the out-degree and in-degree of every vertex is While there are no regular n- tournaments for n even, we do have an analogous tournament. A near regular tournament is a tournament in which the out-degrees of any two vertices differs by at most one. By some counting arguments, one can show that if T is a near regular n-tournament, then n is even, exactly half of the vertices have out-degree | and exactly half of the vertices have out-degree | 1. Up to isomorphism, there is only one transitive n-tournament, however there can be many non-isomorphic regular n-tournaments. To better study regular tournaments we often turn to the class of rotational tournaments. Rotational tournaments have a nice structure which makes them somewhat easier to work with, and while not all regular tournaments are rotational, there are typically a 15 large number of rotational n-tournaments for a given n. This makes rotational tournaments a nice class of regular tournaments to start with when studying questions about regular tournaments. We give the construction for rotational tournaments below. Choose an odd positive integer n, and let 5 be a subset of {1 2,..., n 1} of order such that i Â£ S if and only if i (mod n) is not in S. Construct a digraph T on the vertices {0,1, 2,..., n 1} with i > j in T if and only if j i (mod n) is in S. Since x is in S if and only if x (mod n) is not, we have that for any two distinct i,j Â£ V(T) exactly one of j i (mod n) or % j (mod n) is in S. So we have that i * j or j > i, but not both. Further, since 0 & S, T has no arcs of the form Thus T is a tournament. We call T a rotational tournament with symbol S. To see that rotational tournaments are regular choose any vertex i. Then, 0(i) = {i + j (mod n) : j Â£ S'}, and so each vertex has the same out-degree. Another important property of rotational tournaments is that they are vertex transitive. A vertex transitive tournament T is one in which for every two vertices u,v in T, there exists an automorphism of T that maps u to v. Given a rotational tournament T with symbol S, pick i,j Â£ V(T), and let k = j i (mod n). Consider the function to see that 0 is a bijection. Further, if a > b in T, then b a (mod n) is in S, and and
automorphism which maps i to j, and since i and j were chosen arbitrarily, T |