text:
\begin{document}

\title{Acyclicity in Finite Groups and Groupoids}
\author{Martin Otto\thanks{Research partially supported
by DFG grant OT~147/6-1: \emph{Constructions and Analysis in
  Hypergraphs of Controlled Acyclicity.}}
\\
Department of Mathematics\\
Technische Universit\"at Darmstadt}
\date{January~2020}

\maketitle

\begin{abstract}
\noindent
We expound a concise construction of finite groups and groupoids
whose Cayley graphs satisfy graded acyclicity requirements.
Our acyclicity criteria concern cyclic patterns formed by coset-like
configurations w.r.t.\ subsets of the generator set
rather than just by individual generators. The proposed constructions
correspondingly yield finite groups and groupoids whose Cayley
graphs satisfy much stronger acyclicity conditions than large girth.
We thus obtain generic and canonical constructions of highly
homogeneous graph structures with strong acyclicity properties,
which support known applications in finite graph and hypergraph
coverings that locally unfold cyclic configurations.
with involutive generators, with the
additional benefit of a more uniform approach across these settings.
\end{abstract}

\pagebreak

\tableofcontents

\pagebreak

\section{Introduction}

The intimate connection between finite groups and graph-like structures
is a long-standing theme that illustrates core concepts at the interface
of algebra and discrete mathematics. Groups arise as automorphism
groups of structures, and Frucht's theorem~\cite{Frucht} says that
every finite group arises as an automorphism group of a finite
graph; in particular, the given finite group -- an abstract group --
is realised as a permutation group, and thus as a subgroup of the full
symmetric group of some finite set, and in fact even as the full group of all
symmetries of a specifically designed discrete structure of a very
simple format.

At a very basic level, permutation group actions
can be defined through generators whose operation can be traced in
graph-like structures, which in turn determine the abstract group
structure~\cite{Cayley1,Cayley2}. The key notion in this correspondence is the
representation of the algebraic structure of the given group in its
Cayley graph: an edge-coloured directed graph that represents the
internal group action of a chosen set of generators for the group.

Interesting finite groups can be obtained as permutation
group actions induced by
graph-like extra structure on a finite set,
also in other ways than just as a group of symmetries. Specific graph
structures and carefully designed permutation group actions
can thus give rise to finite groups with desirable algebraic or combinatorial
properties suggested by various applications. A very nice example of
this technique is a construction, due to Biggs~\cite{Biggs89} and
outlined in~\cite{Alon95},
of finite groups over a given set of generators that avoid short
cycles, i.e.\ in which non-trivial products of a small number of generators
cannot evaluate to the neutral element. In terms of the Cayley graph of the
resulting group one obtains finite graphs of large girth that are not
only regular but (like any Cayley graph) highly symmetric in the
stronger sense of possessing a transitive automorphism group.

Acyclicity criteria for groups matter in many natural applications.
The free group over a given set of generators, which can be seen as
the unique fully acyclic group structure over the given generators,
arises naturally in connection with universal coverings in the
classical topological context as well as in the context of discrete
structures, e.g.\ with tree unfoldings of transition systems. The
relevant coverings can be described as products with (the Cayley
graphs of) free groups. Of course free groups, and fully acyclic
coverings in non-trivial settings, are necessarily infinite.
Where finiteness matters and needs to be preserved, e.g.\ in finite
coverings, full acyclicity is typically unavailable. Here
graded degrees of acyclicity, like lower bounds on the girth
of the Cayley graph, are best possible and often can replace full
acyclicity, especially for local structural analysis -- just as a
graph of large girth is locally tree-like. Previous work, which arose
from applications in logic and the model theory of finite structures,
has led to the introduction of similar but much stronger measures
of graded acyclicity in Cayley graphs of finite groups. These notions
of acyclicity arise naturally in connection with covering
constructions for finite graphs and hypergraphs. Instead of
controlling just the length of shortest generator cycles, similar
control is achieved over the length of shortest cycles formed by
cosets w.r.t.\ generated subgroups. This generalisation involves a
passage from cycles at the level of individual generators to cycles
formed by cosets, which a priori are not even bounded in size.
In other words, this
is a shift in focus from first-order objects (generators) to
second-order objects (cosets) in the desired groups.
Corresponding constructions, which are inspired by Biggs' technique
but adapt the basic idea to the more complex technical setting,
were first developed  for groups in~\cite{Otto04} and~\cite{Otto12JACM}
for specific applications of finite graph coverings.
Generalisations of these techniques
to the setting of groupoids offer a more direct route to hypergraph
coverings (here necessarily branched, in a discrete analogue of
classical terminology from~\cite{Fox}). A main challenge and
goal in these settings lies in the construction of corresponding
coverings that are generic and natural in the sense that they
do not break any symmetries of the underlying structure.
This is essential for far-reaching applications, e.g.\ towards
extension problems for local symmetries~\cite{lics2013,arXiv2018}.

The goal here is a concise and generic combinatorial construction
of groups and groupoids with strong acyclicity properties that control
coset cycles rather than just generator cycles.
The present exposition not only serves to correct a serious mistake in
the construction of the relevant groupoids that was sketched
in~\cite{lics2013,arXiv2018}
\footnote{Cf.\ acknowledgements at the end of this paper on this somewhat frayed
  history.}
but also to unify the treatment of finite groups and groupoids with the
desired acyclicity properties.
One main technical point in the generalisation from
groups to groupoids has to do with the
difficulty to overcome the restriction to involutive generators
from~\cite{Biggs89,Otto04},
which seems inadequate in a groupoidal setting. In the current, more
comprehensive and more systematic extension of the original idea we propose a
construction of highly acyclic finite groups with sets of involutive
generators that yields stronger results for these groups -- or stronger notions of
acyclicity based on more general patterns than mere coset cycles. This allows us
to present a self-contained account in which the
construction of highly acyclic finite groupoids
can be reduced to the new, enriched construction
for groups with involutive generators. This yields a unified construction
which offers a transparent view of the commonality between the two,
seemingly so very different settings,
which may support further insights and applications. Concerning known applications
we discuss more general and more direct constructions of finite graph
and hypergraph coverings in Propositions~\ref{graphcoverprop}
and~\ref{hypcoverprop}.

\subsection*{Terminology and notation}

\paragraph*{Graphs and relational structures.}
In this paper we consider various kinds of graphs, some undirected, some directed,
often also allowing loops (reflexive edges), and in Section~\ref{groupoidsec}
also multi-graphs that may have more than one edge linking the same
two vertices. Notation should be standard, with small
adaptations to the specific formats that will be explicitly
stated where they occur. We mostly use a relational format for the
specification of a graph, with a binary edge relation, or with a separate edge
relation for each colour to encode edge-coloured graphs. In some
instances, and especially in Sections~\ref{groupoidsec} and~\ref{Nacycgroupoidsec},
it is natural to treat graphs and especially multi-graphs as
two-sorted structures with a set of edges and a set of vertices
linked by incidence maps that specify source and target vertices of each edge.
For \emph{subgraphs} we explicitly
distinguish between \emph{induced subgraphs} (whose edge
relation is the restriction of the given edge relation to the
restricted set of vertices) and \emph{weak subgraphs} (whose edge
relation may be a proper subset of the given edge relation even
in restriction to the smaller vertex set). Also more generally for relational structures
we use $\subsetw$ for the \emph{weak substructure} relationship,
$\subset$ for the induced \emph{substructure} relationship.
By a \emph{component} of a graph structure we mean
an induced substructure that is closed w.r.t.\ the edge relation;
a \emph{connected component} is a minimal  component.
The term \emph{reduct} refers to a restriction in the number of
edge relations, or edge colours, which corresponds to the
deletion of all edges of the colours to be eliminated.
\footnote{Depending on context the corresponding edge relations
can be thought of as erased (which produces a structure over a
smaller signature),  or just as emptied (which produces a weak substructure).}

\paragraph*{Algebraic structures.}
For structures like groups, semigroups, monoids or groupoids we
adopt multiplicative notation
and would typically write, for instance, $g \cdot h$ or just $gh$
for the result of the composition of group elements $g$ and $h$
w.r.t.\ the group operation, $1$ for the neutral
element and $g^{-1}$ for the inverse of $g$. When dealing with
subgroups of the symmetric group of some set $X$, we sometimes make
the group operation explicit as in $h \circ g$ for the composition
of $g$ with $h$, which maps $x \in X$ to $h(g(x))$, and would in our
standard notation be rendered as $g \cdot h$ or $gh$  (!)
since we think of permutations
as operating from the right.

Among standard terminology from other fields of
mathematics we use some basic terms
from formal language theory, especially to deal with \emph{words}
over a finite alphabet $E$ of letters; the set of all $E$-words is
the set of all finite (but possibly empty) strings or tuples of
letters from $E$, denoted $E^\ast = \bigcup_{n \in \N} E^n$.
As is common in formal language theory, we write a typical word
of length $n \in \N$ as
$w = e_1 e_2 \cdots e_n \in E^n$ (rather than e.g., in tuple notation, as
$(e_1, e_2, \ldots, e_n)$), denoting its length as $n = |w|$.
We also write, e.g.\ just $w_1 w_2$ for the
\emph{concatenation} of the words $w_1,w_2 \in E^\ast$ (which is
often denoted as $w_1 \cdot w_2$ with explicit notation for the
concatenation operation as a monoidal semigroup operation).
The \emph{empty word} $\lambda \in E^\ast$, which
is the unique $E$-word of length $0$, is the neutral element
in the monoid $E^\ast$.
Depending on the r\^ole of the letters $e \in E$, we may use
$E$-words to specify different objects of interest:
thinking of $E$ as a set of generators of some group, an $E$-word
is a generator word which can be read as a group product
specifying a group element; thinking of $E$ as a set of colours in an
edge-coloured graph, an $E$-word is a colour sequence and can
specify the class of walks that realise that colour sequence.
In some cases we also invoke a notion of \emph{reduced words}, which
are typically obtained by some cancellation operation. Especially if $E$ is a set of
generators of a group that is closed under inverses we may
(inductively) cancel factors $e e^{-1}$ in order to associate with
every $E$-word a unique reduced $E$-word that denotes the same
group element. In such contexts we often let $E^\ast$ stand for the
set of reduced words, endowed with the concatenation operation that
implicitly post-processes plain concatenation by the necessary
cancellation steps. More formally one could explicitly distinguish
between $E^\ast$ and its quotient $E^\ast/{\sim}$, but we suppress
this as an unnecessary distraction in our considerations.

\section{General patterns}
\label{genpatternsec}

\subsection{Cayley \& Biggs: the basic construction}
\label{Biggssec}

The fundamental idea to associate groups with
permutation group actions and graphs can be
attributed to Arthur Cayley~\cite{Cayley1,Cayley2}.
The Cayley graph of an abstract group, w.r.t.\
to a chosen set of generators, encodes the algebraic structural
information about the algebraic group, and also represents the given
group as a subgroup of the full symmetric group, and more
specifically as the automorphism group, of the Cayley graph.
The natural passage between combinatorial properties of
graph-like structures and group-like structures offers interesting
avenues for the construction of group-like and graph-like structures.
A classical example is the use of Cayley graphs in Frucht's
construction of (finite) graphs that realise a given abstract (finite)
group as their automorphism group~\cite{Frucht}.
In particular, Cayley graphs are, by construction, not just regular
but homogeneous in the sense of having a transitive
automorphism group. So on one hand, Cayley graphs provide examples of graph
structures with a particularly high degree of internal symmetry.
On the other hand, permutation group actions on suitably designed
graph structures generate groups that can display specific combinatorial properties
w.r.t.\ to a chosen set of generators -- and these groups in turn generate Cayley
graphs that reflect those group properties. It is one characteristic
feature of the inductive constructions to be expounded here that they are based
on a feedback loop built on this interplay.

The idea to extract groups with certain acyclicity properties from
permutation group actions on suitably prepared graph structures is
best illustrated by the basic example of a construction of regular
graphs of high girth due to Biggs~\cite{Biggs89} and outlined
in~\cite{Alon95}.

Let $E$ be a finite set of letters, $|E| = d \geq 2$, to be used to label involutive
generators of a group to be constructed. With $E$ and a parameter $n
\geq 1$ in $\N$ associate a tree $\T(E,n)$ and a
group $\G(E,n)$ as follows. Let $\T(E,n)$ be a
$d$-branching, regularly $E$-coloured, finite undirected tree of depth $n$, as
represented by the set of all \emph{reduced words} $w \in E^{\leq n}
\subset E^\ast$, i.e.\ strings $w = e_1\cdots e_m$ of length
$|w|= m$, $0 \leq m \leq n$,
with $e_i \in E$ for $1 \leq i \leq m$ and $e_{i+1} \not= e_{i}$
for $1 \leq i < m$. We regard the empty word $\lambda \in E^\ast$
as the root of $\T(E,n)$. More formally, we let
\[
\T(E,n) = (V,(R_e)_{e \in E})
\]
be the tree structure with vertex set
\[
V := \{ w \in E^\ast \colon |w| \leq n, w \mbox{ reduced } \}
\]
and undirected edge relation $R = \dot{\bigcup}_{e \in E} R_e$,
$E$-coloured by its partition into the
\[
R_e :=  \{ (w,we), (we,w) \colon w,we \in V \}
\]
for $e \in E$. By construction, each vertex $w \in V$ with $|w| < n$
is an interior vertex of $\T(E,n)$ of degree $d = |E|$, with
precisely one $R_e$-neighbour for each $e \in E$; the remaining
vertices, viz.\ those $w \in V$ with $|w| = n$, are leaves of
$\T(E,n)$, each with an $R_e$-neighbour for a unique $e \in E$
(the last letter of $w$). Note that each $R_e$ is a partial
matching over $V$, and that $R_e$ and $R_{e'}$ are disjoint for $e
\not= e'$. With $e \in E$ we associate
the permutation $\pi_e \in \mathrm{Sym}(V)$ that swaps any pair of
vertices that are incident with a common $e$-coloured edge. This is
the involutive permutation of $V$ whose graph is the
matching $R_e$ augmented by loops in vertices not incident with an
$e$-coloured edge.
The target of the construction is the group $\G(E,n)$,
which is the subgroup of
$\mathrm{Sym}(V)$ generated by these involutions:
\[
\G  = \G(E,n) := \langle \pi_e \colon e \in E \rangle  \subset \mathrm{Sym}(V).
\]

For the group operation we use the convention that the action by the
generators is regarded as a right action via composition, i.e.\
with
\[
\barr{rcl}
\rho \pi_e = \pi_e \circ \rho \colon V &\longrightarrow& V
\\
w &\longmapsto& \pi_e(\rho(w)).
\earr
\]

Its Cayley graph w.r.t.\ the generators $(\pi_e)_{e \in E}$ is an
edge-coloured graph $\CG$, with the set of group
elements $\rho \in G$ as its vertex set, and with a family of
edge relations
\[
R_e^{G} := \{ (\rho, \rho \pi_e) \colon \rho \in G, e \in E \}
\subset G \times G,
\]
one for each $e \in E$.
Here these edge relations are symmetric due to the involutive nature of
the $\pi_e$ in $\mathrm{Sym}(V)$, and they are irreflexive
and pairwise disjoint since $\mathrm{id}_V \not= \pi_e \not= \pi_{e'}$
for $e \not= e'$, as can be seen most easily by their action as
permutations on $\lambda \in V$.
So this Cayley graph is a $d$-regular finite graph, whose
automorphism group acts transitively on the set of vertices. For the
last claim consider the left action of the group on itself:
\[
\barr{rcl}
h \colon G &\longrightarrow& G
\\
g &\longmapsto& hg,
\earr
\]
which clearly induces an automorphism
of the Cayley graph (albeit not of the group, which is rigid once we
label the generators).
That the girth of the Cayley graph of $\G$ is at least
$4n+ 2$ can be seen as follows.
A reduced word $w \in E^k$ of length $k \geq 1$ can be written as
$w = e_1u$. Let $v \in E^n$ be a leaf of $\T(E,n)$ whose reversal
$v^{-1}$ agrees with $u$ (up to $|u|$).
Applying the corresponding permutation
$\pi_w = \pi_u \circ \pi{e_1}$ to $v$, we see that the action of the
permutations prescribed by the first (up to) $n+1$ letters of $w$ takes
that leaf step by step towards the root $\lambda$, the next $n$
letters (if present) will take it step by step towards a different
leaf, where the very next letter (if present) can have no effect so
that it would take at least the action of another $2n$ letters after
that to bring this vertex back to where we started. In other words, no reduced word
of fewer than $n+1+n+1+ 2n = 4n +2$ letters can label a generator
sequence that represents the neutral element of the group,
which is the identity in $\mathrm{Sym}(V)$.

Considering what is essential for the passage from a
graph like $\T(E,n)$ to a group like $\G(E,n)$, the only obvious
necessity is that each of the edge colours induces a partial matching
of the underlying vertex set in order to have well-defined
involutions $\pi_e$. Tree-likeness, by contrast, is of no special
importance, not even for the bound on the girth of the resulting
group or Cayley graph. If $\T(E,n)$ were replaced,
for instance, by the disjoint union of all $E$-coloured line graphs
corresponding to reduced words $w \in E^{2n}$, the above girth bound
of $4n+2$ persists with essentially the same argument.
In the following paragraph we extract the basic format for the
generation of groups with involutive generators from edge-coloured
undirected graphs.

\subsection{E-graphs and E-groups}
\label{Egraphsandgroupssec}

In the following it is convenient to allow loops in the symmetric
edge relation of an undirected graph $(V,R)$,
and to let a loop at vertex $v$ contribute value~$1$ to the
degree of that vertex. A \emph{partial matching} is here cast as a
symmetric edge relation whose degree is bounded by $1$ at every
vertex, and may thus be thought of as the graph of a partial bijection
that is involutive (its own inverse); this involution has precisely
those vertices as fixed points at which the edge relation has loops,
and its domain $\mathrm{dom}(R)$ and range $\mathrm{rng}(R)$
consists of the set of the vertices of degree~$1$. A \emph{full
  matching} is a symmetric edge relation $R$ on $V$
such that every vertex $v \in V$ has a unique $R$-neighbour, which
in the case of a loop may be $v$ itself; it therefore corresponds to
the graph of an involutive permutation of the vertex set $V$.

\bD[$\E$-graph]
\label{Egraphdef}
\mbox{}\\
For a set $E$, an \emph{$\E$-graph} is an undirected
edge-coloured graph $\H= (V,(R_e)_{e \in E})$ whose undirected
edges are $E$-coloured in such a way that each $R_e$ is a partial
matching over the vertex set $V$.
The $\E$-graph $\H = (V,(R_e)_{e \in E})$ is \emph{strict}
if there are \emph{no loops} (each $R_e$ is irreflexive) and
\emph{no multiple edges} ($R_e \cap R_{e'} = \emptyset$ for $e \not= e'$).
The $\E$-graph $\H = (V,(R_e)_{e \in E})$ is \emph{complete} if each $R_e$
is a full matching.
The \emph{trivial completion} of an
$\E$-graph $\H = (V,(R_e)_{e \in E})$ is the
complete $\E$-graph $\bar{\H} = (V, (\bar{R}_e)_{e \in E})$ obtained by
putting $\bar{R}_e := R_e \cup \{ (v,v) \colon v \in V\setminus\mathrm{dom}(R_e)\}$.
\eD

We think of $R_e$-edges as edges of colour $e$ or as edges labelled
with $e$. In this sense an $\E$-graph is a special kind of
$E$-coloured graph whose overall
edge relation would be $\bigcup_{e\in E} R_e$.

\medskip
For groups $\G = (G,\cdot\,,1)$ (in multiplicative notation),
an element $g \in G$ is an \emph{involution} if $g = g^{-1}$.
A subset $E \subset G \setminus \{ 1 \}$ is a \emph{set of generators}
for $\G$  if every group element $g \in G$ can be written as a
product of elements from $E$ and their inverses.

\bD[$\E$-group]
\label{Egroupdef}
\mbox{}\\
For a set $E$, an \emph{$\E$-group}
is any group $\G = (G,\cdot\,,1)$ that has $E \subset G$ as a set of
non-trivial involutive generators.
\footnote{Clearly the elements $e \in E \subset G$ are pairwise
distinct as elements of $\G$, and non-triviality means that $e \not= 1$.}
\eD

If $\G$ is an $\E$-group, we write $[w]_{\G} \in G$ for the group element
that is the group product of the generator sequence $w \in E^\ast$, so that
\[
\barr{rcl}
[\,\nt\,]_{\G} \colon E^\ast &\longrightarrow& \G
\\
w = e_1\cdots e_n &\longmapsto& [w]_{\G} := \prod_{i=1}^n e_i = e_1 \cdots e_n
\earr
\]
is a surjective homomorphism from the free monoid structure of $E^\ast$,
with concatenation and neutral element $\lambda \in E^\ast$ ,
onto the group $\G$.

\bO
\label{freeinvgroupobs}
The quotient of the free group generated by $E$ w.r.t.\ to the
equivalence relation induced by the identities $e = e^{-1}$ for
$e \in E$ (as represented by reduced words in $E^\ast$) can be
regarded as the \emph{free $\E$-group}. All other
$\E$-groups are homomorphic images of this free $\E$-group.
\eO

\bD[$\sym(\H)$]
\label{symdef}
\mbox{}\\
For an $\E$-graph $\H= (V,(R_e)_{e \in E})$ we let $\sym(\H)$ be
the subgroup of $\sym(V)$ that is generated by the involutive permutations
$\pi_e \colon V \rightarrow  V$ induced by the full matchings
of its trivial completion $\bar{\H} = (V, (\bar{R}_e)_{e \in E})$.
\eD

Provided the $(\pi_e)_{e \in E}$ are pairwise distinct and distinct
from $\mathrm{id}_V$, we regard $\sym(\H)$ as an $\E$-group
where we identify $e \in E$ with the generator $\pi_e$, for $e \in
E$. We shall always tacitly assume this whenever we use $\sym(\H)$.
A simple manner to force the necessary distinctions for the $\pi_e$
is to attach to $\H$, as a disjoint component, a copy of the hypercube
$2^E$ (and this modification will nowhere interfere with other
concerns of our constructions).

The Biggs group $\G(E,n)$ as discussed above is $\sym(\T(E,n))$.

Recall that we let permutations act from the right. In terms of
the group product in $\sym(\H)$ this makes $\pi_e \pi_{e'} = \pi_{e'}
\circ \pi_e$. Extending this to arbitrary words $w = e_1 \cdots e_n \in
E^\ast$ over $E$ according to
\[
\barr{rcl}
[\,\nt\,]_{\H} \colon E^\ast &\longrightarrow& \sym(\H)
\\
w &\longmapsto& [w]_{\H} := \pi_w := \prod_{i=1}^n \pi_{e_i} = \pi_{e_n} \circ \cdots \circ \pi_{e_1},
\earr
\]
yields a surjective homomorphism from the free monoid structure of $E^\ast$,
with concatenation and neutral element $\lambda \in E^\ast$,
onto the group structure of $\sym(\H)$ with composition and
neutral element $\pi_\lambda = \mathrm{id}_V$. Factorisation w.r.t.\
the identities $e = e^{-1}$ turns this into a surjective group homomorphism
from the free $\E$-group onto $\sym(\H)$.

\bD[Cayley graph]
\label{Cayleydef}
\mbox{}\\
For an abstract group $\G = (G,\cdot\,,1)$ and any set $E \subset G$ of
generators, the \emph{Cayley graph} of $G$ w.r.t.\ $E$ is the directed
edge-coloured graph $\CG := \mathrm{Cayley}(\G,E)= (G,(R_e)_{e \in E})$
with vertex set $G$ and edge sets
\[
R_e := \{ (g,ge) \colon g \in G \}
\]
of colour $e$, for all $e \in E$.
\eD

The Cayley graph $\CG$ is undirected precisely if the generator set
$E$ consists of involutions of $\G$. In general the $R_e$ will not be
symmetric, but each $R_e$ will always be the graph of a global
permutation $\pi_e$ of the vertex set $G$, viz.\ of right multiplication with
$e \in G$, $\pi_e \colon g \mapsto ge$.
It is easy to check that, as an abstract group with generators $e \in E$,
$\G$ is isomorphic to the subgroup of the full symmetric group
$\mathrm{Sym}(G)$ over the vertex set $G$ generated by these
permutations $\pi_e$. In particular, in the case of a group
$\G = (G,\cdot\,,1)$
that admits a set of involutive generators $E \subset G \setminus \{1\}$, the
associated Cayley graph $\CG = \mathrm{Cayley}(\G,E)$
is a complete and strict $\E$-graph in the sense of
Definition~\ref{Egraphdef}, and
\[
\G = (G, \cdot\,, 1) \;\simeq\; \sym(\CG).
\]

In the following it will be convenient, and without risk of confusion, to
identify the generators $e \in E \subset G$ of a group $\G$ with
the maps $\pi_e \colon g \mapsto g e$ in $\G$ or in its Cayley
graph $\CG$. We similarly identify the family of generators
$(\pi_e)_{e \in E}$ of $\sym(\H)$ with a subset $E \subset
\sym(\H)$ whenever $\sym(\H)$ is an $\E$-group,
by writing just $e$ instead of $\pi_e$ in this context.

\bD[generated subgroup]
\label{gensubgroupdef}
\mbox{}\\
For a subset $\alpha \subset E$ of the set of involutive generators
$E$ of an $\E$-group $\G$ we let
$\G[\alpha]$ stand for the subgroup generated by $\alpha$, regarded as
an $\alpha$-group whose
universe is
\[
G[\alpha] := \{ [w]_{\G} \colon w \in \alpha^\ast \} \subset G.
\]

The Cayley graph $\CG[\alpha]$ of $\G[\alpha]$, correspondingly, is
regarded as an $\alpha$-graph, which is a weak subgraph
$\CG[\alpha] \subsetw \CG$ of the Cayley graph of $\G$.
\footnote{More specifically it is the $(R_e)_{e \in \alpha}$-reduct of the
induced subgraph $\CG\restr G[\alpha]$ on $G[\alpha] \subset G$.}
\eD

\bD[$\alpha$-walk and $\alpha$-component]
\label{alphawalksconnectdef}
\mbox{}\\
For a subset $\alpha \subset E$ and an $\E$-graph $\H = (V,(R_e)_{e \in E})$,
an \emph{$\alpha$-walk} of length $n$ from $v$ to $v'$
is a sequence $v_0, e_1, v_1, e_2, \ldots, e_n, v_n$ of vertices and edge labels
where $v_i \in V$, $v= v_0$, $v_n = v'$, $e_i \in \alpha$ such that $(v_i,v_{i+1})
\in R_{e_{i+1}}$ for $i < n$.
\\
The \emph{$\alpha$-connected component}, or just $\alpha$-component,
of $v \in
V$ consists of those vertices $v'$ that are linked to $v$ by
$\alpha$-walks. We write $\alpha[v] \subset V$ for this set of
vertices and $\H[\alpha;v]$ for the weak subgraph $\H[\alpha;v]
\subsetw \H$ obtained, as an $\alpha$-graph, as a reduct of
the induced subgraph $\H \restr \alpha[v]$.
\eD

Note that the Cayley graph $\CG[\alpha] \subsetw \CG$ of
$\G[\alpha]$ also arises as the $\alpha$-component
of $1 \in G$ in the Cayley graph $\CG$.
It is also useful to note that, if
$v= v_0, e_1, v_1, e_2, \ldots, e_n, v_n=v'$ is an $\alpha$-walk from
$v$ to $v'$ in the $\E$-graph $\H$ such that $w = e_1\cdots e_n$ traces the edge
labels along this walk, then $v' = \pi_w(v) = [w]_{\H}(v)$ w.r.t.\ the
permutation group action of $\sym(\H)$ on $\H$.

\subsection{Compatibility and homomorphisms}

The notion of a homomorphism
between $\E$-groups is the natural one.
It requires compatibility with the group product \emph{and} with the
identification of the generators.
We write $\Ghat \succeq \G$  or $\G \preceq \Ghat$ to
indicate that there is a homomorphism from $\Ghat$ to $\G$.
If there is any homomorphism
$h \colon \Ghat \rightarrow \G$ between
$\E$-groups $\Ghat$ and $\G$ then it must be
\[
\barr{rcl}
h \colon \;\; \Ghat\;\;  &\longrightarrow &\G
\\
\nt
[w]_{\Ghat}\!\! &\longmapsto & [w]_\G
\earr
\]
for all $w \in E^\ast$. So what matters is
well-definedness of this mapping, which is expressible as
the condition that $[w]_\G = [u]_\G$ whenever
$[w]_{\Ghat} = [u]_{\Ghat}$, or just that $[w]_\G =1$ in $\G$ whenever
$[w]_{\Ghat}  =1$ in $\Ghat$.

\bD[compatibility]
\label{compatdef}
\mbox{}\\
For an $\E$-graph $\H$ and $\E$-group $\G$ we say that
$\G$ is \emph{compatible with} $\H$ if there is a
homomorphism of $\E$-groups from $\G$ to $\sym(\H)$, i.e.\
if $\sym(\H) \preceq \G$.
\eD

In straightforward extension of this concept, a family of $\E$-groups
is compatible with $\H$ if each member is; this will be of interest
especially when certain families of (small) generated subgroups of $\G$,
rather than $\G$ itself, are compatible with some $\E$-graph.

Recall that $[w]_{\H} = \pi_w = \prod_{i=1}^n \pi_{e_i} \in \sym(\H)$
for $w = e_1\cdots e_n \in E^\ast$.
Compatibility of $\G$ with $\H$ precisely requires that the mapping
\[
\textstyle
[w]_\G
\;\longmapsto\;
[w]_\H \in \sym(\H).
\]
is well-defined, i.e.\ that
$[w]_\G = 1$ in $\G$ implies $[w]_\H = 1$ in $\sym(\H)$, for all $w \in E^\ast$.

Note that trivially $\sym(\H)$ is compatible with $\H$ and with
every connected component of $\H$.
We collect some further simple but useful facts.

\bO
\label{easycompatobs}
\bre
\item
$\G[\alpha]$ is compatible with $\CG[\alpha]$ for $\alpha \subset E$.
\item
$\G$ is compatible with the disjoint union $\oplus_i \H_i$ of
$\E$-graphs $\H_i$ if, and only if, it is compatible with each
component $\H_i$.
\item
$\G[\alpha]$, for $\alpha \subset E$, is compatible with $\H$
if, and only if, it is compatible with every $\alpha$-connected
component of $\H$, if, and only if, it is compatible with
the $\alpha$-reduct of $\H$.
\ere
\eO

It also follows that $\G \preceq \Ghat$ if, and only if,
$\Ghat$ is compatible with $\CG$. A version of this
observation for generated subgroups will be crucial in the
construction of suitable $E$-groups with specific acyclicity
properties.

\bL
\label{GhatCGcompatlem}
Let $\Ghat \succeq \G$ be  $\E$-groups,
$\Ghat = \sym(\H)$ for an $\E$-graph $\H$.
In this situation, the subgroups $\G[\alpha]$ and $\Ghat[\alpha]$
generated by $\alpha \subset E$ are isomorphic as $\alpha$-groups,
$\Ghat[\alpha] \simeq \G[\alpha]$, if the homomorphism
from $\Ghat$ to $\G$ is injective in restriction to $\Ghat[\alpha]$,
which is the case if, and only if, $\G[\alpha]$ is compatible with
every $\alpha$-connected component of $\H$ and hence with $\H$.
\eL

\prf
For the last claim, assuming that $\G \preceq \Ghat$, we need to show
that conversely $\Ghat[\alpha]\preceq \G[\alpha]$. Note that
$\Ghat[\alpha] = \sym(\H\restr \alpha)$, where
$\H\restr \alpha$ stands for the $\alpha$-reduct of $\H$,
which is an $\alpha$-graph. If $\G[\alpha]$ is compatible with every
connected component of $\H\restr \alpha$, then $[w]_\G = [u]_\G$
for $w,u \in \alpha^\ast$ implies that $\pi_w = \pi_u$ in
$\sym(\H\restr \alpha)$ and therefore also in
$\sym(\H)$, i.e.\ in $\Ghat$.
\eprf

For $k \in \N$ we let
\[
\Gamma_k := \{ \alpha \subset E \colon
|\alpha| <k \}
\]
denote the set of generator subsets of size less than $k$.  We
abbreviate corresponding families of generated subgroups and their
Cayley graphs from a given $\E$-group $\G$ as
\[
\barr{r@{\;:=\;}l}
\Gamma_k(\G) &
(\G[\alpha'] \colon \alpha' \in \Gamma_k)
\\
\hnt
\Gamma_k(\CG) &
(\CG[\alpha'] \colon \alpha' \in \Gamma_k)
\earr
\]

\bL
\label{Ghatcompatlem}
Let $\hat{\G} = \sym(\H)$ for an $\E$-graph $\H = \H(\G)$
that is derived from the $\E$-graph
$\G$ in an isomorphism-respecting manner.
\bae
\item
If $\H(\G)$ comprises a copy of $\CG$ as a component,
then $\Ghat \succeq \G$.
\item
If $\H(\G)$ as in~(a) is such that $\Gamma_k(\G)$, i.e.\ every
$\G[\alpha]$ for $\alpha \in \Gamma_k$,
is compatible with
$\H(\G)$, then $\Ghat[\alpha] \simeq \G[\alpha]$ for
$\alpha \in \Gamma_k$.
\item
If $\H(\G)$ as in~(b) comprises, as a component,
an $\E$-graph $\H_k(\G)$ whose isomorphism type is determined by
the family of the subgroups
$\Gamma_k(\G) = (\G[\alpha] \colon \alpha \in \Gamma_k)$,
then $\Ghat$ is compatible with $\H_k(\G) \simeq \H_k(\Ghat)$.
\eae
\eL

Intuitively the precondition of part~(b) should be seen as
\emph{downward compatibility}. It implies that the transition from
$\G$ to $\Ghat$ is conservative for subgroups generated by
fewer than $k$ generators, and part~(c) gives one criterion
how this can be maintained while unfolding
$\G$ at the level of larger $\alpha$ in non-trivial ways.

\prf
All claims follow from Observation~\ref{easycompatobs}
and Lemma~\ref{GhatCGcompatlem} in a straightforward manner.
\eprf

The above opens up the potential for achieving successively more
stringent structural conditions in an inductive fashion. Essentially
the induction will be on the size $k = |\alpha|$ of the generator set of
subgroups $\G[\alpha]$ that may form certain
obstructive patterns and progresses to exclude them by replacing $\G$
by $\Ghat$ as in item~(c) above. The crux of the matter is to
reconcile the preconditions of~(c), or to find suitable $\H_k(\G)$
that do not spoil $\G[\alpha]$-compatibility.
The key obstructions to be dealt with are cyclic patterns
of cosets w.r.t.\ subgroups $\G[\alpha]$ to be discussed in the
following section.

\medskip
Some application contexts call for an analysis of symmetries of
$\E$-groups $\G$ that are induced by permutations of the underlying
set $E$ of generators. These are not covered by the notion of
automorphisms of $\E$-groups since those,
as special homomorphisms, need to fix the generators individually
(model-theoretically they are treated as constants).
Similarly for $\E$-graphs $\H$, automorphisms of $\H$ viewed
as a relational structure need to respect each $R_e$
individually, and do not account for symmetries induced by
permutations of the edge colours. In both cases, permutations $\rho
\in \mathrm{Sym}(E)$ induce what in model-theoretic terminology is a
\emph{renaming}, sending $\G$ to $\G^\rho$ and
$\H$ to $\H^\rho$. For instance the $\rho$-renaming of the $\E$-graph
$\H = (V, (R_e)_{e \in E})$ is $\H^\rho = (V, (R'_e)_{e \in
  E})$ with $R'_{\rho(e)} = R_e$.
Such a renaming reflects a \emph{symmetry} if it
leaves the underlying structure invariant up to isomorphism.

\bD[symmetry over $E$]
\label{Esymmdef}
\mbox{}\\
A permutation $\rho \in \mathrm{Sym}(E)$ of the set
$E$ is a \emph{symmetry} of an $\E$-group $\G$
if the renaming of generators according to $\rho$
yields an isomorphic $\E$-group, $\G^\rho \simeq \G$.
Similarly, $\rho$ is a symmetry of the $\E$-graph $\H$
if the renaming of its edge relations according to $\rho$
yields an isomorphic $E$-graph: $\H^\rho \simeq \H$.
\eD

For instance, the trees $\T(E,n)$ in Biggs' construction
are \emph{fully symmetric} in the sense that every
$\rho \in \mathrm{Sym}(E)$ is a symmetry; the same
is then true of the resulting $\E$-group $\G = \sym(\T(E,n))$ and its
Cayley graph $\CG$.

\section{Coset cycles and acyclicity criteria}
\label{cosetcycsec}

The common notion of \emph{large girth} for Cayley graphs
naturally leads to
There is a basic notion of $n$-acyclicity for $\E$-groups that
forbids non-trivial \emph{generator cycles} (i.e.\ representations of $1 \in
\G$ by reduced generator words) of lengths up to $n$.
This account matches the graph-theoretic notion of \emph{girth} for the associated
Cayley graph, simply because the length of the shortest shortest
non-trivial generator cycle in $\G$ is the length of the shortest
graph cycle in $\CG$, i.e.\ its girth.
We are interested in a more liberal notion of cycles, which leads to a
more restrictive notion of acyclicity that
forbids short \emph{coset cycles}, i.e.\ cyclic configurations of
cosets $g_i \CG[\alpha_i]$.

\bD[coset cycle]
\label{cosetcycledef}
\mbox{}\\
Let $\G$ be an $\E$-group, $n \geq 2$.
A \emph{coset cycle} of length $n$ in $\G$ is a
cyclically indexed sequence of pointed cosets
$(g_i \G[\alpha_i],g_i)_{i \in \Z_n}$ w.r.t.\ subgroups
$\G[\alpha_i]$ for $\alpha_i \subset E$ satisfying these conditions:
\bre
\item
(connectivity)
$g_{i+1} \in g_i \G[\alpha_i]$, i.e.\ $g_i \G[\alpha_i] =
g_{i+1} \G[\alpha_i]$;
\item
(separation)
$g_i \G[\alpha_{i,i-1}] \cap g_{i+1} \G[\alpha_{i,i+1}] = \emptyset$,
\ere
where $\alpha_{i,j} := \alpha_i \cap \alpha_j$.
\eD

We sometimes put a focus on coset cycles whose constituent cosets
stem from a restricted family of generated subgroups, and especially
from $\Gamma_k(\G)$ for some $1 \leq k \leq |E|$. With terminology
like \emph{coset cycle w.r.t.\ $\Gamma_k$} we then refer to coset
cycles $(g_i \G[\alpha_i])_{i \in \Z_n}$ with $\alpha_i \in \Gamma_k$,
i.e.\ with $|\alpha_i| < k$.

\bD[$N$-acyclicity]
\label{Nacycdef}
\mbox{}\\
For $N \ge 2$, an $\E$-group $\G$ or its Cayley graph $\CG$ are
\emph{$N$-acyclic} if they admit no coset cycles of lengths up to $N$.
\eD

Correspondingly $N$-acyclicity w.r.t.\ $\Gamma_k$
forbids coset cycles $(g_i \G[\alpha_i])_{i \in \Z_n}$
of lengths $n \leq N$ with $\alpha_i \in \Gamma_k$.
Obviously, non-trivial generator cycles are very special coset cycles
with singleton sets $\alpha_i = \{ e_i\}$.
So $N$-acyclicity w.r.t.\ $\Gamma_2(\G)$
precisely says that the girth of $\G$ or $\CG$ is larger than $N$.
Also note that $N$-acyclicity w.r.t.\ $\Gamma_k(\G)$ in particular implies
outright $N$-acyclicity for $\G[\alpha]$ for all $|\alpha| \leq k$.
For $G$ itself outright  $N$-acyclicity is the same as
$N$-acyclicity w.r.t.\ $\Gamma_{|E|}(\G)$.

It is important to note that the graph-theoretic diameter of an
$\alpha_i$-coset in the Cayley
graph or the cardinality of $\G[\alpha_i]$
cannot be uniformly bounded (e.g.\ in terms of $|\alpha_i|$).
Therefore no level
of generator acyclicity captures any fixed level of coset acyclicity.

From now on all reference to acyclicity will be to coset acyclicity.

The lowest level of coset acyclicity, viz.\ $N$-acyclicity for $N=2$,
is of special interest. It is easy to check that the condition for
$2$-acyclicity is equivalent to an intersection condition on pairs of
cosets, which is reminiscent of a notion
of simple connectivity.

\bO
\label{2acycobs}
An $\E$-group $\G$ is $2$-acyclic if, and only if, for all
$\alpha_1,\alpha_2 \strictsubset E$,
\[
\G[\alpha_1] \cap \G[\alpha_2] = \G[\alpha_1 \cap \alpha_2].
\]
\eO

The following associates acyclicity criteria with closure
properties and minimal supporting sets of generators.

\bR
\label{elementcosetsupportrem}
Consider an element $g \in \G$ and its $\alpha$-component
$B = g \G[\alpha] \subset \G$ for some
$\alpha \subset E$ in an $\E$-group $\G$.
\bre
\item
If $\G$ is $2$-acyclic then there is a unique $\subset$-minimal generator set
$\alpha_g \subset E$ such that $g \in \G[\alpha_g]$, which is obtained
as $\alpha_g = \bigcap \{ \alpha' \subset E \colon g \in \G[\alpha'] \}$.
\item
If $\G$ is $3$-acyclic then there is a unique $\subset$-minimal generator set
$\alpha_B \subset E$ such that $\G[\alpha_B] \cap B \not= \emptyset$,
which is obtained as
$\alpha_B = \bigcap \{ \alpha_h \subset E \colon h  \in B \}$.
\ere
\eR

\prf
Observation~\ref{2acycobs} implies that the family of subsets $\alpha'
\subset E$ for which $g \in \G[\alpha']$ is closed under intersections;
this immediately implies claim~(i). Towards claim~(ii) consider two
elements $g_i \in B$ and their supporting $\alpha_i := \alpha_{g_i}$
according to~(i) for $i=1,2$. We need to show that also $\alpha_0 :=
\alpha_1 \cap \alpha_2$ supports $B$ in the sense that
$\G[\alpha_0] \cap B \not= \emptyset$. For this consider the potential
$3$-cycle of cosets $1 \G[\alpha_1] = \G[\alpha_1]$, $g_1 \G[\alpha]$ and
$g_2\G[\alpha_2] = \G[\alpha_2]$. As $\G$ does not admit $3$-cycles of
cosets, at least one of the three instances of the separation conditions
in Definition~\ref{cosetcycledef} must fail. We argue that each such failure
yields an element in $B \cap \G[\alpha_0]$. Failure in the link
$\G[\alpha_1]$ means that there is some
$g' \in g_1 \G[\alpha_1\cap \alpha] \cap 1 \G[\alpha_1 \cap \alpha_2] $;
now $g' \in g_1 \G[\alpha_1\cap \alpha]$ implies that $g' \in B$
since $g_1 \in B$, and $g' \in \G[\alpha_0]$ as
$1 \G[\alpha_1 \cap \alpha_2] = \G[\alpha_0]$.
Failure in the link
$\G[\alpha_2]$ is entirely symmetric.
Failure in the link
$\G[\alpha]$ finally means that there is some
$g' \in g_1 \G[\alpha_1\cap \alpha] \cap g_2 \G[\alpha_2 \cap \alpha]$
which implies that $g' \in B$ as before. Moreover $g' \in \G[\alpha_i]$
as $g_i \in \G[\alpha_i]$ and $g' \in g_i \G[\alpha_i]$; so
$g' \in \G[\alpha_1] \cap \G[\alpha_2] = \G[\alpha_1 \cap \alpha_2] = \G[\alpha_0]$.
\eprf

\bL
\label{3acyclem}
If an $\E$-group $\G$ is compatible with $\CG[\alpha]$ for every
$\alpha \strictsubset E$ then $\G$ is $3$-acyclic.
\eL

\prf
Assume that $(g_i \G[\alpha_i],g_i)_{i \in \Z_3}$
formed a coset cycle in $\G$.
The separation condition implies
that $\alpha_i \strictsubset E$ and that, for instance,
\[
(\ast) \qquad g_0 \G[\alpha_{0,2}]\cap g_1 \G[\alpha_{0,1}] = \emptyset.
\]

By the connectivity condition, there are $w_j \in \alpha_j^\ast$ such that
\[
g_0^{-1} g_1 = [w_0]_\G, \;\; g_1^{-1} g_2 = [w_1]_\G, \;\;  g_2^{-1} g_0
= [w_2]_\G.
\]
Clearly $[w_2 w_0 w_1 ]_\G = 1$.
Let  $w_{0,j} \in \alpha_{0,j}^\ast$ be the projection of the
word $w_j$ to $\alpha_0^\ast$, as obtained by delition of all letters
$e \not\in \alpha_0$. If $\G$ is compatible with $\G[\alpha_0]$
then  $[w_2 w_0 w_1 ]_\G = 1$ implies that $[w_2w_0w_1]_\H = 1 \in
\sym(\H)$ for $\H = \CG[\alpha_0]$, which in turn implies that
$[w_{0,2} w_0 w_{0,1} ]_\G = 1$ since $[e]_\H$ is trivial for $e \not\in \alpha_0$.
But the operation of the corresponding sequence of
generators of $\sym(\CG[\alpha_0])$ maps the element
$g := [w_{0,2}]^{-1}_\G$ (via
$1$ and $g_0^{-1} g_1$) to  $g' := g_0^{-1} g_1 [w_{0,1}]_\G$.
As $g \in \G[\alpha_{0,2}]$ and $g' \in g_0^{-1} g_1\G[\alpha_{0,1}]$,
which by $(\ast)$ are disjoint subsets of $\G[\alpha_0]$,
it follows that $[w_{0,2} w_0 w_{0,1} ]_\G \not= 1$, a contradiction.
Analogously, $\G$ cannot admit $2$-cycles.
\eprf

\bL
\label{acychomlem}
$N$-acyclicity of $\G[\alpha]$ is preserved under inverse
homomorphisms that are injective on $\alpha'$-generated subgroups
for all $\alpha'\strictsubset \alpha$.
\eL

\prf
If $h \colon \Ghat[\alpha] \rightarrow \G[\alpha]$ is a
homomorphism of $\alpha$-groups that is a local isomorphism in restriction to each
$\Ghat[\alpha']$ for $\alpha'\strictsubset \alpha$, then $h$ maps
a coset cycle in $\Ghat$ to a coset cycle in $\G$. The connectivity
condition is obviously maintained under~$h$. The crux
of the matter is the separation condition for links in a potential
coset cycle. As each $\alpha_i$-coset in $\Ghat$, for $\alpha_i \strictsubset
\alpha$, is mapped bijectively onto its image coset in $\G$, so are
the disjoint critical $\alpha_{i,i\pm 1}$-cosets as its subsets.
\eprf

Recall Lemma~\ref{Ghatcompatlem}, which is to be used to
eliminate $N$-cycles of cosets with increasing numbers of
generators, in an inductive treatment.
More specifically, part~(c) of that lemma points at the
way to rule out coset cycles of length up to $N$ formed by
$\alpha$-cosets for $\alpha \in \Gamma_k$ by achieving compatibility
with suitable $\E$-graph configurations $\H_k(\G)$.
The relevant configurations in $\H_k(\G)$ will be suitable amalgams of $\E$-graphs
$\CG[\alpha]$ for $\alpha \in \Gamma_k$, which need to be designed so
as to meet the downward compatibility criterion of part~(b).
Towards coset acyclicity we can use amalgamation chains that unfold
potential cycles.

\section{Free amalgams}
\label{amalgsec}

Free amalgams of copies of $\E$-graphs $\CG[\alpha_i]$
seek to superpose these copies with just those identifications that are forced
by shared generator edges. We first look at
superpositions of two $\CG[\alpha_i]$, then expand the idea to certain
chains or clusters of several $\CG[\alpha_i]$. In each case,
the isomorphism type of the resulting $\E$-graphs is fully determined
by the isomorphism types of the constituents $\CG[\alpha_i]$ -- and not by the
manner in which the constituents are embedded in $\CG$ as weak subgraphs
$\CG[\alpha_i] \subsetw \CG$.
If $\G$ satisfies appropriate acyclicity conditions, however, the
free amalgam will be naturally isomorphic to the corresponding
embedded weak subgraph of $\CG$ on a union of $\alpha_i$-cosets of $\G$
(cf.~Observations~\ref{twoamalgobs},~\ref{amalgchainobs},~\ref{amalgclusterobs}).
For instance, if $\G$ is $2$-acyclic the
weak subgraphs of $\CG$ on overlapping cosets of the form
$g G[\alpha_1] \cup g G[\alpha_2] \subset G$
(with induced $\alpha_i$-edges on the $\alpha_i$-coset) will all be
isomorphic to the free amalgam $\CG[\alpha_1] \oplus \CG[\alpha_2]$
(Observation~\ref{twoamalgobs}).

\bD[free amalgam]
\label{twoamalgdef}
\mbox{}\\
Let $\alpha_1,\alpha_2 \subset E$ with intersection
$\alpha_0 = \alpha_1 \cap \alpha_2$, $\G$ an $\E$-group.
The \emph{free amalgam}
$\CG[\alpha_1] \oplus \CG[\alpha_2]$
of the $\E$-graphs $\CG[\alpha_i] \subsetw \CG$ for $i=1,2$ is
the $\E$-graph $\str{A}$ obtained as the result of free amalgamation of disjoint
copies of relational structures $\str{A}_i \simeq \CG[\alpha_i]$ via the shared
embedded weak substructure $\str{A}_0 \simeq \CG[\alpha_0] \subsetw \CG[\alpha_i]$.
\eD

\[
\mbox{
\resizebox{.65\textwidth}{!}{\xymatrix{
&&
\CG[\alpha_1]
\ar[rrd] &&
\\
*[l]+{\CG[\alpha_0]\!\!\nt} \ar[rru] \ar[rrd] &&&&
*[r]+{\nt\!\!\!\!\CG[\alpha_1] \oplus \CG[\alpha_2]}
\\
&&
\CG[\alpha_2]
\ar[rru] &&
}}}
\]

The arrows in the diagram represent injective relational homomorphisms,
and the target structure interprets $R_e$ for $e \in \alpha_1 \cup
\alpha_2$ as the union of the homomorphic images of $R_e$ from either
constituent.

In related model-theoretic terminology
the free amalgam of the $\CG[\alpha_i]$ is the \emph{disjoint union over
$\CG[\alpha_0]$} of $\CG[\alpha_1]$ and $\CG[\alpha_2]$. It may be obtained
from canonical disjoint isomorphic copies
$\str{A}_i := \CG[\alpha_i] \times \{i\} \simeq \CG[\alpha_i]$ through
identification of $a_1 = (g_1,1) \in A_1$ with $a_2 = (g_2,2) \in A_2$
precisely for $g_1 = g_2 \in \G[\alpha_0]$.
That the resulting graph is a strict $\E$-graph is seen as follows.
It is an $\E$-graph since for $e \in \alpha_0$ the overlap
corresponding to $\G[\alpha_0]$ is closed under $R_e$-edges; it is strict
since the amalgam does not import loops, and also cannot have multiple
edges as two vertices in the overlap corresponding to $\G[\alpha_0]$ can be linked
by at most one $R_e$ even in $\CG$.

\medskip\noindent
A seemingly more general concept of free amalgamation would specify
an isomorphism between specific $\alpha_0$-cosets in the
$\CG[\alpha_i]$ to induce the overlap; alternatively one could specify
a pair of elements from the $\CG[\alpha_i]$ to be identified, which in
turn induces a canonical isomorphism between corresponding $\alpha_0$-cosets.
Such pointed copies of $\CG[\alpha_i]$ are a natural choice
when we iterate the construction as in coset chains (see below).
For the free amalgam of just two $\CG[\alpha_i]$ any such choices
lead to isomorphic results. This is due to the internal homogeneity of
Cayley graphs of $\E$-groups.

\bO
\label{twoamalgobs}
The map that sends an element of the free amalgam
$\CG[\alpha_1] \oplus  \CG[\alpha_2]$ to the
group element in $\G$ that it stems from is a homomorphism of
$\E$-graphs; if the $\E$-group $\G$ is $2$-acyclic then this
homomorphism is injective so that
$\CG[\alpha_1] \oplus  \CG[\alpha_2]$
is realised as a weak substructure of $\CG$ (via a canonical
isomorphism).
$\G$ is $2$-acyclic if, and only if,
$\CG[\alpha_1] \oplus  \CG[\alpha_2] \subsetw \CG$ for any two
$\alpha_i \strictsubset E$.
\eO

\subsection{Amalgamation chains and clusters}
Iterated or multiple free amalgams of more than two $\CG[\alpha_i]$
can be defined in more general contexts, but special restrictions need
to be in place to guarantee that he result is a strict $\E$-graph, or
even just an $\E$-graph. We only discuss two patterns of special
interest to us: \emph{amalgamation chains} and
\emph{amalgamation clusters}.
Both patterns are motivated by desirable acyclicity properties w.r.t.\
local overlaps between $\G[\alpha_i]$-cosets in $\G$. In other words,
they unfold overlaps among a family of $\CG[\alpha_i]$ in the
`tree-like' pattern encountered in sufficiently acyclic $\G$.
This is being brought out in Observations~\ref{amalgchainobs}
and~\ref{amalgclusterobs}, respectively, which extend the basic idea
of Observation~\ref{twoamalgobs} above to the two more complex patterns.
While the pattern of \emph{amalgamation chains} corresponds to a linear
arrangement as in a tree branch, the pattern of
\emph{amalgamation clusters} corresponds to the branching
in a single parent node.

\bD[amalgamation chain]
\label{amalgchaindef}
\mbox{}\\
Let $\G$ be an $\E$-group, $N \geq 1$ and
$\alpha_i \strictsubset E$ for $1 \leq i \leq N$
with intersections $\alpha_{i,i+1} := \alpha_i \cap \alpha_{i+1}$
for $1 \leq i < N$.
Consider the sequence of pointed
$\E$-graphs $(\CG[\alpha_i],g_i)_{1 \leq i \leq N}$ and assume
that the $g_i \in \G[\alpha_i] \subsetw \CG$ are such that the cosets
$1 \G[\alpha_{i-1,i}] \subset \G[\alpha_i]$ and $g_i
\G[\alpha_{i,i+1}]\subset \G[\alpha_i]$
are disjoint in $\G[\alpha_i]$.
In this situation, the \emph{free amalgamation chain}
$\bigoplus_{i=1}^N (\CG[\alpha_i],g_i)$ is the $\E$-graph $\str{A}$ obtained as the result of simultaneous free amalgamation of disjoint copies of relational
structures $\str{A}_i \simeq \CG[\alpha_i]$ via the shared
embedded weak substructures $\str{A}_{i,i+1} \simeq
g_i \CG[\alpha_{i,i+1}] \subsetw \CG[\alpha_i]$ and
$\str{A}_{i,i+1} \simeq 1 \CG[\alpha_{i,i+1}] \subsetw \CG[\alpha_{i+1}]$.
\eD

Note that the precondition on disjoint overlaps w.r.t.\ the
next neighbours in the chain ensures that there is no interference
between the pairwise amalgamation processes between next neighbours.
Also note that (the images of) the cosets $g_i \G[\alpha_{i,i+1}]$ for
$1 \leq i < N$ are separators along the chain.

\bO
\label{amalgchainobs}
Whenever the amalgamation chain $\bigoplus (\CG[\alpha_i],g_i)$
is defined, there is a unique homomorphism from $\bigoplus (\CG[\alpha_i],g_i)$ to
$\CG$, which maps $1$ in (the isomorphic copy of) $\CG[\alpha_1]$ to
$1 \in \CG$.  If the $\E$-group $\G$ is $N$-acyclic then this
homomorphism is injective and $\bigoplus (\CG[\alpha_i],g_i)$
is realised as a weak substructure of $\CG$ (via an essentially
canonical isomorphism).
\\
$\G$ is $N$-acyclic if, and only if,
$\bigoplus_i (\CG[\alpha_i],g_i) \subsetw \CG$ for any
sequence of up to $N$ many pointed generated
subgroups $(\G[\alpha_i],g_i)$ such that
the amalgamation chain is defined.
\eO

For the contrapositive of the `if'-part of last claim consider an
amalgamation chain
$\bigoplus_{i=1}^n (\CG[\alpha_i],g_i)$ that is not
injectively mapped into $\CG$ by the natural homomorphism.
For an $\ell$ that is minimal with the property that
$1 \leq k <  k + \ell \leq N$ and that the subchain $\bigoplus_{i=k}^\ell
(\CG[\alpha_i],g_i)$ is not injectively embedded,
its homomorphic image in $\CG$ constitutes a coset cycle.

\bD[amalgamation cluster]
\label{amalgclusterdef}
\mbox{}\\
Let $\G$ be an $\E$-group, $N \geq 1$.  Consider a family of
generated subgroups $\G[\alpha_i]$ for $\alpha_i \strictsubset E$
for $1 \leq i \leq N$ which are $2$-acyclic with
Cayley graphs $\CG[\alpha_i] \subsetw \CG$. For
$1 \leq i \leq N$ let $\alpha_{i,i+1} := \alpha_i \cap \alpha_{i+1}$.
The \emph{free amalgamation cluster}
$\bigoplus_{i=1}^N \CG[\alpha_i]$
is the $\E$-graph $\str{A}$ obtained as the result of
simultaneous free amalgamation of disjoint copies of relational
structures $\str{A}_i \simeq \CG[\alpha_i]$ where
elements of $\str{A}_i$ and $\str{A}_j$ are identified precisely if
they correspond to the same element of the group $\G[\alpha_{i,j}]$.
\eD

We need to argue for existence (well-definedness) of this
amalgam.

\bL
In the situation of Definition~\ref{amalgclusterdef} the free
amalgamation cluster
$\bigoplus_{i=1}^N \CG[\alpha_i]$ is isomorphic to the quotient
of the disjoint union of the $\CG[\alpha_i]$, as represented
over the universe $\bigcup_i (\G[\alpha_i] \times \{ i \})$,
w.r.t.\ the equivalence relation $\sim$ that identifies $(g_i,i)$ with
$(g_j,j)$ if, and only if, $g_i = g_j \in \G[\alpha_{i,j}]$.
This quotient structure is a strict $\E$-graph.
\eL

\prf
Let $\str{A}$ be the disjoint union of the $\CG[\alpha_i]$
over the universe $A = \bigcup_i (\G[\alpha_i] \times \{ i \})$.
The following shows that $\sim$ is transitive, hence an equivalence
relation (reflexivity and symmetry are obvious). For instance, if
$(g_1,1) \sim (g_2,2)\sim (g_3,3)$ where
$g_i \in \G[\alpha_i]$, $i =1,2,3$, we need to show that $(g_1,1) \sim (g_3,3)$.
The assumption that $(g_1,1) \sim (g_2,2)$ implies that $g_1=g_2 \in \G[\alpha_{1,2}]$
while $(g_2,2) \sim (g_3,3)$ implies that $g_2=g_3 \in
\G[\alpha_{2,3}]$. By the precondition on intersections between the
$\G[\alpha_{i,j}]$ in the definition of the cluster (here an instance of
$2$-acyclicity within $\G[\alpha_2]$), it follows that
$g_1 =g_2 = g_3 \in \G[\alpha_{1,2} \cap \alpha_{2,3}]
\subset \G[\alpha_{1,3}]$, whence $(g_1,1) \sim (g_3,3)$ follows.
That the quotient structure $\str{A}/{\sim}$ does not induce loops,
edges w.r.t.\ multiple $R_e$ or branching w.r.t.\ a single $R_e$
follows from an analysis of when equivalence classes
$[g_i,i]$ and $[g_j,j]$ are linked by an $e$-edge in the quotient.
This is the case if, and only if, $(g_i,i) \sim (g,k)$ and
$(g_j',j) \sim (g',k)$ for some $g,g' \in \G[\alpha_k]$ with
$e \in \alpha_k$ and $g' = g e$. It follows that $g \not= g'$
and $[g_i,i] = [g,k]  \not= [g',k]  = [g_j',j]$ (no loops) and that
$g' \not= g e'$ for any $e' \not= e$ (no multiple edges).
If $[g,i]$ were incident with two $e$-edges in the quotient,
say with $e$-edges to $[g_j',j]$ and to $g_k',k]$, we may w.l.o.g.\
assume that $e \in \alpha_j \cap \alpha_k$ and hence $e \in
\alpha_{j,k}$. It follows that $(g_i,i) \sim (g_j,j) \sim (g_k,k)$ for
suitable $g \in \G[\alpha_{j,k}]$ so that both
$g_j' = ge$ and $g_k' = ge$ in $\G[\alpha_{j,k}]$.
This shows that $g_j' = g_k'$ whence also $(g_j',j) \sim (g_k',k)$
so that the two $e$-edges are one and the same.
\eprf

\bR
\label{elementsupportrem}
In the situation of Definition~\ref{amalgclusterdef}
consider an element $x$ of the free amalgamation cluster
$\bigoplus_{i=1}^N \CG[\alpha_i]$ and let $M \subset
\{ 1,\ldots, N\}$ be the subset of indices $i$ for which $x$ is
represented in the copy of $\CG[\alpha_i]$ in $\bigoplus_{i=1}^N \CG[\alpha_i]$.
Then $x$ determines a unique minimal set
$\alpha_x \subset E$ such that $x$ is represented
in $\CG[\alpha_x] \subsetw \CG[\alpha_i]$ for every $i \in M$.
\eR

\prf
The set $\alpha_x$ arises as the intersection of all those
$\CG[\alpha'] \subsetw \CG[\alpha_i]$ which represent it in the above
sense. This family of generator subsets is closed under intersection
due to the free nature of the amalgamation cluster and, for reasoning
inside constituents $\CG[\alpha_i]$, their
$2$-acyclicity (cf. part~(i) of Remark~\ref{elementcosetsupportrem}).
\eprf

\bO
\label{amalgclusterobs}
Whenever the amalgamation cluster $\bigoplus \CG[\alpha_i]$ is
defined, there is a unique homomorphism from $\bigoplus \CG[\alpha_i]$ to
$\CG$, which maps $1$ in (the isomorphic copies) of the $\CG[\alpha_i]$ to
$1 \in \CG$.  If the $\E$-group $\G$ is $2$-acyclic then this
homomorphism is injective so that  $\bigoplus \CG[\alpha_i]$
is realised as a weak substructure of $\CG$ (via an essentially
canonical isomorphism).
\eO

\subsection{Connected components of free amalgams}
\label{conninfreeamalgsec}

The structure of $\beta$-connected components of
free amalgamation chains and clusters is important
when these configurations occur as components of an $\E$-graph
$\H$ from which an $\E$-group $\G = \sym(\H)$ is
generated as through permutation group action.
Recall that the $\beta$-generated subgroup $\G[\beta]$ of
$\G = \sym(\H)$ is fully determined by
the permutation group action on the $\beta$-connected components
of $\H$; and hence that some $\beta$-group $\Ghat[\beta]$ admits a
homomorphism to $\G[\beta]$ if, and only if, it is compatible with
all $\beta$ components of $\H$.

We start with the simple situation of just a binary free amalgam
$\CG[\alpha_1] \oplus \CG[\alpha_2]$ for
$\alpha_1,\alpha_2 \subset E$ with intersection $\alpha_0 = \alpha_1
\cap \alpha_2$. In this, as in the remaining cases, we want to see that
$\beta$-connected components are again free amalgams of the
corresponding kind, and either trivial or built from smaller
$\CG[\alpha_i]$ (this can be regarded as a notion of downward
compatibility for the corresponding class of configurations).
The proofs show that acyclicity criteria for
the constituent $\CG[\alpha_i]$ are essential in this.

\bL
\label{comptwoamalglem}
Let $\alpha_1,\alpha_2,\beta \strictsubset E$, $\G$ an $\E$-group.
If $\G[\alpha_1]$ and $\G[\alpha_2]$ are $2$-acyclic, then
the $\beta$-connected components of vertices in
$\CG[\alpha_1] \oplus \CG[\alpha_2]$
are either isomorphic to one of the
$\CG[\beta \cap \alpha_i]$ or to a free amalgam of the form
$\CG[\beta \cap \alpha_1] \oplus \CG[\beta \cap \alpha_2]$.
\eL

\prf
Let $B$ be the vertex set of the $\beta$-component in question.
If $B$ is fully contained
in (the isomorphic copy of) one of the constituent $\CG[\alpha_i]$,
then the $\beta$-component
is isomorphic, as an $\E$-graph, to $\CG[\beta \cap \alpha_i]$ for that $\alpha_i$.
Otherwise $B$ must contain a vertex $v$ in the
overlap of the constituent $\CG[\alpha_i]$ and $\beta \cap \alpha_i
\not= \emptyset$ for $i=1,2$.
For $i=1,2$ let $A_i$ be the vertex set
corresponding to the constituent $\CG[\alpha_i]$ in
$\CG[\alpha_1] \oplus \CG[\alpha_2]$. So $A_1 \cap A_2$
corresponds to  $\G[\alpha_0] \subset \G[\alpha_i]$ where $\alpha_0 =
\alpha_1 \cap \alpha_2$.
Considering $B \cap A_i$ within (the isomorphic copy of)
$\CG[\alpha_i]$, the $(\beta \cap \alpha_i)$-
and $(\beta \cap \alpha_0)$-cosets of the shared vertex $v$
cannot form a $2$-cycle of cosets in $\CG[\alpha_i]$. This implies
that $B$ intersects the overlap region $A_1 \cap A_2$ in a single
$(\beta \cap \alpha_0)$-coset. This further implies that $B$ extends
from this copy of $\CG[\beta \cap \alpha_1
\cap \alpha_2]$ to a full copy of $\CG[\beta\cap \alpha_i]$ within
$A_i$ for $i = 1,2$. So the $\beta$-component in question
is isomorphic to the free amalgam $\CG[\beta \cap \alpha_1] \oplus
\CG[\beta \cap \alpha_2]$ as claimed.
\eprf

\bL
\label{compamalgchainlem}
Let $\alpha_i \strictsubset E$ for $1\leq i\leq N$, $\beta \subset E$,
and let the $\E$-group $\G$ and elements $g_i \in \G[\alpha_i]$
be such that the free amalgamation chain
$\bigoplus_{i=1}^N (\CG[\alpha_i],g_i)$ is defined.
If the $\G[\alpha_i]$ are $2$-acyclic, then
the $\beta$-connected components of vertices in the $\E$-graph
$\bigoplus_{i=1}^N (\CG[\alpha_i],g_i)$
are isomorphic to  free amalgamation chains of the form
$\bigoplus_{i=s}^{t} (\CG[\beta_i],h_i)$ for
$\beta_i := \beta \cap \alpha_i$,
some $1 \leq s \leq t \leq N$, and suitable choices
of $h_i \in \G[\alpha_i]$.
\eL

\prf
This follows along the same lines as the binary case in
Lemma~\ref{comptwoamalglem}. Let $B$ be the $\beta$-component under
consideration and choose the index $s$ minimal such that the
$\CG[\alpha_s]$-copy in the chain contributes to $B$.
Starting from a vertex in $B$ from the $\CG[\alpha_s]$-copy we may proceed
through one overlap at a time until the sub-chain may die out.
The $h_i$ are chosen in the (copies of the) overlaps
$\CG[\alpha_{i,i+1}]$ (where $\alpha_{i,i+1} = \alpha_i
\cap \alpha_{i+1}$) that contribute to $B$.
The condition of $2$-acyclicity for the $\G[\alpha_i]$
guarantees that the contribution of each overlap
$\CG[\alpha_{i,i+1}]$ is a single $(\beta \cap \alpha_{i,i+1})$-coset
(note that $\beta \cap \alpha_{i,i+1} = \beta_i \cap \beta_j$).
\eprf

\bD[cluster property]
\label{clusterpropamalgclusterdef}
\mbox{}\\
An $\E$-group $\G$ has the \emph{cluster property} if for all
free amalgamation clusters $\bigoplus_{i \in I} \CG[\alpha_i]$ with
$\alpha_i \strictsubset E$ every
$\beta$-connected component $B$ for $\beta \strictsubset E$
contains an element~$x$ such that $\alpha_x = \alpha_B := \bigcap \{ \alpha_y
\colon y \in B \}$ and, as a $\beta$-graph, is isomorphic to the free
amalgamation cluster $\bigoplus_{i \in M} \CG[\beta_i]$ where
$\beta_i = \beta \cap \alpha_i$ and $M = \{ i \in I \colon \beta_i
\not= \emptyset \}$.
\eD

\bL
\label{compamalgclusterlem}
For any $\E$-group $\G$ and $\alpha \subset E$,
if $\G[\alpha']$ is $2$-acyclic and has
the cluster property for all $\alpha' \strictsubset \alpha$
then $\G[\alpha]$ has the cluster property.
\eL

\prf
Let $\beta \strictsubset \alpha$ and consider a $\beta$-component $B$
of $\bigoplus \CG[\alpha_i]$, $\beta_i := \beta \cap \alpha_i$,
$M := \{ i \colon \beta_i \not= \emptyset \}$ as in the statement.
The claim is trivial if $M$ is empty or a singleton set, as then
$B$ is a singleton or contained in a single $\CG[\alpha_i]$ which
has the cluster property by assumption.

If $M$ has a least two elements, say $i=1,2$,
consider an element $x \in B$ that is an element of
the constituent $\CG[\alpha_i]$-copies for $i=1,2$,
neither of which covers all of $B$. Consider the minimal supporting set of
generators $\alpha_x  \subset \alpha_0 := \alpha_1 \cap \alpha_2$
according to Remark~\ref{elementsupportrem}, and
the $\beta_i$-connected components $B_i$ of $x$ in the
constituent $\CG[\alpha_i]$-copies, which are $\beta_i$-cosets.
The cluster property for the $\G[\alpha_i]$
provides $x_i \in B_i$ with $\alpha_{x_i} =
\alpha_{B_i} = \bigcap \{ \alpha_y \colon y \in B_i \}$.
By minimality of $\alpha_{B_i}$, $\alpha_{x_i} = \alpha_{B_i} \subset
\alpha_x$. Now $x_i$ is linked to $x$ by a $\beta_i$-walk,
and also (via $1$ in the copy of $\CG[\alpha_i]$) by the composition
of an $\alpha_{x_i}$-walk and an $\alpha_x$-walk, which
is an $\alpha_0$-walk
(as $\alpha_{x_i} = \alpha_{B_i} \subset \alpha_x \subset \alpha_0$).
Since $\G[\alpha_i]$ is $2$-acyclic, $x_i$ must be linked to $x$ by a
$\beta_0$-walk for $\beta_0 := \beta \cap \alpha_0$. It follows that
both $x_i$ are elements of the shared copy of $\CG[\alpha_0]$ and
of the $\beta$-component $B_0$ of $x$ within this copy.
As $\CG[\alpha_0]$ has the cluster property, this $\beta$-component
$B_0$ of $x$ in $\CG[\alpha_0]$ has some element $x_0 \in B_0$ such that
$\alpha_{x_0} = \alpha_{B_0} = \bigcap_{y \in B_0} \alpha_y$.
By minimality of $\alpha_{B_0}$ in the shared copy
of $\CG[\alpha_0]$, which represents $x$ and all the $x_i$, we find that
$\alpha_{B_0} \subset \alpha_{x_1}\cap \alpha_{x_2} =
\alpha_{B_1}\cap \alpha_{B_2}$.
Minimality of the $\alpha_{B_i}$ in their $\CG[\alpha_i]$-copies
implies that $\alpha_{B_0} = \alpha_{B_1}=\alpha_{B_2}$.
As $\alpha_1$ and $\alpha_2$ were chosen arbitrarily
from among the $\alpha_i$ with $\beta_i \not= \emptyset$
we find that all contributing $\beta_i$-cosets in their respective
$\CG[\alpha_i]$-copies overlap in a shared $\beta_0$-coset that is
part of a shared constituent $\CG[\alpha_0]\subsetw \CG[\alpha_i]$
where $\alpha_0 = \bigcap_{i \in M} \alpha_i$ and
$\beta_0 = \beta \cap \alpha_0$.
Hence the $\beta$-reduct of the substructure $\bigoplus \CG[\alpha_i]
\restr B$ is isomorphic to the free amalgam $\bigoplus_{i \in M} \CG[\beta_i]$
whose core is the $\CG[\alpha_0]$-copy shared by all the $B_i$ for $i \in M$.
\eprf

\bC
\label{clusterpropcor}
Any $\E$-group $\G$ that is $2$-acyclic has the cluster property.
\eC

\prf
The cluster property for $\G[\alpha]$ is trivial for
$|\alpha| \leq 2$ as connected components for $\beta \strictsubset \alpha$
can only be singletons or individual $\beta$-edges linking two
vertices $x_i$ whose minimal supporting sets $\alpha_{x_i}$ can at most
differ by the label of that $\beta$-edge. An inductive application
of the lemma yields the cluster property for all $\G[\alpha]$ and
hence for $\G = \G[E]$.
\eprf

\section{Construction of N-acyclic E-groups}
\label{acycsec}

The actual construction of finite $N$-acyclic $\E$-groups $\G$ is
achieved in an inductive process that produces, for fixed $N \geq 2$,
a sequence of $\E$-groups  $\G_k$,
for increasing values of $k$ in the range between $1$ and $|E|$ such
that
\[
\G_k \mbox{ is $N$-acyclic w.r.t.\ } \Gamma_k(\G_k),
\]
i.e.\ $\G_k$ admits no coset cycles of length up to $N$
with constituent cosets w.r.t.\ subgroups from $\Gamma_k(\G_k)$
($\alpha$-cosets for $|\alpha| < k$).
In this inductive sequence $\G_{k+1}$ is obtained as
$\G_{k+1} := \sym(\H_k)$ from an $\E$-graph $\H_k$ which in turn is
defined from $\CG_k$; the $\E$-graph $\H_k$ is chosen such that
\bre
\item[--]
$\G_{k+1} \succeq \G_{k}$,
\item[--]
$\Gamma_{k+1}(\G_{k+1}) = \Gamma_{k+1}(\G_k)$, i.e.\
$\G_{k+1}[\alpha] \simeq \G_k[\alpha]$ for $|\alpha| \leq k$.
\ere

The following can then be used for the passage from
$\G_k$ to $\G_{k+1}$ at the level of generated subgroups
$\Gamma_{k+1}(\G_{k+1})$ in relation to chains over
$\Gamma_{k+1}(\G_{k+1}) = \Gamma_{k+1}(\G_k)$.

\bL
\label{fromcompattoacyclem}
For $n \geq 1$, let $\G[\alpha]$ be compatible with all free
amalgamation chains of length up to~$n$
with constituents $\CG[\alpha']$ for $\alpha' \strictsubset \alpha$.
Then $\G[\alpha]$ is $N$-acyclic for $N = n+2$.
\eL

\prf
The gist of the matter is that $\G \succeq \sym(\H)$ for every
free amalgamation chain $\H$ of length up to $n$.
These free amalgamation chains unfold potential coset cycles. This rules out
corresponding cycles in $\sym(\H)$ and hence in $\G$ as follows.
Suppose the pointed cosets $(g_i \G[\alpha_i],g_i)_{i \in \Z_N}$
formed a coset cycle in $\G$.
Similar to the argument in Lemma~\ref{3acyclem}, we think of cutting
the cycle (this time in $g_0$) and test the permutation group action
on a chain formed by the remaining links,  viz.\ on the free amalgamation
chain
\[
\H = \bigoplus_{i=1}^n (\CG[\alpha_i],g_i^{-1}g_{i+1})
\]
of length $n = N-2$. As before let $\alpha_{i,j} := \alpha_i \cap \alpha_j$,
and let $w_i \in \alpha_i^\ast$ be such that $[w_i]_\G = g_i^{-1} g_{i+1}$.
For the links from and to $g_0$ in the cycle,
$w_0 \in \alpha_0^\ast$ and $w_{n+1} \in \alpha_{n+1}^\ast$,
we also look at the projections of
to the neighbouring constituents in the chain $\H$. Let
$w_{0,1} \in \alpha_{0,1}^\ast$ be the projection of $w_0$ to $\alpha_1$
and
$w_{n,n+1} \in \alpha_{n,n+1}^\ast$ the projection of $w_{n+1}$ to $\alpha_n$.
Let $v$ be the element of the chain $\H$ that corresponds to
$[w_{0,1}]_\G^{-1}$ in its first constituent $\CG[\alpha_1]$,
and consider the permutation group action of $[\prod_{i=0}^{n+1}
w_i]_\H \in \sym(\H)$, corresponding to $\prod_{i= 0}^{n+1}
(g_i^{-1} g_{i+1})= 1 \in \G$, on $v$ in $\H$. By the separation condition
for the $\alpha_0$-link of the cycle, the generator sequence
$w_0$ has the same effect on $v$ as its projection $w_{0,1}$ and
maps $v$ to the element corresponding to $1$ in the first constituent
$\CG[\alpha_1]$ of $\H$; the separation condition for the
$\alpha_i$-links up to $i =n$ imply that
$[\prod_{i= 0}^{n} w_i]_\H$ maps $v$ to
the element corresponding to $g_n^{-1}g_{n+1}$ in the
last constituent $\CG[\alpha_n]$ of $\H$; and the separation
condition for the $\alpha_{n+1}$-link of the cycle shows that
the final image of $v$ is an element in the $\alpha_{n,n+1}$-component
of $g_n^{-1}g_{n+1}$ in that $\CG[\alpha_n]$ constituent of $\H$. But
this image is necessarily distinct from $v$, contradicting compatibility
of $\G$ with $\H$, as $[\prod_{i=0}^{n+1} w_i]_\G = 1$.
\eprf

The following lemma focuses on the underlying induction scheme in the
proposed construction.

\bL
\label{indschemaNacyclem}
For any finite $\E$-group $\G$ and $n \geq 1$ there is a sequence
of finite $\E$-groups $(\G_k)_{k \leq |E|}$ starting with $\G_0 := \G$ such
that for  $k < |E|$:
\bre
\item
$\G_k \preceq \G_{k+1}$,
\item
$\Gamma_{k+1}(\G_k) = \Gamma_{k+1}(\G_{k+1})$,
\item
$\G_{k+1}$ is compatible with all free amalgamation chains of length
up to $n$ over $\Gamma_{k+1}(\G_{k+1})  = \Gamma_{k+1}(\G_k)$.
\ere
It follows that, for $N = n+2$,
$\G_{k+1}$ is $N$-acyclic w.r.t.\ $\Gamma_{k+1}(\G_{k+1}) = \Gamma_{k+1}(\G_k)$.
In particular, $\G_k[\alpha]$ is $N$-acyclic for all $\alpha$ of size
$|\alpha|  \leq k$, and for $\Ghat := \G_{|E|}$,
\[
\G \preceq \Ghat \; \mbox{ where $\Ghat$ is $N$-acyclic.}
\]
\eL

\prf
The compatibility/acyclicity requirement in~(iii) is vacuous at the level of
$k=0$, as is the conservative behaviour in~(ii) for $1$-generator
subgroups, which are isomorphic to $\Z_2$ in any $\E$-group.
For $k \geq 0$, $\G_{k+1}$ can be obtained as
$\G_{k+1} = \sym(\H_k)$ where $\H_k$ is the disjoint union of
copies of $\CG_k$ and every free amalgamation chain
of length up to $n$ with constituents
$\G_k[\alpha_i]$ for $\alpha_i \in \Gamma_{k+1}$.
Lemma~\ref{Ghatcompatlem} and Lemma~\ref{compamalgchainlem}
show that $\G_{k+1}$ is as required in~(i) and~(ii) in relation to
$\G_k$. Condition~(iii) follows by choice of $\H_k$ (for
compatibility) and Lemma~\ref{fromcompattoacyclem}
(for acyclicity).
\eprf

Recall from Definition~\ref{Esymmdef} the notion of
symmetries for $\E$-groups and $\E$-graphs that are induced by
permutations of the set $E$.
It is clear from the construction steps in
Lemma~\ref{indschemaNacyclem} above that they do not
break any such symmetry in the passage from $\G_k$ to $\G_{k+1}$.
It follows that the passage from $\G$ to an $N$-acyclic $\Ghat \succeq
\G$ preserves all symmetries of $\G$. We state  this additional
feature in the theorem which otherwise just sums up the outcome
of the lemma.

\bT
\label{symmacycEgroupthm}
For every finite $\E$-group $\G$ and $N \geq 2$ there is
a finite $\E$-group $\Ghat \succeq \G$ that is $N$-acyclic and
fully symmetric over $\G$ in the sense that every permutation
of the generator set $E$ that is a symmetry of $\G$ extends to a
symmetry of $\Ghat$: $\G^\rho \simeq \G \Rightarrow \Ghat^\rho \simeq \Ghat$.
\eT

In particular, we obtain finite $N$-acyclic $\E$-groups $\Ghat$ that
are fully symmetric, admitting every permutation of $E$ as a
symmetry, if we start from the fully symmetric $\G := \sym(\H)$
for the hypercube $\H = 2^E$.

\section{Constraints on generator sequences}
\label{constraintsec}

The building blocks of plain coset cycles are
generated subgroups of the form $\G[\alpha] \subset \G$, which may
also be seen as the images of $\alpha^\ast \subset E^\ast$
under the natural homomorphism
\[
\barr{rcl}
[\,\nt\,]_{\G} \colon E^\ast &\longrightarrow& \G
\\
w = e_1\cdots e_n & \longmapsto & [w]_{\G} := \prod_{i=1}^n e_i = e_1 \cdots e_n
\earr
\]
that associates a group element with any (reduced) word over $E$.
This association naturally translates to cosets $g \G[\alpha]$.
Alternatively, $\G[\alpha]$ and
$g \G[\alpha]$ may be regarded as the $\alpha$-connected
components of $1$ or $g$ in the Cayley graph $\CG$ of $\G$.

A natural way of putting extra constraints on these weak subgraphs,
with reasonable closure properties in terms of
generator sets $\alpha \subset E$, is the following. Consider a
fixed $\E$-graph $\I = (S,(R_e)_{e \in E})$ on vertex set $S$.
We regard $\I$ as a template for systematic restrictions on patterns
of generator sequences, calling it a \emph{constraint graph}.

\bProv
\label{constraintpatternprov}
We fix an $\E$-graph $\I = (S,(R_e)_{e \in E})$ as a
\emph{constraint graph}, and consider
only $\E$-groups $\G$ that are compatible with $\I$,
i.e.\ with $\G \succeq \sym(\I)$.
\eProv

\bR
\label{compatconstraintrem}
The restriction to $\E$-groups that are compatible with $\I$,
$\G \succeq \sym(\I)$, does imply that there is a well-defined group
action of $\G$ on $\I$. But w.r.t.\ this group action, any $s \in S$
that is not incident with an $e$-edge is a fixed point of
$\pi_e \in \sym(\I)$. As $\I$ will typically not be a complete
$\E$-graph, the Cayley graph of $\CG$ does not map
homomorphically to $\I$. But $\alpha$-walks from $s \in \I$ do have
unique lifts to $\alpha$-walks from any $g \in \CG$. Compatibility says
that lifts at the same $g \in \CG$ of different walks from
$s \in S$ can only meet in $\CG$ above positions in which the
given walks meet in $\I$.
\eR

The idea is to regard $\I$ as a template for edge patterns of walks
and correspondingly restricted notions of reachability and connected
components. Recall from Definition~\ref{alphawalksconnectdef}
the notions of $\alpha$-walks in $\E$-graphs, which we shall
now refine in connection with the constraint graph $\I$.
According to Definition~\ref{alphawalksconnectdef}, a
\emph{walk} in an $\E$-graph $\H$
is a sequence of vertices and edge labels
of the form
\[
s_0,e_1,s_1,e_2,\ldots, s_{n-1},e_n,s_n
\]
with $s_i \in S$ and $e_i \in E$ where
$(s_i,s_{i+1}) \in R_{e_{i+1}}$ for $0 \leq i < n$ for some
$n \in \N$. The edges $(s_i,s_{i+1}) \in R_{e_{i+1}}$ are the edges
traversed by this walk. The above walk is a walk of length~$n$ from
the source $s= s_0$ to the target $t= s_n$
and its \emph{edge label sequence} is the word
$w = e_1\cdots e_n \in E^\ast$. We also say that this word $w$
\emph{labels a walk} (of length $n$, from $s_0$ to $s_n$) in $\H$,
and describe the walk in question as a $w$-walk, or as an $X$-walk
for some language $X \subset E^\ast$ if $w \in X$. In the case of
$X = \alpha^\ast$ we also speak of $\alpha$-walks instead of
$\alpha^\ast$-walks.

Note that a word $w \in E^\ast$ can label at most one walk
from a given vertex $v$ in any $\E$-graph $\H$. That all $w \in E^\ast$ label walks
from all $v \in \H$ is equivalent to $\H$ being complete
(i.e.\ to each $R_e$ being a full matching).

\bD[$\I$-words and $\I$-walks]
\label{Ialphawalksdef}
\mbox{}\\
For $\alpha \subset E$ and $s \in S$ let $\I[\alpha,s] \subsetw \I$
be the weak substructure of $\I = (S,(R_e)_{e \in E})$ whose universe
is the $\alpha$-connected component of $s$ (i.e.\ the connected
component of $s$ in the $\alpha$-reduct $\I\restr \alpha$), and
with induced $R_e$ for all $e \in \alpha$.
Natural sets of $E$- or $\alpha$-words that occur as edge label sequences
along walks on the constraint graph $\I$ are defined as follows:
\bre
\item[--]
$\alpha^\ast[\I] \subset E^\ast$ consists of those
$w \in \alpha^\ast$ that label a walk in $\I$;
\item[--]
$\alpha^\ast[\I,s] \subset E^\ast$
consists of those $w \in \alpha^\ast$ that label a walk
from $s$ in $\I$;
\item[--]
$\alpha^\ast[\I,s,t] \subset E^\ast$
consists of those $w \in \alpha^\ast$ that label a walk
from $s$ to $t$ in $\I$.
\ere
\eD

\bD[$\I[\alpha,s]$-component]
\label{Ialphacompdef}
\mbox{}\\
For an $\E$-graph $\H$, $\alpha \subset E$ and $s \in S$,
the \emph{$\I[\alpha,s]$-component} of a vertex $v \in \H$
is the following weak substructure $\H[\I,\alpha,s;v] \subsetw \H$:
its vertex set consists of those vertices that are reachable
on an $\alpha^\ast[\I,s]$-walk from $v$ (i.e.\ on a walk in
$\H$ whose edge label sequence is in $\alpha^\ast[\I,s]$);
its edge relations comprise those $R_e$-edges for $e \in \alpha$
that are traversed by $\alpha^\ast[\I,s]$-walks from $v$ in $\H$.
\eD

When we speak of an $\I[\alpha]$-component we mean an
$\I[\alpha,s]$-component for some $s \in S$, which is left unspecified.

For later use we define a direct product of $\I$ with the Cayley graph
of an $\E$-group, which reflects $\I$-reachability, as follows.

\bD[direct product]
\label{directproddef}
\mbox{}
\\
Let $\G$ be an $\E$-group
that is compatible with
the constraint graph $\I= (S,E)$, $\CG$ the Cayley graph of $\G$.
Then the \emph{direct product} $\I \otimes \CG$ is the
$\E$-graph
\[
\I \otimes \CG = (V,(R_e)_{e \in E})
\]
with vertex set $V = S \times G$ and edge relations
\[
R_e = \{ ((s,g),(s',g')) \colon (s,s') \in R_e \mbox{ in } \I \mbox{
  and } g' = ge \mbox{ in } \G\} \quad \mbox {for $e \in E$.}
\]
\eD

Note that all $\alpha$-walks in $\I \otimes \CG$, by definition of the
edge relations, trace the lifts of $\alpha$-walks in $\I$.
For the following also compare Remark~\ref{compatconstraintrem}
above on lifts of walks from $\I$ to $\CG$.

\bO
\label{directprodobs}
Computability of $\G$ with $\I$ implies that for any $(s,g)$ and $(s',g)$ in the same
connected component of $\I \otimes \CG$ we must have $s = s'$.
It follows that connected components of $\I \otimes \CG$ are isomorphic
to weak subgraphs of $\CG$, and that the connected components of $\I \otimes \CG$
reflect $\I$-reachability in $\CG$ in the sense that
$(s,g)$ and $(t,g')$ are in the same $\alpha$-connected
component of $\I \otimes \CG$ if, and only if,
$g' \in \CG[\I,\alpha,s;g]$.
\eO

We turn to cosets, coset cycles and acyclicity criteria relative to
the given constraint graph $\I$.

\bD[$\I$-coset]
\label{Icosetdef}
\mbox{}\\
In an $\E$-group $\G$
that is compatible with $\I$
the \emph{$\I[\alpha,s]$-coset} of $g \in \G$
is the $\I[\alpha,s]$-component $\CG[\I,\alpha,s;g] \subsetw \CG$
of $g$.
\eD

We drop mention of $g$ for cosets at $g = 1$, writing e.g.\ just
$\CG[\I,\alpha,s] \subsetw \CG$ for $\CG[\I,\alpha,s;1] \subsetw \CG$.
For the following compare Definition~\ref{cosetcycledef}
for plain coset cycles.

\bD[$\I$-coset cycle]
\label{Icosetcycledef}
\mbox{}\\
Let $\G$ be an $\E$-group, $n \geq 2$.
An \emph{$\I$-coset cycle} of length $n \geq 2$ in $\G$ or $\CG$ is a cyclically
indexed sequence $(\CG[\I,\alpha_i,s_i;g_i],g_i)_{i \in \Z_n}$ of pointed
$\I[\alpha_i]$-cosets for $\alpha_i \strictsubset E$, $s_i \in S$ and
$g_i \in G$ satisfying these conditions:
\bre
\item
(connectivity)
there is an $\alpha_i^\ast[\I,s_i, s_{i+1}]$-walk from $g_i$ to
$g_{i+1}$,
\footnote{Equivalently, $g_{i+1} \in \CG[\I,\alpha_i,s_i;g_i]$, or
$\CG[\I,\alpha_i,s_i;g_i] = \CG[\I,\alpha_i,s_{i+1};g_{i+1}]$}
\item
(separation)
$\CG[\I,\alpha_{i,i-1},s_i;g_i] \cap \CG[\I,\alpha_{i,i+1}, s_{i+1}; g_{i+1}] = \emptyset$,
\ere
where $\alpha_{i,j} := \alpha_i \cap \alpha_j$.
\eD

\bD[$N$-acyclicity over $\I$]
\label{INacycdef}
\mbox{}\\
An $\E$-group
that is compatible with $\I$
is called \emph{$N$-acyclic
over $\I$} if it does not admit any $\I$-coset cycles of length up to $N$.
\eD

The above definitions generalise corresponding definitions
in the unconstrained setting. Those definitions,
Definitions~\ref{cosetcycledef} and~\ref{Nacycdef},
are comprised in the above as special cases for
the trivial constraint graph having a single vertex with loops for all $e \in E$.

As in the unconstrained case, $2$-acyclicity over $\I$ is akin
to a notion of simple connectivity, being equivalent to the
requirement that, for all $\alpha_i$ and $s$,
\[
\CG[\I,\alpha_1,s] \cap \CG[\I,\alpha_2, s]
 = \CG[\I,\alpha_1\cap \alpha_2, s].
\]

\section{Construction of N-acyclic E-groups over I}
\label{Iacycsec}

In order to boost degrees of plain coset acyclicity to acyclicity
w.r.t.\ $\I$-cosets we aim to employ compatibility with unfoldings
of potential $\I$-coset cycles in a manner similar to the treatment
of Section~\ref{acycsec}. The following lays out a strong criterion
that allows for the unfolding of potential $\I$-coset cycles
with constituents $\CG[\I,\alpha_i,s_i,g_i] \subsetw \CG[\alpha_i]$
through the unfolding of the surrounding plain cosets $\CG[\alpha_i]$
into free amalgamation chains. This is the same unfolding into
amalgamation chains as discussed in Section~\ref{amalgsec}
and used towards plain coset acyclicity in Section~\ref{acycsec}.
The crucial challenge is to safeguard this unfolding and the
corresponding compatibility arguments against damage through
unwanted shortcuts by $\alpha$-walks that do not correspond to
$\alpha^\ast[\I]$-walks.
It is to this end that we consider the relationship between
$\alpha^\ast[\I]$-components and the halo around them that is
formed by overlapping $\alpha'$-connected components for
$\alpha' \strictsubset \alpha$.

\bD[$\I$-skeleton]
\label{Ialphaskeletondef}
\mbox{}\\
For $\alpha \subset E$ an \emph{$\I[\alpha,s]$-skeleton} is an
$\E$-graph $\H$ that admits a surjective homomorphism
$h \colon \H \rightarrow \I[\alpha,s]$ onto
an $\alpha$-connected component $\I[\alpha,s]$ of $\I$
with the following lifting property:
whenever $h(v) \in S$ is incident with an $e$-edge in $\I[\alpha,s]$
then so is $v$ in $\H$.
\\
An $\I[\alpha]$-skeleton is a disjoint union of
$\I[\alpha,s]$-skeletons whose homomorphic image in $\I$ covers all of
$\I\restr \alpha$ (i.e.\ there is at least one component for each
$\alpha$-connected component $\I[\alpha,s] \subsetw \I$.
\eD

Note that the lifting property guarantees that every
$\alpha^\ast[\I]$-walk from $s'$ in $\I[\alpha,s]$ has a unique lift to
an $\alpha^\ast[\I]$-walk from $v$ for every $v$ in the pre-image of $s'$.
In alternative terminology, the homomorphism establishes
$\H$ as an unbranched bisimilar cover of $\I[\alpha,s]$ (or of $\I\restr
\alpha$).

\bE
\label{skeletobex}
Every $\CG[\I,\alpha,s;g] \subsetw \CG[\alpha] \subsetw \CG$
is an $\I[\alpha,s]$-skeleton, via
the unique homomorphism $h$ that maps $g \in \G$ to $s \in S$.
This map is well-defined since $\G$ is assumed compatible with $\I$
(cf.\ Remark~\ref{compatconstraintrem}
and comments after Definition~\ref{directproddef}).
\eE

The following definition captures the notion that these embedded
$\I[\alpha,s]$-skeletons in $\CG$ are not tied by incidental
overlaps between $\alpha'$-cosets that are not
matched by overlaps between the corresponding
$\I[\alpha']$-cosets within the skeleton,
for smaller generator sets $\alpha' \strictsubset \alpha$.
Similar to the notation $\Gamma_k$ for the set of
all generator subsets of size less than $k$, we now write
\[
\Gamma(\alpha) := \{ \alpha' \subset E \colon \alpha' \strictsubset
\alpha \}
\]
for the collection of the critical generator subsets under consideration.
Again we abbreviate corresponding families of generated subgroups and their
Cayley graphs from a given $\E$-group $\G$ as
\[
\barr{r@{\;:=\;}l}
\Gamma(\G[\alpha]) &
(\G[\alpha'] \colon \alpha' \in \Gamma(\alpha))
\\
\hnt
\Gamma(\CG[\alpha]) &
(\CG[\alpha'] \colon \alpha' \in \Gamma(\alpha))
\earr
\]

\bD[freeness]
\label{Gfreeoverskeletdef}
\mbox{}\\
The embedded $\I[\alpha,s]$-skeleton $\CG[\I,\alpha,s;g] \subsetw \CG$
is \emph{free} in $g \CG[\alpha]$ (or in $\CG$) if any two
cosets $g_1 \G[\alpha_i]$ and $g_2 \G[\alpha_2]$,
for $g_i \in \CG[\I,\alpha,s;g]$ and
$\alpha_i \in \Gamma(\alpha)$  that overlap in $\CG$
also overlap within the skeleton $\CG[\I,\alpha,s;g]$:
\[
g_1 \G[\alpha_1] \cap g_2 \G[\alpha_2] \not= \emptyset
\quad
\Rightarrow
\quad
\CG[\I,\alpha_1,s_1; g_1] \cap \CG[\I,\alpha_2,s_2;g_2] \not= \emptyset
\]
where $s_i = h(g_i)$ for the canonical homomorphism
$h \colon \CG[\I,\alpha,s;g] \rightarrow \I$ from Example~\ref{skeletobex}.
The $\E$-group $\G$ is \emph{free over $\I$} if every
embedded $\I[\alpha,s]$-skeleton $\CG[\I,\alpha,s;g] \subsetw \CG$
for $\alpha \subset E$ is free in $\CG$.
\eD

For generated subgroups we similarly say that $\G[\alpha]$ \emph{is free
over $\I$} if every embedded $\I[\alpha',s]$-skeleton
$\CG[\I,\alpha',s;g] \subsetw \CG[\alpha]$
for $\alpha' \subset \alpha$ is free in $\CG[\alpha]$.

Already the special case of $\alpha_1 = \alpha_2 \in \Gamma(\alpha)$
gives an indication of the strength of this freeness condition.
For $\alpha'= \alpha_1 = \alpha_2 \in \Gamma(\alpha)$
the freeness requirement for
$\CG[\I,\alpha,s;g] \subsetw \CG$ in $g \CG[\alpha]$ says that
$\alpha'$-connected components of the skeleton $\CG[\I,\alpha,s;g]$ are
induced by $\alpha'$-components of the surrounding $g \CG[\alpha]$.
In other words, $\alpha'$-reachability inside the embedded
$\I[\alpha,s]$-skeleton agrees with $\alpha'$-reachability in the
surrounding $\CG$.

The following is an analogue of Lemma~\ref{acychomlem} for freeness.

\bL
\label{freehomlem}
If $\G[\alpha]$ is $2$-acyclic, then freeness of $\G[\alpha]$
over $\I$ is preserved under inverse homomorphisms that are injective on
$\alpha'$-generated subgroups for $\alpha'\strictsubset \alpha$.
\eL

\prf
Let $h \colon \Ghat \rightarrow \G$ be a homomorphism of $\E$-groups
(both assumed to be compatible with $\I$:
Proviso~\ref{constraintpatternprov}), its restrictions to members of
the family $\Gamma(\Ghat[\alpha])$ injective.
The image of an embedded $\I[\alpha,s]$-skeleton in
$\CGhat$ under $h$ is an embedded $\I[\alpha,s]$-skeleton in $\CG$.
Assume that an $\I[\alpha,s]$-skeleton $\Hhat \subsetw \CGhat$
violates the freeness condition through some
$\hat{g} \in g_1 \Ghat[\alpha_1] \cap g_2 \Ghat[\alpha_2]\not= \emptyset$ where
$\CGhat[\I,\alpha_1,s_1; g_1] \cap \CGhat[\I,\alpha_2,s_2;g_2] = \emptyset$.
By assumption $h$ is injective in restriction to each one of the two cosets
$g_1\Ghat[\alpha_i]$ and $g_2 \Ghat[\alpha_2]$. By
Lemma~\ref{acychomlem} $\Ghat[\alpha]$ is
$2$-acyclic so that these two cosets intersect precisely in the coset
$g \G[\alpha_0]$ for $\alpha_0 = \alpha_1 \cap \alpha_2$. By
$2$-acyclicity, $h$ must be injective in restriction to the union
of these overlapping cosets. Therefore the violation of freeness in
$\CG[\alpha]$ would be isomorphically mapped onto a violation in $\G[\alpha]$.
\eprf

An immediate observation relates freeness to reachability
notions that are crucial in connection with the separation condition
for coset cycles. To make the connection with
Lemma~\ref{cosettocosetoverIlem} below, consider
$\alpha,\alpha_1,\alpha_2$ to play the r\^oles
of $\alpha_i, \alpha_{i,i-1}, \alpha_{i,i+1}$ in a potential
coset cycle or $\I$-coset cycle.

\bO
\label{freenessobs2}
For $\alpha_1,\alpha_2 \in \Gamma(\alpha)$
and two vertices $g_2,g_2$ of the same $\I[\alpha,s]$-skeleton
$\CG[\I,\alpha,s_1;g_1] = \CG[\I,\alpha,s_2;g_2]
\subsetw g_1 \CG[\alpha] = g_2 \CG[\alpha]$ in $\CG$,
freeness implies that if
$\CG[\I,\alpha_1,s;g_1] \cap \CG[\I,\alpha_2,s';g_2] =\emptyset$
(separation as in $\I$-coset cycles)
then also $g_1 \G[\alpha_1] \cap g_2 \G[\alpha_2] =\emptyset$
(separation as in plain  coset cycles).
\eO

Finally, the condition on overlaps in Definition~\ref{Gfreeoverskeletdef}
takes an especially neat and concrete form if $\G$ is $2$-acyclic.

\bO
\label{freenessobs3}
Let the embedded $\I[\alpha,s]$-skeleton $\CG[\I,\alpha,s;g] \subsetw \CG$
be free in $g \CG[\alpha]$ and let $\G[\alpha]$ be $2$-acyclic.
Then two cosets $g_1 \G[\alpha_i]$ and $g_2 \G[\alpha_2]$
for $g_i \in \CG[\I,\alpha,s;g]$ and $\alpha_i \in \Gamma(\alpha)$
are either disjoint or their overlap
is a single coset of the form $g_0 \G[\alpha_0]$ for
$\alpha_0 = \alpha_1\cap \alpha_2$ and an element
$g_0 \in \CG[\I,\alpha,s;g]$ of the skeleton, which is
$\alpha_i$-reachable from $g_i$ in the skeleton.
\eO

\prf
Due to $2$-acyclicity a nonempty intersection of
$\alpha_i$-cosets (within $g \CG[\alpha]$) is a single
$\alpha_0$-coset. By freeness it must intersect
the embedded $\I[\alpha,s]$-skeleton in an element
$g_0$ that is $\alpha_i$-reachable from $g_i$ in the
skeleton. The converse implication is obvious.
\eprf

\bL
\label{cosettocosetoverIlem}
If $\G$ is $N$-acyclic (does not admit plain coset cycles of length up
to $N$) and free over $\I$ then
$\G$ is $N$acyclic over $\I$
(does not admit $\I$-coset cycles of length up
to $N$).
\eL

\prf
It suffices to show that every $\I$-coset cycle in $\G$ induces
plain coset cycles if the links $\CG[\I,\alpha_i,s_i;g_i]$ are
extended to the surrounding $g_i\CG[\alpha_i]$.
The crux is the separation condition:
separation w.r.t.\ $\I$-reachability in
links $\CG[\I,\alpha_i,s_i;g_i]\subsetw g_i\CG[\alpha_i]$
needs to translate into the stronger separation condition for
the encompassing $g_i\G[\alpha_i]$ themselves. This
is precisely the content of Observation~\ref{freenessobs2}.
\eprf

\subsection{Small coset extensions}

Towards the construction of $\E$-groups that are free over $\I$
we construct auxiliary $\E$-graphs that reflect the desired
freeness condition locally. The r\^ole of these \emph{small coset extensions}
towards freeness over $\I$ is similar to the r\^ole of free amalgamation
chains for $N$-acyclicity. They reflect the desired freeness
condition locally as a result of an unfolding w.r.t.\ cosets
(cf.\ Definitions~\ref{smallcosetextdef} and~\ref{smallcosetamalgCEdef});
and they serve as components in $\E$-graphs $\H$ which
globally force the required freeness in $\G = \sym(\H)$
(cf.\ Lemma~\ref{smallcosettofreelem}).

Recall that $\Gamma(\alpha) = \{ \alpha' \subset E \colon
\alpha' \strictsubset \alpha \}$ with corresponding families
of generated subgroups $\Gamma(\G[\alpha])$ and Cayley graphs
$\Gamma(\CG[\alpha])$ from a given $\E$-group $\G$.
Also recall that we say that $\Gamma(\G[\alpha])$ is compatible
with an $\E$-graph if every member of this family,
i.e.\ every $\G[\alpha']$ for $\alpha' \strictsubset \alpha$, is.

\bD[small coset extension]
\label{smallcosetextdef}
\mbox{}\\
Let $\G$ be an $\E$-group with Cayley graph $\CG$,
$\alpha \subset E$ and $\H= \H[\I,s,\alpha;v]$
an $\I[\alpha,s]$-skeleton.
An $\alpha$-graph $\hat{\H}$ is a
\emph{small coset extension} of $\H$ w.r.t.\
$\G$ (more specifically: w.r.t.\ $\Gamma(\G[\alpha])$) if
\bre
\item
$\H \subsetw \hat{\H}$,
\item
for $\alpha' \in \Gamma(\alpha)$ every
$\alpha'$-connected component of $\H$ is contained
in a weak substructure of $\hat{\H}$ that is isomorphic to $\CG[\alpha']$.
\ere
The small coset extension $\H \subsetw \hat{\H}$ is \emph{free} if
\bre
\addtocounter{enumi}{2}
\item
for all
$\alpha_1,\alpha_2\in \Gamma(\alpha)$, any two
$\alpha_i$-connected components of $\H$ that are disjoint in $\H$
extend into disjoint $\alpha_i$-connected components of $\hat{\H}$.
\ere
\eD

Note that freeness as in~(iii) implies that the weak substructure
relationship in~(i) becomes an induced substructure relationship:
an $e$-edge of $\hat{\H}$ between vertices of $\H$ is an
$\{ e\}$-connected component of $\hat{\H}$ and, by~(iii), must
be present in $\H$.
The existence of small coset extensions  (not necessarily free)
is obvious e.g.\ for embedded $\I[\alpha,s]$-skeletons as discussed
in Example~\ref{skeletobex}. Here the small coset extension
$\CG[\I,\alpha,s;g]\subsetw \H$ is obtained as
a weak substructure  $\H \subsetw \CG[\alpha]$ formed by the
union of the $\alpha'$-cosets of the elements of
$\CG[\I,\alpha,s;g]$, for $\alpha' \in \Gamma(\alpha)$.
This small coset extension is free if the skeleton is free in $\CG[\alpha]$.

\bL
\label{smallcosettofreelem}
Let $\G$ be an $\E$-group,  $\alpha \subset E$ such that $\G[\alpha]$
is $N$-acyclic for some $N \geq 2$. Let $\H$ comprise, as components,
a small coset extension of an $\I[\alpha,s]$-skeleton w.r.t.\ $\G$
that is free and an isomorphic copy of $\CG$. Assume further that
$\Gamma(\G[\alpha])$ is compatible with $\H$.
Then $\Ghat := \sym(\H)$ is such that
\bre
\item
$\Ghat \succeq \G$,
$\hat{\G}[\alpha'] \simeq \G[\alpha']$ for all
$\alpha' \in \Gamma(\alpha)$, and
$\Ghat[\alpha]$ is $N$-acyclic;
\item
the embedded $\I[\alpha,s]$-skeleton
$\CGhat[\I,s,\alpha] \subsetw \CGhat[\alpha]$ is free in $\CGhat[\alpha]$.
\ere
\eL

\prf
Let $\Hhat_0$ be the free small coset extension
w.r.t.\ $\G$ that appears as a component of $\H$,
$\H_0 \subsetw \Hhat_0$ the underlying $\I[\alpha,s]$-skeleton.

In the situation of the lemma $\H$ also has a component $\CG$ so that,
$\Ghat \succeq \G$ and, as
$\Gamma(\G[\alpha])$ is compatible with $\H$,
$\Ghat[\alpha'] \simeq \G[\alpha']$ for $\alpha' \in \Gamma(\alpha)$
(cf.\ Lemma~\ref{Ghatcompatlem}, or its straightforward analogue
for $\Gamma(\G[\alpha])$ instead of $\Gamma_k(\G)$).
It follows that $\Ghat[\alpha]$ inherits $N$-acyclicity from
$\G[\alpha]$ (cf.\ Lemma~\ref{acychomlem}).

\begin{figure}
\[
\xymatrix{&&w&& & && g &&
\\
&&\raisebox{-10pt}{$\hat{\H}$} && \ar@{<~>}[r] &&&
\raisebox{-10pt}{$\CGhat$} &&
\\
v_1 \ar@{->}[uurr]|*{u_1}\ar@{->}[rr]|*{w_{01}}
&& v_0 && v_2 \ar@{->}[uull]|*{u_2}\ar@{->}[ll]|*{w_{02}}
&
g_1 \ar@{-}[uurr]|*{\alpha_1^\ast}\ar@{-}[rr]|*{\alpha_1^\ast[\I]}
&& g_0 && g_2
\ar@{-}[uull]|*{\alpha_2^\ast}\ar@{-}[ll]|*{\alpha_2^\ast[\I]}
}
\]
\caption{Patterns of walks in union of relevant $\alpha_i$-components of
$\hat{\H}$ and $\CGhat$.}
\label{patternfig}
\end{figure}

It remains to argue for freeness of the embedded
$\I[\alpha,s]$-skeleton
\[
\CGhat[\I,\alpha,s] := \CGhat[\I,\alpha,s;1] \subsetw \CGhat[\alpha].
\]

Let $\alpha_1,\alpha_2 \in \Gamma(\alpha)$
and consider the freeness condition for
$g_1\CGhat[\alpha_1]$ and $g_2\CGhat[\alpha_2]$ where
$g_1,g_2 \in \CGhat[\I,\alpha,s]$.
Compare Figure~\ref{patternfig}, with $g_1,g_2,g$
on the right-hand side.
Let $w_i \in \alpha^\ast[\I,s]$ be such that $g_i = [w_i]_{\Ghat}$
and $u_i \in \alpha_i^\ast$ such that $g_1 [u_1]_{\Ghat} = g_2
[u_2]_{\Ghat}=: g \in g_1 \Ghat[\alpha_1] \cap g_2
\Ghat[\alpha_2]$.
Considering the operation of $w_i u_i$ on $v \in \H_0 \subsetw
\Hhat_0$, we note that
the $w_i$ map $v$ to vertices $v_i \in \H_0$
that are reached from $v$ on corresponding $\alpha^\ast[\I,s]$-walks.
Since $[w_1u_1]_{\Ghat} = g = [w_2u_2]_{\Ghat}$,
the $u_i$-walks from the vertices $v_i$ in $\Hhat_0$ must meet in the
same vertex $w \in \Hhat$, which therefore lies in the intersection
of the $\alpha_i$-connected components of the $v_i$ in $\hat{\H}_0$.
Compare the left-hand side of Figure~\ref{patternfig}.
Since $\Hhat_0 \supsetw \H_0$ is a free small coset extension, the
$\alpha_i$-connected components of the $v_i$ in $\H_0$ must intersect
in some vertex $v_0$ of $\H_0$. It follows that
$v_0$  is reachable from $v_i$ on an $\alpha_i^\ast[\I,s_i]$-walk, for
$i=1,2$; let these walks be labelled by
$w_{0i} \in \alpha_i^\ast[\I,s_i]$ for the appropriate $s_i \in \I[\alpha,s]$.
The union of the
$\alpha_i$-connected components of $v_i$ in $\Hhat$
contains $v_0$ and $w$ (both in the intersection of the two components)
as well as $v_1$ in the former and $v_2$ in the latter of these components.
By Observation~\ref{twoamalgobs}
this union is isomorphic, as an $\E$-graph, to the free amalgam
$\CG[\alpha_1]
\oplus \CG[\alpha_2] \simeq \CGhat[\alpha_1] \oplus \CGhat[\alpha_2]$.
It follows that also in $\Ghat$ the
word
\[
w_{01}^{-1} u_1 u_2^{-1} w_{02}
\]
labels a cycle. In terms of the natural isomorphisms, this labelling traces out
the cycles
\[
\barr{@{}l@{\;}l@{}}
&
(v_0,v_1,w,v_2,v_0)
\\
\hnt
\simeq &
(1,[w_{01}]_{\Ghat}^{-1},
[w_{01}]_{\Ghat}^{-1}[u_1]_{\Ghat},
[w_{01}]_{\Ghat}^{-1}[u_1]_{\Ghat}[u_2]_{\Ghat}^{-1}, 1)
\\
\hnt
\simeq &
(g_0,g_1,g,g_2,g_0)
\earr
\]
for $g_0 := g_1 [w_{01}]_{\Ghat}$.
This translates into the equality
\[
[w_{01}]_{\Ghat}^{-1}[u_1]_{\Ghat}[u_2]_{\Ghat}^{-1}
[w_{02}]_{\Ghat} = 1
\]
in $\Ghat$, which implies that
$g_1^{-1} g_2 = [u_1]_{\Ghat}[u_2]_{\Ghat}^{-1} =
[w_{01}]_{\Ghat}[w_{02}]_{\Ghat}^{-1}$ or that

\[
g_0 = g_1 [w_{01}]_{\Ghat}\in
g_1 \CGhat[\I,s_1,\alpha_1]\cap g_2 \CGhat[\I,s_2,\alpha_2]  \not= \emptyset
\]
as $[w_{0i}]_{\Ghat} \in \alpha_i^\ast[\I,s_i]$.
So the intersection of the cosets $g_i \CGhat[\alpha_i]$
does conform to the condition imposed by freeness according to
Definition~\ref{Gfreeoverskeletdef}.
\eprf

We turn to a canonical construction of a free
coset extension as an amalgam over the given skeleton.
The construction itself, as a natural quotient structure, is
comparatively straightforward.
The compatibility requirement in Lemma~\ref{smallcosettofreelem}
will then be the major challenge towards its usefulness.

In connection with the precondition on freeness at the level of
subgroups in $\Gamma(\G[\alpha])$ compare
Definition~\ref{Gfreeoverskeletdef}.

\bD[small coset amalgam]
\label{smallcosetamalgCEdef}\label{CEdef}
\mbox{}\\
Let $\alpha \subset E$ and $\G$ be an $\E$-group for which all subgroups in
$\Gamma(\G[\alpha])$ are $2$-acyclic and free over $\I$.
Let $\H$ be an $\I[\alpha,s]$-skeleton
such that the $\alpha'$-connected components of $\H$ are
isomorphic to corresponding embedded
$\I[\alpha',s']$-skeletons in the $\E$-group $\G$
for all $\alpha' \in \Gamma(\alpha)$.
In this situation the \emph{small coset amalgam}
$\CE(\H,\G,\alpha)$ is defined as the quotient
\[
\textstyle
\CE(\H,\G,\alpha):=
\Bigl(\bigcup_{v \in \H, \alpha' \in \Gamma(\alpha)}
(\CG[\alpha'] \times  \{ (v,\alpha') \}) \Bigr) \bigm/ \;\approx \qquad\qquad\nt
\]
where $\approx$ is the equivalence relation induced by identifications
of $g_1$ in the $(v_1,\alpha_1)$-tagged copy of $\CG[\alpha_1]$ and
$g_2$ in the $(v_2,\alpha_2)$-tagged copy of $\CG[\alpha_2]$ if
there is a vertex  in the intersection of the
$\alpha_i$-components of the $v_i$ in $\H$
that forces $g_1 = g_2$ in the overlap of copies of
$\CG[\alpha_i]$ (see detailed discussion below).
\eD

Note that the isomorphism type of $\CE(\H,\G,\alpha)$ is fully
determined by $\H$ and the $\Gamma(\CG[\alpha])$, i.e.\
by the $\CG[\alpha']$ for $\alpha' \strictsubset \alpha$, rather than
the global structure of $\CG$. This is relevant for
considerations similar to Lemma~\ref{Ghatcompatlem}.

By definition $\approx$ is the transitive closure of $\sim$, which
is defined as follows (cf.\ Figure~\ref{cosetextnpatternfig}):
\[
(\dagger)
\qquad \quad
\barr{@{}l@{}}
(g_1,v_1,\alpha_1) \sim (g_2,v_2,\alpha_2)
\\
\hnt
\mbox{if there are }
w_i \in \alpha_i^\ast[\I,s_i]
\mbox{ for suitable $s_i$, }
\\
\mbox{and } w \in (\alpha_1\cap\alpha_2)^\ast \mbox{ such that}
\\
\hnt\quad \begin{minipage}[t]{.6\textwidth}
\bre
\item
$[w_1]_\H(v_1) = [w_2]_\H(v_2)$ in $\H$,
\item
$g_i = [w_i w]_\G \in \G[\alpha_i]$,  for $i = 1,2$.
\ere
\end{minipage}
\earr
\]

\begin{figure}
\[
\xymatrix{\raisebox{-20pt}{$\CG[\alpha_1]$} &&\circ && \raisebox{-20pt}{$\CG[\alpha_2]$}
\\
\\
v_1 \ar@{->}[uurr]|*+{g_1}\ar@{->}[rr]|*+{w_1}
&& v_{1,2}
\ar@{->}[uu]|*+{w}
&& v_2 \ar@{->}[uull]|*+{g_2}\ar@{->}[ll]|*+{w_2} & \H
}
\]
\caption{Pattern for identifications in $\CE(\H,\G,\alpha)$.}
\label{cosetextnpatternfig}
\end{figure}

\medskip
Here~(i) says that the $w_i$ provide the addresses
of the shared vertex of $\H$ in the copies of the $\CG[\alpha_i]$,
relative to their anchor points $v_i$ that get identified with $1$ in $\CG[\alpha_i]$.
This shared vertex gives rise to a forced identification
according to~(ii).
Conditions (i)--(ii) can be rephrased as the existence of
\bae
\item
a vertex $v_{1,2}$ in the intersection of the $\alpha_i$-components
of the $v_i$ in $\H$,
\item
some $g_0\in \CG[\alpha_0]$ for $\alpha_0 :=
\alpha_1\cap\alpha_2$,
\eae
such that $(g_0,v_{1,2},\alpha_0)$ is identified with both
$(g_i,v_i,\alpha_i)$ within their copies of $\CG[\alpha_i]$, which are attached at
$v_i$.
Compare Figure~\ref{cosetextnpatternfig}, where we
read off $v_{1,2} = [w_1]_\H(v_1) = [w_2]_\H(v_2)$ and~$g_0 = [w]_\G$.

The precondition
\[
(\ddagger)
\qquad \quad
\begin{minipage}{.63\textwidth}
the subgroups in $\Gamma(\G[\alpha])$ are free over $\I$
\end{minipage}
\]
is essential for the analysis of $\approx$.
As $\approx$ is the transitive closure of $\sim$ according to
$(\dagger)$, we examine the effect successive
identifications through $\sim$. For the following compare Figure~\ref{transpatternfig}.

\begin{figure}
\[
\xymatrix{ &
&*+{\circ} &
&
\\
&
\raisebox{-20pt}{$\qquad\qquad\qquad$}
&
\raisebox{-20pt}{$\qquad\qquad\qquad$}
&
\raisebox{-20pt}{$\qquad\qquad\qquad$}
&
\\
v_1 \ar@{-}[r]|*{\alpha_1}
\ar@{->}[uurr]|*+{g_{1}}
& v_{1,2} \ar@{->}[uur]|*+{g_{1,2}}
\ar@{-}[r]|*{\alpha_{2}}
&  v_2 \ar@{-}[r]|*{\alpha_{2}}
\ar@{->}[uu]|*+{g_{2}}
& v_{2,3} \ar@{->}[uul]|*+{g_{2,3}}
\ar@{-}[r]|*{\alpha_{3}}
& v_3
\ar@{->}[uull]|*+{g_{3}} & \H
}
\]
\caption{Pattern for two consecutive identifications.}
\label{transpatternfig}
\end{figure}

Let $(g_1,v_1,\alpha_1) \sim (g_1,v_1,\alpha_1)$, and
$(g_2,v_2,\alpha_2) \sim (g_3,v_3,\alpha_3)$
according to (i)--(ii) in $(\dagger)$,
for $\alpha_i \in \Gamma(\alpha)$, i.e.\
$\alpha_i \strictsubset \alpha$.
Using the rephrasing according to (a)--(b) above, this implies the
existence of intermediaries
$v)_{i,j}$ and $g_{i,j}$ for $(i,j) = (1,2)$ and $(i,j)= (2,3)$ where
\bae
\item
$v_{i,j}$ is in the intersection of the $\alpha_k$-components of $v_k$
for $k=i,j$,
\item
$g_{i,j} \in \G[\alpha_{i,j}]$ with $\alpha_{i,j} := \alpha_i \cap \alpha_j$
\eae
such that
(cf.\ Figure~\ref{transpatternfig})
\bre
\item[--]
$(v_{1,2},g_{1,2},\alpha_{1,2})$ is identified with
$(v_1,g_1,\alpha_1)$ (in the $\CG[\alpha_1]$-copy at $v_1$)
and with $(v_2,g_2,\alpha_2)$ (in the $\CG[\alpha_2]$-copy at $v_2$);
\item[--]
$(v_{2,3},g_{2,3},\alpha_{2,3})$ is identified with
$(v_2,g_2,\alpha_2)$ (in the $\CG[\alpha_2]$-copy at $v_2$)
and with $(v_3,g_3,\alpha_3)$ (in the $\CG[\alpha_3]$-copy at $v_3$).
\ere

We look at those identifications that occur in the central
$\CG[\alpha_2]$-copy. That the $\alpha_2^\ast[\I]$-component
of $\H$ containing $v_{1,2}, v_2$ and $v_{2,3}$ is free in this
$\CG[\alpha_2]$-copy according to~$(\ddagger)$ means that at least one
of the following must hold
\bne
\item
not $\alpha_{1,2} \strictsubset \alpha_2$, i.e.\ $\alpha_2 \subset \alpha_1$, or
\item
not $\alpha_{2,3} \strictsubset \alpha_2$, i.e.\ $\alpha_2 \subset \alpha_3$, or
\item
the $\alpha_{1,2}$-component of $v_{1,2}$ and
the $\alpha_{2,3}$-component of $v_{2,3}$ intersect
\\
in the $\alpha_2$-component of $v_2$ in $\H$.
\ene

In either one of the first two cases the identification of $(v_1,g_1,\alpha_1)$
with $(v_3,g_3,\alpha_3)$ is obviously mediated by a direct
identification through $\sim$ as defined in $(\dagger)$.
The same is true in the third case, since it
implies that also the $\alpha_1$-component of $v_1$ and the
$\alpha_2$-component of $v_3$ in $\H$ intersect in some vertex $v_2'$
for which there is a $g_2' \in \G[\alpha_{1,2} \cap \alpha_{2,3}]$ that
mediates a direct identification according to~(a)--(b) above.
So the crucial assumption~$(\ddagger)$ implies that
$\sim$ is itself transitive, hence equal to $\approx$.

Parts~(i) and~(ii) in the following are an analogue of the assertion in
Remark~\ref{elementsupportrem} for small coset amalgams instead of
amalgamation clusters.

\bR
\label{smallfootrem}
For $\Hhat :=  \CE(\H,\G,\alpha) \supsetw \H$ as in
Definition~\ref{smallcosetamalgCEdef} the relation
$\sim$ in $(\dagger)$ is itself an equivalence relation so that
$\hat{\H}$ is the quotient w.r.t.\ $\sim$.
Moreover, for every element $x$ of $\Hhat$ there is
\bre
\item
a unique minimal
set $\alpha_x \in \Gamma(\alpha)$ for which $x$ is represented in
a copy of $\CG[\alpha_x]$ attached to some element $v \in \H$, and
\item
a single full $\alpha_x$-component of $\H$ consisting of
those elements $v \in \H$ that admit a
representation of $x$ by $(g,v,\alpha_x)$ for some $g \in \G[\alpha_x]$.
\ere
\eR

\prf
For~(i) note that $\alpha_x$ can be obtained as the intersection of
all generator sets $\alpha' \in \Gamma(\alpha)$ for which the
$\alpha'$-connected component of $x$ in $\hat{\H}$ intersects $\H$.
This set is closed under intersections as indicated in the characterisation of
$\sim$ in~(a)--(b). Tuples that represent $x$ can only be of the from
$(g,v,\alpha')$ for $\alpha_x \subset \alpha' \in \Gamma(\alpha)$.
For~(ii), the relevant subset of $\H$ is closed
under $\alpha_x$-reachability in $\H$. That it cannot comprise disjoint
$\alpha_x$-components follows again by definition of $\sim$ in
(a)--(b) above, $(\dagger)$ and~$(\ddagger)$.
\eprf

\bL
\label{CEfreelem}
In the situation of Definition~\ref{smallcosetamalgCEdef} the small
coset amalgam $\Hhat :=  \CE(\H,\G,\alpha) \supsetw \H$ is
a free small coset extension of the $\I[\alpha,s]$-skeleton $\H$.
\eL

\prf
Conditions conditions~(i)--(iii) on free small coset
extensions in Definition~\ref {smallcosetextdef} are directly built into
the definition of $\CE(\H,\G,\alpha)$.  We need to check that it
actually is an $\E$-graph.

Consider elements $x_i$ represented by $(g_i,v_i,\alpha_i)$
where $\alpha_i = \alpha_{x_i}$, $g_i \in \G[\alpha_i]$ for $i=1,2$
and let $(x_1,x_2)$ be an $e$-edge in $\hat{\H}$. Let this $e$-edge stem
from a copy of some $\CG[\alpha_0]$ at $v_0 \in \H$,
where $e \in \alpha_0$ (all $\alpha_i \in \Gamma(\alpha)$, i.e.\
$\alpha_i \strictsubset \alpha$).
As $x_i \sim (g_{0i}, v_0,\alpha_0)$ for $i=1,2$ and suitable $g_{0i}
\in \G[\alpha_0]$, we find that $\alpha_i \subset \alpha_0$ for $i =1,2$, and all
$v_i$ are in the same $\alpha_0$-component of $\H$.
We may assume w.l.o.g.\ that
\[
\alpha_0 = \alpha_1 \cup \alpha_2 \cup \{ e \},
\]
since
$\alpha_0 \supseteq \{ e\}$ and since this
$\alpha_0$ is sufficient to put $x_1,x_2,v_1,v_2$ in the same
$\alpha_0$-component of $\hat{\H}$.
Looking at the
triangle formed by $v_0, x_1,x_2$ in the $\CG[\alpha_0]$-copy that
represents the $x_i$ and the $e$-link between them, $2$-acyclicity
of $\G[\alpha_0]$ implies
that $e \in \alpha_1 \cup \alpha_2$, and hence that
\[
\alpha_0 = \alpha_{x_1} \cup \alpha_{x_2}.
\]

We further distinguish two cases, based on whether
$e \in \alpha_1 \cap \alpha_2$ or not.
If $e \in \alpha_1 \cap \alpha_2$, then
\[
\alpha_0 = \alpha_{x_1} = \alpha_{x_2},
\]
as $e \in \alpha_1 \cap \alpha_2 =
\alpha_{x_1} \cap \alpha_{x_2}$ implies $\alpha_{x_1} = \alpha_{x_2}$
by minimality of these generator sets for $x_1$ and $x_2$.
Otherwise, i.e.\ if $e \in \alpha_1 \setminus \alpha_2 = \alpha_{x_1} \setminus
\alpha_{x_2}$ or
$e \in \alpha_2 \setminus \alpha_1 = \alpha_{x_2} \setminus
\alpha_{x_1}$, it must be that
\[
\barr{@{}rl@{}}
& \alpha_0 = \alpha_{x_1} = \alpha_{x_2} \,\dot{\cup}\; \{ e \}
\\
\hnt
\mbox{ or } &
\alpha_0 =
\alpha_{x_2} = \alpha_{x_1} \,\dot{\cup}\; \{ e \}:
\earr
\]
if, for instance, $e \in \alpha_1 \setminus \alpha_2 = \alpha_{x_1} \setminus
\alpha_{x_2}$,
since $\alpha_2 \cup \{ e \}  \subset \alpha_0
\strictsubset \alpha$,
the representations of $x_2$ relative to $v_1$ and $v_2$ show
that $\alpha_2 = \alpha_{x_2} \subset \alpha_1
\cap (\alpha_2 \cup \{ e \})$, whence
$\alpha_2 \subset \alpha_1 = \alpha_2 \cup \{ e \}$.

This means that $e$-edges can either occur between
elements that share the same $\alpha_x \strictsubset \alpha$ with
$e \in \alpha_x$, or else
between elements $x$ with $e \not\in \alpha_x$
and $y$ with $\alpha_y = \alpha_x \cup \{ e \}$.
In the first case, both vertices belong to the same
$\CG[\alpha_x]$-copy in $\hat{\H}$
that comprises this $e$-edge; in the second case, the $e$-edge
is simultaneously part of any $\CG[\alpha']$-copy in $\Hhat$ that
contains $y$, as well as of any  $\CG[\alpha']$-copy in $\Hhat$
that contains $x$ and has $e \in \alpha'$. It follows in both cases
that no further $e$-edge can be incident with either vertex so that
$\Hhat$ is indeed an $\E$-graph.
So $\Hhat = \CE(\H,\G,\alpha)$ is a free small coset extension of $\H$.
\eprf

\bR
\label{freefreecosrem}
In the situation of Definition~\ref{smallcosetamalgCEdef}
any free small coset extension of $\H$ is isomorphic to $\CE(\H,\G,\alpha)$.
\eR

\bR
\label{freecosetextnvsCErem}
If the embedded $\I[\alpha,s]$-skeleton
$\H = \CG[\I,\alpha,s] \subsetw \CG[\alpha]$ is free in $\CG[\alpha]$,
then $\CG[\alpha]$ contains, as a weak subgraph, a free small coset
extension $\hat{\H} \supsetw \H$. If $\G[\alpha]$ is $2$-acyclic, then
this $\Hhat$ is isomorphic to $\CE(\H,\G,\alpha)$ and we
refer to this realisation of the
free small coset extension $\CE(\CG[\I,\alpha,s],\G,\alpha) \subsetw \CG[\alpha]$
as the \emph{embedded} free small coset extension.
\eR

\subsection{Cluster property for small coset amalgams}
\label{clustersec}

The next goal is to establish that, under suitable conditions on $\Gamma(\G[\alpha])$,
the free coset extension $\CE(\H,\G,\alpha)$ also satisfies the compatibility
conditions that are relevant for Lemma~\ref{smallcosettofreelem}.
For compatibility of $\Gamma(\G[\alpha])$ with $\CE(\H,\G,\alpha)$
we  look at suitable weak substructures that enclose $\beta$-connected
components for $\beta \in \Gamma(\alpha)$. It turns out that
free amalgamation clusters (cf.\ Definition~\ref{amalgclusterdef}) are
suitable for this purpose.
Assuming corresponding behaviour at the level of $\Gamma(\G[\alpha])$,
every $\beta$-component of $\CE(\H,\G,\alpha)$ is contained in a weak
substructure that is isomorphic to a free amalgamation cluster of
$\Gamma(\G[\alpha])$-cosets. If the subgroups
in $\Gamma(\G[\alpha])$ satsify the cluster property of
Definition~\ref{clusterpropamalgclusterdef} then
Lemma~\ref{compamalgclusterlem} applies to show that this
$\beta$-component is itself isomorphic to a free amalgamation cluster.
The following is an analogue of
Definition~\ref{clusterpropamalgclusterdef}.

\bD[cluster property for small coset amalgams]
\label{clusterpropdef}
\mbox{}\\
In the situation of Definition~\ref{smallcosetamalgCEdef}
let $\Hhat = \CE(\H,\G,\alpha)$ be the small coset extension
of the $\I[\alpha,s]$-skeleton $\H$.
We say that this small coset extension $\Hhat \supsetw \H$ has the
\emph{cluster property} if every $\beta$-connected component $B$
of $\Hhat$ for $\beta \in \Gamma(\alpha)$ satisfies the following:
\bre
\item
$B$ has an element~$x$ such that
$\alpha_x = \alpha_B := \bigcap \{ \alpha_x \colon x \in B \}$
and a constituent $\CG[\alpha_B]$-copy of $\Hhat$ containing~$x$
that is contained in every constituent $\CG[\alpha']$-copy of $\Hhat$
that intersects $B$;
\item
$B$ is contained in a weak substructure of $\Hhat$ that is
isomorphic to a free amalgamation cluster
$\bigoplus_{x \in B} \CG[\alpha_x]$ of $\CG[\alpha_x]$ from
$\Gamma(\CG[\alpha])$, whose core is the constituent $\CG[\alpha_B]$-copy
from~(i).
\ere
\eD

The following lemma shows that the cluster property is preserved
in the passage from free small coset extensions
at the level of the smaller subgroups in $\Gamma(\G[\alpha])$ to
any free small coset extension obtained as a small coset amalgam
according to Definition~\ref{smallcosetamalgCEdef}. It is an analogue
of Lemma~\ref{compamalgclusterlem} for small coset amalgams.
If compatibility of $\Gamma(\Ghat[\alpha])$ with free amalgamation
chains of length $N$ and free amalgamation clusters
is simultaneously maintained in line with
Lemmas~\ref{compamalgchainlem}
and~\ref{compamalgclusterlem}, the cluster property implies
compatibility as required for Lemma~\ref{smallcosettofreelem}.
It follows that Lemma~\ref{smallcosettofreelem} supports an inductive
construction of $\E$-groups that are $N$-acyclic,
free and satisfy the cluster property for free small coset amalgams.
Compare Remark~\ref{freefreecosrem} on embedded free
small coset extensions.

\bL
\label{clusterinCElem}
In the situation of Definition~\ref{smallcosetamalgCEdef} consider the
free small coset extension
$\Hhat = \CE(\H,\G,\alpha)$. If all the embedded free small coset
extensions $\CG[\I,\alpha',s'] \subsetw \CE(\CG[\I,\alpha',s'],\G[\alpha'],\alpha')
\subsetw \CG[\alpha']$ for embedded
$\I[\alpha',s']$-skeletons $\CG[\I,\alpha',s']$ and $\alpha' \in \Gamma(\alpha)$
satisfy the cluster property, then $\hat{\H}$ has the cluster property.
\eL

\prf
Let $\beta \strictsubset \alpha$ and consider a $\beta$-component $B$
of $\hat{\H}$.
If $B$ is contained in some $\CG[\alpha']$-copy of $\hat{\H}$
for $\alpha' \in \Gamma(\alpha)$, we are done: the above analysis
of $e$-edges of $\Hhat = \CE(\H,\G,\alpha)$
shows that every $\beta$-edge between vertices of $B$ must be present
in $\CG[\alpha']$. So $B$ is a $(\beta\cap\alpha')$-component
of a $\CG[\alpha']$-copy and has the required structure by assumption.
(This comprises all instances in which $B$ intersects
the skeleton $\H$, as then $B$ corresponds to a constituent
$\CG[\beta]$-copy of $\Hhat$.)

Otherwise consider an element $x \in B$ that is an element of at least
two distinct constituent $\CG[\alpha_i]$-copies of $\hat{\H}$,
$\alpha_i \in \Gamma(\alpha)$ for $i=1,2$, neither of which covers
all of $B$. Consider the set of
generators $\alpha_x  \subset \alpha_0 := \alpha_1 \cap \alpha_2$
and, for $\beta_i := \beta \cap \alpha_i$,
the $\beta_i$-connected components $B_i$ of $x$ in the
constituent $\CG[\alpha_i]$-copies. Clearly $B_i \subset B$ and by assumption on
$\G[\alpha_i]$, $B_i$ is
contained in a copy of a free amalgamation cluster centred on a core
$\CG[\alpha_{B_i}] \subsetw \CG[\alpha_i]$ where
$\alpha_{B_i} = \bigcap_{y \in B_i} \alpha_y$.
Let $x_i \in B_i$ be such that $\alpha_{x_i} = \alpha_{B_i}$.
By minimality of $\alpha_{B_i}$, $\alpha_{x_i} = \alpha_{B_i} \subset
\alpha_x$.
Now $x_i$ is linked to $x$ by a $\beta_i$-walk,
and also (via $1$ in the copy of $\CG[\alpha_i]$) by the composition
of an $\alpha_{x_i}$-walk and an $\alpha_x$-walk, which
is an $\alpha_0$-walk (as $\alpha_{x_i} = \alpha_{B_i} \subset
\alpha_x \subset \alpha_0$).
Since $\G[\alpha_i]$ is $2$-acyclic, $x_i$ must be linked to $x$ by a
$\beta_0$-walk for $\beta_0 := \beta \cap \alpha_0$. It follows that
both $x_i$ are elements of the shared copy of $\CG[\alpha_0]$.
So the core $\CG[\alpha_{B_i}]$-copies for the $B_i$
touch the same $\beta$-component of $x$ also in this shared copy
of $\CG[\alpha_0]$.
For this $\beta$-component $B_0$ of $x$ in $\CG[\alpha_0]$
the assumption on $\CG[\alpha_0]$ gives us the minimal
$\alpha_{B_0} = \bigcap_{y \in B_0} \alpha_y$.  Arguing with
minimality of $\alpha_{B_0}$ in the shared copy
of $\CG[\alpha_0]$, which represents $x$ and both $x_i$, we find that
$\alpha_{B_0} \subset \alpha_{B_1}\cap \alpha_{B_2}$.
By minimality of the $\alpha_{B_i}$ in their copies of $\CG[\alpha_i]$
it follows that $\alpha_{B_1} = \alpha_{B_0}=\alpha_{B_2}$.
So $B_1$ and $B_2$ share a $\beta_0$-coset
in a $\CG[\alpha_{B_0}]$-copy of $\hat{\H}$. The generator set
$\alpha_{B_0}$ and the constituent $\CG[\alpha_{B_0}]$ of $\hat{\H}$
are uniquely determined by $B$:
$\alpha_{B_1}= \alpha_{B_0} = \alpha_{B_2} =\alpha_{B_i}$ for
any $\alpha_i$ arising from the corresponding $B_i \subset B$
that contribute to $B$, by iteration of the above argument.
It follows that the same $\CG[\alpha_{B_0}]$-copy and
$\beta_0$-coset are contained in all $B' \subset B$ that arise as
$\beta$-components
of elements of $B$ in their respective $\CG[\alpha']$-copies.
Hence $B$ is contained in a free amalgamation cluster of constituents
from $\Gamma(\CG[\alpha])$ with this $\CG[\alpha_{B_0}]$-copy
as its core.
\eprf

\bC
\label{CEcompatcor}
In the situation of Definition~\ref{smallcosetamalgCEdef}, assume
that the subgroups in $\Gamma(\G[\alpha])$ are
free over $\I$ with embedded free small coset extensions
that satisfy the cluster property as in Lemma~\ref{clusterinCElem}
and are compatible with free amalgamation clusters
of Cayley graphs from $\Gamma(\CG[\alpha])$. Then
the family $\Gamma(\G[\alpha])$
is compatible with the free small
coset extension $\Hhat =  \CE(\H,\G,\alpha) \supsetw \H$.
\eC

\prf
Given that $\beta$-connected components of $\Hhat$ for $\beta
\strictsubset \alpha$
are isomorphic to weak subgraphs of free amalgamation
clusters from $\Gamma(\CG[\alpha])$ by Lemma~\ref {clusterinCElem},
the claim of the corollary follows with the compatibility result on free amalgamation
clusters in Lemma~\ref{compamalgclusterlem}.
\eprf

The following lemma outlines an inductive construction of
$\E$-groups that are $N$-acyclic over $\I$; it
is an analogue of Lemma~\ref{indschemaNacyclem},
which provided a similar construction for plain coset acyclicity.
That is now also comprised as a special case, viz.\ for the trivial constraint graph with just loops on a single vertex. Recall that $\Gamma_k$ stands for the set of
generator subsets $\alpha \subset E$ of size $|\alpha| < k$, and
$\Gamma_k(\G)$ for the family of generated subgroups
$\G[\alpha]$ generated by $\alpha \in \Gamma_k$.
The construction of finite $\E$-groups $\G$ that are
$N$-acyclic over $\I$ is again
achieved in an inductive process that produces
a sequence of $\E$-groups  $\G_k$,
for increasing values of $k$ in the range between $1$ and $|E|$ such
that
\[
\G_k \mbox{ is $N$-acyclic w.r.t.\
$\I[\alpha]$-cosets for } \alpha \in \Gamma_k.
\]

These levels of $N$-acyclicity over $\I$ arise as a consequence
of the more specific sufficient condition that
\[
\G_k \mbox{ is free over $\I$ and $N$-acyclic w.r.t.\ }
\Gamma_k(\G_k).
\]

As before, $\G_{k+1}$ is obtained as $\G_{k+1} := \sym(\H_k)$
from an $\E$-graph $\H_k$ defined from $\CG_k$. And, just as in the case of
Lemma~\ref{indschemaNacyclem}, $\H_k$ is chosen such that
\bre
\item[--]
$\G_{k+1} \succeq \G_{k}$,
\item[--]
$\Gamma_{k+1}(\G_{k+1}) = \Gamma_{k+1}(\G_k)$, i.e.\
$\G_{k+1}[\alpha] \simeq \G_k[\alpha]$ for $|\alpha| \leq k$.
\ere

The second condition requires guarantees of compatibility
with $\H_k$. This in turn requires downward
compatibility for $\alpha$-connected components of $\H_k$,
where $\alpha \in \Gamma_{k+1}$. That is where the analysis of
free small coset extensions and
free amalgamation clusters
become a crucial ingredient. The analysis of free amalgamation
chains is already familiar from Section~\ref{acycsec}, including their use
towards plain coset $N$-acyclicity.

\bL
\label{indschemaIacyclem}
For any finite $\E$-group $\G$ and $n \geq 1$ there is a sequence
of finite $\E$-groups $(\G_k)_{k \leq |E|}$ starting with $\G_0 := \G$ such
that for  $k < |E|$:
\bre
\item
$\G_k \preceq \G_{k+1}$,
\item
$\Gamma_{k+1}(\G_k) = \Gamma_{k+1}(\G_{k+1})$,
\item
$\G_{k+1}$ is compatible with all free amalgamation chains of length
up to $n$ and with all free amalgamation clusters
over $\Gamma(\G_{k+1})  = \Gamma_{k+1}(\G_k)$,
\item
$\G_{k+1}$ is free over $\I$ and
$N$-acyclic w.r.t.\ $\Gamma_{k+1}(\G_{k+1})  = \Gamma_{k+1}(\G_k)$
for $N = n+2$.
\ere
It follows that, for $N = n+2$, each
$\G_k[\alpha]$ is $N$-acyclic over $\I$ for all $\alpha$ of size
$|\alpha|  \leq k$ and that, for $\Ghat := \G_{|E|}$,
\[
\G \preceq \Ghat \; \mbox{ where $\Ghat$ is $N$-acyclic over $\I$.}
\]
\eL

Note that free amalgamation clusters include all
free amalgamation chains of length~$1$ and ~$2$ so that
the compatibility with chains in~(iii) only comes into
effect for $n > 2$ (even $4$-acyclicity is guranteed without
direct recourse to chains, by Lemma~\ref{fromcompattoacyclem}).

\prf
Conditions~(ii)--(iv) are trivially satisfied at the level of
$k=0$; condition~(i) will, for all $k$, be guaranteed by letting
$\G_{k+1} := \sym(\H_k)$ where $\H_k$ contains as one of its
components a copy of $\CG_k$ (cf.\ Lemma~\ref{Ghatcompatlem}).
It remains to choose the remaining
components of $\H_k$ in such a way that condition~(ii) is maintained
while (iii) and~(iv) are enforced in
the inductive generation of the $\G_{k+1}$ for $k \geq 0$.
In order to implement the first part of~(iii)
and the plain $N$-acyclicity requirement
of~(iv) we let $\H_k$ comprise copies of
\bre
\item[--]
every free amalgamation chain
of length up to $n$
\\
with constituents $\G_k[\alpha_i]$
for $\alpha_i \in \Gamma_{k+1}$,
\ere
which is as in Lemma~\ref{indschemaNacyclem}. To guarantee the
second part in~(iii) and the freeness
requirement in~(iv), we now also put, as components of $\H_k$, copies
of
\bre
\item[--]
the free small coset amalgam $\CE(\CG_k[\I,\alpha,s],\G_k,\alpha)$
\\
for every $\alpha \in \Gamma_{k+1}$ and $s \in S$,
\ere
which is a free small coset
extension of the underlying $\I$-skeleton.
These ingredients in $\H_k$ are compatible with condition~(ii).
For the chains this is due to Lemma~\ref{compamalgchainlem} as before.
For the free coset extensions it is due to the cluster property,
which entails that compatibility by Corollary~\ref{CEcompatcor}.

That plain $N$-acyclicity is maintained follows from
Lemma~\ref{fromcompattoacyclem}; that freeness is maintained
follows from Lemma~\ref{smallcosettofreelem}.
\eprf

Similar to Theorem~\ref{symmacycEgroupthm} we sum up the
construction and emphasise its preservation of symmetries over $E$.

\bT
\label{symmacycIEgroupthm}
For every finite $\E$-group $\G$ that is compatible with the
constraint graph $\I$ and every $N \geq 2$ there is
a finite $\E$-group $\Ghat \succeq \G$ that is $N$-acyclic over $\I$
and fully symmetric over $\G$ in the sense that every permutation
$\rho \in \mathrm{Sym}(E)$
of the generator set $E$ that is a symmetry of $\I$ and $\G$ extends to a
symmetry of $\Ghat$: $\G^\rho \simeq \G \Rightarrow \Ghat^\rho \simeq \Ghat$.
\eT

In particular, we may obtain finite $\E$-groups
$\Ghat$ that are $N$-acyclic over $\I$ and
fully symmetric over $\I$ in the sense of admitting every symmetry of
$\I$ as a symmetry. For this we may start e.g.\ from
$\G := \sym(\H)$ where $\H$ is the disjoint union of $\I$ and
the hypercube $\H = 2^E$.

\section{From groups to groupoids}
\label{groupoidsec}

In terms of the combinatorial action of the generators $e \in E$ on
an $\E$-graph $\H$, and by extension of the monoid structure of $E^\ast$
on $\H$, the involutive nature of $\pi_e \in \mathrm{Sym}(V)$
is closely tied to the undirected nature of $e$-edges in
$\E$-graphs. We want to overcome this restriction by
allowing for directed $e$-edges. At the same time we may want to relax
the strictly prescribed uniformity between vertices. The latter has
already been achieved in the context of involutive generators
with constraint graphs $\I$ in Section~\ref{constraintsec}.
So now we want to allow for vertices of different sorts
with \emph{directed} transitions via $e$-edges between vertices of
specific sorts. Some applications of
related notions of acyclicity in graph and hypergraph
structures inspired by Cayley graphs
in~\cite{Otto12JACM,arXiv2018} are very naturally cast in
terms of multi-sorted multi-graph structures and
related groupoids. In this section we directly reduce
the construction of groupoids with the desired
coset acyclicity properties to the constructions of groups
from the previous sections.

\subsection{Constraint patterns for groupoids}
\label{constraintpatternsec}

In the following we consider groupoid structures with
a specified pattern of sorts (types of elements, objects) and generators
(for the groupoidal operation, morphisms). Groupoids in our sense can also be
associated with inverse semigroups of correspondingly restricted
patterns.
We choose a format for the specification of their sorts
that is very similar to the format of $\E$-graphs,
and call this specification a \emph{constraint pattern}.
The corresponding structures generalise the constraint graphs
of Section~\ref{constraintsec} in the desired direction.
Such a template will be a directed multi-graph with edge set $E$ and vertex
set $S$, but unlike $\E$-graphs considered so far, the edges $e \in E$
are directed, with an explicit operation of edge reversal.

\bD[constraint pattern $\I$]
\label{Idef}
\mbox{}\\
A \emph{constraint pattern} is a multi-graph
$\I = (S,E, \iota_1,\iota_2, \cdot^{-1})$, which we formalise as a
two-sorted structure with a set $S$ of vertices and a set $E$ of edges
as sorts, linked by surjective maps
$\iota_i \colon E \rightarrow S$
that associate a source and target vertex with every edge
$e \in E$, and a fixpoint-free and involutive operation of
edge reversal $e \mapsto e^{-1}$ on $E$ that is compatible
with the $\iota_i$ in the sense that $\iota_1(e^{-1}) = \iota_2(e)$.
\eD

In the following we mostly abbreviate the notation for a
constraint pattern $\I$ as above to
just $\I = (S,E)$, leaving the remaining structural details implicit.

For $s,s' \in S$, we let $E[s,s'] := \{ e \in E \colon \iota_1(e)= s,
\iota_2(e)=s' \}$ be the set of edges linking source $s$ to target $s'$.

In order to extend the notion of  $\I$-reachability (based on an undirected
constraint graph $\I$ in Section~\ref{constraintsec})
to a similar concept of $\I$-reachability
w.r.t.\ a constraint pattern $\I$ we
consider words that label \emph{directed} walks in $\I$.
It is constructive to compare
related notions in Section~\ref{constraintsec}.
All relevant subsets $\alpha \subset E$ will in the following always
be closed under edge reversal: $\alpha = \alpha^{-1}$.
A \emph{reduced} word over $E$ now is a word in which no
$e \in E$ is directly followed or preceded by its inverse $e^{-1}$.

\bD[$\I$-words and $\I$-walks]
\label{Jalphawalksdef}
\mbox{}\\
Natural sets of (reduced) $\alpha$-words that occur as edge label sequences
along directed walks on the constraint pattern $\I$
are defined as follows:
\bre
\item[--]
$\alpha^\ast[\I] \subset E^\ast$ consists of those
$w \in \alpha^\ast$ that label a walk in $\I$;
\item[--]
$\alpha^\ast[\I,s] \subset E^\ast$
consists of those $w \in \alpha^\ast$ that label a walk
from $s$ in $\I$;
\item[--]
$\alpha^\ast[\I,s,t] \subset E^\ast$
consists of those $w \in \alpha^\ast$ that label a walk
from $s$ to $t$ in $\I$.
\ere
\eD

In particular we write
$E^\ast[\I]$ for the set of all (reduced) words over $E$ that label walks in $\I$,
and naturally extend the $\iota$-maps to
all of $E^\ast[\I]$ as follows. Since a walk from $s$ to $t$ in $\I$ is a
sequence $s= s_0,e_1,s_1,\ldots,e_n,s_n=t$ such that
$\iota_1(e_{i}) = s_{i-1}$ and $\iota_2(e_i) = s_{i}$ for $1 \leq i
\leq n$, this walk is fully determined by the sequence of edges and
can be identified with the word $w = e_1\ldots e_n \in E^\ast$. So we think
of $E^\ast[\I]$ as the set of all words $w = e_1\ldots e_n$ with
$\iota_2(e_i) = \iota_1(e_{i+1})$ for $1\leq i < n$, and put
$\iota_1(w) := \iota_1(e_1)$ and $\iota_2(w) := \iota_2(e_n)$. This word
$w$ labels a walk  in $\I$ from the source vertex $\iota_1(w)$ to the target
vertex $\iota_2(w)$. Correspondingly
\[
E^\ast[\I,s,t] = \{ w \in E^\ast[\I] \colon \iota_1(w) = s,
\iota_2(w) = t\}.
\]

Concatenation between (reduced) words $w_1$ and $w_2$ is defined
as $w_1w_2 \in E^\ast[\I,\iota_1(w_1),\iota_2(w_2)]$ whenever their
$\iota$-values match in the sense that $\iota_2(w_1) = \iota_1(w_2)$.
This concatenation operation reflects composition of walks in $\I$.

\medskip
We think of the vertex set $S$ of $\I$ as a set of \emph{sites} or
\emph{vertex colours} and of the edge set $E$ as a set of
\emph{links} or \emph{edge colours} that will govern the r\^oles of
elements and generators in corresponding groupoids, as in the
following definition.
A groupoid is viewed as a group-like structure with groupoid elements of
specified sorts. These sorts are pairs of sites and specify the source
and the target site of the groupoid element. The
groupoidal composition operation, which is partial overall, is fully
defined for pairs of elements that share the same interface site.

\subsection{I-groupoids and their Cayley graphs}
\label{Igroupoidcayleysec}

\bD[$\I$-groupoid]
\label{groupoiddef}
\mbox{}\\
An \emph{$\I$-groupoid}
based on the constraint pattern $\I = (S,E)$ is a groupoid
structure of the form
$\G = (G,(G_{s,t})_{s,t \in S}, \cdot\,, (1_s)_{s \in S}, (g_e)_{e \in E})$ where
\bre
\item
the family $(G_{s,t})_{s,t \in S}$ partitions the universe
$G$ of groupoid elements;
\footnote{Some of the sets $G_{s,t}$ may be empty as $\I$ is not
required to be connected.}
\item
$\cdot\;$ is a groupoidal composition operation mapping any pair of elements
in $G_{s,t} \times G_{t,u}$ to an element of $G_{s,u}$, for all
combinations of $s,t,u \in S$;
\item
$1_s \in G_{s,s}$ is a left and right neutral element w.r.t.\ $\cdot\,$,
for every $s \in S$;
\item
$G$ is generated by the family of pairwise distinct elements
$g_e \in G_{\iota_1(e),\iota_2(e)}$ for $e \in E$,
where $g_{e^{-1}}$ is the groupoidal inverse of $g_e$ w.r.t.\ $\cdot\;$:
$g_{e^{-1}} = g_e^{-1}$ in the sense that
$g_{e} \cdot g_{e^{-1}} = 1_s$ for $s = {\iota_1(e)}$
and $g_{e^{-1}} \cdot g_e= 1_{s'}$ for $s' = {\iota_2(e)}$.
\ere
\eD

The set $E^\ast[\I,s,t]$ of those (reduced) words over $E$ that
label walks from $s$ to $t$ in $\I$ now suggests an interpretation of
$w \in E^\ast[\I,s,t]$ as a product of generators that represents a
groupoid element in $G_{s,t}$. With $w = e_1\cdots e_n \in
E^\ast[\I,s,t]$ we associate the groupoid element
$[w]_\G$ that is the
groupoidal composition
\[
\textstyle
[w]_\G
:= \prod_{i=1}^n g_{e_i} = g_{e_1} \cdots g_{e_n} \in G_{s,t}.
\]

Note that $[w]_\G \in G_{s,t}$ precisely for $s = \iota_1(w)$ and $t=
\iota_2(w)$.
The $\iota$-maps extend to the elements of an
$\I$-groupoid $\G$ according to
$\iota_i(g) = s_i$ for $i =1,2$
if, and only if, $g \in G_{s_1,s_2}$
if, and only if,
$g = [w]_\G$ for some $w \in E^\ast[\I,s_1,s_2]$.

There is an obvious notion of homomorphisms between
$\I$-groupoids, which needs to
respect the r\^ole of the distinguished generators.
The existence of a homomorphism $h \colon \Ghat \rightarrow \G$ (uniquely
determined and surjective if it exists)
is expressed as $\Ghat \succeq \G$.
The following is analogous to Observation~\ref{freeinvgroupobs}.

\bO
\label{freeIgroupoidobs}
The quotient of $\I$-walks w.r.t.\ cancellation of direct edge
reversal, as represented by the set of reduced words in
$E^\ast[\I]$
as label sequences, forms an $\I$-groupoid with concatenation. This
can be regarded as the \emph{free $\I$-groupoid}, which has any other
$\I$-groupoid as a homomorphic image.
\eO

Analogous to Definition~\ref{Esymmdef} we also consider
symmetries that are induced by admissible re-labellings of the
sites and links. The natural candidates stem from symmetries
of the constraint pattern $\I$. A symmetry of $\I$ is just an
automorphisms in the usual sense for $\I$ as a multi-sorted structure,
induced by matching permutations of the sets $E$ and $S$ that are
compatible with the $\iota_i$ and with edge reversal.

\bD[symmetry over $\I$]
\label{Isymmgroupoiddef}
\mbox{}\\
An automorphism $\rho$ of $\I$ is a \emph{symmetry} of an $\I$-groupoid $\G$
if the renaming of sorts and generators according to $\rho$,
$s \mapsto \rho(s)$ and $g_e \mapsto g_{\rho(e)}$,
yields an isomorphic $\E$-groupoid, $\G^\rho \simeq \G$.
\eD

In an $\I$-groupoid $\G$, the set $\alpha^\ast[\I,s,t]$ of (reduced) words over a
subset $\alpha = \alpha^{-1} \subset E$ carves out
a \emph{generated subgroupoid}
$\G[\alpha] \subset \G$, as well as corresponding
\emph{groupoidal cosets}
at $g \in G$. These are defined in the obvious manner as
\[
\barr{@{}rcl@{}}
\G[\alpha] &=& \bigcup_{s,t} \G[\alpha,s,t]
\mbox{ where }
\\
\hnt
\G[\alpha,s,t] &=& \{ [w]_\G \in G \colon w \in \alpha^\ast[\I,s,t] \},
\\
\hnt
\mbox{ and } \;
g \G[\alpha] &=& \bigcup_t \{ g \cdot [w]_\G \colon  w \in \alpha^\ast[\I,\iota_2(g), t] \}.
\earr
\]

As the constraint pattern $\I$ will mostly be fixed, we shall often
suppress its explicit mention and write, e.g., just $E^\ast[s,t]$, or
$\alpha^\ast[s,t]$, just as we already wrote $\G[\alpha]$ or
$\G[\alpha,s,t]$ when $\I$ was implicitly determined by $\G$.

\medskip
The notion of a Cayley graph for a groupoid $\G$
encodes the operation of generators on groupoid elements, by right
multiplication, as with Cayley graphs of groups (cf.\ Definition~\ref{Cayleydef}).

\bD[Cayley graph of an $\I$-groupoid]
\label{groupoidCayleydef}
\mbox{}\\
The \emph{Cayley graph} of an $\I$-groupoid $\G = (G,(G_{s,t})_{s,t\in S},\cdot\,,(1_s)_{s
  \in S}, (g_e)_{e \in E})$ is the directed
edge-coloured graph $\CG := \mathrm{Cayley}(\G)= (G,(R_e)_{e \in E})$
with vertex set $G$ and edge sets of colour $e \in E$ according to
\[
R_e := \{ (g,g \cdot g_e) \colon g \in G_{s,t} \mbox{ for some } s \in S \mbox{
  and } t = \iota_1(e) \}.
\]
\eD

As with Cayley graphs for $\E$-groups, the Cayley graphs of
$\I$-groupoids are more homogeneous than the underlying groupoid.
In particular the neutral elements $1_s$ are not identified in $\CG$.
What is still recognisable in $\CG$, for an $\I$-groupoid $\G$, is
membership in the sets
\[
G[s,\ast]:= \iota_1^{-1}(s)
\; \mbox{ and } \;
G[\ast,s]:= \iota_2^{-1}(s),
\]
which are identified by the existence of corresponding
incoming or outgoing $R_e$-edge for $e$
with $\iota_2(e) = s$ or $\iota_1(e) = s$, respectively.
The algebraic structure of the $\I$-groupoid $\G$
is still fully determined by its Cayley graph $\CG$
in the corresponding action of partial permutations.
In the terminology of~\cite{Lawson} it can be recovered
as a groupoid embedded in the full
\emph{symmetric inverse semigroup} $I(G)$
over its vertex set $G$. In analogy with
the case of groups and their Cayley graphs, where the group is
realised as a subgroup of the full symmetric group of global
permutations of the vertex set the groupoid is realised
as a subgroupoid of the set of all bijections between
the relevant sets $G[\ast,s]$.

\bO
\label{groupoidbackfromCayleyobs}
The $\I$-groupoid $\G$ is isomorphic to the
$\I$-groupoid generated by the following bijections
$\pi_e$ for $e \in E[s,s']$:
\[
\barr{@{}rcl@{}}
\pi_e \colon G[\ast,s] &\longrightarrow& G[\ast,s']
\\
g &\longmapsto& g \cdot g_e,
\earr
\]
where $g \cdot g_e$ is identified as the unique vertex $g'$ of $\CG$
for which $(g,g') \in R_e$. Here $1_s = \mathrm{id}_{G[\ast,s]}$ is
the identity on $G[\ast,s]$.
\eO

Note that $\pi_e$ is a partial bijection of the set $G$ but total
in restriction to the indicated domain and range.

The analogy is carried further in the following
(cf.\ Definitions~\ref{Egraphdef},~\ref{symdef} and~\ref{compatdef} in
connection with $\E$-graphs and $\E$-groups.)
A major difference is the absence of a simple \emph{completion}
operation for $\I$-graphs.
\footnote{Indeed the proposal of a naive completion operation
accounts for the major flaw in~\cite{lics2013}.}

\bD[$\I$-graph]
\label{Igraphdef}
\mbox{}\\
An \emph{$\I$-graph}, for a constraint pattern $\I = (S,E)$,
is a vertex- and edge-coloured directed graph
$\H = (V,(V_s)_{s \in S}, (R_e)_{e \in E})$, whose vertex set $V$ is partitioned into
non-empty subsets $V_s$ of vertices of colour $s \in S$,
with edge sets $R_e \subset V_{\iota_1(e)}\times V_{\iota_2(e)}$
of colour $e$ for $e \in E$ such that $R_{e^{-1}} = R_e^{-1}$.
The $\I$-graph $\H = (V,(V_s)_{s \in S}, (R_e)_{e \in E})$ is
\emph{complete} if each $R_e$ is a complete matching between
$V_{\iota_1(e)}$ and $V_{\iota_2(e)}$ (i.e.\ the graph of a bijection
$\pi_e \colon V_{\iota_1(e)} \rightarrow V_{\iota_2(e)}$).
An automorphism of $\I$ is a
\emph{symmetry} of the $\I$-graph $\H$ if its operation
as a renaming on $\H$ yields an isomorphic $\I$-graph:
$\H^\rho \simeq \H$.
\eD

Clearly the Cayley graph of an $\I$-groupoid is a complete
$\I$-graph that shares every symmetry of the $\I$-groupoid
(cf.\ Definition~\ref{Isymmgroupoiddef} for symmetries).
Conversely, any complete $\I$-graph determines an $\I$-groupoid
in the manner indicated for this special case in
Observation~\ref{groupoidbackfromCayleyobs} above.
In a complete $\I$-graph $\H$ as in Definition~\ref{Igraphdef},
the composition of the $\pi_e$ along $w = e_1 \cdots e_n \in
E^\ast[\I,s,t]$, $\pi_w = \prod_{i=1}^n \pi_{e_i} = \pi_{e_n} \circ
\cdots \pi_{e_1}$,
induces a bijection $\pi_w \colon V_s \rightarrow
V_t$, which we denote as $[w]_\H$. The natural composition
operation on matching interface sites induces the structure of an
$\I$-groupoid $\G$ on the set $G = \{ \pi_w \colon w \in E^\ast[\I] \}$.

\bD[$\sym(\H)$]
\label{Isymdef}
\mbox{}\\
From a complete $\I$-graph $\H$ as in Definition~\ref{Igraphdef},
with induced partial bijections $\pi_w$ for $w \in E^\ast[\I]$, we
obtain the $\I$-groupoid
\[
\sym(\H) := \bigl(G,(G_{s,t}), \,\cdot\,(1_s), (\pi_e)\bigr)
\]
with $G_{s,t} = \{ \pi_w \colon w \in E^\ast[\I,s,t] \}$,
composition of partial bijections (which is full composition in
matching sites to match concatenation of labelling sequences)
and identities in corresponding sites as neutral elements.
\eD

Observation~\ref{groupoidbackfromCayleyobs} can be restated as
$\sym(\CG) \simeq \G$ if $\G$ is an $\I$-groupoid with Cayley graph $\CG$.

\bD[compatibility]
\label{Igraphcompatdef}
\mbox{}\\
An $\I$-groupoid $\G$ is \emph{compatible} with the complete
$\I$-graph $\H$ if $\G \succeq \sym(\H)$, i.e.\ if
for all $w \in E^\ast[\I,s,s]$
\[
[w]_\G = 1_s\; \Rightarrow \; [w]_\H = \mathrm{id}_{V_s}.
\]
\eD

The following illustrates these concepts and their far-reaching analogy
with the situation for $\E$-groups from Section~\ref{genpatternsec}.

\bO
\label{groupoidcompatobs}
Any $\I$-groupoid $\G$ is compatible with its Cayley graph.
Another $\I$-groupoid $\Ghat$ is compatible with the Cayley graph
$\CG$ of $\G$ if, and only if, $\Ghat \succeq \G$, if, and only if
the map $h \colon \Ghat \rightarrow \G$ which maps
$[w]_{\Ghat}$ to $[w]_{\G}$ is well-defined (and thus the homomorphism
in question).
\eO

\subsection{Coset acyclicity for groupoids}
\label{groupoidcosetacycsec}

Also the following are straightforward analogues of the corresponding notions
for $\E$-groups in Definitions~\ref{cosetcycledef} and~\ref{Nacycdef}.

\bD[coset cycles]
\label{groupoidcosetcycledef}
\mbox{}\\
Let $\G$ be an $\I$-groupoid, $n \geq 2$.
A \emph{coset cycle of length $n$} in $\G$ is a cyclically
indexed sequence of pointed cosets $(g_i \G[\alpha_i], g_i)_{i \in \Z_n}$
such that, for all $i$,
\bre
\item
(connectivity)
$g_{i+1} \in  g_i \G[\alpha_i]$, i.e.\ $g_i \G[\alpha_i] = g_{i+1} \G[\alpha_i]$;
\item
(separation)
$g_i \G[\alpha_{i,i-1}] \cap g_{i+1} \G[\alpha_{i,i+1}] = \emptyset$,
\ere
where $\alpha_{i,j} := \alpha_i \cap \alpha_j$.
\eD

\bD[$N$-acyclicity]
\label{groupoidnacyclicdef}
\mbox{}\\
For $N \geq 2$, an $\I$-groupoid $\G$
is \emph{$N$-acyclic} if it admits no
coset cycles of lengths up to $N$.
\eD

\section{Construction of N-acyclic I-groupoids}
\label{Nacycgroupoidsec}

We associate with a constraint pattern $\I = (S,E)$ for $\I$-groupoids $\G$
a set $\Ehat$ of involutive generators and a constraint graph $\Ihat$
so that $\I$-groupoids of interest can be identified within suitable
$\EEhat$-groups $\Ghat$ that are compatible with $\Ihat$.
More specifically,
we aim for a low-level interpretation of Cayley graphs  of
$\I$-groupoids $\CG$ within the direct product of
$\Ihat$ with the Cayley graph $\CGhat$ of an $\EEhat$-group $\Ghat$
that is compatible with $\Ihat$. Compare Definition~\ref{directproddef} for this
direct product.

\medskip
Firstly, we interpret the directed multi-graph structure of the
constraint pattern
\[
\I = (S,E)
= (S,E,\iota_1,\iota_2,\cdot^{-1})
\]
in the structure of a constraint graph
\[
\hat{\I} = (\hat{S}, (R_{\hat{e}})_{\hat{e} \in \hat{E}})
\]
for a set $\Ehat$ of involutive generators.
Recall that the edge relations $R_e$ of the latter are undirected
while the edges $e \in E$ of the former are directed.
To this end,  associate with every $e \in E$
$3$ new edge labels $\{e\}$, $\{ e,e^{-1} \}$ and $\{ e^{-1} \}$ in $\Ehat$,
as well as $2$ new vertices $s_e$ and $s_{e^{-1}}$ in $\Shat$.
On the basis of
\[
\barr{rcl}
\Ehat &:= &\bigl\{
\{e\}, \{ e,e^{-1} \}, \{ e^{-1} \}   \colon e \in E \bigr\},
\\
\Shat &:=& S \cup \bigl\{ s_e, s_{e^{-1}}
 \colon e \in E \bigr\},
\earr
\]
we represent directed $e$-(multi-)edges
as walks of length~$3$ in an $\EEhat$-graph
$\Ihat$ as follows.
We replace the directed edge $e \in E[s,s']$
and its inverse $e' := e^{-1} \in E[s',s]$ in $\I$
by a succession of $3$ undirected edges with labels
$\{e\}$, $\{e,e'\}$ and $\{e'\}$ that link $s$ and $s'$
via the two new intermediate vertices $s_{e}$ and $s_{e'}$:
\[
\xymatrix{
s \ar@{-}[rr]^{\{e\}}
&& s_{\ssc e} \ar@{-}[rr]^{\{e,e'\}}
&& s_{\ssc e'}
\ar@{-}[rr]^{\{e'\}}
&& s'
}
\]

By the same token, a loop $e\in E[s,s]$ at $s$ and its
inverse $e' := e^{-1}$ get replaced by a cycle of $3$ undirected edges with labels
$\{e\}$, $\{e,e'\}$ and $\{e'\}$:
\[
\xymatrix{
& s \ar@{-}[ld]_{\{e\}} \ar@{-}[rd]^{\{e'\}}&
\\
s_{\ssc e}
\ar@{-}[rr]_{\{e,e'\}}
&& s_{\ssc e'}}
\]

Note that these replacements are inherently symmetric w.r.t.\
edge reversal in the sense that the replacements really concern the edge
pair $\{e,e^{-1}\}$. The direction of $e$ is encoded
in the directed nature of the walk
\[
s,\{e\},s_{\ssc e}, \{e,e^{-1}\}  ,s_{\ssc e^{-1}},\{e^{-1}\},s',
\]
whose reversal exactly is the corresponding walk for $e^{-1}$.
The resulting $\EEhat$-graph $\Ihat$ is special also in that each one of
its edge relations $R_{\hat{e}}$ for $\hat{e} \in \Ehat$ consists
of a single undirected edge. Any automorphism of the constraint
pattern $\I$ turns into a symmetry of the $\EEhat$-graph $\Ihat$, which
is the desired constraint graph.

\medskip
We use this simple schema to associate \emph{$\I$-reachability} w.r.t.\
the constraint pattern $\I$ for $\I$-groupoids and their Cayley graphs
with \emph{$\hat{\I}$-reachability} w.r.t.\ the constraint graph
$\hat{\I}$ for $\hat{\E}$-groups and their Cayley graphs.
Overall, this will allow us to directly extract $\I$-groupoids
from suitable $\hat{\E}$-groups, in a manner that preserves symmetries
and the desired acyclicity properties.

\medskip
For $\Ehat, \Shat$ and  $\Ihat$ as just constructed from $\I$,
there is a one-to-one correspondence between reduced words in
\[
\Ehat^\ast[\Ihat,s,t] :=
\{ w \in \Ehat^\ast \colon \mbox{ $w$ labelling a walk from
  $s$  to $t$ in $\Ihat$ }  \}
\]
and reduced words in $E^\ast[\I,s,t]$
that label directed walks from $s$ to $t$ in $\I$.
In other words, for all $s,t \in S$,
and modulo passage to reduced words,
the natural replacement map
\[
\barr{@{}rcl@{}}
\hat{\nt\;\nt} \; \colon \; E^\ast[\I,s,t] &\longrightarrow&  \Ehat^\ast[\hat{\I},s,t]
\\
\hnt
w = e_1\cdots e_n &\longmapsto& \hat{w} :=
\{ e_1 \} \{ e_1,e_1^{-1}\}\{ e_1^{-1}\}\cdots \{ e_n \} \{
e_n,e_n^{-1}\}\{ e_n^{-1}\}
\earr
\]
induces a bijection.
For this observation it is essential that reduced words in $\Ehat^\ast[\Ihat]$
can only label walks that link vertices from $S$ if they consist of
concatenations of triplets corresponding to admissible orientations
of $E$-edges. In connection with the reduced nature of the words involved,
note on one hand that an immediate concatenation of a triplet for $e \in E$
with the triplet for $e^{-1}$ would not be a reduced $\Ehat$-word.
On the other hand, the only non-trivial $\{ \{ e \}, \{
e,e^{-1}\},\{e^{-1}\}\}$-component of $\hat{\I}$ consists
of $\{\iota_1(e),\iota_2(e), s_{\ssc e}, s_{\ssc e^{-1}}\}$.
The only manner in which a reduced $\Ehat$-word
can label a walk in $\Ihat$ that exits this $\{ \{ e \},\{
e,e^{-1}\},\{e^{-1}\}\}$-component of $\Ihat$
is via $\iota_1(e)$ or $\iota_2(e)$, which are both in $S$.

For notational convenience we also denote as $\hat{\nt\;\nt}$ the
incarnation of the replacement map at the level of reduced words
and at the level of subsets $\alpha \subset E$ that
are closed under edge reversal:
\[
\barr{@{}rcl@{}}
\alpha &\longmapsto& \hat{\alpha} :=
\bigl\{ \{ e \}, \{ e,e^{-1}\}, \{ e^{-1}\} \colon e \in \alpha
\bigr\}.
\earr
\]

\subsection{Groupoids from groups}
\label{extractgroupoidsec}

For a constraint pattern $\I = (S,E)$ and its representation within a
constraint  graph $\Ihat$ for $\EEhat$-graphs according
to the above translation, consider now an $\EEhat$-group
$\Ghat$ that is compatible with $\Ihat$. Let $\CGhat$ be the
Cayley graph of this $\EEhat$-group.
Recall Definition~\ref{directproddef} for the definition of a direct
product, which we now apply to the $\EEhat$-graphs $\Ihat$ and
$\CGhat$:
\[
\Ihat \otimes \CGhat
\]
is an $\EEhat$-graph which reflects $\Ihat$-reachability in the sense
that $(\hat{s}',\hat{g}')$ is in the $\hat{\alpha}$-connected
component of $(\hat{s},\hat{g})$ if, and only if,  $\hat{g}'$ is in the
$\Ihat[\hat{\alpha},\hat{s}]$-component
$\CGhat[\Ihat,\alpha,s;\hat{g}]$
of $\hat{g}$.

\medskip
We next extract an $\I$-groupoid $\G$
from any $\EEhat$-group $\Ghat$ that is compatible with the
constraint graph $\Ihat$. More specifically, the Cayley graph of the
target
$\I$-groupoid
$\G := \Ghat[\I]$ is interpreted within the direct product
$\Ihat \otimes \CGhat$. The idea is to single out the vertices of
$\Ihat \otimes \CGhat$ with $\Shat$-component in $S \subset \Shat$,
and to replace $\{ e \} \{ e,e^{-1} \}
\{e^{-1}\}$-walks of length $3$ between them by directed
$E$-edges. In essence this is a reversal of the translation that led
from $E$ to $\Ehat$ and from $\E$-graphs to $\EEhat$-graphs..

We define $\G$ in terms of its generators $e \in E$,
which are interpreted as partial bijections on
the vertex set of $\Ihat \otimes \CGhat$.
We restrict attention to vertices
$\{ (s,[\hat{w}]_{\Ghat}) \in \hat{\I} \otimes \Ghat
\colon \hat{w} \in \Ehat^\ast[\Ihat,s,t] \}$ for $s,t \in S \subset \Shat$, and put
\[
G_{s,t} := \{ (s, [\hat{w}]_{\Ghat}) \colon
\hat{w} \in \Ehat^\ast[\Ihat,s,t] \}
= \{ (s,[\hat{w}]_{\Ghat}) \colon w \in E^\ast[\I,s,t] \}.
\]

The second equality appeals to the identification of reduced
words in $\Ehat^\ast[\Ihat,s,t]$ and $E^\ast[\I,s,t]$ for $s,t
\in S \subset \Shat$. The sets $G_{s,t}$ are subsets of the
vertex set of  $\Ihat \otimes \CGhat$.
They are disjoint by compatibility of $\Ghat$  with $\Ihat$
and thus partition
\[
G :=
\dot{\bigcup}_{s,t \in S} G_{s,t}
\]
into subsets (not all necessarily non-empty unless $\I$ is
connected). We write $G_{\ast,t}$ for the union
$G_{\ast,t} := \bigcup_{s\in S} G_{s,t}$.
With $e \in E[t,t']$ we associate the
following partial bijection on the vertex set of $\hat{\I}
\otimes \CGhat$, with domain and image as indicated:
\[
\barr{@{}rcl@{}}
g_e \colon G_{\ast,t} &\longrightarrow&
G_{\ast,t'}
\\
\hnt
(s,[\hat{w}]_{\hat{\G}})
&\longmapsto& (s, [\hat{w}\hat{e}]_{\Ghat})
= (s,[\hat{w}]_{\Ghat} \cdot \{ e \} \cdot \{ e,e^{-1} \} \cdot \{ e^{-1} \}),
\earr
\]
where $w \in E^\ast[\I,s,t]$ and $w e \in E^\ast[\I,s,t']$.
Concatenation (and reduction) of corresponding words or walks in $\hat{\I}$
induces a well-defined groupoid operation according to
\[
\barr{@{}rcl@{}}
\cdot \; \colon \; G_{s,t} \times G_{t,u} &\longrightarrow& G_{s,u}
\\
\hnt
((s,[\hat{w}_1]_{\Ghat}),(t,[\hat{w}_2]_{\Ghat})) &\longmapsto&
(s, [\hat{w}_1\hat{w}_2]_{\Ghat}),
\earr
\]
where the concatenation relies on the condition that
$\iota_2(w_1) = t = \iota_1(w_2)$.
The neutral element in $G_{s,s}$ is $1_s := (s,[\lambda]_{\Ghat})$.
With these stipulations,
\[
\G := \Ghat/\I = (G, (G_{s,t})_{s,t \in S}, \cdot, (1_s)_{s
  \in S}, (g_e)_{e \in E})
\]
becomes an $\I$-groupoid with generators
\[
g_e := [e]_{\G} :=
(\iota_1(e),[\hat{e}]_{\Ghat})
\in G_{\iota_1(e),\iota_2(e)}.
\]

The induced homomorphism from the free $\I$-groupoid
(cf.\ Observation~\ref{freeIgroupoidobs})
onto $\G$ maps
\[
w \in E^\ast[\I,s,t] \longmapsto [w]_\G := (\iota_1(w),[\hat{w}]_{\Ghat}) \in G_{s,t}.
\]

For further analysis we also isolate the induced subgraph
on those connected components of the $\EEhat$-graph
$\Ihat \otimes \CGhat$ that embed $\G$:
\[
\barr{r@{}c@{}l}
\Hhat_0 &\;=\;& (\Ihat \otimes \CGhat) \restr V_0
\,\subset\, \Ihat \otimes \CGhat
\\
&&
\hnt
\mbox{where }
V_0 := \{ (s,[u]_{\Ghat}) \in \Shat \times \Ghat \colon
s \in S, u \in \Ehat^\ast[\Ihat,s] \}.
\earr
\]

The set $V_0$ is the vertex set of the union of the connected
components of the vertices $(s,1)$ in  $\Ihat \otimes \CGhat$
(i.e.\ of the neutral elements $(s,1_s) \in \G$).
Restricting further to vertices of $G \subset V_0$ and
linking two such vertices by an $e$-edge
if, and only if, they are
linked by an $\hat{e} = \{ e \} \{ e,e^{-1}\}\{e^{-1}\}$-labelled walk of
length $3$ in $\Hhat_0 \subset \Ihat \otimes \CGhat$, we obtain
an $\I$-graph $\H_0$ that is interpreted in the $\EEhat$-graph
$\Hhat_0$. This $\I$-graph $\H_0$ is (isomorphic to)
the Cayley graph of the $\I$-groupoid $\G$:
\[
\barr{r@{}c@{}l}
\H_0 &\;=\;&\bigl( G, (G_{\ast,s})_{s \in S}, (R_e)_{e \in E} \bigr)
\quad \mbox{ where, for $e = (s,s')$, }
\\
\hnt
R_e &\;=\;& \bigl\{ ((s,[u]_{\Ghat}),(s',[u \{ e \} \{ e,e^{-1}\}\{e^{-1}\} ]_{\Ghat})) \colon
u \in \Ehat^\ast[\Ihat,s] \bigr\}.
\earr
\]

\bO
\label{groupoidCayleyobs}
Let $\Ghat$ be an $\EEhat$-group that is compatible with $\Ihat$.
Then the Cayley graph $\CG$ of the $\I$-groupoid $\G = \Ghat/\I$ as just
constructed from $\CGhat$ is (isomorphic to) the
$\I$-graph $\H_0$ interpreted in $\Hhat_0 \subset \Ihat \otimes \CGhat$.
\eO

\subsection{Transfer of acyclicity, compatibility and symmetries}
\label{transfersec}

The following is the main technical result of this section. It
reduces the construction of $N$-coset acyclic groupoids to the
construction of Cayley groups with involutive generators that are
$N$-acyclic over some constraint graph.

\bP
\label{maingroupgroupidprop}
For a constraint pattern $\I$ and its translation into a constraint
graph $\Ihat$ as above, let $\Ghat$ be an $\EEhat$-groupoid
that is compatible with $\Ihat$.
Let $\G := \Ghat/\I$ the $\I$-groupoid whose Cayley graph $\CG$
is realised as $\H_0$ within $\Ihat \otimes \CGhat$ as discussed above.
\bre
\item
If $\Ghat$ is $N$-acyclic over the constraint graph $\hat{\I}$,  then
$\G$ is $N$-acyclic.
\item
If $\Ghat$ is compatible with the $\EEhat$-translation of a
complete $\I$-graph $\H$, then $\G$ is compatible with $\H$.
\item
Any symmetry $\rho$
of $\I$ induces a permutation $\hat{\rho} \in \mathrm{Sym}(\Ehat)$
that is a symmetry of $\Ihat$; if $\hat{\rho}$ is a symmetry of
$\Ghat$ then $\rho$ is a symmetry of $\G$.
\ere
\eP

The main claim, concerning $N$-acyclicity,
follows directly from the following compatibility
of the corresponding notions of cycles with the interpretation of $\CG
\simeq \H_0$ in $\Hhat_0 \subset \Ihat \otimes \Ghat$. This
is expressed in the following lemma; the arguments
towards compatibility with a given $\H$ and compatibility of the whole
construction with symmetries are straightforward.

\bL
\label{cyclestocycleslem}
In the situation of Proposition~\ref{maingroupgroupidprop}
there is a natural translation of coset cycles in the $\I$-groupoid $\G
=\Ghat/\I$ based on the map $\hat{\nt\;\nt}$ for generator sets,
which translates coset cycles in the groupoid $\G$
into $\Ihat$-coset cycles of the same length in the group $\Ghat$.
\eL

\prf
Let
\[
(\ast) \qquad
(g_i\G[\alpha_i],g_i)_{i \in \Z_n}
\]
be a coset cycle in the groupoid $\G$,
according to Definition~\ref{groupoidcosetcycledef},
viewed in $\H_0$.
The connectivity condition for the cycle $(\ast)$ and the
manner in which $\H_0$ is interpreted in $\Hhat_0 \subset \Ihat \otimes
\CGhat$ implies that there is an
$\hat{\alpha}_i$-walk from $\hat{g}_i = [\hat{w}_i]_{\Ghat}$
to $\hat{g}_{i+1}  = [\hat{w}_{i+1}]_{\Ghat}$, labelled
by the $\hat{\nt\;\nt}$-translation of an
$\alpha_i$-word of generators representing $g_{i}^{-1} g_{i+1} \in \G$.
The natural $\hat{\nt\;\nt}$-translation of the cycle $(\ast)$ into
$\Ghat$ is
\[
(\ast\ast) \qquad (\Ghat[\Ihat,\hat{\alpha}_i, s_i; \hat{g}_i],\hat{g}_i)_{i \in
  \Z_n},
\]
where the labels $s_i \in S \subset \Shat$
are determined by the sorts of the
$g_i$ according to $s_i = \iota_2(w_i)$.
This translation in effect replaces the subsets $g_i\G[\alpha_i]$ by their closures
$\Ghat[\hat{\I},\hat{\alpha}_i, s_i;\hat{g}_i]$ w.r.t.\
$\Ihat$-reachability inside their $\hat{\alpha}_i$-coset.
This closure is obtained as the union of all
$\{\{e\},\{e,e^{-1}\},\{e^{-1}\}\}\}$-connected components
in $\Hhat_0 \subset \Ihat \otimes \CGhat$
that contain at least one element of the representation of
$g_i\G[\alpha_i]$ in $\H_0$.

It is clear that $(\ast\ast)$ has the format of a potential
$\Ihat$-coset cycle of length $n$ over $\Ihat$ in $\Ghat$
in the sense of Definition~\ref{Icosetcycledef}.
It remains to show that the separation
condition in Definition~\ref{Icosetcycledef} for
$(\ast\ast)$ follows from the analogous condition in
Definition~\ref{groupoidcosetcycledef} for $(\ast)$.

Suppose that, in violation of the separation condition
for $(\ast\ast)$,
\[
(\dagger) \qquad
\hat{g} \in \hat{g}_i\Ghat[\hat{\I},\hat{\alpha}_{i-1,i}, s_i] \cap
\hat{g}_{i+1}\Ghat[\Ihat,\hat{\alpha}_{i,i+1}, s_{i+1}],
\]
where $\alpha_{i,i\pm 1} = \alpha_i \cap \alpha_{i\pm 1}$.

We analyse this non-trivial intersection in terms of the
representation of $G$ in $\Hhat_0 \subset \Ihat \otimes \CGhat$.
Let $\hat{g} = \hat{g}_i [w_{i,i-1}]_{\Ghat}  = \hat{g}_{i+1}
[w_{i,i+1}]_{\Ghat}$ for suitable $w_{i,j} \in \hat{\alpha}_{i,j}^\ast[\Ihat,s_j]$.
By the separation condition for $(\ast)$, $\hat{g}$ is not
represented as an element of $\G$ or
$\H_0$ in $\Hhat_0$, so that $\iota_2(w_{i,j}) \in \Shat \setminus S$,
i.e.\ $\iota_2(w_{i,j}) \in \{ s_{\ssc e},s_{\ssc e^{-1}} \}$
for some $e \in E$.

But in $\{\{e\},\{e,e^{-1}\},\{e^{-1}\}\}]$-components
of elements of $G$ or vertices of $\H_0$ in $\Hhat_0$,
any vertex with $\iota_2$-value outside $S$ is isolated
from all vertices with $\iota_2$-value in $S$ by
$\{e\}$- and $\{e^{-1}\}$-edges (just as vertices in $\Shat\setminus S$
are isolated from $S$ in $\Ihat$).
So $(\dagger)$ implies that
$e,e^{-1} \in \alpha_{i,j}$ for $j = i\pm 1$.
This would imply that there also is an $e$-link between
the elements of that component that represent elements of $G$.
So elements of $g_i\G[\alpha_{i,i-1}]$ and of
$g_{i+1}\G[\alpha_{i,i+1}]$ occur in the same $\{ e, e^{-1}\}$-component,
which would violate the separation condition for $(\ast)$ since
$e \in \alpha_{i,i-1}$ and $e \in \alpha_{i,i+1}$.
\eprf

\bT
\label{acycgroupoidthm}
For every finite constraint pattern $\I = (S,E)$, every
complete $\I$-graph $\H$ and  every $N \geq 2$
there is a finite $N$-acyclic $\I$-groupoid
$\G$ that is compatible with $\H$. Such $\G$ can be chosen to be
fully symmetric w.r.t.\ the given data, i.e.\ such that every
symmetry $\rho$ of $\I$ that induces a symmetry of the $\I$-graph
$\H$ is also a symmetry of the $\I$-groupoid $\G$:
$\H^\rho \simeq \H \Rightarrow \G^\rho \simeq \G$.
\eT

Choosing the Cayley graph of a given $\I$-groupoid $\G_0$ for $\H$,
we obtain a fully symmetric $N$-acyclic $\I$-groupoid $\G \succeq
\G_0$. For $\H := \sym(\I)$ (regarding $\I$ as a complete $\I$-graph
according to Definition~\ref{Igraphdef}) one obtains $N$-acyclic
$\I$-groupoids that are fully symmetric over $\I$.

\section{Conclusion and primary applications}

The generic constructions of the preceding chapters show
the versatility of the fruitful idea to go back and forth
between group-like structures (monoids and groups as well as groupoids)
and graph-like structures (graphs and multi-graphs, undirected as well
as directed, and possibly vertex- or edge-coloured). In one
direction the passage involves the familiar encoding of algebraic
structures in the graph-like representation of generators, as in the
classical notion of Cayley graphs for groups; in the converse
direction, permutation groups are induced by various operations
on graph-like structures. We have here tried to contribute to these
connections with a special emphasis on strong algebraic-combinatorial
criteria of graded acyclicity in finite structures. The constructions
presented here extend techniques for the construction
of $N$-acyclic groups with involutive generators
from~\cite{Otto12JACM} to yield a conceptual improvement and correction
of the proposed constructions for groupoids from~\cite{lics2013}.
Due to its symmetry preserving generic character,
the new presentation also supports the use of these groupoids
in~\cite{arXiv2018} where symmetry considerations are of the essence
towards lifting local symmetries to global symmetries in finite
structures.
In a different direction, $2$-acyclic finite groupoids have
also been used to resolve an open problem of a purely
semigroup-theoretic nature in Bitterlich~\cite{Bitterlich}.

To conclude the present treatment we briefly look at the most
salient application for finite groups and groupoids of
graded coset-acyclicity. This concerns the construction of
finite coverings of graphs and hypergraphs that unravel short
cycles.
\bne
\item
Natural, unbranched finite coverings of graphs
by graphs with interesting acyclicity properties can be obtained as weak
subgraphs of the Cayley graphs of suitable $\E$-groups where $E$
is the set of edges of the graph to be covered (individually labelled
as it were). While similar constructions have been used
in~\cite{Otto04,Otto12JACM}
and a precursor for special graphs in~\cite{CO17}, we illustrate the key to the new
generalisation in Proposition~\ref{graphcoverprop} below.
\item
Natural reduced products with $N$-acyclic $\I$-groupoids
yield finite branched $N$-acyclic coverings of hypergraphs where
a constraint pattern $\I = (S,E)$ is induced by the intersection graph
of $(V,S)$ that encodes the intersection
pattern between hyperedges in the given hypergraph (cf.~\cite{lics2013}).
\item
A new and more direct approach to finite branched  $N$-acyclic coverings of
hypergraphs $(V,S)$ can be based on $\I$-products between a constraint graph
$\I = (S,E)$ induced by the intersection graph of $(V,S)$ and suitable
$\E$-groups that are not just $N$-acyclic but $N$-acyclic over $\I$;
cf.~Proposition~\ref{hypcoverprop} below.
\ene

Of these fundamental applications, (2)
has been explored in stages in~\cite{Otto12JACM,lics2013,arXiv2018}.
Application~(1) is new in its strong form that involves the new notion of $N$-acyclicity
of groups over a constraint graph $\I$. Application~(3) similarly
supersedes~(2).
Recall from Section~\ref{constraintsec} how control of cyclic
configurations can be extended
to configurations governed by reachability patterns w.r.t.\ a given
constraint graph $\I$. While we have seen in Section~\ref{groupoidsec}
how such groups can yield coset acyclicity in groupoids as used in~(2),
the underlying groups can also be put to use directly in~(1) and~(3).

\paragraph*{Graph coverings.}
For a finite simple graph $\V = (V,E)$ consider, as a set $E$ of
involutive generators for $\E$-groups, the set of all edges
$e=\{v,v'\} \in E$, and as a constraint graph $\I$ the $\E$-graph
$\I = (V, (\{ e \})_{e \in E})$ ($\V$ with individually labelled
edges). For any $\E$-group $\G$ that is compatible with $\I$
consider the direct product $\Vhat = \I \otimes \CG$
of the constraint graph $\I$ with the Cayley graph $\CG$ of $\G$
according to Definition~\ref{directproddef}. Then the
natural projection
\[
\pi \colon \barr[t]{@{}rcl@{}}
\Vhat  &\longrightarrow& \V
\\
\hnt
(v, g) &\longmapsto& v
\earr
\]
provides an unbranched covering of $\V$ by
$\hat{\V} =\I \otimes \CG$. Recall that the connected components of
$\I \otimes \CG$ are isomorphic to weak subgraphs of $\CG$
(cf.\ Remark~\ref{directprodobs}).

\bP
\label{graphcoverprop}
Let $\V = (V,E)$ be a connected finite simple graph, $E$ associated
with its edge set $E$ as above and $\G$ an $\E$-group that is
compatible with the $\E$-graph $\I := (V,(\{e\})_{e \in E})$.
Then each connected component $\H$ of the direct product
$\I \otimes \CG$,
\bre
\item
is realised as a weak subgraph of the Cayley graph $\CG$ of $\G$ and
\item
is an
unbranched finite covering w.r.t.\ the natural projection
$\pi \colon (v,g) \mapsto v$.
\ere
This covering graph $\H$ inherits the acyclicity properties of $\CG$:
if $\G$ is $N$-acyclic over $\I$,
then $\H$ admits no cyclic configurations of length up to~$N$
of overlapping $\alpha_i$-connected components with the natural
separation condition for subsets $\alpha_i \subset E$.
\eP

\paragraph*{Hypergraph coverings.}
With a finite hypergraph $\V = (V, S)$ with $S \subset \mathcal{P}(V)$
associate its \emph{intersection graph}
$\I = (S,E)$ where
\[
E = \{ \{s,s'\} \in S^2 \colon  s \not= s'  , s \cap s' \not=\emptyset\}.
\]

If $\G$ is an $\E$-group that is compatible with $\I$
then the direct product $\I \otimes \CG$ of the intersection graph $\I$
with the Cayley graph $\CG$ of $\G$ gives rise to a finite
branched hypergraph covering $\V = (V,S)$ as follows.
Consider the following disjoint union
of $G$-tagged copies of the hyperedges of $\V$,
\[
\bigcup_{s \in S} s \times G
\]
and its quotient w.r.t.\ the equivalence relation $\approx$
induced by identifications
\[
(v,g) \approx (v,ge) \; \mbox{ for } \;
e = \{s,s'\} \in E, v \in s \cap s'.
\]

The induced equivalence is such that $(v,g) \approx (v',g')$
if, and only if, $v'=v$ and $g^{-1}g' \in \G[\alpha]$ for
$\alpha =\alpha_v := \{ e = \{s,s'\} \in E \colon v\in s \cap s'  \}$.

Writing $[(v,g)]$ for the equivalence class of $(v,g) \in s \times G$,
we extend this notation to the subsets induced by the $s \in S$:
\[
[s,g] := \{ [v,g] \colon v \in s \} \mbox{ for }  (s,g) \in \I \otimes \CG.
\]

In the $\approx$-quotient, the $e$-edge between
$(s,g)$ and $(s',ge)$ in $\I \otimes \CG$ becomes
an intersection of the copies $[s,g]$ and $[s',ge]$ of the
hyperedges $s$ and $s'$ in the covering hypergraph. This covering
hypergraph is $\hat{\V} := \V \otimes \CG = (\hat{V},\hat{S})$ where
\[
\barr{@{}l@{\;:=\;}l@{}}
\hat{V} & \{ [(v,g)]\colon s \in S, g \in G \}
\\
\hnt
\hat{S} & \{ [s,g] \colon s \in S, g \in G \}
\earr
\]
with covering projection
\[
\barr{@{}rcl@{}}
\pi \colon \hat{\V} = (\hat{V},\hat{S}) &\longrightarrow&
\V = (V,S)
\\
\hnt
[(v,g)] &\longmapsto& v.
\earr
\]

\bP
\label{hypcoverprop}
Let $(V,S)$ be a finite hypergraph,
$\I = (S,E)$ its intersection graph.
If $\G$ is an $\E$-group that is compatible with
$\I$ then the hypergraph $\hat{\V} := \V \otimes \CG$, which is
based on the $\I$-product $\I \otimes \CG$ of $\I$
with the Cayley graph $\CG$ of $\G$,
gives rise to a finite branched hypergraph covering
$\pi \colon \hat{\V} \longrightarrow \V$. This
covering hypergraph $\hat{\V}$
inherits the acyclicity properties of $\CG$
in the following sense: if $\G$ is $N$-acyclic over $\I$,
then every induced sub-hypergraph on up to $N$ vertices is acyclic
in the sense of classical hypergraph theory.
\eP

For acyclicity in
hypergraph terminology (conformality and chordality and
tree-decomposability),
compare~\cite{BeeriFaginetal,Berge}.

\prf
Consider the hypergraph $\V \otimes \CG$ as defined above, for
an $\E$-group $\G$ that is compatible with the intersection graph $\I
= (S,E)$ of $\V$.

Note that in $\hat{\V}$, $\hat{v} \in [t,g] \cap [t',g']$ if, and only if,
$\hat{v} = [(v,g)] = [(v,g')]$ for some
$v \in t \cap t'$ and $g,g'$ such that $g^{-1} g' = [w]_\G$ for some $w \in
\alpha^\ast[\I,t,t']$ where $\alpha = \alpha_v = \{ e = \{s,s'\} \in E \colon
v \in s \cap s'  \}$.

It remains to argue for $N$-acyclicity
of $\hat{\V}$ if $\G$ is chosen to be $N$-acyclic over $\I$.
We show that in this situation the Gaifman graph of
$\hat{\V}$ cannot have chordless
cycles of lengths $n$ for $3 < n \leq N$
($N$-chordality), nor can it have cliques of size up to $N$ that are
not contained in a single hyperedge ($N$-conformality).

\medskip\noindent
\emph{$N$-chordality.} Suppose $(\hat{v}_i)_{i \in \Z_n}$ is a
chordless cycle of length $n > 3$ in the Gaifman graph
of $\hat{\V} = (\hat{V},\hat{S})$,
and let $[s_i,g_i] \in \hat{S}$ be such that $\hat{v}_{i} \in
[s_i,g_i] \cap [s_{i+1},g_{i+1}]$. This implies that
$\hat{v}_{i}$ can be represented as
$\hat{v}_{i} = [(v_{i},g_i)] = [(v_{i},g_{i+1})]$
for some $v_{i} \in s_i \cap s_{i+1}$ and that
$h_i := g_i^{-1} g_{i+1} = [w_i]_\G$ for some $w_i \in
\alpha_i^\ast[\I,s_i,s_{i+1}]$ where $\alpha_i = \{ e = \{s,s'\} \in E \colon
v_i \in s \cap s'  \}$.
We claim that
\[
(\CG[\I,\alpha_i,s_i;g_i],g_i)_{i \in   \Z_n}
\]
is an $\I$-coset cycle in $\G$, in the sense of
Definition~\ref{Icosetcycledef}. Then $n > N$ follows
from $N$-acyclicity of $\G$ over $\I$.
Of the two conditions in Definition~\ref{Icosetcycledef},
connectivity is obvious; it remains to check the
separation condition:
\[
\CG[\I,\alpha_{i,i-1},s_i;g_i] \cap \CG[\I,\alpha_{i,i+1},s_{i+1};g_{i+1}] = \emptyset,
\]
where $\alpha_{i,j} := \alpha_i \cap \alpha_j$.
This follows from chordlessness of the given cycle. Suppose $g$ were a
member of this intersection, i.e.\
$h := g_i^{-1}g =[w]_\G$ for some
$w \in (\alpha_{i-1}\cap\alpha_i)^\ast[\I,s_i,s]$ and
$h' := g_{i+1}^{-1}g =[w']_\G$ for some
$w' \in (\alpha_{i+1}\cap\alpha_i)^\ast[\I,s_{i+1},s]$ (the same $s$,
due to compatibility of $\G$ with $\I$).
Then $\hat{v}_{i-1} = [(v_{i-1},g_{i-1})] = [(v_{i-1},g)]$ because
$w \in \alpha_{i-1}^\ast$ and $\hat{v}_{i-1} \in [s_i,g_i]$, which implies
$\hat{v}_{i-1} \in [s,g]$. Similarly,
$\hat{v}_{i+1} = [(v_{i+1},g_{i+1})] = [(v_{i+1},g)]$ because
$w' \in \alpha_{i+1}^\ast$, which implies that
$\hat{v}_{i+1} \in [s,g]$, too. So the given cycle would have a chord
linking $\hat{v}_{i-1}$ to $\hat{v}_{i+1}$.

\medskip\noindent
\emph{$N$-conformality.}
Suppose $m = \{ \hat{v}_i \colon 1 \leq i \leq n \}$ forms a
clique of size~$n$ in the Gaifman graph of $\hat{\V} = (\hat{V},\hat{S})$
such that every
subset $m_i := m \setminus \{ \hat{v}_{i-1} \}$ of size $n-1$ is contained
in some hyperedge (a minimal violation of conformality).
Let $\hat{v}_i = [(v_i,g_i)]$, $h_i := g_i^{-1} g_{i+1}$.
For $1 \leq i \leq n$, let $[s_i,g_{i}] \in \hat{S}$
be a hyperedge that contains $m_i = m \setminus \{
[(v_{i-1},g_{i-1})]\}$. Therefore $\hat{v}_j = [(v_j,g_j)] \in
[s_i,g_i]$ for all $j \not= i-1$.
Let $\alpha_i = \{ e = \{s,s'\} \in E \colon v_i \in s \cap s'  \}$
and put $\beta_i := \bigcap_{j \not= i-1} \alpha_j$ so that
$\hat{v} = [(v,g_j)] = [(v,g)]$ for all
$g \in \CG[\I,\beta_i,s_j;g_j]$, $v \in m_i$ and $j \not= i-1$.
Note that any intersection $\beta_{i,j} := \beta_i \cap \beta_j$ for
$i\not= j$ is just $\bigcap_{i \in \Z_n} \alpha_i =: \beta$.
Consider
\[
(\CG[\I,\beta_i,s_i;g_i],g_i)_{i \in   \Z_n}
\]
as a candidate for an $\I$-coset cycle. We show that if this is not
an $\I$-coset cycle, then the whole of
$m$ is contained in some hyperedge $[s,g] \in \hat{S}$.
Again, the connectivity condition on $\I$-coset cycles
from Definition~\ref{Icosetcycledef} is obvious for the
given data. The separation condition now is that
\[
\CG[\I,\beta_{i,i-1},s_i; g_i] \cap \CG[\I,s_{i+1},\beta_{i,i+1},s_{i+1};g_{i+1}] = \emptyset,
\]
where $\beta_{i,i-1} = \beta_{i,i+1} = \beta =
\bigcap_{i \in \Z_n} \alpha_i$.
Assume there were some $g$ in this intersection, i.e.\
$g = g_i h$ for some $h = [w]_\G$ with $w \in \beta^\ast[\I,s_i,s]$
and $g =  g_{i+1} h'$ for some $h' =[w']_\G$ with
$w' \in \beta^\ast[\I,s_{i+1},s]$.
We claim that this would imply $m \subset [s,g]$.
This follows as $\hat{v}_j = [(v_j,g_j)] = [(v_j,g)] \in [s,g]$ for
$j \not= i-1$, by the nature of $h = [w]_\G$ and since $\hat{v}_j \in [s_i,g_i]$,
and as $\hat{v}_j = [(v_j,g_j)] = [(v_j,g)] \in [s,g]$ for
$j \not= i$, by the nature of $h' = [w']_\G$ and since $\hat{v}_j \in [s_{i+1},g_{i+1}]$.
\eprf

\paragraph*{Acknowledgements.}
This paper has a complicated history. It is based on
ideas revolving about acyclicity in hypergraphs and Cayley groups
that I first expounded in \cite{Otto12JACM} (the journal version of
a LICS 2010 paper). That paper deals with the construction of finite
$N$-acyclic groups  and applies it to the finite model theory of
the guarded fragment. The promising extension to the groupoid
situation was seemingly achieved with~\cite{lics2013},
which also paved the way to more fundamental
applications in hypergraph coverings and extension properties for
partial automorphisms. These applications were successively elaborated
in a series of arXive preprints leading to~\cite{arXiv2018} and stand
as key motivations and achievements also of my DFG project
on \emph{Constructions and Analysis in Hypergraphs of Controlled
  Acyclicity}, 2013--18. The proposed construction of $N$-acyclic
groupoids in~\cite{lics2013}, however, contained a serious flaw that
was also carried in the arXive preprints.
This mistake from~\cite{lics2013} was finally found out in 2019 by Julian
Bitterlich \emph{after}
he had shown, as part of his PhD work, that those results would
positively resolve a longstanding conjecture by Henkell and Rhodes
in semigroup theory, which had attracted the attention of,
among others, Karl Auinger. I am deeply indebted to Julian
Bitterlich for identifying and clarifying the gap in my earlier
attempts at the construction of finite $N$-acyclic groupoids.
Initial concerns about the use of my sketchy and, as it later turned
out, truly flawed construction from~\cite{lics2013} in Julian
Bitterlich's contributions had earlier been raised by Jiri~Kadourek. In a
way, it was his initial challenge of the result that triggered the
intense re-investigation that led to Julian's discovery of the actual
flaw. I am also very grateful to Karl Auinger and Julian Bitterlich
for helpful discussions in these difficult matters at the time
of Julian's breakthrough and discovery of my mistake.