BREAKING SYMMETRY ON COMPLETE BIPARTITE GRAPHS OF ODD SIZE

Oleg Pikhurko^{1}

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 L_{sym}(G) be the largest number of moves during which B can keep the red and blue subgraphs isomorphic, no matter how A plays.

This function was introduced by Harary, Slany and Verbitsky who in particular showed that for complete bipartite graphs we have L_{sym}(K_{m,n}) = \frac{mn}{2} if mn is even and that L_{sym}(K_{2m+1,2n+1}) ≥ max(m, n). Here we prove that

L_{sym}(K_{2m+1,2n+1}) = O(n), if m ≤ n ≤ m^{O(1)},

answering a question posed by Harary, Slany and Verbitsky.

1. Introduction

Let G be a graph. The following symmetry breaking-preserving game on G was 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.

Let L_{sym}(G) be the maximum number of moves during which B can keep the red and blue subgraphs isomorphic, no matter how A plays. 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.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #G04 2

L_{sym}(G) is the smallest k such that A can guarantee his win in at most k + 1 moves. It is not quite clear how to define L_{sym}(G) in the cases when B can preserve the symmetry until the players run out of edges; following [2] we define L_{sym}(G) = ⌊e(G)/2⌋ then.

One of the motivations of Harary, Slany and Verbitsky for introducing these notions was that L_{sym}(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 G has an involutary automorphism ψ without fixed edges, then L_{sym}(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 L_{sym}(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 P_{n} with n vertices, one has to know (the parity of) its order n 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)) log_{2} n ≤ L_{sym}(P_{2n}) ≤ (3.5 + o(1)) (log_{2} n)^{2}.

Its proof exploits some beautiful connections to the so-called Ehrenfeucht-Fraïssé game.

Complete bipartite graphs of even size clearly admit a copycat strategy. The following argument from [2] shows that

L_{sym}(K_{m,n}) ≥ max(\frac{m−1}{2}, \frac{n−1}{2}), for odd mn.  (1)

Indeed, let X ⊂ V (K_{m,n}) be the bigger part of K_{m,n}. Starting with ψ being the identity automorphism, B uses 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 K_{m,n} swapping the blue and red subgraphs.

Harary, Slany and Verbitsky [2, Question 4.3] asked for the rate of growth of the function L_{sym}(K_{n,n}) for odd n. The following more general result implies that L_{sym}(K_{m,n}) grows linearly in n if m ≤ n ≤ m^{O(1)} and mn is odd.

Theorem 1 Let odd integers m and n and an integer k ≥ 8 satisfy

51 ≤ m ≤ n ≤ \frac{(m − 2k − 3)^{k}}{(k + 1)! m} .  (2)

Then we have

L_{sym}(K_{m,n}) ≤ k(n − m + 3) + 2m + 14.  (3)

In particular, if m = n, then letting k = 8 we obtain

L_{sym}(K_{n,n}) ≤ 2n + 38, for odd n ≥ 51.  (4)

In Section 3 we present the bound (3) as a more digestible, explicit function of m and n.

Let us describe the main idea behind the proof of Theorem 1. In outline, A builds a red graph which has no non-trivial automorphism. If B has not lost yet, the isomorphism ψ between the red and blue graphs is unique and B is forced 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 on D 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 ∪ V′ = V (K_{m,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 x_{1}, x′_{1}, …, x_{l}, x′_{l} in this order, plus one edge from some vertex y_{0} ∈ Y to X′, where we denote X = {x_{1}, …, x_{l}} ⊂ V, X′ = {x′_{1}, …, x′_{l}} ⊂ V′, Y = V \ X, and Y′ = V′ \ X′.

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 x_{1}, x′_{1}, …, x_{m−3}, x′_{m−3} one by one in this order. If the edge {x_{1}, x′_{m−3}} is available, then A colours it and we are done because the addition of an edge between X′ and Y is always possible as m − 3 > 2. Otherwise, A extends the path by two more edges. Now, if {x_{1}, x′_{m−2}} is available, then A selects it and we are done again. Otherwise, A can add x_{m−1} to the path: indeed, the vertex x′_{m−2} sends a blue edge to x_{1}, so it sends at most one blue edge to V \ X. If {x_{m−1}, x′_{1}} is available, then A selects it, obtaining the desired configuration (up to relabelling). Otherwise, the edge {x_{m−1}, x′_{1}} is blue and A can extend the path to x′_{m−1}. In the next move A colours the edge {x_{1}, x′_{m−1}} which cannot be blue because we have already encountered two blue edges incident to x_{1}. Finally, A connects some y_{0} ∈ Y to X′, obtaining the desired configuration in all cases.

Phase 2. A connects Y to X′.

The vertex y_{0} ∈ Y will play a special role. Assume that x′_{1} is the vertex in X′ connected to y_{0} by a red edge.

Consider first the case when y_{0} is incident to at least one blue edge. By reversing, if necessary, the direction of the red 2l-cycle, we can assume that y_{0} has at least one blue neighbour outside {x′_{1}, …, x′_{10}}. In the next five moves A colours {y_{0}, x′_{i}} for the smallest possible index i ≥ 2 each time. Suppose that the last such edge was {y_{0}, x′_{s}}. When A was colouring it, at most 5 edges incident to y_{0} were blue of which at most 4 lie in X′_{0} = {x′_{1}, …, x′_{s}}. Hence s ≤ 10.

In the next three moves A colours {y_{0}, x′_{i}}, where i is the smallest available index with i ≥ 2s except, when colouring the third edge in the case s = 6, the additional condition on i is that the indexes of the last three red neighbours of y_{0} do not form an arithmetic progression. (Note that for s ≥ 7 the indexes of the first six neighbours of y_{0} cannot form a six-term arithmetic progression as s ≤ 10.)

Let t > 2s be the largest index of a red neighbour of y_{0} and let X′_{1} = {x′_{2s}, …, x′_{t}}. We claim that t ≤ 26. If s ≥ 7, then y_{0} sends at most 8 − (s − 6) = 14 − s blue edges to X′_{1} because y_{0} sends s − 6 blue edges to X′_{0}; thus

t − 2s + 1 = |X′_{1}| ≤ 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 y_{0} 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 y_{0}. In particular, A can connect y_{0} to

{x′_{1}, x′_{2}, …, x′_{6}, x′_{12}, x′_{13}, x′_{15}}

and we have s = 6 and t = 15.

Next, A connects the vertices of Y \ {y_{0}} to X′, by five edges each, so that distinct vertices of Y have disjoint neighbourhoods in X′, which is possible as l > 2·9+5·(|Y |−1).

The first two phases last for r_{2} = 2l + 9 + 5(m − l − 1) rounds.

Phase 3. If m = n = l + 1, then A connects the (unique) vertex of Y′ to arbitrary 12 vertices of X. Otherwise, A picks vertices of Y′ one by one and connects each selected vertex by k edges to X. Suppose that A has already dealt with y′_{1}, …, y′_{i} ∈ Y′ and connected the next vertex y′ ∈ Y′ to a set H ⊂ X of size h ∈ [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}(y′) ∩ X, will be at most k + 1 when we deal with the vertex y′. This is true for i ≤ 3 when the maximum degree of the blue graph is at most max(k, 9). If i ≥ 4, then the isomorphism between the red and blue graphs must respect the classes V and V′ because the non-trivial red component has at least l + i > |V | vertices in V′. So the blue degree of y′ is at most the maximum red degree of a vertex in V′ which is k, giving the desired bound on f.

Here is the strategy: A connects y′ to a vertex x ∈ X \ (F ∪ H) such that μ(H ∪ {x}) is minimum, where

μ(Z) = ∑_{j=1}^{i} c_{|Z\Γ_{red}(y′_{j})|}, Z ⊂ X,

where c_{0} = l, c_{1} = 1, and all other c’s are zero. In other words,

μ(Z) = l |{j ∈ [i] | Z ⊂ Γ_{red}(y′_{j})}| + |{j ∈ [i] | |Z \ Γ_{red}(y′_{j})| = 1}| .

It is easy to see that

∑_{x∈X\(F ∪H)} μ(H ∪ \{x\}) ≤ ∑_{{j∈[i] \atop H⊂Γ_{red}(y′_{j})}}(c_{0}(k − h) + c_{1}(l − k))

+ ∑_{{j∈[i] \atop |H\Γ_{red}(y′_{j})|=1}} c_{1}(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\}) ≤ \frac{k − h + 1}{l − f − h} μ(H) ≤ \frac{k − h + 1}{m − 2k − 3} μ(H).

As μ(∅) = li < mn, the inequality

μ(H) < \frac{(k + 1)!}{(m − 2k − 3)^{k}} mn ≤ 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}(y′_{j})| ≥ 2 for any j ∈ [i]. Thus A can ensure that the hamming distance between any two sets in {Γ_{red}(y′) | y′ ∈ Y′} is at least 4 at the end of Phase 3.

The first three phases took r_{3} = r_{2} +12 rounds if n = m = l +1 and r_{3} = r_{2} +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 A_{i} (resp. B_{i}) consist of red (resp. blue) edges after i rounds, viewed as a subset of E(K_{m,n}). Thus A = A_{r_{3}} is the red graph at the end of Phase 3. Note that X ∪ X′ spans in A an induced 2l-cycle which we denote by C ⊂ A.

Claim 1. Let A′ be obtained by adding to A at most two edges of the encompassing graph K_{m,n}. Let ϕ : V (K_{m,n}) → V (K_{m,n}) be a bijection such that ϕ^{∗}(A) ⊂ A′, where ϕ^{∗} denotes the induced action on 2-point sets. Then ϕ(y_{0}) = y_{0}, ϕ(Y) = Y, ϕ(X) = X, ϕ(Y′) = Y′ and ϕ(X′) = X′.

If, furthermore, ϕ^{∗}(C) = C, then ϕ is the identity map.

Proof. As A, A′ are connected bipartite graphs, we have ϕ(V) = V or ϕ(V) = V′.

Let us show first that ϕ(V) = V, which needs justification when |V | = |V′|. If |Y′| = 1, then the (unique) vertex of Y′ of degree at least 12 must be preserved by ϕ as any other vertex has A′-degree at most 11; thus ϕ(V) = V, as required. Suppose that |Y′| = |Y | ≥ 2. The vertices in X are incident to at most 4 + |Y′| ≤ 7 < k A′-edges each. Thus V contains at most one vertex of A′-degree at least k and ϕ must map Y′ into V′. Now it follows that ϕ(V) = V and ϕ(V′) = V′.

As each vertex of Y′ has degree at least 8 while the A′-degrees in X′ are all at most 5, we conclude that ϕ(Y′) = Y′. As each vertex of ϕ(Y) sends at least five edges to ϕ(X′) = X′, we have ϕ(Y) = Y. Similarly, ϕ(y_{0}) = y_{0}, which proves the first part of the claim.

Suppose furthermore that ϕ^{∗}(C) = C. This means that the restriction of ϕ to X ∪ X′ is a cyclic rotation, possibly composed with the reflection x_{i} ↦ x′_{l−i+1}, x′_{i} ↦ x_{l−i+1}. We are going to show that ϕ|_{X∪X′} is the identity by considering the neighbourhood of y_{0}.

Recall that the set X′_{0} = {x′_{1}, …, x′_{s}} contains six A-neighbours of y_{0} and X′_{1} = {x′_{2s}, …, x′_{t}} the remaining three. The sets X′_{0} and X′_{1} cannot both intersect ϕ(X′_{0}) as they are separated by s − 1 other vertices of X′. Hence, ϕ(X′_{0}) ∩ X′_{1} = ∅ and ϕ(X′_{0}) ∩ X′_{0} contains at least four A-neighbours of y_{0}. If ϕ(X′_{1}) is situated at the ‘wrong’ side of ϕ(X′_{0}), then (as l ≥ 2t − 4) we have ϕ(X′_{1}) ∩ X′_{1} = ∅ and at least three A′-neighbours of y_{0} fall outside ϕ(X′_{0} ∪ X′_{1}), a contradiction. Thus ϕ|_{X∪X′} is a cycle rotation (without any reflection). Moreover, it is the identity rotation for otherwise we obtain the contradiction |ϕ(Γ_{red}(y_{0})) \ Γ_{red}(y_{0})| ≥ 3. (The latter inequality holds because in Phase 2 we excluded the possibility that the indexes of the red neighbours of y_{0} form two arithmetic progressions.)

Now, for any two vertices of Y ∪Y′ the hamming distance between their A-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 ψ = ψ_{r_{3}} is uniquely determined, where ψ_{r} denotes the red-blue isomorphism after r rounds. The bipartition V ∪ V′ is clearly preserved (or reversed) by ψ so we have the induced action ψ^{∗} on E(K_{m,n}).

Claim 2. For any (r_{3} + 1)st move e of A, the player B is forced to reply with ψ^{∗}(e).

Proof. By Claim 1 any bijection ϕ with ϕ^{∗}(A) ⊂ A_{r_{3}+1} preserves X ∪ X′. As X ∪ X′ induces in A_{r_{3}+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 A_{r_{3}+1} isomorphic to A and the analogous claim holds for the blue edges. Thus ψ_{r_{3}+1}^{∗}(A) = B_{r_{3}}, which implies that ψ_{r_{3}+1} = ψ. Now, ψ^{∗} must map {e} = A_{r_{3}+1} \ A into B_{r_{3}+1} \ B_{r_{3}}, as required.

As the total number of edges mn is odd, some ψ^{∗}-orbit D ⊂ E(K_{m,n}) has the odd number of elements.

If at least one element of D is already coloured, then we can find via a parity argument an uncoloured e ∈ D such that ψ^{∗}(e) is red. Now, A colours e red and B loses 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 e′ = ψ^{∗}(e) and e′′ = (ψ^{∗})^{−1}(e) are two distinct edges belonging to D.

Suppose first that e = {x_{i}, x′_{j}} and that both C ∪{e, e′} and C ∪{e, e′′} have a 2l-cycle passing through the edge e. Trivial considerations show that

{e′, e′′} = { {x_{j}, x′_{i−1}}, {x_{j+1}, x′_{i}} } .  (6)

(Of course, we do all index calculations modulo l.) If ψ(V) = V, then (6) means that for some δ = ±1 we have ψ^{δ}(x_{i}) = x_{j+1}, ψ^{δ}(x′_{j}) = x′_{i}, ψ^{−δ}(x_{i}) = x_{j} and ψ^{−δ}(x′_{j}) = x′_{i−1}. But then ψ^{δ} maps the red edge {x_{j}, x′_{j}} into the red edge {x_{i}, x′_{i}}, a contradiction. In the same way we obtain a contradiction in the case ψ(V) = V′.

Thus, by the first part of Claim 1, we can assume that we can recover C from knowing, for example, A ∪ {e, e′}. Now, A selects e′ to which, by Claim 2, B is forced to reply by colouring ψ^{∗}(e′). Then A selects e ≠ ψ^{∗}(e′). Claim 1 implies that A is the unique subgraph of A ∪ {e, e′} isomorphic to A and the argument of Claim 2 shows that B loses.

Let us count the total number r_{4} of rounds. If n = m = l + 1, then

r_{4} ≤ 2(m − 1) + 9 + 12 + 2 ≤ 3(n − m + k) + 2m + 15,

as k ≥ 8. Otherwise,

r_{4} ≤ 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 L_{sym}(K_{m,n}) ≤ r_{4} − 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 integer k satisfying (2) can be found. For example, if n > 2^{m}, then any subgraph of K_{m,n} contains two vertices in V′ with the same neighbourhood in V, which ruins our strategy. The value of n can range up to

max_{k≥8} \frac{(m − 2k − 3)^{k}}{(k + 1)! m} = (1.531... + o(1))^{m}.

The optimal choice is to take the smallest integer k ≥ 8 satisfying (2). If m is large, then the following formulae can be routinely verified. If log n/ log m < 7 − o(1), then k = 8. If 7 − o(1) ≤ log n/ log m = O(1), then

\frac{log n}{log m} + 1 < k < \frac{log n}{log m} + 3.

If O(log m) < log n = o(m), then

k = (1 + o(1)) \frac{log n}{log m − log log n}.

If (1 + o(1))^{m} < n < (1.531... + o(1))^{m}, then k = (x_{0} + o(1)) m, where x_{0} is the smallest positive root of equation

((1 − 2x)e/x)^{x} = e^{log n/m}.

The present best known bounds on L_{sym}(K_{n,n}) for odd n are given by (1) and (4). Unfortunately, it seems that a minor modification of our method cannot give any considerable 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 than C vertices (as no two can be isomorphic), while the remaining components span at least (v(H) − O(1)) \frac{c−1}{c} edges. Also, one meets difficulties when trying to improve on (1): it is not hard to see that A can ensure that within first \frac{n+1}{2} rounds there was a position when no blue-red isomorphism could be generated by an involutary automorphism of K_{n,n}. Hence, B must go beyond copycat if he wants to survive for more than (\frac{1}{2} + o(1)) n rounds.

In fact, we do not even have any solid conjecture what the value of

lim_{n→∞} \frac{L_{sym}(K_{2n+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 breakingpreserving games on graphs. To appear in Theoretical Computer Science.