{'fraction_non_alphanumeric': 0.06095718693751607, 'fraction_numerical': 0.019510156852661352, 'mean_word_length': 3.3498776651520448, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Borel Edge Colorings for Finite Dimensional Groups

We study the potential of Borel asymptotic dimension, a tool introduced recently in arXiv:2009.06721, to help produce Borel edge colorings of Schreier graphs generated by Borel group actions. We find that it allows us to recover the classical bound of Vizing in certain cases, and also use it to exactly determine the Borel edge chromatic number for free actions of abelian groups.


Introduction
In a recent paper [2], Conley et al. introduced a new tool, Borel asymptotic dimension, to the study of Borel combinatorics. We will define this notion in Section 2, but for now we emphasize that they exhibited several useful consequences which follow when a locally finite Borel graph has finite Borel asymptotic dimension, including hyperfiniteness for its connectedness relation, and Borel vertex colorings using relatively few colors.
The aim of this paper is to add to this list by showing applications of finite Borel asymptotic dimension to edge colorings.
Let X be a standard Borel space and G ⊂ X × X a Borel graph on X. An edge coloring of G is a function c : G → Y which sends adjacent edges in G, that is, edges sharing a vertex, to distinct elements of Y , or "colors". Such a c is called a k-coloring if |Y | = k. The edge chromatic number of G, denoted χ (G), is the smallest cardinal k such that G admits a k-coloring. The Borel edge-chromatic number of G, denoted χ B (G), is the smallest cardinal k such that G admits a Borel k-coloring. See [8] for a survey of these and related notions.
The Borel graphs of interest to us in this paper will be those generated by Borel actions of finitely generated groups. A marked group is a pair (Γ, S) where Γ is a group and S is a finite symmetric generating set for Γ not containing 1. We will sometimes omit the S if it will not cause confusion. Let X be a standard Borel space and a : Γ X a free Borel action. Let G(a, S) denote the Schreier graph generated by this action. This is the graph defined by setting x, y ∈ X adjacent if and only if γ · a x = y for some γ ∈ S.
Note that all the notions in the above paragraph make sense even if S does not generate the entire group Γ. We shall sometimes use them in this case.
A classical theorem of Vizing states that if G is a graph with maximum degree d, then χ (G) ≤ d + 1. Of natural interest is the extent to which this bound continues to hold in the Borel setting. Grebík and Pikhurko have shown that this bound holds in the measurable setting when G is measure preserving [5], but on the other hand Marks has shown that it fails in the general Borel setting, even for acyclic G [10].
As was previously promised, in section 2 we shall see a precise definition of Borel asymptotic dimension for graphs and Borel actions. Actually, of more direct use to use will be a variant of this number, also from [2], called Borel asymptotic separation index. Our main result in Section 3 will be that the Vizing's bound holds in the Borel context for graphs generated by certain group actions when this index is 1.
Theorem 1. Let a : Γ X be a free Borel action of a marked group (Γ, S) on a standard Borel space X with Borel asymptotic separation index 1, and such that none of the elements of S have odd order. Then χ B (G(a, S)) ≤ |S| + 1.
We emphasize that the condition on the generators in Theorem 1 implies that χ (G(a, S)) = |S|. Nevertheless, we will see in Section 4 that the "+1" in Theorem 1 cannot always be removed.
In [2], it is shown that finite Borel asymptotic dimension implies a Borel asymptotic separation index of 1. Several quite general classes of groups, including those with a polynomial growth rate, are also shown to always have finite Borel asymptotic dimension for their free Borel actions. The work of that paper therefore provides us with many groups to which Theorem 1 can be applied.
We will also see in Section 3 that Theorem 1 can be applied to finite extensions of marked groups which satisfy its constraints.
Finally, we will note in Section 3 that Theorem 1 implies that the Vizing bound holds in certain Baire measurable or measurable settings.
It follows from the third most recent paragraph that free actions of abelian groups always have finite Borel asymptotic dimension, although this was known earlier from work of Gao et al. [4]. In Section 4, we will see how a more specific analysis allows us to improve on Theorem 1 for these groups by exactly determining their edge chromatic numbers.
Theorem 2. Let (Γ, S) be a marked group with Γ = ∆ × Z d abelian, where ∆ is the torsion part of Γ and d ∈ ω is its free rank. Let a : Γ X be the action of Γ on its Bernoulli shift, and G = G(a, S) The point of using the Bernoulli shift in the above statement is that arbitrary Borel free actions of Γ always admit Borel Γ-equivariant embeddings to the Bernoulli shift [7], and so the chromatic numbers for the Bernoulli shift are the supremums of the chromatic numbers of arbitrary free actions of Γ.
Note that the statements in parentheses follow from Vizing's Theorem/ Theorem 1 (or rather the aforementioned generalization of the theorem to finite extensions) and the fact that when Γ is finite, its discrete and Borel combinatorics coincide.
During the preparation of this project, we became aware that this result was recently arrived at two other times independently in the special case Γ = Z d and S = the standard generating set. [6], [1] (the latter for d = 2). The key ideas from the proof given in [6] appear also in this work, but some additional ideas are needed to extend the result to arbitrary abelian groups and arbitrary generating sets. Additionally, we learned via personal communication that the authors of [6] were aware of Theorem 1. Our paper provides the first write up of this result.

Borel asymptotic dimension and asymptotic separation index
In this section we will review the relevant definitions and facts from [2] regarding Borel asymptotic dimension and asymptotic separation index. We start with the discrete versions of these notions: Let G be a locally finite graph on a set X, and N a positive integer. Let G ≤N denote the distance Ngraph of G. This is the graph which sets two vertices adjacent if and only if there is a path from one to the other of length at most N .
The asymptotic separation index of G, denoted asi(G) is the infimum over s ∈ ω such that the following holds: For every positive integer N , X can be partitioned into s + 1 sets, say U 0 , . . . , U s , such that for each i, the induced graph G ≤N U i has only finite connected components. The asymptotic dimension of G, denoted asdim(G), is defined similarly, except now the connected components of each G ≤N U i are required to have a uniform (finite) bound on their size.
Let G now be a Borel graph on a standard Borel space X. The Borel asymptotic separation index and Borel asymptotic dimension of G, denoted asi B (G) and asdim B (G) respectively, are defined exactly as their discrete counterparts were, except that now all the U i 's are required to be Borel sets. Now let Γ be a finitely generated group, and a : Γ X a free Borel action. It is easy to verify that none of the above numbers for the graph G(a, S) depend on the choice S of generating set for Γ. We can thus talk about the (Borel) asymptotic separation index and (Borel) asymptotic dimension of the action a itself.
We now list some facts. If G has only finite connected components, then asi B (G) is trivially 0 and its Borel and discrete combinatorics coincide, so until Section 4 assume this is not the case. The following facts, which were referenced in Section 1, can be used to establish that Borel actions of free abelian groups have Borel asymptotic separation index 1, and are also relevant to the discussion more broadly.

Theorem 3 ([2]
). Let Γ be a finitely generated group with polynomial growth rate for its Cayley graph(s). Then any free Borel action of Γ has finite Borel asymptotic dimension.

Theorem 4 ([2]
). Let G be a locally finite Borel graph with asdim B (G) < ∞. Then asi B (G) = 1 These next facts will sometimes allow us to recover Vizing's bound in the Baire measurable and measurable contexts, even for groups for which asi B = 1. [2]). Let G be a locally finite Borel graph on a Polish space X. Then there is a Borel G-invariant comeager set X ⊂ X such that asi B (G X ) = 1.
Theorem 6 ([3]). Let G be a locally finite Borel graph on a standard Borel probability measure space (X, µ) such that the connectedness equivalence relation of G is hyperfinite. Then there is a Borel G-invariant µ-conull set X ⊂ X such that asi B (G X ) = 1.

Degree plus one colorings
In this section we prove Theorem 1 and give some examples where it cannot be improved.

Proof of Theorem 1
Let G be a graph on a set X. An injective G-ray is an injective infinite sequence x 0 , x 1 , . . . ∈ X such that (x i , x i+1 ) ∈ G for all i ∈ ω. Given a set U ⊂ X and an n ∈ ω, let us write B(U, n) for the ball of radius n around U . That is, the set of all points x ∈ X whose path distance to U is less than or equal to n. For m ∈ ω, let us write A(U, n, m) = B(U, m) − B(U, n). One can check that if G and U are Borel, these sets are always Borel.
The following two lemmas together explain how having a Borel asymptotic separation index of 1 will help us to construct edge colorings. Lemma 1. Suppose G is a locally finite graph Borel graph on a space X with asi B (G) = 1, and d ∈ ω. Then we can find pairwise disjoint Borel sets V 1 , . . . , V d ⊂ X such that any injective G-ray contains infinitely many edges within each V i .
Proof. Since the tail of an injective G-ray is still an injective G-ray, it suffices to prove this with "infinitely many edges" replaced by "an edge".
Let X = U 0 U 1 be a Borel partition of X witnessing asi B (G) = 1 for N = 4d + 1. That is, such that the graphs G ≤N U 0 and G ≤N U 1 both have only finite connected components. Set V i = A(U 0 , 2(i − 1), 2i) for each 1 ≤ i ≤ d. Also set W = X \ B(U 0 , 2d). As was mentioned above, these are all still Borel. Let us now show these V i 's work. Let x = (x n ) be an injective G-ray. We first show that x contains some point from W . Suppose not. Then for each n, there is a y n ∈ U 0 whose path distance to x n is less than or equal to 2d. Now for each n, going from y n to x n , then to x n+1 , then to y n+1 , produces a path from y n to y n+1 of length at most 2d + 1 + 2d = N , so all the y n 's are in the same G ≤N U 0 -connected component. By definition of U 0 , then, the set {y n | n ∈ ω} is finite. But now x gives infinitely many points within distance 2d of this set, contradicting local finiteness.
Similarly, x must contain some point from U 0 . Let x n ∈ W and x m ∈ U 0 . We can assume m < n. Now the path distance from x i to U 0 changes by at most 1 each time i is incremented by 1. Thus, since x m has distance 0 from U 0 and x n has distance greater than 2d from U 0 , for each 1 ≤ i ≤ d, there must be some m < j < n such that x j and x j+1 have distance 2i − 1 and 2i respectively from U 0 . Then (x j , x j+1 ) is an edge of x contained in V i , as desired.
Lemma 2. Let a : Z → X be a free Borel action of Z, and S the usual generating set for Z. Suppose V ⊂ X is a Borel set with the property that every injective G(a, S)-ray contains infinitely many edges within V . Then there is a Borel 3-edge coloring of G(a, S), say with the colors 1, 2, and 3, such that the color 3 only occurs on edges contained within V .
Proof. A well known theorem from [9] (Proposition 4.2) states that for locally finite Borel graphs, it is always possible to find Borel maximal independent sets. Apply this to the edge graph of G(a, S) V to get a maximal set of edges A contained within V such that no two edges in A share a vertex. Give all the edges in A the color 3.
By maximality and the defining condition for the set V , these edges occur infinitely often in both directions along each Z-orbit. Thus, the connected components of G(a, S) \ A are all simply finite paths. These can of course be 2-colored with the colors 1 and 2, and since they are all finite, this can be done in a Borel fashion. (For example, by fixing a Borel linear order on the space of 2-edge colored finite subgraphs of G(a, S), and picking the least 2-coloring in this order for each path above.) The proof of Theorem 1 is now easy: Proof. By hypothesis, we may write S = S 0 S 1 , where S 0 contains all of our generators of infinite order, and S 1 contains all of our elements of even (finite) order. For each γ ∈ S 1 , the connected components of the graph G(a, {γ ±1 }) are all even (finite) cycles, or just single edges if γ has order 2. Thus they may be 2-colored in a Borel fashion as in the previous proof (or just 1-colored if γ has order 2). Thus we may Borel |S 1 |-color the edges in G(a, S 1 ).
It now suffices to Borel |S 0 | + 1-color the edges in G(a, S 0 ) using a disjoint set of colors. Let S 0 = {γ ±1 1 , . . . , γ ±1 d }, so that |S 0 | = 2d. We will use the color set {1, . . . , 2d + 1}. Let V 1 , . . . , V d ⊂ X be the sets from Lemma 1. Since γ i ∼ = Z for each i, by Lemma 2 we may for each i color the edges in G(a, {γ ±1 i }) using the colors 2i − 1, 2i, and 2d + 1 such that the color 2d + 1 only appears on edges contained within V i . Since the V i 's are pairwise disjoint, this does not cause any color conflicts, so we are done.
We now wish to see that we can extend Theorem 1 to finite extensions. To do this, it will be helpful to slightly expand our notion of graph to allow for multiple edges.
Let Γ be a group and S ⊂ Γ a finite symmetric multi-set of generators for it not containing 1. That is, the elements of S can appear with some multiplicity. With a : Γ X a Borel free action as before, let G(a, S) denote the Borel-multigraph where now points x and y are connected with one edge for each γ ∈ S such that γ · x = y. Edge colorings can be defined as before. Of course, if x and y have multiple edges between them, those all need different colors in an edge coloring.
Observe that Theorem 1 still holds, with the same proof, if S is allowed to be a multi-set. This allows us to prove: X be a free Borel action of a marked group (Γ, S) on a standard Borel space X with Borel asymptotic separation index 1. Suppose ∆ ≤ Γ is a finite normal subgroup of Γ, and that for each γ ∈ S \ ∆, the image of γ in the quotient Γ/∆ does not have odd order. Then χ B (G(a, S)) ≤ |S|+1.
Proof. Write S = S 0 S 1 , where S 1 = S ∩∆. Consider first the graph G(a, S 1 ). Its connected components are all contained within ∆-orbits, and therefore finite. They are also |S 1 |-regular, so by the classical Vizing's Theorem and the argument from the final paragraph of Lemma 2, we may find a Borel (|S 1 | + 1)-edge coloring of this graph, say using the color set C.
Now let X be the Borel space of ∆-orbits. Then a induces a free Borel action, say a, of Γ/∆ on X. Let S 0 be the multi-set which results from considering the images of the elements of S 0 in Γ/∆. By the last paragraph before the statement of the corollary, we may find a Borel (|S 0 | + 1)-edge coloring using a disjoint set of colors from C, say C , of G(a, S 0 ). Now, given an edge (x, γ ·x) in G(a, S 0 ), give it the color received by the edge (∆·x, ∆γ ·x) in G(a, S 0 ) corresponding to γ. This results in a Borel (|S 0 | + 1)-edge coloring of G(a, S 0 ) since whenever x, y are distinct vertices in the same ∆-orbit, the edges (x, γ · x) and (y, γ · y) are disjoint.
Amalgamating these two colorings gives us a Borel (|S| + 2)-edge coloring of G(a, S), but we can remove a color: Fix a color c from C. For each ∆-orbit, say E ∈ X, E has degree |S 0 | in the graph G(a, S 0 ), and therefore is incident to only |S 0 | colors in our coloring of that graph. By our construction, it is still incident to only those colors in resulting coloring of G(a, S 0 ). Thus, we may pick a color c from C which E does not meet. Then we may may change the color of any edge within E colored c to c . This process maintains Borel-ness, and results in an edge coloring not using c, hence a |S| + 1-edge coloring.
Proof. Repeat the proof of Corollary 1, but now where the color set C has size |S 1 |. The condition S 1 = ∅ is needed for the final step in the proof where we fix a color from C.
Corollary 1 also generalizes a previous result of this author, which was proved using similar ideas [13]: X be a free Borel action of a marked group (Γ, S) with two ends. Then χ B (G(a, S)) ≤ |S| + 1.
Proof. Two ended groups are always finite extensions of Z or the infinite dihedral group D ∞ , neither of which have any odd order elements. Furthermore a Borel asymptotic separation index of 1 is automatic by Theorem 3 since Γ has linear growth rate, though this also follows from earlier work of Miller [11].
Similarly, Corollary 1 implies Vizing's bound for any action of an abelian group: X be a free Borel action of an abelian marked group (Γ, S). Then χ B (G(a, S)) ≤ |S| + 1.
Proof. By the fundamental theorem of finitely generated abelian groups, Γ is a finite extension of some Z d . This implies it has polynomial (degree d) growth rate, and Z d does not have any odd order elements.
Note that the combination of Corollary 3 and Theorem 2 actually render this Corollary redundant. It is still nice to state here, though, as Theorem 2 will require somewhat more work.
We now pause briefly to address the measurable and Baire measurable situations. If G is a Borel graph on a polish space X, we denote by χ BM (G) the minimum of χ B (G X ) as X ranges over all Borel comeager G-invariant subsets of X. If X is instead equipped with a Borel probability measure µ, χ µ (G) is defined similarly. Note that these numbers are both lower bounds for χ B (G). Now, Theorems 5 and 6 have the following obvious consequences: Corollary 5. If we replace χ B with χ BM , Theorem 1 and Corollary 1 hold for Borel actions on Polish spaces without any assumptions on asymptotic separation index.
Similarly in the measurable setting for actions with hyperfinite orbit equivalence relation.

Examples of tightness
Let us now consider when the "+1" in Theorem 1 can't be removed. It is well known that there are free Borel actions of Z with its usual generating set which cannot be even Baire measurably 2-edge colored [9] (page 11, essentially), and so the bound in Theorem 1 is certainly sometimes tight. It would be reasonable, however, to chalk this up to the fact that 2-colorings are very rigid. For example, the following fact shows that the situation can sometimes be very different for graphs of max degree > 2: Thus it is natural to ask for examples in our situation for larger degrees.
The following shows that that Theorem 1 remains tight for graphs of arbitrarily large degree, even if they are also assumed to be bipartite. It also provides one of the directions in the d = 1 case of Theorem 2.
Proposition 1. Let (Γ, S) be a marked group with Γ = ∆ × Z and ∆ finite of odd order. Let a : Γ X be the usual action of Γ on its Bernoulli shift. Then G(a, S) does not admit a Baire measurable perfect matching (i.e, it does not admit a Borel perfect matching on a Γ-invariant comeager set). In particular χ BM (G(a, S)) = χ B (G(a, S)) = |S| + 1.
Proof. Suppose, to the contrary, there is a Borel Γ-invariant comeager set X ⊂ X and a Borel perfect matching M ⊂ (G(a, S) X).
Start by defining a : Z = Γ/∆ X, S 0 , and S 0 exactly as in the proof of Corollary 1. Also let X ⊂ X be the set of ∆-orbits contained in X .
Let M ⊂ G(a, S 0 ) be the sub-multigraph which includes an edge between distinct ∆ orbits y and y for each edge between y and y in M . Since ∆ has odd order, each orbit y ∈ X must be contained in an odd number of edges in M .
Let n ∈ ω large enough so that S ⊂ ∆ × (−n, n). For any edge (y, m · y) ∈ G(a, S 0 ) with m > 0, define y to be the left endpoint of that edge and m · y to be the right endpoint. For y ∈ X , define F (y) to be the number of edges in M with a right endpoint in [0, n] · y and a left endpoint not in [0, n] · y. Put another way, this is the number of edges in M which leave the set [0, n] · y to the left.
Let us compare F (y) and F (1 · y). For an edge of M to be counted in F (1 · y) but not F (y), it would have to either have y has a left endpoint, or (n + 1) · y as a right endpoint. Since S 0 ⊂ (−n, n), though, no edge with (n + 1) · y as a right endpoint can leave the set [1, n + 1] · y to the left, and so this cannot occur. Thus our edge would have to have the form (y, m · y) for some 0 < m < n, and conversely any edge with this form is counted in F (1 · y) but not F (y).
Similarly, for an edge of M to be counted in F (y) but not F (1 · y), it would have to have y as its right endpoint or (n + 1) · y as its left endpoint. The latter is absurd, though, and so our edge would have to have the form (m · y, y) for some m < 0. Once again, conversely any edge with this form is counted in Now, y must be the left or right endpoint of each edge in M which it belongs to. Let L, and R be the number of such edges falling into these respective cases. By the above discussing, we can conclude F (1 · y) = F (y) + L − R. By an earlier comment, though, L + R is odd, so F (1 · y) = F (y) + 1 (mod 2). Thus, if we define f (y) to be the mod 2 value of F (y), f is a 2-vertex coloring of G(a, {±1}) X . It is also clearly Borel since M was. This is well known to be impossible for nonmeager X by a basic ergodicity argument [9] (page 11), so we are done.
Finally, the conclusions about the edge chromatic numbers follow from this and Corollary 3, since an |S|-edge coloring is a decomposition into perfect matchings.
Note that this fails if we do not use the convention that S must be finite. Indeed it is not hard to construct Borel perfect matchings for the Borel graph on X above which connects any two points in the same Γ-orbit.

Open problems
We end this section by listing interesting open problems related to Theorem 1.
First, for Schreier graphs, it seems to be open whether any of the assumptions of the theorem are necessary: Problem 1. Is there any marked group (Γ, S) and free Borel action a : Γ X such that χ B (G(a, S)) > |S| + 1?
Natural candidates to resolve this question are the free groups with their usual generating sets. It follows from the results in [10] that the Schreier graphs of these marked groups do not necessarily admit Borel pefect matchings, ruling out Borel degree-edge colorings, but not much else seems to be known. (See Problem 5.37 in [8].) It is also unclear whether the presence of a group action is necessary: It may be necessary to add an assumption of bipartite-ness to get an affirmative answer to this problem as a replacement to Theorem 1's prohibition of odd-order generators. This restricted version of the problem still seems to be open. Note that by Theorem 5, an affirmative answer to Problem 2 would imply that Vizing's theorem holds in complete generality in the Baire measurable setting.
Given Theorem 1, one way to make progress on Problem 2 in the case where d is even would be to find so-called Schreier decorations of G which are Borel. These are orientations of the edges of G along with edge colorings so that each vertex ends up with exactly one in and one out edge of each color, and so they essentially realize G as the Schreier graph of some not-necessarily free group action. Some recent progress has been made in this area: See [12], [1]. Even more generally, it would be useful to simply find Borel ways of decomposing G into graphs of max degree 2.
Finally, given Proposition 1 it is interesting to ask whether any groups other than finite extensions of Z can provide examples where the degree plus one bound is tight.
Is there a marked group (Γ, S) and a free Borel action a : Γ X satisfying the hypothesis of Theorem 1 for which χ B (G(a, S)) = |S| + 1, and for which Γ is not a finite extension of Z?
See Question 38 in [1] for a similar problem. Note that by Theorem 2, the answer is "No" for abelian Γ.

Degree colorings for abelian groups
In this section we prove Theorem 2. In two situations the theorem asserts the non-existence of degree colorings: In the discrete setting when d = 0 and ∆ has odd order, and in the Borel setting when d = 1 and ∆ has odd order. We have already mentioned that the latter is covered by Proposition 1. The former is obvious since a finite graph with an odd number of vertices cannot admit a perfect matching. Therefore in this section we can focus on constructing degree colorings in the remaining cases.
Throughout, let a,X,Γ,S, d, and ∆ be as in the statement of the theorem, unless otherwise stated. Note, though, that nothing in this section is specific to the Bernoulli shift. We only use that a is a free Borel action of Γ.

Free rank 0
In this subsection we complete the proof of statement 1 of Theorem 2 by showing that if Γ = ∆ is an even order finite abelian group, then χ (G(a, S)) = |S|. Note that this will imply the same for χ B (G(a, S)), by the argument from the second half of Lemma 2. While it seems unlikely that this result is original, our coverage of it will introduce a general technique which will be useful for dealing with the torsion part when d > 0. We feel it is also simply nice to include for the sake of completeness.
It suffices to consider the case when a is the action of ∆ on itself by multiplication. In this case our graph is called the Cayley graph of (∆, S).
The following lemma is not specific to the case d = 0.
Proof. Let S 1 = S ∩ ∆ = S \ S 0 . By hypothesis, we may find a |S 0 |-edge coloring of χ B (G(a, S 0 )), say using the set of colors C. As in the proof of Corollary 1, we may lift this to a |S 0 |-edge coloring of G(a, S 0 ) by giving the edge (x, γ · x) for x ∈ X and γ ∈ S 0 whichever color was given to the edge (∆ · x, γ∆ · x) in G(a, S 0 ) corresponding to γ.
Fix a color c ∈ C, which exists since ∆ is proper, so S 0 is nonempty. Consider the subgraph G of G(a, S) consisting of G(a, S 1 ) along with all the edges colored c in the previous step.
Since, in our coloring of G(a, S 0 ), the set of edges colored c gives a perfect matching, each connected component of our subgraph looks like the following: Two adjacent ∆-orbits, say y and γ · y for some γ ∈ S 0 , with all the internal edges from S 1 , along with all edges between them of the form (x, γ · x) for x ∈ y.
Fix a set C of |S 1 | + 1 colors disjoint from C. We now use C to edge color the above component. First, by Vizing's theorem, we may use C to color the edges within y. Now, for every such edge, say (x, x ), give the edge (γ · x, γ · x ) the same color. Since Γ is abelian, this colors all edges within γ · y without conflict. Finally, for each x ∈ y, by this construction the set of colors of edges in y meeting x is the same as the set of colors of edges in γ · y meeting γ · x. This set has size |S 1 |, though, so we still have one free color, and can assign it to the edge (x, γ · x), completing our coloring.
Thus we can edge color G using C , and we already have an edge coloring of G(a, S)\G using C\{c}, so unioning these gives a coloring using |C| +|C|−1 = Finally, if our original coloring was Borel, our lift will still be Borel, and then our construction can be done in a Borel fashion since we only need to work with finite components. Again this uses the argument from Lemma 2.

Statement 1 now follows:
Proof. Since ∆ has even order, we may by the fundemental theorem of finite abelian groups find an index 2 subgroup ∆ ≤ ∆. We now wish to apply Lemma 3 with this choice of ∆ . We clearly can, though, since we will have Γ = Z/2, and so G(a, S 0 ) will just consist of two points with |S 0 |-many edges between them.

Free rank ≥ 2
In this subsection we complete the proof of Statement 3 of Theorem 2. Applying Lemma 3 with ∆ = ∆, we reduce to the case Γ = Z d , but where we now allow multiplicity for the generators in S. For the rest of the subsection, assume (Γ, S) has this form.
For motivation, consider Figures 1 and 2. The former shows that we can think about the proof of Theorem 1 as follows: For each i, the orbits of γ i are edge colored using mostly the colors 2i − 1 and 2i, but with an occasional 2d + 1 thrown in to help align parity.
The latter makes an analogy between this and our upcomming proof of Statement 3. For notational convenience, consider the case where S = {±e i | 1 ≤ i ≤ d} is the standard generating set, where e i = (0, . . . , 0, 1, 0, . . . , 0), with the 1 in the i-th coordinate. We will still color the orbits of each e i using mostly the colors 2i − 1 and 2i, but as before we will need to occasionally break parity. Thanks to the structure of Z d , though, when d ≥ 2 we will be able to do this by "borrowing" a color from some e j -edge, j = i.

Borrowing colors
We will now describe a general setup for using this "borrowing" idea. See Figure 3 for a visualization. Let γ 1 , γ 2 ∈ S such that γ 1 , γ 2 ∼ = Z 2 . That is, γ 1 and γ 2 are not scalar multiples of eachother. Work in some finite subset U of some Z d -orbit, with two disjoint subsets A, B ⊂ U . Let S = {±γ 1 , ±γ 2 }.
Let F denote the set of γ 1 -orbits meeting U . Call two elements of F adjacent (with respect to γ 2 ) if the action of γ 2 sends one to the other. Note that this makes sense since Z d is abelian. Suppose P is a partition of F into adjacent pairs. Suppose e = (x, γ 1 · x) is a γ 1 -edge in some f ∈ F. Let Figure 1: The key idea in the proof of Theorem 1 . The color 2d + 1 is used (within the region V 1 ) to "break parity" along the orbits of γ 1 .

Figure 2:
The key idea in the proof of Theorem 2. Now parity along the horizontal orbits is broken without the use of an additional color. The regions A and B are labeled so that they can be referenced later.
3. Parallel γ 1 -edges are always given the same color.
4. If e, e are two edges in a single element of F meeting A, they get the same color iff the distance between them is odd. Likewise for B. Proof. Essentially a proof by picture; See Figure 3. First, the move from c to c will not change which edges get the color 4, so ignore those edges for the rest of the proof. We are left with a graph like the one in the figure. Fix a pair {f, f } ∈ P , so that we need to fill in the colors of the edges in f and f not meeting A ∪ B. We would like to simply do this by continuing to alternate between the colors 1 and 2 on them, but we may run into parity issues.

For every path from
By condition 4, this can only be the case along paths in f or f between A and B. By condition 5, though, whenever we have such a situation, we can "borrow" the color 3 to indeed do a parity swap if necessary. Item (a) in the figure shows an example where this is the case, and item (b) an example where it is not.

The standard generators
The remainder of Subsection 4.2 will involve reducing our desired result to several concrete cases. All will be handled using similar overall strategies, and ultimately relying on Lemma 4. The first of these will be when S = {±e i | 1 ≤ i ≤ d} is the usual generating set for Z d . Fix this particular S for now. We will cover this case carefully to illustrate our general strategy.  We first set up some additional terminology. Let U ⊂ U be subsets of some fixed Z d -orbit U , and let c : (G(a, S) U ) → {1, . . . , 2d} an edge coloring. Let x 0 ∈ U . We say that c follows protocol x 0 on U if for each edge (x, e i · x) of G(a, S) U meeting U , c gives this edge the color 2i − 1 if a i is even and 2i, otherwise, where (a 1 , . . . , a d ) ∈ Z d is the unique element such that (a 1 , . . . , a d ) · x 0 = x. Of course, it is always possible to 2d-edge color a given subset of U following a given protocol. Also note the choice of x 0 only matters modulo the action of the subgroup (2Z) d .
It is clear that if U and V are two disjoint subsets of U and c is a coloring of G(a, S) (U ∪ V ) following a given protocol, then c can be extended to a coloring of all of G(a, S) U following that same protocol. We now need to see what to do when U and V follow different protocols.
Lemma 5. Let 1 ≤ i ≤ d. Suppose U ⊂ U and c is an edge coloring of B(U, 1) following some protocol x 0 on A(U, 0, 1). Then we can extend c to a coloring of G B(U, 5) which still follows protocol x 0 on A(U, 0, 1), but also follows protocol e i · x 0 on A(U, 4, 5).
Proof. First, color any edges in B(U, 5) meeting A(U, 4, 5) or A(U, 0, 1) as dictated by the protocols e i · x 0 and x 0 respectively. These two protocols agree about how to color edges corresponding to e j for j = i, so tentatively color all these edges in A(U, 0, 5) as dictated by these protocols.
We need to fill in the colors for the remaining e i edges: those contained in A(U, 1, 4). Since d > 1, fix some j = i. Observe that we can do this by applying Lemma 4 with γ 1 = e i , γ 2 = e j , A = A(U, 0, 1), B = A(U, 4, 5) and the colors 1,2,3, and 4 replaced with 2i − 1, 2i, 2j − 1, and 2j respectively. All conditions other than 5 are immediately apparent. P will pair up any two adjacent e i orbits whose connecting edges all get the color 3. That is, it will consist of pairs of the form f, e j · f for which f contains a point (a 1 , . . . , a d ) ∈ x 0 with a j even. Then, for condition 5, any edge e such that both e and its parallel edge are contained in A(U, 1, 4) will work. 4 is large enough so that we are always guaranteed the existence of such an edge, so we are done. Note that the picture here will look like that in Figure 2.
Lemma 6. Suppose U ⊂ U and c is an edge coloring of G(a, S) U following some protocol x 0 . Then we can extend c to a coloring of G(a, S) B(U, 4d + 1) which still follows protocol x 0 on U , but also follows some arbitrary second protocol, say x 1 , on A(U, 4d, 4d + 1).
Proof. This is an obvious induction using Lemma 5.
Lemma 7. Suppose U, V ⊂ U , the G(a, S)-path distance between U and V is greater than 4d + 1, and c is an edge coloring of G (U ∪ V ) which follows some protocols x 0 and x 1 on U and V respectively. Then we can extend c to a coloring of U which still follows those protocols on U and V respectively.
Proof. First, extend c to B(U, 4d + 1) as in Lemma 6. Then color the rest of the edges in U following protocol x 1 . Now, thanks to the fact asi B (G(a, S)) = 1, Lemma 7 is enough: Lemma 8. With S the standard generating set, χ B (G(a, S)) = |S| = 2d.
Proof. Let N = 8(d + 1). Let X = U 1 V be a Borel partition witnessing asi B (G(a, S)) = 1 for this value of N . Let V 1 = X \ B(U 1 , 4d + 1). Arguing as in the proof of Lemma 1, we can conclude that every injective G(a, S)-ray passes through V 1 . Thus, by König's lemma, the connected components of G(a, S) (X \ V 1 ) are still all finite. G(a, S) V 1 also has only finite connected components since V did. Likewise for U 1 and its complement. See Figure 5 to see how these sets might be arranged.
Thus, as in the proof of Lemma 2, we may Borel 2d-edge color G(a, S) U 1 so that a consistent protocol is followed within each G(a, S) (X \ V 1 ) component, and Borel 2d-edge color G(a, S) V 1 so that a consistent protocol is followed within each G(a, S) (X \ U 1 )-component. Now let C be a G(a, S) (V \ V 1 )-component. Let V 2 be the union of the V 1 -components meeting C,and U 2 the union of the U 1 -components meeting C. V 2 is contained in a single (X \ U 1 )-component, and hence is colored using a consistent protocol , and likewise for U 2 . Thus, by Lemma 7 (note that the path distance between U 2 and V 2 is more than 4d + 1), we can find a coloring of C ∪ U 2 ∪ V 2 which still follows the original protocols set for U 2 and V 2 on those sets. Since C is always finite, we can in a Borel fashion do this simultaneously for every such C, and by construction this does not cause any color conflicts.
Since the remaining cases we cover will be handled very similarly to this one, we will not go over these details for each one. Instead we will content ourselves in each one with establishing some appropriate notion of "protocol", and using Lemma 4 to at least sketch some analogue of Lemma 6 saying different such protocols can be transitioned between in a bounded neighborhood.
For example, one case we will need to address is d = 2, a 1 , 0), . . . , ±(a n , 0), ±(0, b 1 ), . . . , ±(0, b m )} for n, m > 1 and the a i 's and b i 's arbitrary positive integers (possibly with repeats). Let U be a Z 2 -orbit as before. In this setting, for x 0 ∈ U , protocol x 0 will dictate that if x ∈ U with x = (g 1 , g 2 ) · x 0 , then the edge (x, (a i , 0) · x) gets the color 2i − 1 if g 1 ∈ [0, a i ) (mod 2a i ) and the color 2i otherwise, and likewise for the (0, b j ) generators.
The technique in this setting for transitioning between different given protocols is exactly like that in the standard generator case. Thus we have: Lemma 9. With d = 2 and S as above, χ B (G(a, S)) = |S|.
Of course, there is nothing special here about d = 2, but it makes for shorter notation and we will not need the higher dimensional versions of this case.

Z 2 with three generators, subcase 1
We now consider cases of the form d = 2, S = {±(n, 0), ±(0, n), ±(b 1 , b 2 )}, where n, b 1 , and b 2 are positive integers. Of course, we may assume n, b 1 , and b 2 do not share any common factors. Fix such an S for the time being.
First consider the sub-case n = 1. This will split into two further sub-cases, depending on the parity of b 1 and b 2 . For the first, suppose one of the b's is even. WLOG let us say it is b 2 .
We already know how to alter the protocol used for the (1, 0) and (0, 1)edges, so we need to consider the (b 1 , b 2 ) edges. Given a coloring following some protocol x 0 , though, consider the subgraph consisting of (b 1 , b 2 )-edges along with all (0, 1)-edges colored 3. Since b 2 is even, the resulting picture will look exactly like the one from the standard generators case (Figure 2), but with the colors 5 and 6 in place of 1 and 2. That is, in the Language of Lemma 4 with γ 1 = (b 1 , b 2 ) and γ 2 = (0, 1), we can chose P so that for any {f, f } ∈ P , all (0, 1)-edges from f to f have the color 3. Thus by the Lemma we can swap parity for the 5's and 6's for such pairs as necessary. For example, if we want to transition to the protocol (1, 0) · x 0 , we do this swap for all pairs {f, (0, 1) · f } ∈ P for which f contains a point of the form (a 1 , a 2 ) · x 0 with a 1 a multiple of b 1 , and leave the parity unchanged on all other pairs.
For the second sub-case, suppose both b 1 and b 2 are odd. Our notion of protocol will be defined identically as in the previous subcase, but altering protocol for the (b 1 , b 2 )-edges will be more difficult.
Suppose U ⊂ U is some finite subset, and we have an edge coloring c on B(U, 1) which follows some protocol x 0 . Since Lemma 4 allows us to control parity separately in each pair of γ 1 -orbits in P , we can, as in the standard generators case, extend c to an edge coloring on B(U, 5), but this time shifting parity on every other adjacent pair of (0, 1)-orbits. Call this new pattern of edge colors the alternating protocol x 0 . Figure 6 shows the result of this new protocol in the case b 1 = b 2 = 1. Consider the result when taking from this new protocol only the (b 1 , b 2 )-edges and the (0, 1)-edges colored 3. Since b 1 and b 2 are odd, the resulting picture  2 )-edges, while the vertical ones are the (0, n)-edges colored 3. The label (g 1 , g 2 ) for a point is shorthand for (g 1 , g 2 )·x 0 . Whether or not a vertical edges touching some (g 1 , g 2 ) is included depends on the value of g 2 mod 2n.
looks exactly like that in Figure 3, but with the colors 5 and 6 in place of the colors 1 and 2. It therefore follows from Lemma 4 that for some large enough N (but only depending on b 1 and b 2 ), we will be able to extend c further to an edge coloring on B(U, N ) which, on A(U, N − 1, N ), follows alternating protocol x 0 for the (1, 0) and (0, 1)-edges, but follows protocol (1, 0) · x 0 for the (b 1 , b 2 )-edges. As in the previous subcase, this will involve switching parity along exactly those (b 1 , b 2 )-orbits which meet a point of the form (a 1 , a 2 )·x 0 for which a 1 is a multiple of b 1 . Finally, we extend this to a coloring on B(U, N +5) while undoing the parity shifts in the (0, 1)-orbits, ending up with a coloring which, on A(U, N +4, N +5), follows protocol x 0 for the (1, 0) and (0, 1)-edges, but (1, 0) · x 0 for the (b 1 , b 2 )-edges. This is exactly what we wanted, so this case is done.

Z 2 with three generators, subcase 2
Finally, we remove the assumption n = 1. Then, since we assumed there were no common divisors, WLOG n does not divide b 2 . Our notion of protocol for the (n, 0) and (0, n) edges will be defined as in the Lemma 9 case. For the (b 1 , b 2 ) edges, it will be defined exactly as in the previous subcases.
Thus, we can alter protocol for the (n, 0) and (0, n)-edges as we did in Lemma 9, so once again it suffices to see how to shift parity for the (b 1 , b 2 )edges.
We wish to apply Lemma 4 with γ 1 = (b 1 , b 2 ), γ 2 = (0, n), and the colors 5 and 6 in place of 1 and 2. Suppose we have some edge coloring of G(a, S) U following protocol x 0 . In the language of Lemma 4, consider 2 adjacent (b 1 , b 2 )-orbits f and f = (0, n) · f . Note that as in the previous subcases, condition 3 of the lemma is automatic by our choice of protocol for the (b 1 , b 2 )-edges. Thus to apply the lemma in the way we want, It would suffice to find an N (depending only on n, b 1 , and b 2 ) such that for every path in f of length N , there is some edge e in the path satisfying condition 5 of the lemma. That is, such that both (0, n)-edges from e to f get the color 3.
Let (a 1 , a 2 ) · x 0 be an arbitrary point in f , so that the points on f are those of the form (a 1 + kb 1 , a 2 + kb 2 ) · x 0 for k ∈ Z. By definition of our protocol, the edge from such a point to f will get the color 3 if and only if a 2 + kb 2 ∈ [0, n) (mod 2n).
Our problem thus reduces to the following number theoretic one. Given that n | b 2 , find N large enough so that for any a 2 ∈ Z, there is some k ∈ [0, N ] such that a 2 + kb 2 and a 2 + (k + 1)b 2 are both in the range [0, n) (mod 2n). Since everything is modulo 2n, it just suffices to show that we can find some such k ∈ N, and then we can take N = 2n. Assume that b 2 ∈ (0, n) (mod 2n), as the case b 2 ∈ (n, 2n) (mod 2n) will follow from a similar argument. Now let q = gcd(b 2 , 2n) < n. Then there will always be a k such that a 2 + kb 2 ∈ [0, q) (mod 2n). Also, since we have assumed b 2 ∈ (0, n) (mod 2n), we must actually have b 2 ∈ [q, n − q] (mod 2n). Then a 2 + (k + 1)b 2 is in the range [0, n) (mod 2n) as desired. Let

Combining the cases
Finally, we are ready to finish the proof for general d and S.
Proof. Let S = {±γ 1 , . . . , ±γ n }, and let S = {γ 1 , . . . , γ n }. We define an equivalence relation ∼ on S which sets two generators as equivalent if one is a scalar multiple of the other. Equivalently, if the subgroup they generate is cyclic. Let C 1 , . . . , C m list the classes in S / ∼. Note that we must have m ≥ d > 1.
Because of this, we can partition the C i 's into sets of size 2 and 3. It now suffices to show that given an element of this partition {C i j | 1 ≤ j ≤ r}, where r ∈ {2, 3}, we can Borel color the edges in G(a, ± j C i j ) using |± j C i j | colors.
First consider the case r = 2. For notational convenience, take i j = j for j = 1, 2. Let Γ = C 1 , C 2 ∼ = Z 2 . Then (Γ, ±(C 1 ∪ C 2 )) is isomorphic as a marked group to Z 2 with a set of generators of the form covered in Lemma 9, so that Lemma says this case is done.
Next consider the case r = 3, and again take i j = j for j = 1, 2, 3. We would like to reduce to the case where C 1 , C 2 , and C 3 are all singletons. Suppose, for instance that C 1 includes at least two elements, and let δ 1 be one. Pick some δ 2 from C 2 . Then we can 4-edge color G(a, {±δ 1 , ±δ 2 }) by the previous paragraph. We are left with C 1 − {δ 1 }, C 2 − {δ 2 }, and C 3 . Note that C 1 − {δ 1 } is still nonempty. If |C 2 | = 1, then we have reduced to the previous paragraph.
If not, and one of our three sets still contains more than one element, repeat this.

Free rank 1
In this subsection we complete the proof of Statement 2 of Theorem 2. For the discrete part of the statement, since we can use Lemma 3 with ∆ = ∆ , it suffices to prove χ (G(a, S)) = |S| when Γ = Z, but where we now allow multiplicity for generators. This is obviously the case, though.
We thus turn to the Borel part of the statement, We need to show that if ∆ has even order, then χ B (G(a, S)) = |S|. As in the proof of Statement 1, we can start by finding an index 2 subgroup ∆ ≤ ∆, and then use Lemma 3 to reduce to the case where ∆ = Z/2, but where we now allow multiplicity for generators in S. For the rest of the subsection, assume (Γ, S) has this form. We will sometimes write "Z" to refer to the subgroup {0} × Z ≤ Γ.
We start with the special case where (1, 0) ∈ S. (Recall we are writing Γ = Z/2 × Z. For example this element has order 2.) Proof. This follows immediately from Corollary 2 with ∆ = Z/2.
Thus, from now on assume (1, 0) ∈ S. Then we can write S = S −S , where S consists of all pairs ( , n) ∈ S for which n > 0. Our proof will be organized as follows: The elements ( , n) ∈ S will be organized into 4 categories corresponding to the value of and the parity of n. We will consider these categories roughly one at a time, for each establishing a suitable notion of protocol as in the previous subsection, and demonstrating how to transition between protocols.
These transitions will always be accomplished by an argument in the style of Lemma 4. That lemma was stated in the context of Z d , but in this context its terminology still makes sense and its conclusion still holds. Let's begin. There must be some element ( , n) ∈ S for which n is odd. Note that there is an automorphism of Γ exchanging (1, 1) and (0, 1). This will send ( , n) to (1 − , n), so we may assume S has an element of the form (0, n) for n odd. Then it must also have an element of the form (1, m). Fix such elements for the rest of the proof.
We start by examining how to color the (0, n) and (1, m)-edges. Let U be a Γ-orbit, and x 0 ∈ U . For any generator of the form (1, m ), protocol x 0 will dictate that edges of the form (x, (1, m ) · x) get the color 3 if x and x 0 are in the same Z-orbit, and 4 if they are not. We will always use such protocols for such edges, so we will need to be able to transition between the protocols x 0 and (1, 0) · x 0 . Call these protocols two sided protocols.
For any generator of the form (0, n ) for n odd, a coloring of the (0, n )edges on Z · x 0 will be said to follow the odd protocol x 0 if (x, (0, n ) · x) gets the color 1 or 2 according to whether the integer a such that x = (0, a ) · x 0 is even or odd respectively. Note that this protocol does indeed give a coloring since n is odd. Now a coloring of the (0, n )-edges on U will be said to follow the parallel protocol x 0 if it follows the odd protocols x 0 and (1, 0) · x 0 on Z · x 0 and (Z + (1, 0)) · x 0 respectively, and the alternating protocol x 0 if it follows the odd protocols x 0 and (1, 1) · x 0 on Z · x 0 and (Z + (1, 0)) · x 0 respectively. Whichever of these protocols is used, we will need to be able to transition between that corresponding to x 0 and that corresponding to (0, 1) · x 0 . Now, returning to our fixed (0, n) and (1, m), if m is odd, we will use alternating protocols for the (0, n)-edges, and if m is even, we will use parallel protocols. Pictures of both cases are shown in Figure 8.
We now see how to shift these protocols. To shift the protocol used for the (0, n)-edges, We want to apply Lemma 4 with γ 1 = (0, n) and γ 2 = (1, m). Our partition P will group together two (0, n)-orbits f and (1, m) · f if f is in the same Z-orbit as x 0 , This, way, by our use of the two sided protocol x 0 for the (1, m)-edges, the (1, m)-edges connecting f and (1, m) · f will always have the Same, but now with m = 2. Note that now the (0, 1)-edges use the parallel protocol. The dotted line sections off a pair of adjacent (1, m) orbits. This makes it clear that they follow the necessary hypotheses to apply Lemma 4. color 3, which will give condition 5 in the lemma. Our use of an alternating or parallel protocol with respect to the parity of m ensures condition 3 is satisfied. Thus, for every such pair, we can flip parity for the (0, n)-edges. Doing this for each pair transitions us from protocol x 0 to protocol (0, 1) · x 0 for the (0, n)-edges, as desired.
The (1, m)-edges work out similarly. We now want to apply the lemma with γ 1 = (1, m) and γ 2 = (0, n). Observe that it is still possible to define the partition P so that if f and f are (1, m)-orbits grouped together, the edges between them all get color 1. Part (b) of Figure 8 gives an example how to do this. The general idea is that we have chosen our protocol for the (0, n)-edges so that our coloring of them descends to one of the quotient of our graph by the subgroup (1, m) , so we can just group together orbits just in case they are related in this quotient by an edge of color 1. This takes care of condition 5, and condition 3 comes from our use of a two sided protocol for the (1, m)-edges.
A remark for clarity: While we have defined the above protocols all relative to a single base point x 0 , when making transitions we never need to assume the base point used for the (0, n)-edges is the same as that used for the (1, m)edges. This is important, as to actually turn these protocol shifting arguments into a Borel edge coloring, we need to be able to shift the protocol for each generator one at a time. This will continue to be the case throughout this subsection, and we will not remark on it further.
If S has additional elements of the form (0, n ) for n odd, we can color them using alternating or parallel protocols (but with new colors) according to the parity of m, and as above use the (1, m)-edges to make transitions. Likewise, if S has additional elements of the form (1, m ) with m ∼ = m (mod 2), we can color them using two sided protocols and use the (0, n)-edges (since they will be colored using the correct protocol to work with m ) to make transitions.

Generators from Z + (1, 0) with different parity
A difficulty arises if S contains elements of the form (1, m ) for m both odd and even. If this is the case, let us decide that our fixed m from before is even, so that in the previous paragraph we have handled all (1, m )'s for m even. We now need to see what to do with generators of the form (1, b) Fix such a generator. When coloring the (1, b)-edges according to our usual two sided protocols, let us use the colors 5 and 6 in place of 3 and 4 respectively. We will divide our argument into two cases depending on whether n divides b. Suppose first that n does divide b.
By working separately on each Z/2 × nZ-orbit, we can assume n = 1. Then, Figure 9 shows how to use the (0, 1)-edges to transition between our two possible protocols for the (1, b)-edges in the case b = 3. It should be clear how this pattern can be continued to other b.
Next suppose that n does not divide b. Let q = gcd(n, b) = gcd(n, 2b) < n. The following will be important for a soon to come number theoretic argument. Proof. Suppose not. Then, since m + b and m − b differ by 2b, a multiple of q, they must either be equal mod 2n, or differ by exactly q mod 2n.
In the former case, we get 2b = 0 (mod 2n), which contradicts n not dividing b.
In the latter case, we get 2b = ±q (mod 2n), but note that q must be odd, so this is also a contradiction.
Assume then that b−m does not lie in this interval mod 2n. The argument in the case where b + m is not in this interval will be similar. Assume further that b − m ∈ [0, n − q] (mod 2n), as the argument in the case where it is in [n + q, 2n] (mod 2n) will again be similar. Now, our transition will occur in three steps. In step 1, we will use the (1, m)-edges to put the colors of the (0, n)-edges in a more useful arrangement. Recall that, in the previous subsubsection, to swap protocols for the (0, n)edges, we divided the (0, n)-orbits into pairs of the form f, (1, m) · f , for f ⊂ Z · x 0 , and saw we could swap parity for the colors 1 and 2 along each orbit. In our step 1 for this case, let us only swap parity on those pairs for which Step 1 of the procedure. The dashed vertices are those included in one of the (0, n)-orbits along which parity is changed. The edges drawn are the (0, n) and (1, m)-edges involved in making that change for these orbits. (b): The effects of step 1, along with a pair of (1, b)-orbits of the form f, (0, n) · f from step 2. The solid and dashed lines are the edges from f and (0, n) · f respectively. A vertex (0, a 0 + 2kb) · x 0 of f which satisfies the number theoretic condition from step 2 is highlighted.
(0, 2l) · x 0 ∈ f , for l = 0, 1, . . . , (n − 1)/2. This is demonstrated in Figure  10, with the result of these swaps shown in part (b) of the figure: The (0, n)edges in each Z-orbit are now colored with 1 and 2, but in alternating blocks of length n. In the orbit Z·x 0 , a block of color 2 starts at the edge (x 0 , (0, n)·x 0 ), while in the other orbit (Z + (1, 0)) · x 0 , a block of color 2 starts at the edge ((1, m) · x 0 , (1, m + n) · x 0 ). That is, the patterns in these two orbits are "offset by m".
In step 2, we will make an argument similar to that from Subsubsection 4.2.4. Partition the (1, b)-orbits into pairs of the form f, f = (0, n) · f , which is possible as (0, n) has even order in the quotient Γ/ (1, b) , since n is odd. One such pair is depicted in part (b) of Figure 10. Such an f can be described by a vertex of the form (0, a 0 ) · x 0 , so that the elements of f ∩ Z · x 0 are those of the form (0, a 0 + 2kb) · x 0 for k ∈ Z. Each such point determines a pair of parallel edges e := ((0, a 0 + 2kb) · x 0 , (1, a 0 + 2kb + b) · x 0 ) and (0, n) · e in f and f respectively. If the two (0, n)-edges connecting e and (0, n) · e both have the color 2, then this pair of edges will witness condition 5 from Lemma 4, so we will be able to change parity along f and f as desired.
By our previous description of the effects of step 1, this will be the case if both a 0 + 2kb and a 0 + 2kb + b − m are in the interval [0, n) (mod 2n), so we want to show that given a 0 , we can always find a k such that this is the case. Well, since q = gcd(n, 2b), we can find a k such that a 0 + 2kb ∈ [0, q) (mod 2n), and then since are working under the assumption b − m ∈ [0, n − q] (mod 2n), we will also have a 0 + 2kb + b − m ∈ [0, n) (mod 2n) as desired. Thus we can swap parity along all (1, b)-orbits as desired.
Finally, in step 3, we reverse step 1. That is, we swap parity along all the pairs of (0, n)-orbits used in step 1 to return to a coloring of the (0, n)-edges which follows parallel protocol x 0 .

Generators from 2Z
The only generators left to consider are those of the form (0, b) ∈ S for b even. Fix such a b. In our treatment of these, we will often work in one Zorbit at a time. We therefore start by establishing a key lemma in the setting of Z-actions. For this, we'll start with a purely combinatorial game.
Suppose we have a finite graph consisting of a single path v 0 , . . . , v l of length l, where v i and v j are adjacent if and only if |i − j| = 1. Suppose the vertices of this path are labeled with two colors, say 5 and 6. In one move, we are allowed to pick two adjacent vertices of the same color, and change both of their colors. Some examples of moves are shown in Figure 11. Figure 11: An example of a sequence of moves in our game with l = 4. When a pair of adjacent vertices is circled, it indicates that our next move will be changing the color on those vertices. We sometimes draw two moves as occuring in a single step if the pairs of vertices they involve are disjoint. Note also that this sequence provides and example for Lemma 13.
Lemma 13. If either l is even and v 0 and v l have different colors, or l is odd is v 0 and v l have the same color, then there is a sequence of moves which result in v 0 and v l switching their colors, but all other vertices keeping the same color.
Proof. We proceed by strong induction on l. The base case l = 1 is clear. Now suppose l > 1. By hypothesis, there must be some pair v i , v i+1 of adjacent vertices with the same color. Pick the pair with i minimal. Our first move will be changing the colors on this pair.
If i = 0, then v 0 is now the color we want it to be. If i > 0, then we now want to change the colors on v 0 and v i , but leave the vertices between them the same color. By the minimality of i, though in our initial coloring, v 0 and v i had the same color if and only if i is even. Thus, after our first move, the path from v 0 to v i satisfies the hypotheses of the lemma, so by the inductive hypothesis, we can indeed change the colors of v 0 and v i and leave the vertices between them the same color.
Essentially the same thing happens for the path from v i+1 to v l . We'd like to check that in our initial coloring, v i+1 and v l had the same color if and only if l − (i + 1) is even. We know as in the previous paragraph that v i+1 has the same color as v 0 if and only if i + 1 is odd. Also by hypothesis, v l has the same color as v 0 if and only if l is odd. Combining these gives us what we want.
We now turn to the promised Z-action setting. Let X be an orbit of some Z-action a . Let n , b > 0 with n odd, b even, and furthermore assume gcd(n , b ) = 1. Consider edge colorings of the graph G(a , {±n , ±b }) X .
Since n is odd, let us always use the odd protocol for coloring the n -edges with the colors 1 and 2. Now a 2 coloring of the b -edges, say with the colors 5 and 6, is completely determined by the colors it gives to the edges (k · x 0 , (k + b ) · x 0 ) for k = 0, . . . , b − 1, where here x 0 ∈ X is as before some fixed base point. Consider this sequence of colors, say c(0), . . . , c(b − 1), as a map c : Z/b → {5, 6}. We will say this coloring follows protocol (x 0 , c). We will also say c is the code of this coloring relative to x 0 . For α ∈ {5, 6}, let ¬α denote the element of {5, 6} not equal to α. Define the map c : Z/(2b ) → {5, 6}. By c(k) = c(k) if k ∈ [0, b ) (mod 2b ) and c(k) = ¬c(k) otherwise. c will be called the double code of our coloring relative to x 0 . Of course, it carries the same information as c, but will sometimes be easier to work with. The point is that c(k) is the color received by the edge (k · x 0 , (k + b ) · x 0 ) for each k ∈ Z.
Of course, we are interested in using the n -edges to transition between protocols for the b edges. Because of Proposition 1, we should not expect arbitrary transitions to be possible. We do however still have: Lemma 14. In the above setting, if c, c : Z/b → {5, 6} differ in an even number of entries, we can transition between protocols (x 0 , c) and (x 0 , c ).
We first note the following special case of the lemma: Lemma 15. Suppose k ∈ Z/(2b ) is such that c(k) = c(k + n ). Then we can transition from the protocol (x 0 , c) to the protocol (x 0 , c ), where c = ¬c at k and k + n , and c = c everywhere else.
Proof. Let f be the b -orbit of k · x 0 . We want to apply Lemma 4 to change parity for f and n · f . Observe that since b is even and n is odd and we use an odd protocol for the n -edges, all of the n -edges from f to n · f have the same color. This will give condition 5 of the lemma. Our hypothesis on the double code gives condition 3. Figure 12 shows the technique used in Lemma 15. Now we can establish Lemma 14: Proof. Of course it suffices to consider the case where c and c differ in exactly two entries, say at r 1 , r 2 ∈ Z/b .
We first find a sequence k 0 , . . . , k l ∈ Z/(2b ) with the following properties: in Figure 13. In it, once again following the procedure from Subsubsection 4.3.1, we use the (1, m) edges to swap parity along certain pairs f, (1, m) · f of (0, b)-orbits. Specifically, we will do this for each f containing a point of the form (0, kb ) · x 0 . Note that here the condition m < b (mod 2b ) is used to get condition 3 from Lemma 4. The result of this step is shown in part (b) of the figure. It should be clear that, after making, it, the (0, b)-edges in the orbit Z · x 0 follow our desired protocol (x 0 , c 0 ), but not those in the orbit (Z + (1, 0)) · x 0 . Instead, on this orbit, the (0, b)-edges follow the protocol (x 0 , c 0 ), where c 0 (m) = 6, but c 0 = 5 everywhere else. In particular, since m = 0 (mod b ), c 0 and our desired code c 0 differ in exactly 2 places. (And their corresponding double codes differ in 4 places.) For step 2, within this second Z-orbit, we will work separately within each qZ-orbit to correct this. Fix some such orbit qZ · x 0 , where x 0 = (1, r) · x 0 for some 0 ≤ r < q. Within this orbit, the generators (0, b) and (0, n) behave like b and n , and these satisfy the hypotheses used for the b and n from the setting of Lemma 14.
Using the terminology from that setting, let c be the code of our coloring for this orbit relative to x 0 following step 1, and c the code relative to x 0 that we want to transition to.
For the sake of clarity, we remark that these are codes with domain Z/b , while the codes c 0 and c 0 have domain Z/b . While this is an important difference to keep in mind, what follows will still make sense since b is an odd multiple of b .
Then, the corresponding double code c is given by c(k) = c 0 (r + kq), and likewise for c and c 0 . Now q is coprime to 2b since the former is odd and the latter is a power of 2. Therefore, as k ranges over Z/(2b ), r + kq will take every value mod 2b b /b times. Therefore, since c 0 and c 0 differ in 4 places, c and c differ in 4b /b places, and so c and c differ in 2b /b places. This is even, so by Lemma 14 a transition is possible, and we are done.
This was the last type of generator we had to deal with, so we can record our result: Of course, Lemmas 11 and 16 together complete our proof of statement 2 of Theorem 2, and hence of Theorem 2.