Oleg Pikhurko1
Department of Mathematical Sciences Carnegie Mellon University
Pittsburgh, PA 15213-3890
http://www.math.cmu.edu/˜pikhurko/
Received: 10/25/02, Revised: 10/24/03, Accepted: 12/3/03, Published: 12/4/03
Abstract
Players A and B alternatively colour edges of a graph G, red and blue respectively. Let Lsym(G) be the largest number of moves during which B can keep the red and blue subgraphs isomorphic, no matter howA plays.
This function was introduced by Harary, Slany and Verbitsky who in particular showed that for complete bipartite graphs we have Lsym(Km,n) = mn2 if mn is even and that Lsym(K2m+1,2n+1)≥max(m, n). Here we prove that
Lsym(K2m+1,2n+1) =O(n), if m≤n≤mO(1), answering a question posed by Harary, Slany and Verbitsky.
1. Introduction
LetGbe a graph. The followingsymmetry breaking-preserving gameonGwas introduced by Harary, Slany and Verbitsky [1, 2]. We have two players,A and B, who alternatively select a previously uncoloured edge of G and colour it red and blue respectively. Player A starts the game. A move of A followed by a move of B is called a round. Clearly, we have the same number of red and blue edges after every round. The aim of Player B is to keep the red and blue subgraphs isomorphic after every round of the game; as soon as B fails to do so, he loses.
LetLsym(G) be the maximum number of moves during which Bcan keep the red and blue subgraphs isomorphic, no matter howAplays. Equivalently (see [2, Proposition 2.1])
1This research was carried out when the author was supported by a Research Fellowship, St. John’s College, Cambridge, UK.
Lsym(G) is the smallest k such thatA can guarantee his win in at mostk+ 1 moves. It is not quite clear how to define Lsym(G) in the cases when B can preserve the symmetry until the players run out of edges; following [2] we define Lsym(G) =be(G)/2c then.
One of the motivations of Harary, Slany and Verbitsky for introducing these notions was that Lsym(G) is clearly a lower bound on how long the second player can survive in any graph avoidance game on G. (The rules of the avoidance game are the same except that the player who first constructs a monochromatic copy of a certain forbidden subgraph loses.)
As it is observed in [1], if Ghas an involutary automorphism ψ without fixed edges, then Lsym(G) = e(G)/2. Indeed, every orbit of the induced action ψ∗ on E(G) consists of two edges, so B can use the copycat strategy of choosingψ∗(e)∈E(G) where e is the edge previously coloured by A.
The determination of Lsym(G) is suddenly getting rather complicated and deep when we consider graphs which do not admit a copycat strategy but for which this cannot be derived by looking at a part of the graph. For example, when one considers the path Pn with n vertices, one has to know (the parity of) its ordern in order to ascertain the existence of an appropriate automorphism ψ. So, if A follows some ‘local’ strategy, B might put up a strong resistance by playing copycat on a few separate parts of the graph.
The surprising (at least to me) result of Harary, Slany and Verbitsky [2, Corollary 3.7 &
Proposition 3.8] states that
(0.5 +o(1)) log2n ≤Lsym(P2n)≤(3.5 +o(1)) (log2n)2.
Its proof exploits some beautiful connections to the so-called Ehrenfeucht-Fra¨ıss´e game.
Complete bipartite graphs of even size clearly admit a copycat strategy. The following argument from [2] shows that
Lsym(Km,n)≥max(m2−1,n−21), for oddmn. (1) Indeed, let X ⊂V(Km,n) be the bigger part ofKm,n. Starting with ψ being the identity automorphism,Buses theψ-copycat strategy, that is, responds withψ∗(e) to the previous move e. This works unless ψ∗(e) = e in which case B locally modifies ψ so that it exchanges x and y now, where {x} = X∩e and y ∈ X is a vertex not incident to any coloured edge. Such y always exists during the first (|X| −1)/2 rounds during which ψ remains an involutary automorphism of Km,n swapping the blue and red subgraphs.
Harary, Slany and Verbitsky [2, Question 4.3] asked for the rate of growth of the functionLsym(Kn,n) for oddn. The following more general result implies thatLsym(Km,n) grows linearly in n if m≤n ≤mO(1) and mn is odd.
Theorem 1 Let odd integers m and n and an integer k ≥8 satisfy 51≤m ≤n ≤ (m−2k−3)k
(k+ 1)!m . (2)
Then we have
Lsym(Km,n)≤k(n−m+ 3) + 2m+ 14. (3) In particular, if m=n, then letting k = 8 we obtain
Lsym(Kn,n)≤2n+ 38, for odd n≥51. (4) In Section 3 we present the bound (3) as a more digestible, explicit function ofm and n.
Let us describe the main idea behind the proof of Theorem 1. In outline,Abuilds a red graph which has no non-trivial automorphism. IfB has not lost yet, the isomorphism ψ between the red and blue graphs is unique andBisforced to play theψ∗-copycat strategy now. As the total number of edges is odd, ψ∗ has at least one odd orbit D ⊂E(G). No matter how D has been coloured, Player A can beat the ψ∗-copycat strategy onD with at most two moves. So, if ψ remains the unique isomorphism during these two moves of A, then B loses.
This method might be applicable to many graphs with odd size. Here is its concrete realisation for complete bipartite graphs.
2. Proof of Theorem 1
We will describe the appropriate strategy of A which consists of a few phases. Assume that B keeps the red and blue subgraphs isomorphic throughout our strategy.
Let V ∪V0 =V(Km,n) be the vertex classes, where|V|=m.
Phase 1. A builds a red cycle of length 2l ∈ [2m−6,2m−2], say visiting vertices x1, x01, . . . , xl, x0l in this order, plus one edge from some vertex y0 ∈ Y to X0, where we denote X={x1, . . . , xl} ⊂V, X0 ={x01, . . . , x0l} ⊂V0, Y =V \X, and Y0 =V0 \X0.
The red/blue subgraph will have maximum degree at most 2 at any moment before the end of Phase 1, so in particular A can easily create a red path of length 2m−7 by choosing vertices x1, x01, . . . , xm−3, x0m−3 one by one in this order. If the edge {x1, x0m−3} is available, then A colours it and we are done because the addition of an edge between X0 and Y is always possible as m − 3 > 2. Otherwise, A extends the path by two more edges. Now, if {x1, x0m−2} is available, then A selects it and we are done again.
Otherwise,Acan addxm−1 to the path: indeed, the vertexx0m−2 sends a blue edge tox1, so it sends at most one blue edge to V \X. If {xm−1, x01} is available, then A selects it, obtaining the desired configuration (up to relabelling). Otherwise, the edge{xm−1, x01}is blue andAcan extend the path tox0m−1. In the next moveAcolours the edge{x1, x0m−1} which cannot be blue because we have already encountered two blue edges incident to
x1. Finally, A connects some y0 ∈ Y to X0, obtaining the desired configuration in all cases.
Phase 2. A connects Y to X0.
The vertex y0 ∈ Y will play a special role. Assume that x01 is the vertex in X0 connected toy0 by a red edge.
Consider first the case when y0 is incident to at least one blue edge. By reversing, if necessary, the direction of the red 2l-cycle, we can assume that y0 has at least one blue neighbour outside {x01, . . . , x010}. In the next five moves A colours {y0, x0i} for the smallest possible index i ≥ 2 each time. Suppose that the last such edge was {y0, x0s}. When Awas colouring it, at most 5 edges incident toy0 were blue of which at most 4 lie inX00 ={x01, . . . , x0s}. Hence s≤10.
In the next three movesAcolours{y0, x0i}, whereiis the smallest available index with i≥2s except, when colouring the third edge in the case s = 6, the additional condition oni is that the indexes of the last three red neighbours of y0 do not form an arithmetic progression. (Note that for s ≥ 7 the indexes of the first six neighbours of y0 cannot form a six-term arithmetic progression as s≤10.)
Let t > 2s be the largest index of a red neighbour of y0 and let X10 = {x02s, . . . , x0t}. We claim that t≤26. Ifs ≥7, theny0 sends at most 8−(s−6) = 14−s blue edges to X10 because y0 sends s−6 blue edges to X00; thus
t−2s+ 1 =|X10| ≤3 + (14−s), (5) which gives the required in view of s ≤ 10. If s = 6, then we have to add 1 to the bound (5), still obtaining the claimed inequality t≤26.
If y0 is not incident to a blue edge at the end of Phase 1, then this stays so, in whichever manner we add red edges incident to y0. In particular,A can connecty0 to
{x01, x02, . . . , x06, x012, x013, x015} and we haves = 6 andt= 15.
Next, A connects the vertices of Y \ {y0} to X0, by five edges each, so that distinct vertices ofY have disjoint neighbourhoods inX0, which is possible asl >2·9+5·(|Y|−1).
The first two phases last for r2 = 2l+ 9 + 5(m−l−1) rounds.
Phase 3. If m = n =l+ 1, then A connects the (unique) vertex of Y0 to arbitrary 12 vertices of X. Otherwise, A picks vertices of Y0 one by one and connects each selected vertex by k edges to X. Suppose that A has already dealt with y10, . . . , yi0 ∈ Y0 and connected the next vertexy0 ∈Y0 to a setH ⊂X of sizeh∈[0, k−1]. Let Γred(y) (resp.
Γblue(y)) denotes the red (resp. blue) neighbourhood of a vertex y.
We claim that f, the number of vertices in F = Γblue(y0)∩X, will be at mostk+ 1 when we deal with the vertex y0. This is true for i ≤ 3 when the maximum degree of the blue graph is at most max(k,9). Ifi≥4, then the isomorphism between the red and blue graphs must respect the classes V and V0 because the non-trivial red component has at least l+i >|V| vertices in V0. So the blue degree of y0 is at most the maximum red degree of a vertex in V0 which is k, giving the desired bound on f.
Here is the strategy: A connectsy0 to a vertex x∈X\(F∪H) such thatµ(H∪ {x}) is minimum, where
µ(Z) =
Xi
j=1
c|Z\Γred(y0j)|, Z ⊂X,
where c0 =l,c1 = 1, and all otherc’s are zero. In other words, µ(Z) = l ¯¯¯n
j ∈[i]|Z ⊂Γred(yj0)o¯¯¯+¯¯¯n
j ∈[i]| |Z\Γred(y0j)|= 1o¯¯¯. It is easy to see that
X
x∈X\(F∪H)
µ(H∪ {x}) ≤ X
j∈[i]
H⊂Γred(y0 j)
(c0(k−h) +c1(l−k))
+ X
j∈[i]
|H\Γred(y0 j)|=1
c1(k−h+ 1) ≤ (k−h+ 1)µ(H),
by straightforwardly comparing the corresponding terms. Hence, A can choose an x ∈ X\(F ∪H) such that
µ(H∪ {x})≤ k−h+ 1
l−f −h µ(H)≤ k−h+ 1
m−2k−3µ(H).
As µ(∅) = li < mn, the inequality
µ(H)< (k+ 1)!
(m−2k−3)kmn≤1
holds when we reach the case |H|= k. As µ is integer-valued, it must be the case that µ(H) = 0, which means by the definition that |H\Γred(y0j)| ≥2 for any j ∈[i]. Thus A can ensure that the hamming distance between any two sets in {Γred(y0)|y0 ∈Y0} is at least 4 at the end of Phase 3.
The first three phases tookr3 =r2+ 12 rounds ifn =m =l+ 1 andr3 =r2+k(n−l) rounds otherwise.
Phase 4. A adds at most two more edges and wins.
This phase needs some analysis before we can specify the moves of A. Let Ai (resp.
Bi) consist of red (resp. blue) edges after i rounds, viewed as a subset ofE(Km,n). Thus
A=Ar3 is the red graph at the end of Phase 3. Note thatX∪X0 spans inA an induced 2l-cycle which we denote by C ⊂A.
Claim 1. Let A0 be obtained by adding to A at most two edges of the encompassing graph Km,n. Let φ : V(Km,n) → V(Km,n) be a bijection such that φ∗(A) ⊂ A0, where φ∗ denotes the induced action on 2-point sets. Thenφ(y0) = y0, φ(Y) =Y, φ(X) =X, φ(Y0) = Y0 and φ(X0) =X0.
If, furthermore, φ∗(C) =C, then φ is the identity map.
Proof. As A, A0 are connected bipartite graphs, we have φ(V) =V or φ(V) =V0.
Let us show first that φ(V) = V, which needs justification when |V| = |V0|. If
|Y0|= 1, then the (unique) vertex of Y0 of degree at least 12 must be preserved by φ as any other vertex has A0-degree at most 11; thus φ(V) = V, as required. Suppose that
|Y0|=|Y| ≥2. The vertices inX are incident to at most 4 +|Y0| ≤7< k A0-edges each.
ThusV contains at most one vertex of A0-degree at least k and φ must map Y0 into V0. Now it follows that φ(V) =V and φ(V0) =V0.
As each vertex of Y0 has degree at least 8 while the A0-degrees in X0 are all at most 5, we conclude that φ(Y0) = Y0. As each vertex of φ(Y) sends at least five edges to φ(X0) = X0, we have φ(Y) = Y. Similarly, φ(y0) =y0, which proves the first part of the claim.
Suppose furthermore thatφ∗(C) = C. This means that the restriction ofφ toX∪X0 is a cyclic rotation, possibly composed with the reflection xi 7→ x0l−i+1, x0i 7→xl−i+1. We are going to show that φ|X∪X0 is the identity by considering the neighbourhood of y0.
Recall that the set X00 = {x01, . . . , x0s} contains six A-neighbours of y0 and X10 = {x02s, . . . , x0t} the remaining three. The sets X00 and X10 cannot both intersect φ(X00) as they are separated by s−1 other vertices of X0. Hence,φ(X00)∩X10 =∅and φ(X00)∩X00 contains at least four A-neighbours of y0. If φ(X10) is situated at the ‘wrong’ side of φ(X00), then (as l ≥ 2t−4) we have φ(X10)∩X10 = ∅ and at least three A0-neighbours of y0 fall outside φ(X00 ∪X10), a contradiction. Thus φ|X∪X0 is a cycle rotation (without any reflection). Moreover, it is the identity rotation for otherwise we obtain the contra- diction |φ(Γred(y0))\Γred(y0)| ≥ 3. (The latter inequality holds because in Phase 2 we excluded the possibility that the indexes of the red neighbours ofy0 form two arithmetic progressions.)
Now, for any two vertices ofY ∪Y0 the hamming distance between theirA-neighbour- hoods is at least 4. This clearly implies that φ is the identity bijection.
Claim 1 implies in particular that A has no non-trivial automorphism. Thusψ =ψr3
is uniquely determined, where ψr denotes the red-blue isomorphism after r rounds. The bipartition V ∪V0 is clearly preserved (or reversed) by ψ so we have the induced action ψ∗ onE(Km,n).
Claim 2. For any (r3+ 1)st move e of A, the player B is forced to reply with ψ∗(e).
Proof. By Claim 1 any bijection φ with φ∗(A) ⊂ Ar3+1 preserves X ∪X0. As X ∪X0 induces in Ar3+1 a cycle with at most one chord added, we have φ∗(C) = C and, again by Claim 1, φ is the identity map. This means that A is the only subgraph of Ar3+1
isomorphic toAand the analogous claim holds for the blue edges. Thusψ∗r3+1(A) =Br3, which implies that ψr3+1 = ψ. Now, ψ∗ must map {e}= Ar3+1\A into Br3+1 \Br3, as required.
As the total number of edges mn is odd, some ψ∗-orbit D ⊂ E(Km,n) has the odd number of elements.
If at least one element ofDis already coloured, then we can find via a parity argument an uncolourede∈Dsuch thatψ∗(e) is red. Now,Acoloursered andBloses by Claim 2.
Suppose that no edge of D has been coloured. If D = {e}, then ψ∗(e) = e and A wins by choosing e by Claim 2. Suppose that |D| > 1 and let e ∈ D. Now e0 = ψ∗(e) and e00 = (ψ∗)−1(e) are two distinct edges belonging to D.
Suppose first thate={xi, x0j}and that bothC∪{e, e0}andC∪{e, e00}have a 2l-cycle passing through the edge e. Trivial considerations show that
{e0, e00}=n{xj, x0i−1}, {xj+1, x0i}o. (6) (Of course, we do all index calculations modulo l.) If ψ(V) = V, then (6) means that for some δ =±1 we have ψδ(xi) =xj+1, ψδ(x0j) = x0i, ψ−δ(xi) =xj and ψ−δ(x0j) = x0i−1. But then ψδ maps the red edge {xj, x0j} into the red edge {xi, x0i}, a contradiction. In the same way we obtain a contradiction in the case ψ(V) =V0.
Thus, by the first part of Claim 1, we can assume that we can recoverCfrom knowing, for example, A∪ {e, e0}. Now, A selects e0 to which, by Claim 2, B is forced to reply by colouring ψ∗(e0). Then A selects e 6= ψ∗(e0). Claim 1 implies that A is the unique subgraph ofA∪ {e, e0}isomorphic toAand the argument of Claim 2 shows thatB loses.
Let us count the total number r4 of rounds. If n=m=l+ 1, then r4 ≤2(m−1) + 9 + 12 + 2≤3(n−m+k) + 2m+ 15, as k≥8. Otherwise,
r4 ≤2l+ 9 + 5(m−l−1) +k(n−l) + 2≤k(n−m+ 3) + 2m+ 15,
where we used the inequality l ≥ m − 3. This finishes the proof of Theorem 1 as Lsym(Km,n)≤r4−1.
3. Concluding Remarks
It is not hard to convert our strategy into an algorithm which has running time O(mn) per one move of A.
Unfortunately, not for every pair (m, n) an integerk satisfying (2) can be found. For example, ifn >2m, then any subgraph ofKm,n contains two vertices inV0 with the same neighbourhood inV, which ruins our strategy. The value ofn can range up to
maxk≥8
(m−2k−3)k
(k+ 1)!m = (1.531...+o(1))m.
The optimal choice is to take the smallest integerk ≥8 satisfying (2). Ifm is large, then the following formulae can be routinely verified. If logn/logm <7−o(1), then k = 8.
If 7−o(1)≤logn/logm=O(1), then logn
logm + 1< k < logn logm + 3.
If O(logm)<logn =o(m), then
k = (1 +o(1)) logn
logm−log logn.
If (1 +o(1))m < n <(1.531...+o(1))m, then k = (x0+o(1))m, wherex0 is the smallest positive root of equation
((1−2x)e/x)x = elogn/m.
The present best known bounds on Lsym(Kn,n) for odd n are given by (1) and (4).
Unfortunately, it seems that a minor modification of our method cannot give any con- siderable improvement on (4) as any graph H with no non-trivial automorphism has at least (1−o(1))v(H) edges. Indeed, if we fix some large constant C, then H has O(1) components with less thanC vertices (as no two can be isomorphic), while the remaining components span at least (v(H)−O(1))c−c1 edges. Also, one meets difficulties when try- ing to improve on (1): it is not hard to see thatAcan ensure that within first n+12 rounds there was a position when no blue-red isomorphism could be generated by an involutary automorphism ofKn,n. Hence,Bmust go beyond copycat if he wants to survive for more than (12 +o(1))n rounds.
In fact, we do not even have any solid conjecture what the value of
nlim→∞
Lsym(K2n+1,2n+1) n
is (if the limit exists).
Acknowledgements
I wish to thank Oleg Verbitsky for drawing my attention to this problem and for his helpful comments.
References
[1] F. Harary, W. Slany, and O. Verbitsky. A symmetric strategy in graph avoidance games. In R. J. Nowakowski, editor, More Games of No Chance, pages 369–381.
Cambridge Univ. Press, 2002.
[2] F. Harary, W. Slany, and O. Verbitsky. On the lengths of symmetry breaking- preserving games on graphs. To appear in Theoretical Computer Science.
