Today my 15th posting to the arXiv went live! I intend to write about some of the other aspects of that paper elsewhere (possibly another post on this blog), since I think it really clarified something important for me, but I wanted to explain one insight that made a mysterious thing less mysterious to me: “double cosets”.

Graphs

There are (fortunately or unfortunately) too many ways to think of graphs in mathematics. For me, today, a graph is a thing $\Gamma$ with a set of “vertices” $V\Gamma$ and a set of “oriented edges” $E\Gamma$. Formally if $e$ is an oriented edge, it has an “initial” or “source” vertex and a “terminal” or “target” vertex. You might draw a graph by making a little dot for each vertex and a little arrow between vertices for each edge, with the arrow pointing towards the target vertex and away from the source vertex. We are considering “graphs” and not “directed graphs”, so each oriented edge has a friend, which is “the same edge with the opposite orientation”, i.e. you swap which vertex is considered initial and which terminal.

Sometimes the source and target vertex may be the same, in which case you might draw a little loop. Or there may be multiple oriented edges with the same intial and terminal vertices, in which case you might draw parallel copies. A graph in which neither of these possibilities actually occur is called a simplicial graph. (The word “simplicial” feels like it has to do with “simplicity” and it might, but it more directly has to do with the kind of mathematical shape called a “simplex”.)

For a simplicial graph, the set $E\Gamma$ may be profitably identified with a subset of $V\Gamma \times V\Gamma$; that is, an edge $e$ is “the same” as the pair of its source and target vertices.

Cosets and group actions

If you got to this section and felt wait, what’s a group again?, go read the linked post; that’s why I wrote it!

Subgroups

A subset $H$ of $G$ is a subgroup if it is closed under the group operation and inverses. That is, if $g$ and $h$ belong to $H$, $gh$ should also belong to $H$, as should $h^{-1}$.

Stabilizers

I initially defined group actions in my post So what’s a group again? but just to remind you, a (left) action of a group $G$ on a set $S$ is a function $G \times S \to S$ sending $(g,s)$ to $g.s$ with the property that $g.(h.s) = (gh).s$.

Anyway, given a point $s$ in $S$, the stabilizer of $s$, written $\operatorname{stab}(s)$ is the collection of $g$ in $G$ such that $g.s = s$. Notice that if $g.s = s$, then $g^{-1}.s = g^{-1}.(g.s) = (g^{-1}g).s = s$, and similarly stabilizers are closed under the group operation.

So: in a group action, the stabilizer of a point is a subgroup.

Orbits

Also given a point $s$, the collection of points $g.s$ (in other words, the set of elements $s'$ for which there exists $g$ such that $g.s = s'$) is called the orbit of $s$ under $G$, sometimes written $G.s$.

Cosets

If $H$ is a subgroup of $G$, the left coset of $H$ in $G$ associated to $g$ in $G$, written $gH$ is the set of elements of $G$ which may be written as $gh$ with $h$ in $H$. The right coset, $Hg$, is defined analogously as the set of elements which may be written as $hg$, again with $g$ fixed but $h$ variable.

The collection of all left cosets of $H$ in $G$ is denoted $G/H$, while the collection of all right cosets is $H\backslash G$.

Groups only really act on their cosets

The orbit–stabilizer theorem says that if $G$ acts on a set $S$ (on the left), for each $s$ in $S$, if we write $H = \operatorname{stab}(s)$, the orbit of $S$ may be identified with $G/H$, in the sense that there is a bijection between the two. So in a certain precise sense, the only transitive actions of a group (i.e. the orbit of any point is the entire set) are on its cosets.

So, in this sense, I have a way of thinking about cosets as “orbits” and subgroups as “stabilizers”.

Also, given a subgroup $H$ and an element $g$, we can form the conjugate $gHg^{-1}$, which is what it looks like, the set of elements of the form $ghg^{-1}$ with $h$ in $H$ variable but $g$ fixed.

Notice that if $H$ is the stabilizer of a point $s$, then $gHg^{-1}$ is the stabilizer of $g.s$: indeed, given $h$ in $H$ we compute

[ ghg^{-1}.(g.s) = g.(h.(g^{-1}g).s) = g.(h.s) = g.s ]

Notice also that if $H$ and $K$ are subgroups of $G$, we may consider elements which can be written as $hgk$ for $g$ fixed but $h$ in $H$ and $k$ in $K$ variable. This is a double coset, and the set of double cosets as $g$ varies is denoted $H\backslash G / K$.

Group actions on graphs

A group $G$ acts on a simplicial graph $\Gamma$ when it acts on the vertex set $V\Gamma$ and preserves adjacency: that is, if $(v,w)$ is an oriented edge, then $(g.v, g.w)$ is an oriented edge.

Double cosets are edges

Notice that if $e = (v,w)$ is an oriented edge in a graph $\Gamma$ equipped with an action of $G$, where the stabilizer of $v$ is $H$ and the stabilizer of $w$ is $K$, the orbit of the oriented edge $e$ is the set of edges of the form $(g.v, g.w)$. By the orbit–stabilizer theorem, such an edge is in the identity double coset $H1K$, since the orbit of $v$ is $G/H$, the orbit of $w$ is $G/K$, and two vertices $gH$ and $g'K$ in the orbit of $v$ and $w$ are in the orbit of $e$ when they have representatives $gh$ and $gk$ with the same element $g$, in which case $h^{-1}g^{-1}gk$ obviously belongs to $H1K$.

Previously I had not understood how to think of double cosets “geometrically” in the same way that I thought about cosets as orbits, subgroups as stabilizers, and conjugation as stabilizing other elements in the same orbit.

Abstract groups act on graphs

If $G$ is a group, it acts on many simplicial graphs! Indeed, just take a collection of subgroups and have the vertex set be the disjoint union of their cosets. Then just choose arbitrarily some double cosets to be the edge orbits and voila!

One example is a Cayley graph. Here you act on cosets of the “trivial” subgroup (comprising just the identity element of $G$). So vertices of the graph are elements of $G$, as are double cosets. Typically Cayley graphs are required to be connected (in the topological sense, sure, but also just in the sense that you can imagine “walking” in the graph between any two vertices across a finite number of edges), for which the set of elements chosen to be the edge orbits must generate the group. Unwinding the definitions a bit, you see that such a graph is connected precisely when the set of edge orbits $S$ has the property that any group element $g$ may be written as $s_1^{\pm}\cdots s_n^{\pm}$, where each $s_i$ belongs to $S$.

Where can I learn more?

At the high end of the spectrum, some friends of mine and I combined the insight I alluded to in this blog post with a bit more topology and some ideas of Christian Rosendal to produce a preprint, which hit the arXiv today!

If you’ve forgotten what a group is, you can always refresh your memory.

For Cayley graphs, I recommend Groups, Graphs and Trees as well as Office Hours With a Geometric Group Theorist.

For more scholarly stuff, Dicks and Dunwoody have a book titled Groups acting on Graphs. That book references the Bass–Serre theory of groups acting on trees, for which the initial reference is a book called Trees.