# Decomposition of cycle space of a graph

Let $G=(V,E)$ be a simple graph, $n=|V|, m=|E|$. The automorphism group of $G$ is a subgroup of $S_n$, namely

$$\operatorname{Aut}(G) = \{\phi: V \to V \textrm{ bijective} : (v, w)\in E \Leftrightarrow (\phi(v), \phi(w))\in E\}$$

$\operatorname{Aut}(G)$ is acting on the set $E$ by $\pi.(v, w) = (\pi(v), \pi(w))$.

$\mathbb{C}^E$ is the complex edge space and

$$C := \operatorname{span}(\{e \mapsto \delta_{e \in M} : M\subset E \textrm{ simple cycle}\})$$

should be a subspace of $\mathbb{C}^E$. The group action of $\operatorname{Aut}(G)$ on $M$ yields a group action on $\mathbb{C}^E$. As far as I have considered, $C$ is closed under this action and the action is linear. So we get a representation of $\operatorname{Aut}(G)$:

$$D: \operatorname{Aut}(G) \to GL_{\mathbb{C}}(C)\\ D(\pi)(v) = \pi.v$$

Applying the theorems of Maschke and Schur yields a unique decomposition of the module $C$ into simple submodules

$$C = C_1 \oplus ... \oplus C_r$$

EDIT: This is wrong: Hence we get a partition of $\{e \mapsto \delta_{e \in M} : M\subset E \textrm{ simple cycle}\}\subset C$ and therefore a partition of the set of simple cycles in $G$.

Does anyone know how this partition looks like or whether there are any nice properties? References or further ideas or comments on the construction above are also welcome.

• I don't think this is how the cycle space is defined over $\mathbb{C}$, that definition will only work over $\mathbb{F}_2$. For example, if you take $G$ to be a square with one diagonal added, the dimension of the cycle space should be $5 - 4 + 1 = 2$. However, there are 3 simple cycles in $G$, so the $C$ you defined will have dimension 3. – Joppy Dec 4 '17 at 7:24
• As another comment, one would usually not expect the decomposition of a representation to act nicely with respect to a basis: if $e_1, \ldots, e_n$ is a random basis of $V$, and $V$ decomposes as a representation of some group $\Gamma$ as $V = V_1 \oplus \cdots \oplus V_r$, it will be highly unlikely that $V_i$ will be spanned by any subset of the $e_i$, the decomposition will be more complicated. – Joppy Dec 4 '17 at 7:26
• @Joppy: Thank you for your comments. First comment: Yes, the cycle space is usually defined over $\mathbb{F}_2$. I wanted to make it a $\mathbb{C}$ vector space, since this enables me to apply Maschke and Schur (Maschke works with $\mathbb{F}_2$ if $\mathbb{Z}/2\mathbb{Z}$ is not a subgroup of $\operatorname{Aut}(G)$, Schur only for algebraic closed fields AFAIK). Secound comment: Yes you're right. Actually the question about a partition of the simple cycles was an addition to make it more combinatorical. It would be nice to know whether the decomposition of $C$ is interesting itself. – S. M. Roch Dec 4 '17 at 8:45

As I noted in the comments, this is not really the correct analogue of cycle space for anything except the field $\mathbb{F}_2$. Here is the "correct" or rather, most useful, definition.
Let $F$ be any field, and $G = (V, E)$ be a simple undirected graph. Pick any orientation of each edge of the graph, and let $\overline{E} \subset V \times V$ be the set of oriented edges: write $(u, v)$ for an edge $u \to v$. Then we can define the edge space to be the vector space with the basis of oriented edges: $\mathcal{E} = \mathrm{span}_F\langle (u, v) \mid (u, v) \in \overline{E}\rangle$. We also have the vertex space $\mathcal{V} = \mathrm{span}_F\langle v \mid v \in V\rangle$, and a boundary map $\partial: \mathcal{E} \to \mathcal{V}$, defined on an oriented edge by $\partial(u, v) = v - u$.
If a linear combination of edges form an oriented cycle (add all the edges up, adding signs as necessary), then $\partial$ applied to them will be $0$. So, the cycle space of $G$ is $\mathcal{C} := \ker \partial \subseteq \mathcal{E}$. From this definition, it is already possible to show that $\dim \mathcal{C} = |E| - |V| + C(G)$, where $C(G)$ is the number of connected components of $G$.
The graph automorphism group $\mathrm{Aut}(G)$ act on both $\mathcal{V}$ and $\mathcal{E}$ in the obvious way, and so the vertex space and edge space each become representations. Furthermore, $\partial$ is a homomorphism of representations, so the cycle space $\ker \partial$ is a subrepresentation of $\mathcal{E}$.
Now, if we take $F = \mathbb{F}_2$ in the above definition, then we get the usual definition of cycle space. However, as you pointed out, the representation theory over $\mathbb{F}_2$ will probably not be semisimple. If we take $F = \mathbb{C}$, we should get nicer representation theory, and it will be possible to decompose $\mathcal{C} = X_1 \oplus \cdots \oplus X_r$, where each $X_i$ is an irreducible representation of $\mathrm{Aut}(G)$. However, this decomposition will probably not partition the edges, except in silly cases like when there are different connected components.