Coset complexes

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The complexes of the theorem stated in Coboundary expansion are built from a group and a family of subgroups: the vertices are cosets, and a set of cosets is a face when the cosets have an element in common. This lesson studies the construction for an arbitrary group. All the properties of the complexes that do not depend on the particular matrix groups are proved here.

The construction is the one used in [OpenAI-C, Section 2]. The lesson uses the notions of group, subgroup, coset, normal subgroup and quotient group (core course Abstract Algebra I).

1. The construction

Let \(G\) be a group, \(S\) a finite set with at least two elements, whose elements are called types, and \((K_i)_{i\in S}\) a family of subgroups of \(G\). A vertex of type \(i\) is a pair \((i,gK_i)\) of a type and a left coset of \(K_i\). We write \(gK_i\) for it when the type is clear; cosets of different subgroups count as different vertices even if they are the same subset of \(G\).

Definition 1.1. The coset complex \(\mathcal C(G;(K_i))\) has as faces the finite sets of vertices whose cosets have a common element, and the empty set. A face with a vertex of every type is a chamber.

A subset of a face is a face, so this is a simplicial complex in the sense of the lesson on coboundary expansion, except that it may be infinite. Two different cosets of the same subgroup are disjoint. So a face has at most one vertex of each type, and the set \(A\subseteq S\) of the types of its vertices is called its type. For \(A\subseteq S\) let \[ K_A=\bigcap_{i\in A}K_i,\qquad K_\emptyset=G . \]

Lemma 1.2. Let \(A\subseteq S\) be nonempty.

  1. For every \(g\in G\) the set \(F_A(g)=\{(i,gK_i):i\in A\}\) is a face of type \(A\), and every face of type \(A\) is of this form.
  2. The intersection of the cosets of the face \(F_A(g)\) is \(gK_A\), and \(F_A(g)=F_A(g')\) exactly when \(gK_A=g'K_A\). So the faces of type \(A\) correspond to the left cosets of \(K_A\).
  3. For \(A'\subseteq A\), the face of type \(A'\) contained in \(F_A(g)\) is \(F_{A'}(g)\).

Proof. (1) The cosets \(gK_i\) all contain \(g\). Conversely let \(\{(i,g_iK_i):i\in A\}\) be a face and \(g\) a common element of its cosets; then \(g_iK_i=gK_i\) for all \(i\in A\).

(2) \(\bigcap_{i\in A}gK_i=g\bigcap_{i\in A}K_i=gK_A\). If \(F_A(g)=F_A(g')\), the intersections are equal, so \(gK_A=g'K_A\). If \(gK_A=g'K_A\), then \(g'\in gK_i\) for every \(i\in A\), so \(g'K_i=gK_i\).

(3) is clear from the definition. \(\blacksquare\)

Proposition 1.3.

  1. Every face is contained in a chamber. So the complex is pure of dimension \(|S|-1\).
  2. \(G\) acts on the complex by \(h\cdot(i,gK_i)=(i,hgK_i)\). The action preserves types and is transitive on the faces of each type. The stabilizer of \(F_A(g)\) is \(gK_Ag^{-1}\).
  3. The chambers containing \(F_A(g)\) correspond to the cosets of \(K_S\) contained in \(gK_A\). If the index of \(K_S\) in \(K_A\) is finite, their number is this index.
  4. If \(K_S=\{1\}\), the map \(g\mapsto F_S(g)\) is a bijection from \(G\) to the set of chambers, and a face of type \(A\) lies in exactly \(|K_A|\) chambers.

Proof. (1) \(F_A(g)\subseteq F_S(g)\). (2) The action maps faces to faces and \(h\cdot F_A(g)=F_A(hg)\); transitivity follows from Lemma 1.2(1). By Lemma 1.2(2), \(h\) fixes \(F_A(g)\) exactly when \(hgK_A=gK_A\), that is \(h\in gK_Ag^{-1}\). (3) By Lemma 1.2, a chamber \(F_S(h)\) contains \(F_A(g)\) exactly when \(F_A(h)=F_A(g)\), that is \(h\in gK_A\), and the chambers correspond to the cosets \(hK_S\). (4) is the case \(K_S=\{1\}\) of (3) and of Lemma 1.2(2). \(\blacksquare\)

Example 1.4. Let \(G=(\mathbb Z/2)^3\) with the generators \(e_1,e_2,e_3\), let \(S=\{1,2,3\}\), and let \(K_i\) be the subgroup generated by the two generators other than \(e_i\). Then \(K_i\) has index \(2\), so there are two vertices of each type, six in all. The intersections \(K_{\{i,j\}}\) have order \(2\) and \(K_S=\{1\}\). So there are \(8\) chambers, which are triangles, every edge lies in \(2\) of them, and every vertex in \(4\). Two vertices of different types always have a common element, because \(K_iK_j=G\); two vertices of the same type are not joined. This is the surface of the octahedron: the two vertices of each type are opposite.

2. Connectedness

A simplicial complex is connected if any two vertices can be joined by a path of edges.

Proposition 2.1. The coset complex \(\mathcal C(G;(K_i))\) is connected if and only if \(G\) is generated by the subgroups \(K_i\), \(i\in S\).

Proof. Let \(G'\) be the subgroup generated by the \(K_i\).

Suppose \(G'=G\). Let \(h\in G\) and \(k\in K_i\). The chambers \(F_S(h)\) and \(F_S(hk)\) have the vertex \((i,hK_i)\) in common. Any two vertices of a chamber are joined by an edge, because \(S\) has at least two elements and a chamber is a face. So all vertices of \(F_S(h)\) and of \(F_S(hk)\) lie in one connected component. Every \(g\in G\) is a product \(k_1k_2\cdots k_r\) of elements of the subgroups, so by induction on \(r\) the vertices of \(F_S(g)\) lie in the component of the vertices of \(F_S(1)\). Every vertex lies in a chamber.

Suppose the complex is connected. Let \(\mathcal V\) be the set of the vertices \((i,gK_i)\) with \(g\in G'\). If \((i,gK_i)\in\mathcal V\) is joined by an edge to \((j,hK_j)\), the two cosets have a common element \(x\); then \(x\in gK_i\subseteq G'\) and \(hK_j=xK_j\), so \((j,hK_j)\in\mathcal V\). So \(\mathcal V\) is a union of connected components, hence the set of all vertices. For \(g\in G\) the vertex \((i,gK_i)\) is then \((i,g'K_i)\) with \(g'\in G'\), so \(g\in g'K_i\subseteq G'\). \(\blacksquare\)

3. Quotients

Let \(\Gamma\) be a normal subgroup of \(G\), let \(\overline G=G/\Gamma\), and write \(\overline g\) and \(\overline K\) for the images of an element \(g\) and of a subgroup \(K\) in \(\overline G\). The subgroup \(\Gamma\) acts on \(\mathcal C(G;(K_i))\) by Proposition 1.3(2).

Proposition 3.1. Suppose that for every nonempty \(A\subseteq S\) \[ \bigcap_{i\in A}\overline{K_i}=\overline{K_A} . \] Then \(F_A(g)\mapsto F_A(\overline g)\) is, for every nonempty \(A\), a well defined map from the faces of type \(A\) of \(\mathcal C(G;(K_i))\) onto the faces of type \(A\) of \(\mathcal C(\overline G;(\overline{K_i}))\). It respects inclusion of faces, and two faces have the same image exactly when they lie in one orbit of \(\Gamma\). If moreover \(\Gamma\cap K_i=\{1\}\) for every \(i\), then no element of \(\Gamma\) other than \(1\) fixes a nonempty face.

Proof. By Lemma 1.2 the faces of type \(A\) of the first complex are the cosets \(gK_A\), and those of the second are the cosets of \(\bigcap_{i\in A}\overline{K_i}\), which by assumption is \(\overline{K_A}\). The map is \(gK_A\mapsto\overline g\,\overline{K_A}\); it is well defined and surjective, and it respects inclusion by Lemma 1.2(3). Two cosets \(gK_A\) and \(g'K_A\) have the same image exactly when \(g'\in gK_A\Gamma\). Since \(\Gamma\) is normal, \(gK_A\Gamma=\Gamma gK_A\), so this means \(g'K_A=\gamma gK_A\) for some \(\gamma\in\Gamma\).

The stabilizer in \(\Gamma\) of \(F_A(g)\) is \(\Gamma\cap gK_Ag^{-1}=g(\Gamma\cap K_A)g^{-1}\), again because \(\Gamma\) is normal, and \(K_A\subseteq K_i\) for \(i\in A\). \(\blacksquare\)

So under the assumption on the intersections the coset complex of \(\overline G\) is the quotient of the coset complex of \(G\) by the action of \(\Gamma\), type by type. The assumption is not automatic: the image of an intersection is contained in the intersection of the images, and the inclusion can be proper (Exercise 4.3).

4. Exercises

4.1. Let \(G\) be the group of the permutations of \(\{1,2,3\}\), \(S=\{1,2\}\), \(K_1\) the subgroup generated by the transposition of \(1\) and \(2\), and \(K_2\) the subgroup generated by the transposition of \(2\) and \(3\). Describe the coset complex.

4.2. In the situation of Proposition 1.3(4) with \(G\) finite, show that the number of vertices of type \(i\) is \(|G|/|K_i|\), and that every vertex of type \(i\) lies in at most \(|K_i|\binom{|S|-1}{s}\) faces of dimension \(s\). When is the number equal to this bound?

4.3. Give an example of a group \(G\) with subgroups \(K_1,K_2\) and a normal subgroup \(\Gamma\) such that \(\overline{K_1}\cap\overline{K_2}\) is larger than \(\overline{K_1\cap K_2}\). What happens to the coset complex?

4.4. Show that in a coset complex with \(K_S=\{1\}\) two chambers \(F_S(g)\) and \(F_S(h)\) have the same vertex of type \(i\) exactly when \(g^{-1}h\in K_i\), and that the chambers containing a given face of type \(S\setminus\{i\}\) correspond to the elements of \(K_{S\setminus\{i\}}\).

5. Solutions

4.1. \(K_1\) and \(K_2\) have order \(2\) and index \(3\), and \(K_1\cap K_2=\{1\}\). So there are three vertices of each type and six chambers, which are edges; every vertex lies in two edges. The two subgroups generate \(G\), so the graph is connected by Proposition 2.1. A connected graph with six vertices, all of degree two, is a cycle of length six, and the types alternate along it.

4.2. The vertices of type \(i\) are the cosets of \(K_i\), and there are \(|G|/|K_i|\) of them. A face of dimension \(s\) containing the vertex \(gK_i\) has a type \(A\) with \(i\in A\) and \(|A|=s+1\); there are \(\binom{|S|-1}{s}\) such types. By Lemma 1.2 the faces of type \(A\) containing the vertex are the cosets of \(K_A\) inside \(gK_i\), and there are \(|K_i|/|K_A|\) of them. So the number of faces of dimension \(s\) at the vertex is the sum of \(|K_i|/|K_A|\) over these types \(A\). It is at most \(|K_i|\binom{|S|-1}{s}\), with equality exactly when all these \(K_A\) are trivial.

4.3. Let \(G=(\mathbb Z/2)^2\) with the generators \(e_1,e_2\), \(K_1=\langle e_1\rangle\), \(K_2=\langle e_2\rangle\) and \(\Gamma=\langle e_1+e_2\rangle\). Then \(K_1\cap K_2=\{0\}\), but \(\overline{K_1}=\overline{K_2}=\overline G\), a group of order \(2\). The coset complex of \(G\) has two vertices of each type and four edges, one for each element of \(G\); it is a cycle of length four. The coset complex of \(\overline G\) has one vertex of each type and one edge. The group \(\Gamma\) has two orbits on the edges of the cycle, and both have the same image. So the conclusion of Proposition 3.1 fails: the coset complex of the quotient group is smaller than the quotient of the coset complex.

4.4. \(F_S(g)\) and \(F_S(h)\) have the vertices \(gK_i\) and \(hK_i\) of type \(i\), which are equal exactly when \(g^{-1}h\in K_i\). A face of type \(B=S\setminus\{i\}\) is \(F_B(g)\); by Proposition 1.3(3) the chambers containing it are the \(F_S(gk)\) with \(k\in K_B\), and different \(k\) give different chambers because \(K_S=\{1\}\).

References