I had the following considerations:

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.

  • $\begingroup$ 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. $\endgroup$ – Joppy Dec 4 '17 at 7:24
  • $\begingroup$ 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. $\endgroup$ – Joppy Dec 4 '17 at 7:26
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ Thank you very much, your construction does seem to make more sense. Unfortunately, the things will depend on the orientation of the edges, so actually we investigate directed graphs. Still interesting. $\endgroup$ – S. M. Roch Dec 4 '17 at 18:39
  • $\begingroup$ Actually, almost nothing depends on the orientation of the edges, and there is a way to construct the edge space without choosing an orientation, but picking a basis of that space is the same as choosing an orientation. $\endgroup$ – Joppy Dec 4 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.