Groups and graphs (and computation)

Graphs in group theory

Given a group G, or more specifically a finite set S of generators for G, one can form the Cayley graph \mathrm{Cay}(G,S) by taking the vertex set to be the set of group elements, and adding an edge vw iff v = ws for some s \in S.

One can then attempt to study algebraic properties of the group by looking at properties of (one of) its Cayley graph(s). In the case of an infinite group G, one can show that any two Cayley graphs, i.e. the Cayley graphs associated to any two sets of generators, have the same coarse geometry (in the sense of quasi-isometry—see the post on geometric group theory), so that the coarse geometric properties of any Cayley graph can be considered to be intrinsic geometric properties of the group, rather than properties of any particular presentation thereof. Indeed, this is the key insight that drives geometric group theory.

One particularly striking example where such geometric methods seem to yield great insight with much less pain than directly algebraic ones is in the case of free groups and their automorphism groups, which may be thought of geometrically as fundamental groups of bouquets of circles. This is equivalent to the Cayley graph viewpoint: the Cayley graph is the universal cover of the bouquet of circles. Automorphisms of the free group then correspond to homotopy equivalences of the bouquet of circles, and arguments about the automorphism group can be conducted in terms of these homotopy equivalences, leading to such results as classifications and characterizations of these automorphisms analogous to the classification of mapping classes of surfaces.

The same arguments apply to finite groups, although in this case the graphs are finite, and so quasi-equivalent to trivial graphs (i.e. the graph with one vertex and no edges), and geometric group theory has nothing more to say. From this point of view, finite groups are, in a very precise sense, virtually trivial. I do wonder though: can the theory of finite graphs, itself a rather rich area of combinatorics, be fruitfully used to say / argue interesting things about finite groups?

Graphs also appear in group theory in the notion of graphs of groups which is fundamental to the Bass-Serre theory of groups acting on simplicial trees. Here the graph acts essentially as a book-keeping mechanism to record the structure of the group as built up from vertex and edge stabilisers; these graphs have also been described as “one-dimensional analogues of orbifolds”. Group actions on trees appear in a variety of settings, for fundamental reasons I do not yet fully understand, and so this notion takes on some importance.

Groups in graph theory

Conversely, group theory can play a role in elucidating the structure theory of graphs. For instance, group theory played a significant role in Laci Babai’s recent breakthrough on graph isomorphism. Very roughly speaking, Babai’s algorithm relies on the heuristic that any isomorphism between graphs has to preserve degree. Thus, given a highly irregular graph, a brute-force search could actually be (sufficiently) efficient, since the number of possible isomorphisms is small relative to the number of vertices.

The problem, then, is if we have highly regular graphs. One way around this is to consider an equitable partition; but one may not always have one of these either. However, Babai proved that the only obstacle to the existence of such a partition is the existence of a large Johnson graph, and then used subtle structural results, of an essentially algebraic nature, on Johnson groups and how they sit inside larger (finite) permutation groups to obtain, constructively, either an isomorphism, or a certificate of non-isomorphism (a provably empty automorphism group.)

In the language of Babai’s preprint: “We shall certify both the presence and the absence of local symmetry. … If we don’t find local symmetry, we infer global irregularity; if we do find local symmetry, we either build it up to global symmetry (find automorphisms) or use any obstacles to this attempt to infer local irregularity which we then synthesize to global irregularity. Building up symmetry means approximating the automorphism group from below; when we discover irregularity,we turn that into an effective upper bound on the automorphism group . When the lower and the upper bounds on the automorphism group meet, we have found the automorphism group and solved the isomorphism problem.”

Here the group theory plays a key role in introducing more rigidity / structure to an otherwise fairly flexible and fluid structure. The structural theory of finite groups is used in a fairly strong way: indeed, the proof relies on the classification of finite simple groups, although the strict logical dependence is only on one of its corollaries (Schreier’s statement that the outer automorphism group of a finite simple group is solvable.)

A concrete application to coding theory

Group theory and graph theory both come into play in e.g. the construction and study of codes from Cayley graphs and Schreier graphs: the algebraic structure introduced by the group-theoretic construction of these graphs is very helpful in proving key desired properties of these codes.

Reading Notes

Tangles and a Structure Theorem

The result that we discuss here is Theorem 2.1 in Kawarabayashi and Wollan’s article, originally (3.1) in Graph Minors XVI, which plays a bigger role in the subsequent proof of the graph minor theorem than the “cornerstone” Graph Decomposition Theorem, and which indeed is used in the proof of said decomposition theorem.

This structure theorem states that given a H-minor-free graph G, for every tangle \mathcal{T} in G of order \geq \theta, there exists A \subset V(G) of size at most \alpha such that G - A has an \alpha-bounded \alpha-near embedding into a surface \Sigma into which H cannot be embedded, and this near-embedding captures \mathcal{T} - A.

Here capturing the tangle means that we can find a (\mathcal{T} - A)-central segregation \mathcal{S} of G - A (i.e. a partition \mathcal{S} of G - A into edge-disjoint societies such that no society in \mathcal{S} contains the large side of any separation in \mathcal{T}) with a bounded number of large vortices and vortex decompositions of bounded depth in our near-embedding.

What is a tangle?

A tangle \mathcal{T} of order \theta is a set of ordered separations (A,B) such that for every separation \{A, B\} of G of order \leq \theta, either (A,B) or (B,A) is in \mathcal{T}, and such that G[A_1] \cup G[A_2] \cup G[A_3] \neq G for any (A_i, B_i) \in \mathcal{T} with i=1, 2, 3. In short, a tangle is a “complete” (in the sense of the first axiom) set of small-order separations which leave a substantial part of the graph on the B side (in the sense of the second axiom.)

From the Structure Theorem to the Graph Decomposition Theorem

The structure theorem here plays a key role in Kawarabayashi-Wollan’s proof of the Graph Decomposition Theorem (which is essentially the same as Robertson-Seymour’s proof [?].)

Recall our last restatement of the Graph Decomposition Theorem; this we will prove by induction on |V(G)|. The structure theorem gives us (positive) constants \hat{\theta} and \hat{\alpha} such that, for every tangle of order \geq \hat{\theta}, G is \hat\alpha-close to having an \alpha-bounded \hat\alpha-near embedding into a surface \Sigma into which H does not embed, and this near-embedding H_0, H_1, \dots, H_m captures \mathcal{T}.

Choose \theta = \max(\hat\theta, 3\hat\alpha+1) and \alpha := 4\theta - 2 (\theta is chosen so that 3 + \hat\alpha \leq \theta and \hat\theta \leq \theta hold, and \alpha so that 3\theta - 1 \leq \alpha). For the base case, we observe that we may assume |V(G)| \geq \alpha, otherwise the result is trivially true.

We now induct by decomposing each vortex H_i in our near-embedding separately and putting the pieces together. The exceptional subgraph H_0 can be left as is; the small vortices can be split along society vertices; the large vortices can be split along vortices of the parts of its vortex decomposition (see p.9 of Kawarabayashi and Wollan for details); inductively we obtain the desired tree-decompositions for each smaller part, and then piece them together by connecting one of their vertices to the new root v_0 (representing $latex G[V(H_0) \cup \hat{A}$), we may check that the torso of the new part V_0 can be \alpha-nearly embedded as desired.

Reading Notes

Vortices and Graph Decomposition

At the heart of the proof of Seymour and Robertson’s graph minor theorem lies the graph decomposition theorem (commonly referred to as the graph structure theorem), which is the main result of Graph Minors XVI and which Seymour and Robertson describe as “the cornerstone theorem of the [Graph Minors] series”. This theorem states that any graph G with no H minor can be decomposed as into graphs H_i which (almost) constitute “obvious” obstructions to a H minor because there exist surfaces \Sigma_i into which H_i can (almost) be embedded, but H cannot.

Two restatements

More precisely, any H-minor-free graph is the result of clique-sums, with join sets of size \leq\alpha, of graphs H_i which are \alpha-close to admitting a totally bounded \alpha-near embedding into a surface \Sigma into which H does not embed.

Note that a tree decomposition is precisely a clique-sum of its parts torsos along their respective torsos intersections. This motivates an even more precise re-statement of the theorem: any H-minor-free graph G has a bounded number \theta of apex vertices Z, and a rooted tree decomposition \{V_t \:|\: t \in T\} with root r such that

  1. its torsos \{G_t \:|\: t \in T\} have vertex subsets \{A_t \:|\: t \in T\} of bounded size \alpha such that G_t - A_t has an \alpha-near embedding into a surface \Sigma_t into which H does not embed;
  2. these embeddings are totally bounded, i.e. G_t - A_t is obtained from a graph embeddable in \Sigma_t by adding \leq \alpha vortices, each of path-width \leq \alpha (in particular, the path decompositions of the vortices have adhesion \leq \alpha, so that this is an indeed a strengthening of \alpha-bounded);
  3. for adjacent vertices t, t' \in T,where t \in rTt' (i.e. t is the parent of t'), V_t \cap V_{t'} \subset A_t (i.e. the overlap sits inside the excluded vertices of the parent), and V_t \cap V_{t'} \subset A_t \cup X_t where X_t is either two consecutive parts of a vortex decomposition in G_t - A_t, or an embedded clique of size at most 3 (i.e. the overlap almost sits inside the excluded vertices of the child, modulo two controllable special cases);
  4. the apex vertices Z sit inside A_r.

where \alpha and \theta depend only on the excluded minor H.

This last is the form in which Kawarabayashi and Wollan prove the theorem using induction on |V(G)|.

What is a vortex?

The original motivation for this structure theorem is the result from Graph Minors V, inspired by the earlier result of Dirac and Duffin characterising K_4-minor-free graphs as series-parallel graphs, that states that for H a planar graph, every H-minor-free graph has tree-width bounded by some number which is a function of H only. Additional elements, however, need to be introduced to generalize to the case where H is not planar:

  1. In particular, drawing on Wagner’s characterisation of K_5-minor-free graphs as graphs with tree-decompositions whose parts are either planar or isomorphic to V_8 (the graph obtained by joining opposite vertices of a 8-cycle), we allow the building blocks of our tree-decomposition to be arbitrary graphs of bounded genus.
  2. Adding a single vertex connected to every vertex to a large grid produces a K_6-minor-free graph of large genus; similarly adding k such vertices produces a K_{k+5}-minor-free graph or large genus. Hence we really want our building blocks to be arbitrary graphs of bounded genus plus a bounded number of arbitrarily-connected vertices (such vertices are known as apex vertices, from the image of the archetypal single vertex connected to everything on a grid.)
  3. There is one more sort of obstruction that must be taken into account, and these are vortices …

A vortex is, roughly speaking, a site of limited complexity where we allow arbitrary violations of bounded genus; they differ from apex vertices in that their complexity is limited not by the size of their vertex set, but by (essentially) their path-width. The archetypal vortex is a planar graph with edges added between every pair of vertices at distance 2 in the boundary of its infinite face—such a graph has no K_8 minor (Seese and Wessel, cited in Graph Minors XVI, 45), but cannot be obtained (as a family) by adding a bounded number of apex vertices to graphs of bounded genus.

More precisely, a vortex is a pair (G, \Omega) where G is a graph and \Omega is a cyclic ordering of some \bar{\Omega} = \{v_1, \dots, v_n\} \subset V(G) such that we can find a partition of G into edge-disjoint subgraphs H_1, \dots, H_n satisfying

  1. v_i \in V(H_i) and for every edge e \in G, we have $latex e \in H_j$ for some j.
  2. \{v_j : v \in V(H_j)\} \cap \bar{\Omega} =: \Omega_j forms a segment or circular interval of  \bar{\Omega}, i.e. if v_m, v_n \in \Omega_j, then v_ k \in \Omega_j whenever m \leq k \leq n.

(Notational asides: the pair (G[\bar{\Omega}], \Omega) is known as the society of the vortex; H_1, \dots, H_n is a vortex decomposition of (G, \Omega).)

The depth \alpha of a vortex is the maximum of |V(H_i) \cap V(H_j)| over all choices of i, j.

One way to build a vortex constructively (which also generalises in a visible way from the archetypal example given above) is to start with a cycle C, consider a finite list \Lambda of segments on that circle, add a vertex v_\gamma for each segment \gamma \in \Lambda which is arbitrarily connected to the vertices of C, and then add an edge between v_\gamma and v_{\gamma'} if \gamma \cap \gamma' \neq \varnothing. If no vertex of C appears in more than \alpha intervals of \Lambda, we have a vortex of depth \alpha. This construction corresponds to what are called fringes of depth \alpha in Lovász’s survey. If C was the boundary of a face in an embedding of a graph G, then we say that the graph resulting from this construction was obtained by adding a vortex of depth \alpha to G.

One way to visualize what the graph structure theorem is saying is provided by this awesome picture drawn by Felix Reidl:


(here the things sticking out are apex vertices, and the circular things on the surface that are not holes are vortices.)


For definitions of terminology which appears but is not defined here see e.g. Kawarabayashi and Wollan’s article, or the chapter on Minors in Diestel’s book. See also these slides from Daniel Marx, which are good for aiding intuition.