Symmetry breaking in tournaments

Symmetry Breaking in Tournaments Antoni Lozano Logic and Programming Research Group, Technical University of Catalonia Abstract. We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S⊆V(T) is a determining set for a tournament Tif every nontrivial automorphism of Tmoves at least one vertex of S, while Sis a resolving set for Tif every two distinct vertices in Thave different distances to some vertex in S. We show that the minimum size of a determining set for an order ntournament (its determining number) is bounded by ⌊n/3⌋, while the minimum size of a resolving set for an order nstrong tournament (its metric dimension) is bounded by ⌊n/2⌋. Both bounds are optimal. 1 Introduction The idea of somehow fixing the vertices of a graph in order to destroy all its nontrivial automorphisms has captured the attention of reserchers in recent years, leading to theoretical results for different graph families (trees [9], Kneser graphs [2], digraphs [8], wheels [19], or hypercubes [7]) and to applications in areas such as robotics [14] or chemistry [6]. One can distinguish vertices in a graph by considering their distances to a given subset of fixed vertices: If every two distinct vertices of the graph have different distances to some vertex in the chosen subset, no nontrivial automorphism can be left. In a more nonconstructive approach, one can just fix a given set of vertices so that no nontrivial automorphism is possible in the graph without caring whether it is due to distances or not. The set fixed in the first approach is known as a resolving set [18, 11], while the set fixed in the second one has been called fixing set [10] and determining set [5]. In both cases, it is desirable to find a set of minimum size which “fixes” or “destroys” all nontrivial automorphisms in a graph, making the automorphism group of the resulting structure —say, a labeled graph— trivial. This way, the sizes of the smallest determining and resolving sets for a graph can be seen as two parameters on its degree of symmetry. Still another way that has been considered for fixing the vertices in a graph is by a coloring (called distinguishing coloring [3]) such that the only automorphism which preserves colors is the identity. Again, the problem here is to find a distinguishing coloring where the number of colors is minimized. In order to make reference to this notion, Albertson and Collins [3] introduced the term symmetry breaking, which will be used here to refer to the three preceeding approaches as a whole, while the associated parameters to be minimized will be called symmetry parameters. Tournament graphs have been extensively studied (for classical references, see [12, 15]). Some of their well-known properties (for example, the fact that their automorphism groups have odd order and, hence, are solvable) may help to get stronger conclusions on symmetry breaking in tournaments than in general directed graphs. In this paper, we consider determining and resolving sets for tournaments and prove the existence of optimal upper bounds for their minimum sizes amounting to constant fractions of their order: 1 3for determining sets, and 1 2for resolving sets of strong tournaments. 1.1 Tournaments If Dis a directed graph (digraph for short) V(D) and A(D) will denote the vertex set and the arc set of D. Given two distinct vertices u,vof D, we will write u∈Dinstead of u∈V(D) and uv ∈A(D) rather than (u, v)∈A(D). The notation dD(x, y) (or just d(u, v) when Dis understood) stands for the directed distance from uto vin D, that is, the length of the shortest directed path from uto vin D. A tournament models the outcome of a competition where every player plays against each other in a 2-player match. Formally, a digraph Tis a tournament if between every pair of distinct vertices u, v ∈T, we have uv ∈T or vu ∈Tbut not both. For any tournament T, define the following subsets of its vertices for any u, v ∈T: –Tu→={w∈T|uw ∈T} –T→u={w∈T|wu ∈T} –Tuv→=Tu→∩Tv→ –Tu→j=Tu→∩T→v –T→uv =T→u∩T→v The indegree of a vertex uis |T→u|while its outdegree is |Tu→|. A tournament Tis regular if the indegree (and, consequently, the outdegree) of all vertices is the same. In the case of a regular tournament Tof order 2n+ 1, it is easy to see that |Tu→|=|T→u|=nfor every vertex u∈T. A tournament Tis transitive if its vertices can be numbered from 1 up to nin such a way that every arc ij in Tsatisfies i < j. Therefore, there is a unique transitive tournament of order nup to isomophism, which is denoted by TTn. Since the existence of a directed 3-cycle —which we will denote by C3— contradicts the condition in the definition of TTn, a characterization of transitive tournaments, then, is precisely that they do not contain the subtournament C3. An almost transitive tournament of order n≥3, denoted by TT∗ n, is a tournament that differs from TTnin the fact that it contains the arc n1 instead of 1n, while the rest of the arcs remain unchanged. 2 A tournament is strong if all directed distances between vertices are defined. It is obvious that while T Tnis not strong, T T ∗ nis a strong tournament. 1.2 Symmetry Parameters Given a digraph D, we denote by Γ(D) the automorphism group of Dand by S1the trivial group. We note the well-known fact that every automorphism in Γ(D) is an isometry, that is, for any u, v ∈Dand φ∈Γ(D), d(u, v) = d(φ(u), φ(v)). We say that an automorphism φfixes a vertex uif φ(u) = uand that it fixes a set S⊆V(D) if it fixes every u∈S. The set of automorphisms of Dthat fix the set Sis a subgroup of Γ(D) called pointwise stabilizer of Sin D, and we denote it by StabΓ(D)(S) (or just Stab(S) when Dis understood). Given a vertex uof D, the set OD(u) = {φ(u)|φ∈Γ(D)}is called the orbit of uin D. Orbits of Dinduce a partition in the set of vertices. Note that no automorphism can move a vertex from an orbit to another. Definition 1. A set S⊆V(D)for which StabΓ(D)(S) = S1is called a determining set of D, and the minimum cardinality of a determining set for D, denoted by Det(D), is called determining number of D. A digraph with no nontrivial automorphisms is called rigid. Determining sets (also known as fixing sets) have been introduced independently by Harary [10] and Boutin [5]. As a simple example, a determining set for C3is any set containing one vertex, while the empty set is a determining set for TTk, for any k, since any transitive tournament is rigid. Also note that any set with n−2 vertices of a tournament of order nis a determining set, since no automorphism can exchange the remaining two vertices (tournaments do not have involutions). In a different approach introduced separately by Harary and Melter [11], and by Slater [18], the vertices in a graph can be distinguished according to their distances to a given subset of vertices. Definition 2. We say that a vertex uof a digraph Dresolves a pair of vertices v, w ∈Dif d(v, u)6=d(w, u). We also say that S⊆V(D)is a resolving set for Dif every pair of vertices in Dcan be resolved by some vertex in S. The minimum size of a resolving set for Dis referred to as the metric dimension of D, and is denoted by Dim(D). While the metric dimension of a digraph does not need to be defined, the situation in the case of tournaments is different. We would like to stress the fact that Definition 2 does not require all directed distances to be defined (not even the directed distances to all vertices in the resolving set), but only the distances to the vertices which resolve each pair of distinct vertices. 3 Proposition 1. For any order ntournament T,Dim(T)≤n−1. Proof. It is well known that every tournament has a Hamiltonian path [17]. Suppose, then, that u1. . . unis a Hamiltonian path for a tournament T. Then, given two vertices ui, ujsuch that i < j, they can be resolved by uj since d(ui, uj)> d(uj, uj) = 0. Therefore, {u2,...,un}is a resolving set. ⊓⊔ We observe that the upper bound of Proposition 1 is best possible for general tournaments. Proposition 2. For every integer n,Dim(TTn) = n−1. Proof. Let V(TTn) = {1,...,n}be the numbering of the vertices from the definition of TTngiven in Subsection 1.1 (that is, every arc ij satisfies i < j), and let Sbe a determining set for TTn. Then, given two vertices i, j such that i < j, we have that –vertex jresolves the pair since d(i, j) = 1 and d(j, j) = 0, –no vertex k < j can resolve it since distance d(j, k) is undefined, and –no vertex k > j can resolve it neither since d(i, k) = d(j, k) = 1. We conclude that jis the only vertex which resolves a pair i, j such that i < j, and then, must belong to S. Therefore, the only vertex that can be left out of Sis 1, and we have Dim(TTn)≥n−1. On the other hand, Dim(TTn)≤n−1 by Proposition 1, and the result is proved. ⊓⊔ To establish the relation between resolving and determining sets, we just follow the proof by Erwin and Harary ([9], Lemma 2), which can be applied without changes to digraphs and we reproduce here for completeness. Proposition 3. Every resolving set for a digraph is also a determining set. Therefore, for any digraph D,Det(D)≤Dim(D). Proof. Let Sbe a resolving set for a digraph D. To get a contradiction, suppose that Sis not a determining set for Dand, then, Stab(S)6=S1. In this case, there must be a vertex vand an automorphism φ∈Stab(S) such that v6=φ(v). Since Sis a resolving set for D, there must be a vertex u∈S for which d(v, u)6=d(φ(v), u). However, d(v, u) = d(φ(v), φ(u)) = d(φ(v), u) where the first equality holds because φis an isometry, and the second one because φfixes u, and we have a contradiction. ⊓⊔ 4 1.3 Outline In Section 2, we prove that the determining number of every tournament of order nis tightly bounded by ⌊n/3⌋. Section 3 is devoted to the metric dimension. We derive a tight upper bound of ⌊n/2⌋in the case of strong tournaments of order n(as we have just seen, there is no constant fraction upper bound in the general case). In order to prove this bound, we first answer a conjecture posed by Kannan, Naor, and Rudich on their concept of anchor ([13]), and link it to the metric dimension. We also show in Section 3 that resolving sets and anchors are exactly the same concept in regular tournaments. Finally, in the light of our results, we remind in Section 4 a conjecture posed by Albertson and Collins ([4]) on the distinguishing number of tournaments. 2 The Determining Number The determining number is 0, for exemple, for the transitive tournament of kvertices, TTk, (in fact, for any rigid tournament) but how large can it be for a general tournament? Define T Tk(T) as T Tkwhere each vertex has been substituted by a copy of T. Proposition 4. For every n > 0, there is an order ntournament Tnsuch that Det(Tn) = ⌊n/3⌋. Proof. If n= 3kfor some integer k, we take Tn=T Tk(C3). Consider any set S⊆V(Tn) containing exactly one vertex from each copy of C3in Tn. Since no vertex can be moved by an automorphism between different copies of C3, and every nontrivial automorphism of one of the copies must move all three vertices, we have that Stab(S) = S1, and Sis a determining set for Tn with |S|=k. Observe that any set of cardinality smaller than kwould fail to contain some vertex from one of the copies of C3, and that would make it possible to rotate C3while fixing the rest of the vertices in Tn. If n≡dmodulo 3 with d= 1 or d= 2, we take Tnas the tournament Tn−ddefined above plus dnew vertices pointing to all vertices in Tn−d. Since the new vertices must be fixed in any nontrivial automorphism of Tn, Det(Tn) = Det(Tn−d) = (n−d)/3 = ⌊n/3⌋.⊓⊔ Now we will see that there is always a determining set with at most ⌊n/3⌋vertices for an norder tournament. In the proof, we exploit the fact that an automorphism cannot move vertices between different orbits and, then, in order to construct a determining set for T, it is enough to construct determining sets for the subtournaments induced by the orbits, and then 5 merge them. We will need the following proposition for digraphs, which is the direct translation of a similar one stated in [5] for graphs and does not require a separate proof. Proposition 5. Let O1,...,Okbe the vertex orbits of a digraph D. Let H1,...,Hkbe the associated induced subtournaments. Let S1,...Skbe determining sets for H1,...,Hk. Then, S=S1∪ · · · ∪ Skis a determining set for D. Now, we can state the main theorem of this section. Theorem 1. For every order ntournament T,Det(T)≤ ⌊n/3⌋. Proof. Given a tournament Tof order n, we will show that the subtournament T[O] induced by an orbit Oof Thas a determining set SOof size at most ⌊|O|/3⌋. Therefore, the union of all determining sets for the different orbits S=SOis an orbit of TSOwill satisfy that |S| ≤ ⌊n/3⌋while, by Proposition 5, Sis a determining set for T. Thus, it is enough to prove the statement separetely for each orbit. Suppose then that Ois an orbit of T, and that |O| =m. Let H=T[O] be the subtournament of Tinduced by O. The fact that Ois an orbit implies that Hmust be vertex transitive (there exists φ∈Γ(H) such that φ(u) = v for any u, v ∈H) and, hence, regular. We will proceed by induction on m. For m≤2, the determining set can be empty since there is no nontrivial automorphism. For the inductive step, we will suppose that m≥3, but note that in the case m= 3, the only tournaments are T T3(which is already rigid) and C3(which can be made rigid by fixing one vertex). Now, for m≥3, we consider three cases depending on the remainder of mwhen dividing by 3. All congruencies in the rest of the proof are taken modulo 3. Case 1: m≡0. Let ube any vertex in H. Since His regular, |H→u|=|Hu→|, which together with the fact that |H→u|+|Hu→|+ 1 = m≡0 leaves the only possibility that |H→u|=|Hu→| ≡ 1. Therefore, there exists an integer rsuch that |H→u|=|Hu→|= 3r+ 1. By induction hypothesis, both H→uand Hu→have determining sets of size r. Their union plus vertex uform a determining set for Hof size 2r+ 1. Since |H|=m= 2(3r+ 1) + 1 = 6r+ 3, the determining set has at most (in this case, exactly) ⌊m/3⌋vertices as expected. Case 2: m≡2. Let ube any vertex in H. As in the previous case, |H→u|=|Hu→|, which now implies that |H→u|=|Hu→| ≡ 2. Therefore, there exists an integer r 6 such that |H→u|=|Hu→|= 3r+ 2. By induction hypothesis, both H→u and Hu→have determining sets of size r. Their union plus vertex uform a determining set for Hof size 2r+ 1. Since |H|=m= 2(3r+ 2) + 1 = 6r+ 5, the determining set has at most (in this case, less than) ⌊m/3⌋vertices. Case 3: m≡1. In this case, for any u∈H,|H→u|=|Hu→| ≡ 0. A determining set for Hconstructed inductively as in the previous cases would have more than ⌊m/3⌋vertices. However, we can complete the proof using two subcases: –Subcase 3.1: For every arc uv ∈H,|Hu→v| ≡ 2. Since we are assuming that m≥3, let u, v, w be three vertices in H. Moreover, we can select them in such a way that uv,vw, and wu are in H, the reason being that Hcannot be transitive in this subcase and, therefore, it must contain a 3-cycle. Now, Hcan be split into the following subsets: •Hu→v,Hv→w, and Hw→u, whose cardinalities are all congruent with 2 modulo 3. Let |Hu→v|= 3r+2, |Hv→w|= 3s+2, and |Hw→u|= 3t+2 for some r, s, t ≥0, •the set {u, v, w}, and •the remaining vertices in H, say H′. Note that since m≡1 and the number of vertices counted so far is multiple of 3, |H′| ≡ 1, say |H′|= 3z+ 1 for some z. u vw Hvw HwuHuv Fig. 1. Subcase 3.1: |Hu→v| ≡ |Hv→w| ≡ |Hw→u| ≡ 2. Summing up the previous numbers, we have: m=|Hu→v|+|Hv→w|+|Hw→u|+|{u, v, w}| +|H′|= 7 = (3r+ 2) + (3s+ 2) + (3t+ 2) + 3 + (3z+ 1) = = 3(r+s+t+z) + 10. On the other hand, we can assume the existence of determining sets for Hu→v,Hv→w,Hw→u, and H′by induction hypothesis, of sizes r,s,t, and z, respectively. Their union plus the vertices u,v, and wis a determining set for Hwith less than ⌊m/3⌋vertices. –Subcase 3.2: There is an arc uv ∈Hfor which |Hu→v| 6≡ 2. Let u, v be two such vertices. Now, we consider the partition of Hinto the sets: Hu→v,H→uv,Hv→u,Huv→, and {u, v}. Using the assumption (of Case 3) that for any w∈H,|H→w|=|Hw→| ≡ 0, we can observe the following: i. |Hu→v∪H→uv| ≡ 2, since the previous union plus vis exactly H→v. ii. |H→uv ∪Hv→u| ≡ 0, since the previous union is exactly Hv→. iii. |Hv→u∪Huv→| ≡ 2, since the previous union plus vis exactly Hu→. Hu–›v Huv–› Hv–›u H–›uv uv 2 Fig. 2. Subcase 3.2: For some arc uv ∈H,|Hu→v| 6≡ 2. Now, we can see that there are only two possibilities: • |Hu→v| ≡ 1. Then, by i, |H→uv| ≡ 1; by ii, |Hv→u| ≡ 2; and by iii, |Huv→| ≡ 1. There must be some r, s, t, z in this case such that |Hu→v|= 3r+ 1, |H→uv|= 3s+ 1, |Hv→u|= 3t+ 2, and |Huv→|= 3z+ 1. • |Hu→v| ≡ 0. Then, by i, |H→uv| ≡ 2; by ii, |Hv→u| ≡ 1; and by iii, |Huv→| ≡ 2. There must be som r, s, t, z in this case such that |Hu→v|= 3r,|H→uv|= 3s+2, |Hv→u|= 3t+1, and |Huv→|= 3z+2. In any of the above two possibilities, Hcontains the four previous subsets plus uand v, giving |H|= 3(r+s+t+z)+7. The union of the determining 8 sets given by the induction hypothesis plus uand vgives a determining set for Hof size r+s+t+z+ 2, which is less than ⌊m/3⌋.⊓⊔ Note that the upper bound ⌊n/3⌋given in Theorem 1 is tight by Proposition 4. 3 The Metric Dimension As we have seen in Section 1, if we do not consider any additional condition on a tournament of order n, its metric dimension can be as large as n−1. In this section, we show that just requiring a tournament to be strong, its metric dimension drops to at most ⌊n/2⌋. We start with an example of a strong tournament having a large metric dimension, and we will see later that it is indeed the largest possible for any strong tournament. Proposition 6. For every n > 2,Dim(TT∗ n) = ⌊n/2⌋. Proof. Let V(TT ∗ n) = {1,...,n}be the numbering of the vertices from the definition of TT∗ n(that is, ij ∈Timplies i < j except for the case of the arc n1, which belongs to TT∗ n). Note that the even (odd) numbered vertices constitute a resolving set of size ⌊n/2⌋since every pair of odd (even) numbered vertices are distinguished by some even (odd) numbered vertex. This shows that Dim(TT ∗ n)≤ ⌊n/2⌋. To see why Dim(TT∗ n)≥ ⌊n/2⌋, we observe in the first place that it cannot happen that two vertices i, i+1 in the range 1 < i < i+1 < n do not belong to the resolving set, for no other vertex can resolve them. Moreover, if one of the vertices 2 or n−1 is not in the resolving set, then either 1 or nmust be in. Both conditions imply that the resolving set must contain at least ⌊n/2⌋vertices. ⊓⊔ Kannan, Naor, and Rudich [13] introduced the notion of anchors for tournaments in order to get a simple algorithm for tournament isomorphism. Anchors can be seen as a sort of simplification of resolving sets having the advantage that they are always defined. An anchor in a tournament Tis a subset S⊆V(T) such that for all vertices u, v ∈V(T)−S,u6=v, there exists a vertex w∈Ssuch that exactly one of uw and vw is an arc of T, in which case we say that w distinguishes the pair u, v. Thus, if the vertices in an anchor are fixed, all vertices in the tournament would be fixed and no automorphism other than the identity would be possible; in this respect, the concept is similar to the other symmetry breaking concepts seen so far. Let Anchor(T) denote the size of the smallest anchor for T. 9