summaries: The paper studies the relationship between dimensional representation of tournament and their structural characterization. In particular, a relationship is established between rank d tournament and their forbidden configurations in terms of flip classes, introduced by Fisher&Ryan(1995) as a way to partion the set of tournaments of a given order. In addition, the problem of bounding the minimum possible dimension of a representation of a tournament is also investigate and lower and upper bounds are given.

summaries: This paper studies the theory of tournament representations, i.e. low-rank matrices $M$ whose sign agrees with the sign matrix of a tournament $T$.  The authors show several properties of such representations, reducing the study to so called $R$-cones, i.e. tournaments where one vertex beats all others. They also characterize completely rank 2 tournaments, and provide a forbiden class for rank $d$ tournaments.  Finally, they provide an upper bound on the minimum dimension of a presentation of any tournament $T$, in the for of a bound involving minimum feedback arc sets of $T$, and show how this can be extended to sign matrices.

summaries: A tournament is made by choosing a direction for each of the edges in a complete graph. A tournament can be induced of by skew symmetric matrices M where entries M_{ij} > 0 if and only if (i,j) is an edge. A tournament on n edges can be represented by a set of d-dimensional vectores {h_1, … , h_n} if (h_j)^T A h_i is not zero iff (i,j) is an edge (and A is an appropriate matrix).  The authors address two questions:  1) What structurally characterizes the class of tournaments that can be represented in d dimensions?  2) Given a tournament T on n nodes, what is the minimum dimension d needed to represent it?.  The first question is answered by considering structures the authors called forbidden. The authors provide a characterization of these forbidden structures as a union of certain equivalence classes.   They answer the latter question in part by providing bounds on what said dimension d should be.

summaries: This paper provides fundamental theories of tournament representations. The authors study two main questions. First they characterize the class of tournaments that can be represented in d dimensions. Second they give lower and upper bounds on the minimum dimension needed to represent a tournament on n nodes.

abstractText: Real world tournaments are almost always intransitive. Recent works have noted that parametric models which assume d dimensional node representations can effectively model intransitive tournaments (Rajkumar & Agarwal (2016)). However, nothing is known about the structure of the class of tournaments that arise out of any fixed d dimensional representations. In this work, we develop a novel theory for understanding parametric tournament representations. Our first contribution is to structurally characterize the class of tournaments that arise out of d dimensional representations. We do this by showing that these tournament classes have forbidden configurations which must necessarily be union of flip classes, a novel way to partition the set of all tournaments. We further characterize rank 2 tournaments completely by showing that the associated forbidden flip class contains just 2 tournaments. Specifically, we show that the rank 2 tournaments are equivalent to locally-transitive tournaments. This insight allows us to show that the minimum feedback arc set problem on this tournament class can be solved using the standard Quicksort procedure. For a general rank d tournament class, we show that the flip class associated with a coned-doubly regular tournament of size O( √ d) must be a forbidden configuration. To answer a dual question, using a celebrated result of Forster & Simon (2006), we show a lower bound of O( √ n) on the minimum dimension needed to represent all tournaments on n nodes. For any given tournament, we show a novel upper bound on the smallest representation dimension that depends on the least size of the number of unique nodes in any feedback arc set of the flip class associated with a tournament. We show how our results also shed light on upper bound of sign-rank of matrices.

authors:
Noga Alon
Shay Moran
Amir Yehudayoff

title: Sign rank versus vc dimension

venue: In Conference on Learning Theory,

authors:
Shalabh Bhatnagar
Michael C Fu
Steven I Marcus
I-Jeng Wang

title: Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences

venue: ACM Transactions on Modeling and Computer Simulation (TOMACS),

authors:
Amanda Bower
Laura Balzano

title: Preference modeling with context-dependent salient features

venue: In International Conference on Machine Learning,

authors:
Ralph Allan Bradley
Milton E Terry

title: Rank analysis of incomplete block designs: I. the method of paired comparisons

authors:
David Causeur
François Husson

title: A 2-dimensional extension of the Bradley–Terry model for paired comparisons

venue: Journal of statistical planning and inference,

authors:
Pierre Charbit
Stéphan Thomassé
Anders Yeo

title: The minimum feedback arc set problem is NP-hard for tournaments

venue: Combinatorics, Probability and Computing,

authors:
Shuo Chen
Thorsten Joachims

title: Modeling intransitivity in matchup and comparison data

venue: In Proceedings of the ninth acm international conference on web search and data mining,

authors:
Nir Cohen
Marlio Paredes
Sofía Pinzón

title: Locally transitive tournaments and the classification of {(1, 2)}-symplectic metrics on maximal flag manifolds

venue: Illinois Journal of Mathematics,

authors:
David C Fisher
Jennifer Ryan

title: Tournament games and positive tournaments

venue: Journal of Graph Theory,

title: A linear lower bound on the unbounded error probabilistic communication complexity

venue: Journal of Computer and System Sciences,

authors:
Jürgen Forster
Hans Ulrich Simon

title: On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes

venue: Theoretical Computer Science,

title: Intransitivity in theory and in the real world

title: Individual choice behavior: A theoretical analysis

venue: Courier Corporation,

authors:
Rahul Makhijani
Johan Ugander

title: Parametric models for intransitivity in pairwise rankings

venue: In The World Wide Web Conference,

authors:
Arun Rajkumar
Shivani Agarwal

title: When can we rank well from comparisons of O(n log(n)) non-actively chosen pairs

authors:
KB Reid
Ezra Brown

title: Doubly regular tournaments are equivalent to skew hadamard matrices

venue: Journal of Combinatorial Theory, Series A,

title: Intransitivity of preferences

venue: Psychological review,

heading: 1 INTRODUCTION

text: In this work, we lay the the foundations for a theory of tournament representations. A tournament is a complete directed graph and arises naturally in several applications including ranking from pairwise preferences, sports modeling, social choice, etc. We say that a tournament T on n nodes can be represented in d dimensions if there exists a skew symmetric matrix M ∈ Rn×n of rank d such that a directed edge from i to j is present in T if and only if Mij > 0. Real world tournaments are almost always intransitive (Tversky (1969); Klimenko (2015)) and it is not known what type of tournaments can be represented in how many dimensions. This is important to understand because of the following reason: As a modeler of preference relations using tournaments, it is often more natural to have structural domain knowledge such as ‘The tournaments under consideration do not have long cycles’ as opposed to algebraic domain knowledge such as ‘The rank of the skew symmetric matrix associated with the tournaments of interest is at most k’. However, algorithms that learn rankings from pairwise comparison data typically need as input the algebraic quantity - the rank of the skew symmetric matrices associated with tournaments or equivalently the dimension where they are represented (Rajkumar & Agarwal (2016)). To bridge the gap between the structural and the algebraic world, we ask and answer two fundamental questions regarding the representations of tournaments.

text:
2) Given a tournament T on n nodes, what is the minimum dimension d needed to represent it?.
We answer the first question by investigating the intricate structure of the rank d tournament class via the notion of forbidden configurations. Specifically, we show that the set of forbidden config-
uration for the rank d tournament class must necessarily be a union of flip classes, a novel way to partition the set of all tournaments into equivalence classes. We explicitly characterize the forbidden configurations for the rank 2 tournament class and exhibit a forbidden configuration for the general rank d tournament class. Specifically, we show that the rank 2 tournaments are equivalent to locally transitive tournaments, a previously studied class of tournaments (Cohen et al. (2004)). Our results throw light on the connections between transitive and locally transitive tournaments and also lets us develop a classic Quicksort based algorithm to solve that the minimum feedback arc set problem on rank 2 tournaments with O(n2) time complexity. Our results for the general rank d tournament class have connections to the classic long standing Hadamard conjecture and we discuss this as well. Figure 1 gives a glimpse of some of the main results.
We answer the second question by proving lower and upper bounds on the smallest dimension needed to represent a tournament on n nodes. We exhibit a lower bound of Ω( √ n) using a variation of the celebrated dimension complexity result of Forster & Simon (2006) for sign matrices. To show upper bounds, we introduce a novel parameter associated to a tournament called the Flip Feedback Node set of a Tournament. This quantity depends on the least number of unique nodes in any feedback arc set of an associated tournament class for the tournament of interest and upper bounds linearly the representation dimension of any tournament. We show how our results can be used to provide upper bounds on the classic notion of sign-rank of a matrix. Previously known upper bounds for sign rank depended on the VC dimension of the associated binary function class (Alon et al. (2016)). Our upper bounds on the other hand have a graph theoretic flavour.
Organization of the Paper: We discuss briefly in Section 2 the foundational works this paper builds upon. We introduce necessary preliminaries in Section 3. The answer to the first question about the structural characterization of d dimensional tournament classes span Sections 4, 5 and 6. We devote Section 7 to answer the second question about the number of dimensions needed to represent a tournament. Section 8.1 explores connections of our results to upper bounds on the sign rank of a sign matrix. Finally, we conclude in Section 10. All proofs are defered to the Appendix.

heading: 2 RELATED WORK

text:
The work in this paper builds on several pieces of work across different domains. We summarize below the most important related works under different categories:
Intransitive Pairwise Preference Models: One of the main reasons to study representations of tournaments is to model pairwise preferences. Parametric pairwise preference models that can model intransitivity have gained recent interest. Rajkumar & Agarwal (2016) develop a low rank pairwise
ranking model that can model intransitivity. However, their study and results were restricted to just the transitive tournaments in these classes. A generalization of the classical Bradley-Terry-Luce model (Bradley & Terry (1952), Luce (2012)) was studied in Causeur & Husson (2005). However, no structural characterization is known. Same holds for the more recent models studied in Chen & Joachims (2016), Makhijani & Ugander (2019) and Bower & Balzano (2020).
Flip Classes: The notion of flip classes, a novel way to partition the set of all tournaments on n nodes, was first introduced in Fisher & Ryan (1995). The goal however was completely different and was on studying equilibrium on certain generalized rock-paper-scissors games on tournaments. Interestingly, and perhaps surprisingly, the notion of flip classes turn out to be fundamental to our study of understanding forbidden configurations of d dimensional tournament classes.
Dimension Complexity and Sign Rank: Dimension complexity and sign rank of sign pattern matrices were studied in Forster (2002). These results have found significant applications in learning theory and lower bounds in computational complexity (Forster & Simon (2006)). More recently, Alon et al. (2016) study the sign rank for function classes with fixed Vapnik-Chervonenkis (VC) dimension and show upper bounds. Our upper bounds however depend on certain graph theoretic properties.

heading: 3 PRELIMINARIES

text:
Tournaments: A tournament T is a complete directed graph i.e., a graph on n nodes where for every pair of nodes (i, j) either an edge is oriented from i to j or j to i. The number of nodes n in T will be usually clear from the context or will be explicitly specified. For nodes i and j in T, we say i T j if there is a directed edge from i to j. Given a node i, we define the out and in neighbours of i as T+i = {j : i T j} and T − i = {j : j T i} respectively. Given a set of nodes S, we denote by T(S) the induced sub-tournament of T on the nodes in S.
Feedback Arc Set and Pairwise Disagreement Error: Given a permutation σ on n nodes, the feedback arc set of σ w.r.t the tournament T is defined as Eσ(T) = {(i, j) : σ(i) > σ(j), i >T j}. The pairwise diagreement error of σ w.r.t T is given by |E
σ(T)| (n2) . It is known that finding the σ
that minimizes the pairwise disagreement error w.r.t a general tournament T is a NP-hard problem (Charbit et al. (2007)).
Skew Symmetric Tournament Classes: A square matrix M ∈ Rn×n is skew symmetric if Mij = −Mji∀i, j. In this paper, whenever we refer to a skew symmetric matrix M ∈ Rn×n, we always assume Mij 6= 0 ∀i 6= j and Mii = 0 ∀i. Given such an M, we denote by T{M} the tournament on n nodes induced by M where i T j ⇐⇒ Mij > 0. We refer to class of tournaments induced by rank d skew symmetric matrices as the rank d tournament class.
Forbidden Configurations: A tournament class T is a collection of tournaments. T is said to forbid a tournament T if no tournament in T has a sub-tournament that is isomorphic to T. We call T a forbidden configuration for T if T forbids T but does not forbid any sub-tournament of T. For example, the class of all acyclic/transitive tournaments has the 3-cycle as a forbidden configuration i.e, the tournament T on three nodes i, j, k where i T j T k T i. Representations and Tournaments: The matrix Arot ∈ Rd×d is defined for every even d and is a block diagonal matrix which consists of d/2 blocks of [0−1; 1 0]. This is the canonical representation of a non-degenerate skew symmetric matrix i.e., any non-singular skew symmetric matrix can be brought to this form by a suitable basis transformation. Given a set of vectors in H = {h1, . . . ,hn} where each hi ∈ Rd for some even d, we refer to the set H as a tournament inducing representation if hTi A
rothj 6= 0 for all i 6= j. Furthermore, we refer to the tournament induced by H as T[H] where a directed edge exits from node i to j if and only if hTi A
rothj > 0. It is easy to verify that hTAroth = 0 for any h ∈ Rd. Any skew symmetric matrix M ∈ Rn×n of rank d can be written as M = HTArotH for some H ∈ Rd×n. It follows that if M = HTArotH, then T{M} = T[H]. Positive Spans: A set of vectors H = {h1, . . . ,hn} where each hi ∈ Rd is said to positively span Rd if for any w ∈ Rd, there exists non-negative constants c1, . . . , cn ≥ 0 such that ∑ i cihi = w. If H positively spans Rd, then there does not exist a w ∈ Rd such that wThi > 0 ∀i. This is a easy consequence of Farkas’ Lemma.
Remark on Notation: We reiterate that we use T(·),T{·} and T[·] to mean different objects - the tournament induced by a subset of nodes, the tournament induced by a skew symmetric matrix and the tournament induced by a representation of a set of vectors respectively. These will be usually clear from the context.

heading: 4 FLIP CLASSES, FORBIDDEN CONFIGURATIONS AND POSITIVE SPANS

text:
The main purpose of this section is understand the space of forbidden configurations of rank d tournaments. The main result of this section shows that the forbidden configurations for rank d tournament classes occur as union of certain carefully defined equivalence classes of non-isomorphic tournaments. Towards this, we define the notion of flip classes which was introduced first in (Fisher & Ryan, 1995) although in a different context: Definition 1. Given a tournament T on n nodes and a set S ⊆ [n], define φS(T) to be the tournament obtained from T by reversing the orientation of all edges (i, j) such that i ∈ S, j ∈ S̄.
In other words, φS(T) is obtained from T by reversing the edges across the cut (S, S̄) = {(i, j) : i ∈ S, j ∈ S̄}. Definition 2. A class of tournaments on n nodes is called cut-equivalent if for every pair of tournaments T,T′ in the class, there exists a S ⊆ [n] such that T′ is isomorphic to φS(T)
It is easy to show that the set of cut-equivalent tournaments form an equivalence relation over the set of all tournaments on n nodes Fisher & Ryan (1995). The corresponding equivalence classes are called a flip classes. We denote by F(T) the flip class of T i.e., the equivalence class of all cut-equivalent tournaments to T. In the following theorem we show the fundamental relation between flip classes and forbidden configurations. Theorem 1. Let T, a tournament on k nodes, be a forbidden configuration for some rank d tournament class. Then every tournament in the flip class of T is also a forbidden configuration for the rank d tournament class. Corollary 1. (Structure of Forbidden configurations) Forbidden configurations of rank d tournament classes are unions of flip classes.
Thus, to characterize the forbidden configuration of rank d tournament classes, we need to understand the flip classes. We begin with the following simple but useful definition. Definition 3. A tournament T is called a R-cone if there exists a node i∗ such that
• i∗ T j for all j 6= i∗ ( j T i∗ for all j 6= i∗ ) • T(T+i∗) ( T(T−i∗) ) is isomorphic to the tournament R.
R-cones are essentially the tournament R along with an additional node that either beats or loses to nodes in R. R-cones are useful as they be viewed in some sense as canonical tournaments in flip classes. This is justified because of the following observation. Proposition 1. Every flip class contains an R-cone for some tournament R.
The above observation says that to identify the forbidden configurations for a given tournament class, it suffices to identify all forbidden R-cones. Then by Corollary 1, the associated flip classes will be the set of all forbidden configurations. However, it does not throw light on what property the tournament R must satisfy. The following lemma establishes this. Lemma 2. Let R be a tournament with the property that if R = R[H] for some representation H = {h1, . . . ,hn} ∈ Rd then H positively spans Rd. Then rank d tournament class forbids R-cones.
The above lemma is extremely helpful in the sense that it reduces the study of forbidden configurations to the study of finding tournaments such that any representation that induces it must necessarily positively span the entire Euclidean space. Note that there may be several representations which positively span the entire space. This does not mean their the associated coned tournaments are forbidden configurations. Instead, we start with an R cone and conclude it is forbidden if every
representation that induces R necessarily positively spans the entire space. It is a non-trivial problem to identify such tournaments R for an arbitrary dimension d.
In the following sections, we explicitly identify the only forbidden flip class for rank 2 tournaments, one forbidden flip class for rank 4 and then (a potentially weaker) forbidden flip class for the general rank d case.

heading: 5 RANK 2 TOURNAMENTS ⇐⇒ LOCALLY TRANSITIVE TOURNAMENTS

text:
The goal of this section is to characterize the forbidden configurations of rank 2 tournaments. Thanks to Lemma 2, this reduces to the problem of identifying a tournament whose representation necessarily span the entire space. The following lemma exhibits this tournament.
Lemma 3. Let H = {h1,h2,h3} ∈ R2 be two dimensional representation of 3 nodes which induce a 3 cycle tournament. Then the set H positively spans R2. Furthermore, the 3 cycle is the only such tournament on 3 nodes.
The above lemma immediately implies that a coned 3-cycle is the only forbidden configuration for rank 2 matrices. This is indeed true. However, for the purposes of generalizing our result (which as we will see will be useful when discussing the higher dimension case), we will view the 3-cycle as a special case of a doubly regular tournament (defined next).
Definition 4. A tournament T on n nodes is said to be n-doubly regular if |T+i | = |T + j | for all i, j and |T+i ∩T + j | = k for some fixed k for all i 6= j
Trivially the 3-cycle is the only 3-doubly regular tournament. The following lemma establishes that the flip class of a coned 3 doubly regular tournament only contains itself.
Proposition 2. The flip class of 3-doubly-regular-cone does not contain any other tournament. Theorem 4. 3-doubly-regular-cone is the only forbidden configuration for the rank 2 tournament class.
We have thus far established that any rank 2 tournament on n nodes forbids the 3-doubly-regular-cone. The advantage of this result is that we can go one step further and explicitly characterize the rank 2 tournament class. To do this, we need the definition of a previously studied tournament class.
Definition 5. A tournament T is called locally transitive if for every node i in T, both T(T+i ) and T(T−i ) are transitive tournaments
Before seeing why locally transitive tournaments are relevant to our study, we first show that they are intimately connected to transitive tournaments via the following characterization.
Theorem 5. (Connection between Transitive and Locally Transitive Tournaments) The set of all non isomorphic locally transitive tournaments on n nodes is equivalent to the flip class of the transitive tournament on n nodes.
We will see next that this key result allows us to immediately characterize the rank 2 tournament class. We will see later (Section 7) that this result is also crucial in determining an upper bound on the dimension needed to represent a given tournament.
Theorem 6. (Characterization of rank 2 tournaments) A tournament T on n nodes is locally transitive if and only if there exists a skew symmetric matric M ∈ Rn×n with rank(M) = 2 such that the T{M} = T.
It is perhaps surprising that a purely structural description of a tournament class namely that of local transitivity turns out to be exactly equivalent to the rank 2 tournament class. To the best of our knowledge, this characterization appears novel and hasn’t been previously noticed. One of the interesting consequence of the above characterization is that the minimum feedback arc set problem on rank 2 tournaments can be solved using a standard quick sort procedure. This is formalized below.
Theorem 7. (Minimum Feedback Arc Set is Poly-time Solvable for Rank 2 tournaments) Let T be a locally transitive tournament on n nodes and let σ1 be the permutation returned by running a standard quick sort algorithm choosing 1 as the initial pivot node and where the outcome of
comparison between items i and j is i if and only if i T j. Let σk be obtained from σ1 by k − 1 clockwise cyclic shifts for k ∈ [n]. Let Ek be the feedback arc set of σk w.r.t T. Then mink |Ek| achieves the minimum size of the feedback arc set for T.
Proof. (Sketch) The proof involves two steps: first arguing that by fixing any pivot, quick sort would return a ranking that is a cyclic shift of σ1. The second step involves inductively arguing that one of the cyclic shift must necessarily minimize the feedback arc set.

heading: 5.1 RANK 4 TOURNAMENTS

text:
We now turn to rank 4 tournaments. We could have directly considered rank d tournaments, but it turns out that what we can show a slightly stronger result for rank 4 tournaments than the general case and so we focus on them separately. While it is arguably simple in the rank 2 case to identify the tournament that necessitates the positive spanning property, it is not immediately clear in the rank 4 case. A first guess would be to consider the regular tournaments (as the 3 cycle for rank 2 is also a regular tournament) on 5 nodes or 7 nodes. However, these turn out to be insufficient as one can construct counter examples of regular tournaments on up to 7 nodes with representations that don’t span the entire R4. In fact, as we had defined earlier, the right way to generalize to higher dimension turns out to be using doubly regular tournaments. Theorem 8. The 11-doubly-regular-cone is a forbidden configuration for rank 4 tournament class.
Note that while for the rank 2 case, we were able to prove that the only forbidden flip class is the one that contains a coned 3 cycle, we have not shown that the only forbidden configuration for rank 4 class is the 11 doubly regular cone. In fact, we believe that the smallest forbidden tournament for rank 4 class is the 7- doubly regular cone. However, we haven’t been able to prove this. This appears to be a non-trivial problem. From our simulation experiments, we observe that the only flip class that could be forbidden on 8 nodes is the one that contains the 7-doubly regular cone. In particular, we were able to produce examples of representations for all other flip classes on 8 nodes. However, this does not imply that the ones where we could not produce a forbidden configuration is in fact forbidden. Unfortunately, it seems tricky to prove this and we don’t have a way to show this at this point. On the other hand, as we will see in the next section, the result in Theorem 8 is still stronger than the result for the general rank d tournaments.
Having discussed rank 2 and rank 4 cases separately, we next turn our attention to the general rank d tournament class.
6 RANK d TOURNAMENTS AND THE HADAMARD CONJECTURE
From the understanding of rank 2 and rank 4 tournament classes in the previous sections, and noting that the corresponding forbidden configurations are intimately related to doubly regular tournaments, it is tempting to conjecture that this is true in general. Conjecture 1. Rank 2d tournament class forbids 4d− 1-doubly-regular-cones.
Ideally, the conjecture above must have a qualifier ‘if they exist’ for the 4d − 1 doubly regular cone. This is because of the equivalence between doubly regular tournaments on 4d− 1 nodes and Hadamard matrices in {+1,−1}4d×4d (Reid & Brown (1972)). A matrix H ∈ {+1,−1}n×n is called Hadamard if H′H = nI where I is the identity matrix. It is known that there is a bijection between skew Hadamard matrices and doubly regular tournaments Reid & Brown (1972). A long standing unsolved conjecture about Hadamard matrices is the following: Conjecture 2. (Hadamard) There exists a Hadamard matrix of order 4d for every d > 0.
If Conjecture 1 were true, then it would imply the existence of 4d− 1-doubly regular tournament for every d and thus would imply the Hadamard conjecture is true. In fact, Conjecture 1 being true would say more which we state below: Conjecture 3. There exists a skew symmetric Hadamard matrix of order 4d for every d > 0.
The main result of this section is a weaker form of the conjecture: Theorem 9. Rank 2(d− 1) tournament class forbids 12d2 − 1-doubly-regular-cones if they exist.

heading: 7 HOW MANY DIMENSIONS ARE NEEDED TO REPRESENT A TOURNAMENT?

text:
The previous sections considered a specific rank d tournament class and tried to characterize them using forbidden configurations. In this section, We turn to the dual question of understanding the minimum number of dimensions needed to embed a tournament. We start by not considering a single tournament T but the set of all tournaments on n nodes. We show below a general result which provides a lower bound on the minimum dimension needed to embed any tournament on n nodes.
Theorem 10. (Lower Bound on minimum representation dimension) Let T be a tournament on n nodes. Then there exists H = {h1, . . . , hn} ∈ Rd such that T = T[H] only if d ∑n i=1(ρi(T+I))
2 ≥ n2. Furthermore, let d be the minimum dimension needed to embed every tournament on n nodes. Then, d ≥ √ n.
The result follows the arguments in the celebrated work of Forster & Simon (2006). As Alon et al. (2016) point out, Forster’s technique cannot be stretched further in obvious ways to get upper bounds. The above theorem tells us that in the worst case at least Ω( √ n) dimensions are necessary to represent all tournaments on n nodes. In fact if Conjecture 1 were true, the minimum dimension would be Ω(n). However, in practice one might not encounter tournaments with such extremal/worst-case properties.
Remark: The lower bound for the representation dimension of random tournaments (where the orientation of each edge is determined by an unbiased Bernoulli coin toss) will depend on the singular values of random tournaments. However, we don’t expect the representation dimension to be of independent of n, the number of nodes. Loosely speaking, a doubly regular tournament is "like" a random tournament (the associated Hadamard Tournament has been used in deterministic perturbation schemes as alternatives for random sign matrices (Bhatnagar et al. (2003))). On the other hand, the most interesting real-world tournaments might be characterized by constant sized node representations and hence may be structurally much more constrained than random tournaments. Typically, a smaller number of dimensions might be enough to represent tournaments of practical interest.
Our goal below is to upper bound on the number of dimensions needed to embed a given tournament T.
Recall that Eσ(T) denotes the feedback arc set of a permutation σ w.r.t a tournament T. We define the number of nodes involved in the feedback arc set as follows: θ(σ,T) = |{i : ∃j : σ(i) > σ(j), (i, j) ∈ Eσ(T)}|. We next define a crucial quantity µ(T) which we term as the Flip Feedback Node set size. This quantity will determine an upper bound on the dimension where a tournament can be represented:
Definition 6. Given a tournament T, define the Flip Feedback Node Set Size as follows:
µ(T) = min σ min T′∈F(T)
θ(σ,T′)
In words, given a tournament T, the quantity µ(T) captures the minimum number of nodes involved in any feedback arc set among all tournaments in the flip class of T. For instance if T is a locally transitive tournament then µ(T) would be 0 - as T is necessarily in the flip class of a transitive tournament and so the Eσ corresponding to the topological ordering of the transitive tournament would have an empty feedback arc set. As another example, consider T to be the coned 3-cycle. The flip class of this tournament contains only itself and the best permutation will have one edge in the feedback arc set. Thus µ(T) = 1. In general, it is trivially true that µ(T) is upper bounded by n, the number of nodes. Howeverµ(T) could be much smaller than n depending on T. The main result of this section is the theorem below that shows that µ(T) gives an upper bound on the number of dimension needed to represent any tournament.
Theorem 11. (Upper Bound on minimum representation dimension) For any tournament T, there exists H = {h1, . . . ,hn} ∈ R2(µ(T)+1) such that T = T[H].
Remark 1: The above theorem says that one can always obtain an representation H in dimension d = O(µ(T)) that induces T. The bound gets tighter for tournaments with smaller feedback arc sets, which is what one might typically expect in practice. Note that even for some tournaments that may
have a large feedback arc set, the associated flip class might contain a tournament with a smaller feedback arc set.
Remark 2: We note that in general µ(T) is not necessarily the cardinality of the minimum feedback arc set among all tournaments in the flip class of T. Instead µ(T) captures the cardinality of the set of nodes involved in any feedback arc set. To see why these two could be different, consider the tournament in Figure 2. Here, σa = [6 1 2 3 4 5] is the permutation minimizing the feedback arc set. Let σb = [1 2 3 4 5 6]. Note that |Eσa | = 2, θ(σa,T) = |{1, 2}| = 2. However |Eσb | = 3, yet θ(σb,T) = |{6}| = 1. Thus, σb gives a tighter upper bound on the dimension needed to represent T.

heading: 8 APPLICATIONS OF THE RESULTS

heading: 8.1 CONNECTIONS TO SIGN RANK

text:
The sign rank of a matrix G ∈ {+1,−1}m×n is defined as the smallest integer d such that there exists a matrix M ∈ Rm×n of rank d that satisfies sign(M) = G 1. Here sign(z) = 1 if z > 0 and −1 otherwise. A breakthrough result on the lower bound on the sign rank was given by Forster & Simon (2006). However, good upper bounds have been harder to obtain. We show below how Theorem 11 also translates to an upper bound on the sign rank of any sign matrix G. Theorem 12. Let G ∈ {+1,−1}m×n be an arbitrary sign matrix. Let T be any tournament on m+ n nodes. Let S = {1, . . . ,m} and let edge orientations of the cut(S, S̄) in T be determined by G Then sign-rank(G) ≤ 2(µ(T) + 1)
We argue that the the above result can give significantly tigher bounds than the bounds in Alon et al. (2016). The simplest example one can consider is a locally transitive tournament on n nodes. Viewing this as a sign pattern matrix, it is easy to argue that the VC dimension of such a matrix is atmost 2. Theorem 5 in Alon et al. (2016) shows that the sign rank is upper bounded by O( √ n)) when VC dimension is 2 (For a general hypothesis class of VC dimension d, the upper bound is O(n1− 1d ). On the other hand, by definition µ(T) for any locally transitive tournament is exactly 0 (and so the upper bound of 2µ(T) + 1 is exactly 2 and is tight) for any locally transitive tournament which is independent of the number of nodes n. The important reason for this significantly improved bound using µ(T) is that we consider only skew symmetric sign pattern matrices while Alon et al. (2016) look at the worst case (w.r.t representation dimension/sign rank) sign pattern matrices for a fixed VC dimension. Our bound reduces the study of sign rank to a more graph theoretic study of the feedback arc set problem. It is not clear if the upper bound of 2(µ(T) + 1) can be improved and we leave this to future work.

heading: 8.2 CONNECTIONS TO LEARNING FROM PAIRWISE COMPARISONS

text:
Consider a learning to rank problem from pairwise comparisons. Here, a set of n items need to be ranked from a subset of pairwise comparisons among them. Every pair that is chosen for comparison is compared a fixed number of times. Every time items i and j are compared, i is preferred over j with probability Pij. A common and popular model to capture these probabilities is the BradleyTerry-Luce (BTL) model Bradley & Terry (1952) where Pij = si/(si + sj) for some score vector s ∈ Rn. Note that the model is completely specified by the score vector s which in turn completely determines the probability preference matrix P. The learning problem is to learn these unknown
1Sign-rank can be defined for any general matrix G ∈ Rm×n. We restrict to the sign matrices to make the connections to the tournament matrices explicit
score vector s ∈ Rn from pairwise comparisons. Once the score vector is learnt, a ranking can be obtained by sorting these scores and the pairwise probabilities of unseen pairs of items can be predicted.
The above BTL model is an example of a rank-2 model in the sense that the probability preference matrix P results in a rank 2 matrix under the log-odds skew symmetric transformation. Indeed, if we define Mij = log(
Pij Pji ). then equivalently Mij = log(si) − log(sj). It is easy to show that M is a rank 2 skew symmetric matrix. However, the major disadvantage of the BTL model is that it can capture only transitive preferences i.e, Pij > 0.5 and Pjk > 0.5 =⇒ Pki > 0.5. In real world situations, intransitivity is very common. To achieve intransitivity, the simplest way would be to start with a general rank r skew symmetric matrix M and consider the probability matrix that determines the preference probabilities as Pij = 1/(1 + exp(−Mij). Here, the learning problem would be to estimate the two score vectors or equivalently the two dimensional representation for each item. Previous studies (Rajkumar & Agarwal (2016)) show that this can be learnt using Matrix completion based approaches or maximum likelihood based approaches (Chen & Joachims (2016)). However, what was not known earlier is the structure of tournaments that can be captured using such low rank restrictions which is important to decide on the parameter r. Our work helps modellers make informed decision to choose r based on explicitly identifying the types of tournaments that can be modelled and subsequently learnt.
We discuss next a simple application where modeling a ranking from pairwise comparisons problem can benefit from the insights gained using our results. Consider a situation of modelling sports tournaments such as Tennis. Here, one can choose to model the players (nodes) using 2-dimensions where the dimensions corresponds to their offense (forehand) and defense (backhand) strengths respectively. When two players compete, the advantage of the offense strength of player 1 w.r.t the defense of player 2 and vice versa determine the outcome of the match. This is precisely captured by a rank 2 model where the learning problem would be to infer these latent offense/defense strength of each player from outcomes of pairwise competitions. Theorem 6 says that such a model would immediately lead to locally transitive tournaments among the players. This structural characterisation now gives insights to the modeller if 2 dimensions are enough to model the players or not.

heading: 9 REAL WORLD TOURNAMENT EXPERIMENTS

text: We conducted simple experiments on real world data sets. Specifically, we considered 114 real world tournaments that arise in several applications including election candidate preferences, Sushi preferences, cars preferences, etc (source: www.preflib.org). The number of nodes in these tournaments varied from 5 to 23. Out of the 114 tournaments considered, 76(66.67%) were in fact locally transitive. For these tournaments, the upper bounds and lower bounds given by our theorems matched and was equal to 2. Interestingly, even for the non-locally transitive tournaments, the lower bound still turned out to be 2. We computed the upper bound for tournaments of size at most 9 (we did not do it for larger tournaments as this involves a brute force search) and found the value to be either 4 or 6. This shows that the upper bounds are usually non-trivial and efficiently approximating it is an interesting direction for future work.

heading: 10 CONCLUSION

text: In this work, we develop a theory of tournament representations. We show how fixing the representation dimension enforces, via forbidden configurations, restrictions on the type of tournaments that can be represented. We study and characterize rank 2 tournaments and show forbidden sub-tournaments for the rank d tournament class. We develop upper and lower bounds for minimum dimension needed to represent a tournament. Future work includes attempting to look deeper into some of the conjectures presented and possible strengthening of some of the bounds presented.

heading: A APPENDIX

heading: Proof of Theorem 1

text: Proof. Assume there is a T′ ∈ F(T) which is not forbidden for rank d tournament class. Thus, ∃H′ = {h′1, . . . ,h′n} ∈ Rd such that T′ = T[H′]. By definition, there must also exist a S ⊆ [n] such that T′ = φS(T). Consider the representation H obtained from H′ where hi = −h′i for all i ∈ S and hi = h′i otherwise. It is easy to verify that T = T[H] which is a contradiction to the assumption that T is a forbidden configuration for rank d tournaments.

heading: Proof of Proposition 1

text: Proof. Consider any tournament T. Let T′ = φ{i∪T−i }(T) for an arbitrary node i. By definition T′ ∈ F(T). Also, T′ is a R-cone, coned by i.

heading: Proof of Lemma 2

text: Proof. Consider any representation H that induces a tournament R. By assumption of the theorem, H positively spans Rd. Thus, by Farkas’ lemma, there cannot exist a v ∈ Rd such that vThi > 0 ∀i. Note that if R-cone is not a forbidden configuration for rank d tournaments, then there must exist a h ∈ Rd such that hTArothi > 0 ∀i. As Arot is invertible, one can set v = (Arot)Th with the property that vThi > 0 ∀i. But this contradicts the conclusion drawn earlier from Farka’s lemma.

heading: Proof of Proposition 2

text: Proof. This is easily verified by checking all tournaments in F(T) where T is the coned 3-cycle.

heading: Proof of Lemma 3

text: Proof. Wlog, assume that 1 ≥T 2 ≥T 3 ≥T 1. Then, it must be the case that the counterclockwise angle between the representation of the corresponding items must be ≤ 180 degrees. However, if the representations {h1,h2,h3} did not positively span R2, then by Farka’s Lemma, there must be some supporting hyperplane for the representations. However, this would imply at least one of the node pairs {(1, 2), (2, 3), (3, 1)} must necessarily make an angle ≥ 180 degrees. But this contradicts the assumption that the nodes form a 3 cycle.

heading: Proof of Theorem 5

text:
Proof. Let T be a transitive tournament on n nodes and let T′ ∈ F(T). Then, there exists some S ⊆ [n] such that T′ = φS(T). Consider any node i ∈ [n]. Define following 4 subset of nodes associated with i: S1 = T+i ∩ S, S2 = T + i \S1, S3 = T − i ∩ S, S4 = T − i \S. Note that each of T(Sk) for k = 1 to 4 is a transitive sub-tournament and the relationship across Si, Sj for any two sets is either one completely beats the other or completely loses to the other. Note that in φS(T) the orientation of the edges across these sets is either flipped as a whole or not flipped at all. Thus, exactly two of these sets will be part of T′+i and two part of T − i (the exact sets among these sets will depend on whether i ∈ S or not), thus preserving the local transitivity property. Thus T′ is locally transitive.
To prove the opposite direction, let T be a locally transitive tournament. Let i ∈ [n] be an arbitrary node. We argue that T′ := φT+i (T) is a transitive tournament. We will show this by arguing that there does not exist a 3 cycle in T′. Consider any 3-cycle a >T b >T c >T a. As T is locally transitive, not all {a, b, c} can be in T+i . Also not all {a, b, c} can avoid T + i as [n] \T + i is transitive. Thus at least one and at most two of {a, b, c} belongs to T+i (T). This means that the 3-cycle becomes a transitive tournament in T′ := φT+i (T). Thus every cycle in T becomes transitive in T
′. Now consider any 3 nodes which forms a transitive tournament a >T b >T c and involves at least one
node and at most two nodes in T+i . Then there are only two cases to consider: (1) a ∈ [n] \ T + i and {b, c} ∈ T+i or (2) {a, b} ∈ [n] \T + i and c ∈ T + i . In both these cases, it is easy to verify that the the corresponding tournament in T′ is either the transitive tournament b >T′> c >T′ a or the transitive tournament c >T′ a >T′ b. As these are the only possibilities, the result follows by noting that T′ = φT+i (T) =⇒ T = φT+i (T ′) and so T ∈ F(T′).

heading: Proof of Theorem 6

text: Proof. Assume T is locally transitive. Then by Theorem 5, it must be in the flip class of some transitive tournament T′ i.e. T = φS(T′) for some S ⊆ [n]. It is easy to represent a transitive tournament using a rank 2 skew symmetric matrix. Indeed pick any vector u ∈ Rn which is sorted according to the topological ordering of T′. Let v ∈ Rn be the all ones vector. Then M = uvT −vuT represents T′. Let M = (H′)TArotH for some H′ ∈ R2×n. Then the columns of H′ represent T′. Now consider the representation H′ obtained from H′ where the columns indexed by S are multiplied by−1. This does not change the rank of H′ and it can be verified that T = T[H]. To prove the other direction, consider any rank 2 skew symmetric matrix M ∈ Rn×n. Then there must exist u,v ∈ Rn such that M = uvT − vuT . Consider any node i ∈ [n]. Consider three nodes a, b, c such that uivj > ujvi for j ∈ {a, b, c}. Furthermore let uavb > vaub and ubvc > vbuc. Then by carefully going over all {±} sign possibilities for {ui, ua, ub, uc, vi, va, vb, vc}, one can conclude that it must be the case that uavc > vauc. This just shows that T+i is transitive. Analogously one can show that T−i is also transitive. As i was arbitrary, the result follows.

heading: Proof of Theorem 7

text:
Proof. Recall that the classic quick sort algorithm picks a pivot node (say 1) and places all nodes that beat the pivot to the right in the ranking and those that lose to the left and then recurses on the left and right subsets. As T is locally transitive, choosing any pivot i would correspond to fixing the pivots position and simply returning the ranking [σ(N−i ), i, σ(N + i )] where σ(N + i ), σ(N − i ) correspond to the topological ordering of the transitive tournaments T(N+i ) and T(N − i ) respectively. We first argue that changing the pivot only cyclically shifts the final ranking. To see why this is true, consider two pivots i and j and their corresponding rankings σi and σj . Without loss of generality, assume that the ranking σi = [1, . . . , n] and i >T j. We argue that there exists an integer k such that N+j = {j + 1 mod n, (j + 2) mod n, . . . , (j + k) mod n} (where by convention n mod n = n). As N+i is transitive, and j is part of it, it must be the case that all the nodes {j + 1, . . . , j + n} ∈ N+j . Then to prove the claim, it remains to be shown that the set N−i ∩N + j is either empty or must be the nodes {1, . . . , `} for some ` < i. If empty, we are done. If not, assume for the sake of contradiction that there exists three succesive integers `a, `b, `c < i such that `a, `c <T j but `b >T j. It is easy to verify that this cannot happen as it would lead to T({`a, `b, `c, j}) being a forbidden configuration. Notice that as every locally transitive tournament is in the flip class of a transitive tournament i.e., T = φS(T) for some S, one can divide the set of all nodes into 2k + 1 groups as follows: Let [1, . . . , n] be the ordering corresponding to the transitive tournament wlog. Starting from 1, add as many nodes to a group such that all the elements belong to either S or S̄. Once the condition is violated, create a new group and continue the same process. It is not hard to verify that 2k+ 1 groups will be formed in this process for some k ≥ 0. Moreover, each group would separate two other groups by construction.
We can first show that the items of a single group must appear in consecutive positions in one of the optimal rankings. This is proven as follows.
Consider there exists an optimal ranking with items which belong to the same group not occurring consecutively. Consider two items belonging to the same group, which have items from other groups present in between them in the ranking. Consider these items to be a1, a2, with a1 present above in the rankings. Consider the number of upsets that the two items are involved in to be u1 and u2. If u1 ≤ u2, a2 can be placed right after a1 in the ranking, creating a better or equivalent ranking in terms of upsets. Similarly if u1 ≥ u2, a1 can be placed directly above a2 in the rankings to create
an equivalent or better ranking. Therefore there exists an optimal ranking which has all items in the same group consecutively.
This theorem is then reduced to finding a ranking of groups, which is proven using induction on k.

heading: Base Case

text:
Consider the base case with k = 1. Let there be 3 groups, C, A1, B1. We can say that the optimal ranking cannot be any of the following
CB1A1
A1CB1
B1A1C
since all three rankings can be made better by swapping the second and third ranked groups. Therefore the 3 possible optimal rankings are
CA1B1
A1B1C
B1CA1
which are cyclic shifts of each other.

heading: Inductive Step

text:
One property of rankings which is useful for the inductive step proof is as follows. Let there be 2k+ 1 groups G = {g1, g2 . . . g2k+1}. Label the optimal ranking with the condition that gi be placed first in the ranking as Ri. The ranking Ri with gi removed must be the optimal ranking for G \ {gi}. This can be shown using contradiction i.e, if there was a better ranking for G \ gi, that ranking with gi appended to the front would be better than Ri.
We now assume the theorem is true for size 2k − 1 instances and aim to prove for the same for size 2k + 1 instances. Consider g1 as the first group in the ranking. This creates a certain number of upsets, for the purposes of ranking the remaining groups, 2 of the remaining groups can be merged into a single group. This follows from the observation earlier that each group also ’separates’ two groups. This can be considered an instance of the size 2k − 1 problem. Therefore the set of optimal rankings with g1 as the first group in the rankings is made up of g1 as the first group and a cyclic sweep of the remaining items to fill the remaining positions. Therefore the optimal permutation must be among the sets created by considering each of the 2k + 1 groups as the first group in the rankings. Let Ri,j represent the ranking which has group gi as the first group and the remaining groups present as a cyclic sweep from gj . Consider the case of R1,k. Let xi represent the number of items in group gi. If R1,k is a better ranking than Rk,k+1, it implies that
n+1∑ i=k xi > 2n+1∑ i=n+2 xi (1)
by considering the shift of g1 in the two rankings. The difference in the number of upsets between R1,2 and R1,k is given by
x2(−xk−xk+1 . . .−xn+2 +xn+3 . . . x2n+1) +x3(−xk−xk+1 . . .−xn+3 +xn+4 . . . x2n+1) . . . Using Equation 1, it can be seen that each of the above terms are negative for any j ≤ n+ 1, making R1,2 the better ranking. Any j > n+ 1 cannot be considered as an optimal ranking since the first group as per the ranking must precede the second(otherwise switching them would decrease the upsets). Since either R1,2 or Rk,k+1(both counterclockwise orderings) is better than R1,k whenever k ≤ n+ 1(R1,k cannot be the optimal ranking when k > n+ 1), and since this can be generalised for any Ri,j , it is shown that one of the counterclockwise orderings of the items is the optimal ranking.

heading: A.0.1 FINDING FORBIDDEN CONFIGURATIONS

text:
Given a tournament and a representation dimension, there is no known method to check whether the tournament can be represented by vectors in the given dimension. The forbidden configurations presented above were found by carefully creating an exhaustive set of cases, and showing each one causes a contradiction. The techniques used are presented below.
Proof of Theorem 8
Proof. Consider the representation of tournaments as given in Subsection 3. Since adding minor noise to each hi will not change tournament, we can deal only with cases in which any size 4 subset of h1, h2, ...h12 consists of linearly independent vectors. By using this property, and without loss of generality, c1h1 + c2h2 + c3h3 + c4h4 = h5 (2) We can construct cases based on the signs of the coefficients(ci) in the above equation. There are 24 = 16 sign patterns/cases for any equation. These cases are filtered by multiplying the entire expression with expressions of the form Arothi.
c1h1A rothi + c2h2A rothi + c3h3A rothi + c4h4A rothi = h5A rothi (3)
In the above equation, the signs of all expressions of the form hiArothj is known from the tournament configuration. Therefore simply comparing the sign of the LHS and RHS for all possible values of i rules out many cases.
We now use multiple equations together in a bid to further filter the remaining cases. Consider the following equations without loss of generality.
c1h1 + c2h2 + c3h3 + c4h4 = h5 (4)
b1h2 + b2h3 + b3h4 + b4h5 = h6 (5) a1h1 + a2h2 + a3h3 + a4h4 = h6 (6)
h5 can be eliminated from the first two equations, leaving two expressions of h6 in terms of h1, . . . h4. The two sets of coefficients of h1, . . . h4 can be equated, and sign based arguments can eliminate a few more cases. Also, a set of 3 tuples can be constructed, with each item representing possible sign patterns for the 3 equations. Note that this set of 3 tuples does not contain entries which cannot apply simultaneously on the 3 equations.
The above elimination step can be considered as a filtration procedure given a size 6 tuple (h1, h2, h3, h4, h5, h6) by using 3 equations. We can perform a similar filtration step given any size 6 tuple as well. Let the equations corresponding to (h1, h2, h3, h4, h5, h6) be E1,1, E1,2, E1,3. Similarly, consider the tuples (h1, h2, h3, h4, h5, h7), (h2, h3, h4, h5, h6, h7), (h1, h2, h3, h4, h6, h7) and their corresponding equations represented by Ei,j where i is the index of the tuple it corresponds to and j is the index of the equation. The above filtration process can be performed on all the tuples, following which an additional filtering step can be performed by using
• E1,1 ≡ E2,1
• E1,2 ≡ E3,1
• E1,3 ≡ E4,1
• E2,2 ≡ E3,3
• E2,3 ≡ E4,2
where the equivalence relation represents that the 2 equations are identical. Since identical equations must have identical sign patterns, the sign patterns not present in both sets of possible sign patterns can be filtered out. For the 11-DRT cone, this leaves us with null set, proving that it is a forbidden configuration.

heading: Proof of Theorem 9

text:
Proof. The result follows the arguments in Forster & Simon (2006). We note that the arguments in Forster & Simon (2006) work only for non-zero sign matrices. By overloading T to denote the signed adjacency matrix of the corresponding tournament, we can consider the non-zero sign matrix G = T + diag(b) where b ∈ {1,−1}n. By Gershgorin’s circle theorem and exploting the fact that any two rows of a doubly regular tournament are orthogonal, one can show that ρi(G) 2 ≤ ρi(T)2 + 2n − 2 where ρi denotes the i-th largest singular value of the corresponding
matrix. It then follows from Forster & Simon (2006) that if G has an representation in dim dimensions, then it must be the case that
dim dim∑ i=1 (ρi(G)) 2 ≥ n2.
Noting that for a doubly regular cone T on n nodes, ρi(T).2 = n− 1 ∀i, we get dim2 · 3(n− 1) ≥ n2 => dim ≥ √ n
3 (7)
Thus to get a matrix M such that sign(M) = G, one needs at least √
n 3 dimensions i.e., rank(M) ≥√
n 3 .
Now we show that this also is a lower bound for representing T. To see this, assume for the sake of contradiction that T has a representation in d dimension where d < √ n 3 . Then, there exists H ∈ Rd×n such that T = T[H]. The diagonal entries of T[H] are zero. Now introduce a small enough perturbation E to H and consider the matrix (H + E)TArotH. The entries of the perturbation matrix E ∈ Rd×n can be chosen to be small enough such that the sign of the off-diagonal entries of HTArotH is same as that of (H + E)TArotH. However, the diagonal entries of (H+E)TArotH can get an arbitrary sign pattern, say b. Let G be the sign pattern matrix corresponding to (H + E)TArotH. By definition, G has a representation in dimension d < √ n 3 . But this contradicts inequality (7). Thus, it must be the case that T has a representation in dimension at least √ n 3 .
Finally, setting n = 12d2 to the number of nodes in the doubly regular cone as given in the Theorem, we get that at least 2d dimensions are needed to embed such a tournament. The result follows.

heading: Proof of Theorem 10

text: Proof. The proof is the same arguments as the first part of the proof of Theorem 9.

heading: Proof of Theorem 11

text:
Proof. Given a tournament T, we first show that we can start with an arbitrary transitive tournament and add enough rank 2 corrections to obtain a representation for T. Every addition of a rank 2 matrix will increase the representation dimension by at most 2. The result will follow then by noting that for the choice of the transitive tournament which minimizes the number of corrections needed, one needs at most 2(µ(T) + 1) representation dimension.
Let T′ be an arbitrary transitive tournament which has a 2 dimensional representation and let M ∈ Rn×n be the associated skew symmetric matrix that represents T′. W.l.o.g, assume that Mij > 0 if and only if i < j. Define Ek(T) = {i : i < k, i <T k}. By definition, the feedback arc set Eσ(T) = ∪nk=1(k,Ek(T)) where σ = [1, . . . , n] is the topological order corresponding to the transitive tournament T′. We start with k = n and correct the feedback arc errors arising from Ek iteratively. Define ∆n = √ max i<n
(Min + ) for some small enough > 0. Let u ∈ Rn be such that ui = ∆ ∀i ∈ En and ui = 0 otherwise. Let v ∈ Rn be such that vn = −∆, vi = 0 ∀i 6= n. It is easy to verify that M+uvT −vuT represents a tournament that has the feedback arc set ∪n−1k=1(k,Ek(T)) i.e., the errors in En have been corrected. The cost of correcting the error is adding a rank 2 skew symmetric matrix which increases the representation dimension by at most 2. One can repeat the same procedure for n− 1, n− 2, . . . until all errors are corrected. The upper bound in the theorem follows noting that the above argument works for any transitive tournament T′ and so we can start with the one which has the least number of nodes involved in the feedback arc set to minimize the number of extra dimensions needed to represent T.

heading: Proof of Theorem 12

text: Proof. From Theorem 11, T can be represented using at most 2(µ(T) + 1) dimensions. By construction any representation of T must also represent G. The result follows.

heading: A.0.2 ADDITIONAL FILTRATION FOR VERIFYING 10 NODE FORBIDDEN CONFIGURATION

text:
T =  0 1 1 1 −1 −1 −1 −1 −1 1 −1 0 1 −1 1 1 −1 −1 1 −1 −1 −1 0 1 1 −1 1 −1 −1 −1 −1 1 −1 0 −1 1 1 −1 −1 −1
1 −1 −1 1 0 1 −1 −1 1 −1 1 −1 1 −1 −1 0 1 −1 1 −1 1 1 −1 −1 1 −1 0 −1 1 −1 1 1 1 1 1 1 1 0 1 −1 1 −1 1 1 −1 −1 −1 −1 0 −1 −1 1 1 1 1 1 1 1 1 0  Due to the lesser number of constraints present when dealing with 10 nodes instead of 12, an additional filtration step is required. The entire procedure described above can be considered as an elimination procedure given a tuple T1 = (h1, . . . h7). Also consider that in the final filtration above, a set of size 4 tuples is created. These size 4 tuples will represent the possible sign patterns for E1,1, E1,2, E1,3, E2,2. If a similar procedure is carried out on T2 = (h2, . . . h8), another set of 4 tuples will be generated. The filtration in this step is based on the fact that the equations E1,3, E2, 2 corresponding to T1 are the same as E1,1, E1,2 for T2. The sign patterns which are not present in both sets of tuples are filtered out. This type of relationship can be obtained between T2 and T3 = (h3, . . . h8, h0) as well, and in general between any Ti and Tj such that Tj can be obtained from Ti by removing the first entry and adding an entry to the end. Note that the tuples must have unique entries. Therefore a ’circular elimination’ procedure can be followed, where the Ti tuples considered are size 7 subsets of the circular permutations of h1, . . . h8. By following this procedure, all the sign patterns remaining can be eliminated. Using size 7 circular permutations of h1, . . . h10 in the last step does not eliminate all the cases, we believe this is due to nodes 1 to 8 forming a 7-DRT cone, which leads to many eliminations. The anonymized code for the filtration can be found here.