# Which 3-regular graphs are Schreier coset graphs?

Given a group $$G$$ and a subgroup $$H$$ the Schreier coset graph (w.r.t. some set $$S$$ of $$G$$) is the directed (and labelled) graph whose vertices are the cosets of $$H$$ (i.e. the set $$G/H$$) and $$x \sim y$$ if there is a $$s \in S$$ so that $$x = sy$$.

When $$S$$ is symmetric (i.e. $$s \in S \implies s^{-1} \in S$$), then one can associate to this graph an undirected graph (by replacing the two edges with opposite directions and labels $$a$$ and $$a^{-1}$$ by an undirected edge). Note that it could happen that $$a = a^{-1}$$ which is unproblematic unless the edge makes a loop. So in the undirected graph one needs to distinguish the degree 2 loops (which come from $$a$$ and $$a^{-1}$$ acting trivially on the coset $$x$$) and the degree 1 loops (which come from $$a = a^{-1}$$ acting trivially on the coset $$x$$).

Using this construction (and this convention for loops), a Schreier graph is always a regular graph (of degree $$|S|$$).

Given an even degree regular graph (without "degree 1" loops), then it is possible to find a group $$G$$ (a free group actually), subgroup $$H and set $$S$$ so that this graph is a Schreier coset graph. This is a result of J.L.Gross, see https://doi.org/10.1016/0095-8956(77)90068-5.

Question: Assume $$\Gamma$$ is a an 3-regular graph. What are the necessary conditions for $$\Gamma$$ to be a Schreier Graph?

I'm fine with any answers which assumes that $$\Gamma$$ is loopless. Sufficient conditions are somehow much more easy to come by (see examples below).

A combinatorial way to ask the question is to find a labelling of the directed graph underlying $$\Gamma$$ so that $$a^{-1}$$ always labels an edge in the opposite direction to $$a$$ (with the pesky exception of those degree 1 loops).

Example (of a sufficient condition for a loopless graph): if the graph has a perfect matching (a.k.a. 1-factor), then you can label these edges by an element $$a = a^{-1}$$. There only remains an even degree graph, so by the result of Gross you can get away with $$G = F * \mathbb{Z}_2$$ where $$F$$ is the free group mentioned above and $$a$$ is the generator (and only non-trivial element of $$\mathbb{Z}_2$$).

Example (continued): every 3-regular bridgeless (i.e. without a cut-edge) graph has a 1-factor (a result of Petersen again). So every 3-regular bridgeless graph is a Schreier graph. In particular, the Petersen graph (or any other snark) are Schreier graphs.

Note that an element $$a \in S$$ so that $$a \neq a^{-1}$$ need not always label a 2-factor of $$\Gamma$$. It just needs to label a spanning subgraphs whose connected components are either edges or cycles (so a mix of 1-factor and 2-factor).

[EDIT]

Non-example: There is an example of an 3-regular graph which is not a Schreier graph. It's sometimes called the "no perfect matching graph", see http://mathworld.wolfram.com/PerfectMatching.html (you have to remove three edges in order to make the graph on that page 3-regular).

This non-example builds a lot on the fact that there are many bridges.

[EDIT]

If there is a way to colour the edges in $$k$$-colours (and the graph is $$k$$-regular), then this gives a way to turn the graph in a Schreier graph. (Every element is so that $$a = a^{-1}$$ and the group $$G$$ is a free product of $$k$$ copies of $$\mathbb{Z}_2$$.)

[EDIT]

It thought that a result of M.Kano see https://doi.org/10.1016/0095-8956(86)90025-0 would give the necessary decomposition of the graph for odd degrees $$\geq 5$$, but this turns out to be incorrect.

Graphs which cannot be coloured are sometimes called of "class 2" (see Vizing's theorem). Although the Petersen graph (or any snark) is of "class 2", it is a Schreier graph (so being of class 1 is not a necessary condition).

• Are you asking only about infinite graphs? I'm not familiar with the result of Gross you mention, but for finite graphs I'm pretty sure it's false: a graph (finite or not) is a Schreier coset graph iff it is vertex transitive, and there are surely even degree regular finite graphs that aren't vertex-transitive... – Joshua Grochow Dec 5 '17 at 14:25
• @JoshuaGrochow. No, a Schreier graph doesn't have to be vertex-transitive (the group acts on the vertices of the Schreier graph but does not preserve the graph structure). For instance, the Schreier graph of the action of the dihedral group of order 6 (with a generating pair $(a,b)$ of elements of order 2), modulo the subgroup $\langle b\rangle$, consists of 3 consecutive vertices $\bullet-\bullet-\bullet$ (with a self-loop at each extremity); it's not vertex-transitive. – YCor Dec 5 '17 at 14:28
• @JoshuaGrochow no I don't think so. Start from 2 hexagons with 2 colors (each is a Scheier graph of a dihedral group). Choose a bad bijection between their vertices to join them with a third color, e.g., $123456\mapsto 124635$. Then this is by construction a Schreier graph (of a free product of 3 cyclic groups of order 2, or a suitable cyclic quotient), but it's not vertex-transitive, because it has a unique square. – YCor Dec 5 '17 at 18:30
• @JoshuaGrochow : I edited in a link to the original paper of J.L. Gross, if you want to have a look. There are definitively 4-regular graphs which are not vertex-transitive, so vertex-transitive is definitively not a necessary condition. – ARG Dec 5 '17 at 19:10
• The following just appeared on arXiv (by P-H. Leemann), "We prove that every connected locally finite regular graph has a double cover which is isomorphic to a Schreier graph". He mentions that the case of even degree was done in Lubotzky's book "Discrete groups, expanding graphs...". – YCor Oct 14 '20 at 6:18

Here are some usefull facts, and some historical details.

Every $$2d$$-regular graph (without loops of degree 1) is isomorphic to a Schreier graph.

The results for finite graphs is due to Gross. The result for locally finite graphs follows by compacity and was probably one of this well-known "folklore result" for long. To my knowledge, the first written proof of it can be found in "Some problems of the dynamics of group actions on rooted trees" by R. Grigorchuk 2011. But it has since be "reproven" many times (by J. Cannizzo in 2013, in my own phd thesis around the same time, ...).

A (2d+1)-regular graph (without loops of degree 1) is isomorphic to a Schreier graph if and only if it has a perfect matching.

This follows from the previous fact. See for example ARG's answer.

Every countable vertex transitive graphs is isomorphic to a Schreier graphs.

The finite case was done by C. Godsil and G. Royle in 2001. I did (circa 2013) the locally finite case in my phd thesis, using results of Aharoni on matchings in infinite graphs. I believe that an independant proof of it was published in 2016 by another author, but sadly cannot remember more details. Finally, the countable case was done by M. Hamman and A. Wendland in the appendix of https://arxiv.org/abs/2007.06432

Up to a double cover, any locally finite regular graphs is isomorphic to a Schreier graph.

See https://arxiv.org/pdf/2010.06431.pdf, which is intended as a small note for reference.

Here is the skeleton of the proof. Let $$G$$ be a locally finite graph. If $$G$$ is bipartite, put $$K=G$$. Otherwise, put $$K=G\times C_2$$. Then $$K$$ is connected, bipartite (and hence without loops of degree 1), regular and covers $$G$$. Since $$K$$ is bipartite and regular it has a perfect matching. The desired result follows.

[community wiki since it's my own question]

The answer is actually simple once the convention on degrees is clear (which it apparently was not at the time of writing)

Answer: If $$k$$ is odd, a $$k$$-regular loopless graph is a Schreiers graph if and only if it has a matching.

First note that elements $$a \in S$$ so that $$a \neq a^{-1}$$ necessarily create a 2 factor. There three cases (here $$x$$ is a vertex, or a coset):

(1) $$a \cdot x = x$$ this makes a loop and also a loop in the "reverse" direction since then $$a^{-1} \cdot x =x$$.

(2) $$a \cdot a \cdot x = x$$, this is an interesting case [and the main cause of my confusion], because it will often be displayed in the literature as a single-edge although there should be another edge coming from the fact that $$a^{-1} \cdot a^{-1} \cdot x = x$$

(3) $$a$$ makes a longer cycle before coming back to $$x$$.

If there are no loops then elements $$a \in S$$ so that $$a = a^{-1}$$ can only make a matching of the graph.

Hence, under the convention for degree taken, loopless Schreier graphs need to have a matching.

On the other hand, if you have a matching then you can label this matching by an element $$b$$ with $$b=b^{-1}$$. The rest of the graph is $$2r$$-regular for some $$r$$, so you can find $$r$$ disjoint $$2$$-factors and label them with $$a_1,a_2,\ldots,a_r$$.

My confusion came from diagrams such as the one below. Edge with arrows indicate how an element acts. Edge without arrow means the element switches both ends of that edge. This completely determine the action, but it gives a false impression on the vertex degree. In the picture below the vertices have degree 5 or 6 (depending on whether $$c= c^{-1}$$ or $$c \neq c^{-1}$$).

• I've never understood why people want to collapse double edges to single ones when defining Cayley and Schreier graphs. The correct definition of a Cayley graph is that it's the covering space of the rose corresponding to the kernel of the natural map to your group. Similarly, the correct definition of a Schreier graph is that it's the covering space of the rose corresponding to the preimage of the subgroup $H$. According to that definition, your single edges should actually be double, with arrows pointing in both directions. – HJRW Jul 13 '20 at 17:35
• I think that was exactly the source of my confusion: I focused on the diagrams that were drawn of Schreier graphs (and the definitions which accompany them) instead of looking at the functorial definitions (like yours ). (Just to make sure we are on the same page: the picture I put at the end was meant as an example of a badly made picture.) – ARG Jul 13 '20 at 20:04