# Commensurability of 2-colorings of finite 4-valent graphs

It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph $X''$ which is a regular covering space of both; that is, $X$ and $X'$ are commensurable. (To see this it suffices to see that both graphs are quotients of the 4-valent tree by subgroups of finite index in $F_2$; equivalently one can build covering maps from $X$ and $X'$ to the 8 graph).

I am interested in a refinement of this statement (or its impossibility): given two colourings of the vertices of $X,X'$ as above by two colours (say red and black), is there a third finite 4-valent graph $X''$ with covering maps $\pi:X''\to X,\, \pi':X''\to X'$ and a red/black colouring such that (i)for any $x\in X$ (resp. $x'\in X'$) all vertices in the fiber $\pi^{-1}(x)$ (resp. $(\pi')^{-1}(x')$ are of the same colour and (ii) this coulour is the same as that of $x,x'$ in the original covering of $X,X'$? Of course one can rephrase this in terms of colourings on the 4-valent tree preserved by two free group actions.

I would be happy to know if such colourings exist (i.e. without specifying colouring on $X,X'$, is there a coloured $X''$ with $\pi,\pi'$ as above satisfying (i)?) and if there does, to learn about any quantitative results on the number of such colourings that might exist.

• One quick observation is that if $X$ is all red and $X'$ is all black then no $X''$ exists. – Neil Hoffman Sep 19 '13 at 11:31
• @Jean : by 2-coloring do you mean (as is usual in graph theory) that adjacent vertices have distinct colors ? – BS. Sep 19 '13 at 12:06
• @BS: No, you can allow neighbouring vertices to have the same colour. On the other hand, to answer Neil Hoffman's comment, I am not interested in the "trivial" colourings where all vertices have the same colour. – Jean Raimbault Sep 19 '13 at 12:27

Here are two commensurability class invariants for these graphs that might help you with the refined statement you are looking for. The general answer to the question as stated is no, often $X''$ does not exist.

Assume $X$ and $X'$ are commensurable. $\pi: X'' \rightarrow X$ is degree $n$ and $\pi': X'' \rightarrow X'$ is degree $n'$.

Also, let's define the following: r (resp. r', r''), the number of red vertices in X (resp. X',X''), b (resp. b', b''), the number of black vertices in X (resp. X',X'').

Then $r'' = n\cdot r$, $b'' = n\cdot b$, $r'' = n'\cdot r'$, $b'' = n'\cdot b'$, so $r/b=r'/b'=r''/b''$, and so the ratio of red/black vertices is a commensurability class invariant.

However, consider the graphs as directed graphs with two edges coming into every vertex and two edges coming out. Although there is some freedom in this assignment, let's address that later. Given an edge labelling by directions, we can also define (RR,RB,BR,BB) by the counts of the directed edges that connect red vertices to red vertices, red vertices to black vertices, black to red and black to black respectively.

This is a vector in $\mathbb{Q}^4$ and by a similar argument to that above a necessary condition for $X$ and $X'$ to be commensurable is that for some pair of labelings of the edges of $X$ and $X'$, the vectors (RR,RB,BR,BB) and (RR',RB',BR',BB') corresponding to each labeling must be related by rational scalar multiple. Although this might be computationally expensive to determine, we of course have the weaker invariant that (RR,BB) and (RR',BB') must be related by a rational multiple.

• Thank you for the idea, I'll try to play around with it and see if it leads to something. I guess that in the first sentence of your last paragraph you meant to write " and by a similar argument to that above it is a commensurability invariant when normalized by dividing by the number of edges (?)": it seems to me that the 4-tuple is an invariant of the colouring together with the orientations of the edges. Why not consider the triple (BB,BR/RB,RR) instead? (it seems to contain already more information than – Jean Raimbault Sep 19 '13 at 14:53
• @JeanRaimbault Thanks for the suggested edit. I tried to clean up the last paragraph to reflect this. Also, you are right that you can avoid the ambiguities of labelling the edges with directions and just put the number of edges in three categories: RR, RB, BB. Dividing out by the number of edges is also a nice, concise way to define the invariant. – Neil Hoffman Sep 20 '13 at 0:09