6
$\begingroup$

In the mathematical literature there are examples of graphs where the vertices form a group - the most famous example are probably the Cayley graphs.

I'm curious about a somewhat dual situation. Are there examples in mathematics of multigraphs (many possible edges between the same two vertices), where the set of edges between two vertices forms a group in an interesting way?

I'd be particularly interested in the case of an abelian group, that could be interpreted as "the sum of two edges is again an edge".

$\endgroup$
3
  • 3
    $\begingroup$ It sounds like you might be thinking about the concept of a group action. In a Cayley graph, while it may be true that there is a bijection between group elements and vertices, I think it is an over-interpretation to state this as "the vertices form a group". A much more useful interpretation -- in fact, a theorem -- is that the group acts on its Cayley graph, and the action restricted to the vertex set is transitive and free. $\endgroup$
    – Lee Mosher
    Feb 9, 2022 at 13:52
  • 1
    $\begingroup$ And, by the way, if you are not too careful about your terminology then in some sense any set forms a group. $\endgroup$
    – Lee Mosher
    Feb 9, 2022 at 13:56
  • $\begingroup$ @LeeMosher That is an interesting idea. Are there examples of multigraphs where the sets of edges between two vertices all admit actions of the same group (in an interesting way)? $\endgroup$
    – geodude
    Feb 9, 2022 at 15:01

1 Answer 1

5
$\begingroup$

While this is well outside my area and so I wouldn't be fully comfortable to say "no", I think this extended comment may be of some interest.

The idea of attaching group elements to vertices is "in the spirit" of other mathematical ideas, in a way that's harder to interpret for edges. The Cayley graph originates in geometric group theory, which aims to study a group by considering spaces on which the group acts. The rough* idea of the Cayley graph is to turn the group itself into a space, since it already has an action. Well, at minimum, such a space must have group elements as its points! And it is reasonable to think about vertices of a graph as points of a space.

When you flip it around and ask "What are the edges of a graph doing?" the answer is that they are describing the existence of "a relationship" between two vertices. For the Cayley graph this means that two vertices differ by a generator, but of course there are all sorts of other relationships that may be possible.

Critically, though: note that this answer is really about the set of edges between two vertices. The set of edges is much less coherent as a "uniform" collection. There is a reason that when a group is represented as a category, then yes the group elements become edges (arrows), but there is only one vertex (object)!** Doing this "uniformizes" the edge set by forcing all edges to have the same endpoints.

The way I see it, what a group really "wants" to do as a collection of edges is not to uniquely label every edge of a graph, but rather to label the collection of edges that originate at a particular vertex. After all, the whole point of a group is to act on something (usually by symmetries); so it is natural to ask what the action does. This gives rise immediately to a graph structure (with edges $x\to gx$), and edges are labelled by group elements, but of course if there is more than one vertex then each element appears many times.

(* "Rough" in the sense that literally speaking, this is at odds with Lee Mosher's interpretation, and theirs is better. The distinction that Mosher is making is important: if you start with a graph that is unlabelled but I tell you it is a Cayley graph $\Gamma(G,S)$, you will not be able to find the identity element, even if you know $G$ and $S$, and even if the edges are already $S$-labelled. So we are not literally making $G$ into a space, but only making a space that "looks like" $G$.)

(** But, you may also be interested in groupoids.... It's not an answer to your question since it really is a cheat; groupoids are more or less defined to be the edge sets of graphs. Well, that's not quite true, but it's not far off.)

$\endgroup$
2
  • 1
    $\begingroup$ "if you start with a graph that is unlabelled but I tell you it is a Cayley graph, you will not be able to find the identity element", this is a really good point! $\endgroup$ Feb 9, 2022 at 14:28
  • 2
    $\begingroup$ Indeed it is (thanks Mosher!) and I will add that this distinction is precisely what one should think of when hearing the phrase "free transitive action". (And while we're in this circle of ideas: I also feel like I could have saved a lot of trouble if someone had sat me down one day and told me that free and transitive were the group-action analogues of injective and surjective, respectively.) $\endgroup$ Feb 9, 2022 at 14:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .