# A random Hall-Paige conjecture

Alp Müyesser University College London, UK. email<EMAIL_ADDRESS>Alexey Pokrovskiy University College London, UK. email:
<EMAIL_ADDRESS>
###### Abstract

A complete mapping of a group $G$ is a bijection $\phi\colon G\to G$ such that
$x\mapsto x\phi(x)$ is also bijective. Hall and Paige conjectured in 1955 that
a finite group $G$ has a complete mapping whenever $\prod_{x\in G}x$ is the
identity in the abelianization of $G$. This was confirmed in 2009 by Wilcox,
Evans, and Bray with a proof using the classification of finite simple groups.

In this paper, we give a combinatorial proof of a far-reaching generalisation
of the Hall-Paige conjecture for large groups. We show that for random-like
and equal-sized subsets $A,B,C$ of a group $G$, there exists a bijection
$\phi\colon A\to B$ such that $x\mapsto x\phi(x)$ is a bijection from $A$ to
$C$ whenever $\prod_{a\in A}a\prod_{b\in B}b=\prod_{c\in C}c$ in the
abelianization of $G$. We use this statement as a black-box to settle the
following old problems in combinatorial group theory for large groups.

  1. 1.

We characterise sequenceable groups, that is, groups which admit a permutation
$\pi$ of their elements such that the partial products $\pi_{1}$,
$\pi_{1}\pi_{2}$, $\pi_{1}\pi_{2}\cdots\pi_{n}$ are all distinct. This
resolves a problem of Gordon from 1961 and confirms conjectures made by
several authors, including Keedwell’s 1981 conjecture that all large non-
abelian groups are sequenceable. We also characterise the related
$R$-sequenceable groups, addressing a problem of Ringel from 1974.

  2. 2.

We confirm in a strong form a conjecture of Snevily from 1999 by
characterising large subsquares of multiplication tables of finite groups that
admit transversals. Previously, this characterisation was known only for
abelian groups of odd order (by a combination of papers by Alon and Dasgupta-
Károlyi-Serra-Szegedy and Arsovski).

  3. 3.

We characterise the abelian groups that can be partitioned into zero-sum sets
of specific sizes, solving a problem of Tannenbaum from 1981. This also
confirms a recent conjecture of Cichacz.

  4. 4.

We characterise harmonious groups, that is, groups with an ordering in which
the product of each consecutive pair of elements is distinct, solving a
problem of Evans from 2015.

##  1 Introduction

This paper is about finding large-scale structures in finite groups using
techniques from probabilistic combinatorics. The prototypical example of a
“large-scale structure” in a group is a complete mapping, or equivalently, a
transversal in the Latin square corresponding to the multiplication table of
the group. We now define each of these terms. A complete mapping of a group
$G$ is a bijection $\phi\colon G\to G$ such that the function $x\mapsto
x\phi(x)$ is also a bijection. A Latin array is an $n\times n$ array filled in
with arbitrary symbols such that each symbol appears at most once in each row
and column. A Latin square is an $n\times n$ Latin array with exactly $n$
symbols. A transversal of a Latin array is a collection of $n$ cells which do
not share a row, a column, or a symbol. Denote by $M(G)$ the multiplication
table of the group $G$ whose rows and columns are labelled by the elements of
the group, and the entry in row $g_{i}$ and column $g_{j}$ is the group
element $g_{i}\cdot g_{j}$. Observe that $M(G)$ is a Latin square, and that
$M(G)$ has a transversal if and only if $G$ has a complete mapping.

The study of transversals in Latin squares began more than two hundred years
ago, when Euler posed a problem equivalent to determining for which $n$ there
exists a $n\times n$ Latin square whose entries can be partitioned into
transversals. This motivates the study of transversals in multiplication
tables because if the multiplication table of a group has a transversal, then
it can be partitioned into transversals. To see this, we can translate the
columns of a transversal by a non-identity group element to produce another
transversal, entirely disjoint from the first. However, some multiplication
tables do not contain any transversals at all, let alone partitions into
transversals. Indeed, if we suppose that the multiplication table of a group
has a transversal, equivalently, we know that the group has a complete mapping
$\phi$. Denote by $\pi$ the permutation $x\mapsto x\phi(x)$, so we have that
$\pi(x)=x\phi(x)$ for every $x\in G$. Multiplying these equations111One can
fix an arbitrary ordering of $G$ for the product to be well-defined for non-
abelian groups. All the statements about products like this that we write in
the introduction are independent of the ordering picked. together for each
$x\in G$, we obtain the following.

$\prod_{x\in G}\pi(x)=\prod_{x\in G}x\phi(x)$ (1)

For abelian groups, (1) rearranges into $\prod_{x\in G}x={e}$ (where ${e}$ is
the identity element of $G$), giving a necessary condition for having a
complete mapping in abelian groups. An immediate consequence is that even-
order cyclic groups do not admit complete mappings (for example in
$G=\mathbb{Z}_{2n}$ we have $\prod_{x\in G}x=n\neq{e}$). For non-abelian
groups, (1) implies that $\prod_{x\in G}x\in G^{\prime}$, where $G^{\prime}$
denotes the commutator subgroup of $G$ (to see this note that since every
group element occurs exactly twice in $\prod_{x\in G}x\phi(x)$, we can
rearrange this product into the identity. It is a standard result that this is
equivalent to $\prod_{x\in G}x\phi(x)\in G^{\prime}$ — see Lemma 3.10). Thus
“$\prod_{x\in G}x\in G^{\prime}$” is a necessary condition for the existence
of a complete mapping in a general group. Letting $G^{\mathrm{ab}}$ denote the
abelianization of $G$, that is $G^{\mathrm{ab}}=G/G^{\prime}$, we see that
this condition is equivalent to $\prod_{x\in G}\pi_{ab}(x)$ being equal to the
identity when projected to $G^{ab}$ (where $\pi_{ab}:G\to G^{ab}$ is the
quotient homomorphism). Since $G^{ab}$ is abelian, we write this as
“$\sum_{x\in G}x=0$ in $G^{ab}$”.

The condition that $\sum_{x\in G}x=0$ in $G^{\mathrm{ab}}$ (or equivalently
that $\prod_{x\in G}x\in G^{\prime}$) is known as the Hall-Paige condition
[36]. We remark that the Hall-Paige condition is sometimes written as “all
$2$-Sylow subgroups of $G$ are trivial or non-cyclic”. This is equivalent to
$\prod_{x\in G}x$ being trivial in $G^{\mathrm{ab}}$, as shown by Hall and
Paige themselves [36]. Perhaps astonishingly, the Hall-Paige condition is not
only necessary, but also sufficient for the existence of a complete mapping.
This was first conjectured by Hall and Paige [36]. The Hall-Paige Conjecture
has a rich history, we refer the reader to the book of Evans [25] (Chapters
3-7) for a description of various approaches taken for this problem. The
conjecture was finally shown to be true in a combination of papers by Wilcox
[60], Evans [22], and Bray [13] in 2009. The original proof of Wilcox, Evans,
and Bray uses an inductive argument which relies on the classification of
finite simple groups. However, recently, a completely different proof for
large groups was found by Eberhard, Manners, and Mrazović using tools from
analytic number theory [19].

In this paper, with the goal of giving a unified approach to many related
conjectures in the area, we study complete mappings between subsets of groups.
For example, given equal sized subsets $A,B,C$ of a group $G$, is there a
bijection $\phi\colon A\to B$ such that $\psi\colon A\to C$ defined via
$\psi(a):=a\phi(a)$ is also a bijection? This corresponds to starting with the
multiplication table of a group, and then deleting the rows corresponding to
$G\setminus A$, columns corresponding to $G\setminus B$, and symbols
corresponding to $G\setminus C$, and then searching for a transversal in the
resulting structure, which is simply a Latin array with some missing entries.
Generalising the Hall-Paige condition to this set-up, we see that

$\sum A+\sum B=\sum C\text{ (in $G^{ab}$)}$ (2)

is a necessary condition for the existence of such a map $\phi$ (we use $\sum
S$ to denote $\sum_{s\in S}s$, $\prod S$ is defined analogously). Of course,
we cannot expect (2) to be a sufficient condition for any triple of equal
sized subsets222For example, consider $G=\mathbb{Z}_{99}$, $A=\\{98,1\\}$,
$B=\\{98,1\\}$, $C=\\{49,50\\}$. . However, our main theorem essentially
states that for most subsets $A,B,C\subseteq G$, (2) is the only obstruction
for finding the desired map $\phi$. Recall that a $p$-random subset $X$ of a
finite set $G$ is a subset sampled by including each element of $G$ in $X$
independently with probability $p$, and $\Delta$ denotes symmetric difference.
When we say that an event holds with high probability, we mean that the
probability of that event approaches $1$ as $n$ tends to infinity. The letter
$n$ throughout the paper always denotes the order of the ambient group $G$.

######  Theorem 1.1 (Main result).

Let $G$ be a group of order $n$. Let $p\geq n^{-1/10^{100}}$. Let
$R^{1},R^{2},R^{3}\subseteq G$ be $p$-random subsets, sampled independently.
Then, with high probability, the following holds.

Let $X,Y,Z\subseteq G$ be equal sized subsets satisfying the following
properties.

  * •

$|X\Delta R^{1}|+|Y\Delta R^{2}|+|Z\Delta R^{3}|\leq
p^{10^{10}}n/\log(n)^{10^{15}}$

  * •

$\sum X+\sum Y=\sum Z$ in $G^{\mathrm{ab}}$ (or equivalently $\prod X\prod
Y(\prod Z)^{-1}\in G^{\prime}$)

Then, there exists a bijection $\phi\colon X\to Y$ such that $x\mapsto
x\phi(x)$ is a bijection from $X$ to $Z$.

We remark that setting $p=1$ and $X=Y=Z=G$, we see that the Hall-Paige
conjecture holds for sufficiently large groups. However, Theorem 1.1 extends
far beyond the setting of the Hall-Paige conjecture. Indeed, we can settle
several longstanding conjectures at the interface of group theory and
combinatorics using the full strength of Theorem 1.1. In the following
section, we discuss several such problems. All of these problems are similar
in spirit to the Hall-Paige conjecture in the sense that they concern finding
large-scale structures in groups with certain desirable properties. However,
all of these problems lack the level of symmetry present in the Hall-Paige
problem. For example, some of these problems concern finding complete mappings
in subsets of groups with limited structure, or they concern finding complete
mappings permuting the group elements via a particular cycle type. Both of
these constraints seem difficult to reason about using only algebraic
techniques.

This perhaps explains why many of the commonly used tools, such as Alon’s
combinatorial Nullstellensatz, were only able to go so far in addressing these
questions. On the other hand, one clearly needs use some of the group
theoretic structure. Indeed, the key obstruction for problems of this type end
up being some derivative of the Hall-Paige condition, which is inherently
group theoretic. As surveyed by Gowers in [31], there are many problems in
combinatorics which are difficult for a similar reason. These are problems
where “there is too much choice for constructions to be easy to discover, and
too little choice for simple probabilistic arguments to work” [31]. Our proof,
similar in spirit to Keevash’s celebrated construction of designs [39], uses
probabilistic tools but also exploits the algebraic structure of the problem.
We give a detailed overview of our strategy in Section 2.

From now on, additive notation will always imply that the corresponding
operation is taking place in the abelianization of the ambient group (e.g.
when for $A\subseteq G$ we write “$\sum A={e}$” we mean that $\prod_{a\in
A}\pi_{ab}(a)={e}$ where $\pi_{ab}:G\to G^{ab}$ is the quotient map to the
abelianization of $G$). Otherwise, operations within non-abelian groups will
be denoted multiplicatively. The quantity $n$ always denotes the size of the
ambient group. We use ${e}$ to denote the identity element of a group, and we
sometimes use $0$ to denote ${e}$ in the special case of abelian groups.

###  1.1 Applications

As we already noted, the first application of our main result, Theorem 1.1, is
an alternative proof that the Hall-Paige conjecture holds for all sufficiently
large groups. This uses only the $p=1$ case of Theorem 1.1, where we set the
subsets $X,Y,Z$ to be the entirety of the group $G$. We now mention another
result we can recover easily, this time setting $X,Y,Z$ to be sets of size
$|G|-1$. Goddyn and Halasz recently proved that multiplication tables contain
near transversals, that is, a collection of $n-1$ cells which do not share a
row, column, or a symbol [29]. Perhaps surprisingly, there does not seem to be
an easy way of deriving this from the Hall-Paige conjecture directly, and the
proof in [29] is somewhat involved. However, we can derive this result from
Theorem 1.1 as follows.

######  Proposition 1.2.

Let $M$ be the multiplication table of a sufficiently large finite group $G$.
Then, $M$ contains a near transversal.

###### Proof.

Applying Theorem 1.1 with $p=1$, we derive that for $|G|$ large enough,
$R^{1}=R^{2}=R^{3}$ satisfies the conclusion of Theorem 1.1 with positive
probability, and therefore, with probability exactly $1$. Let $z\in G$ be some
element equal to $\sum G$ in $G^{\mathrm{ab}}$. Setting
$X=Y=G\setminus\\{{e}\\}$ and $Z=G\setminus\\{z\\}$, we have that $\sum X+\sum
Y=\sum Z$ in $G^{\mathrm{ab}}$. This implies that there is a bijection
$\phi\colon X\to Y$ such that $x\to x\phi(x)$ is injective. $\phi$ then
corresponds to a near transversal in $M$, as desired. ∎

The $p=1$ case of Theorem 1.1 when applied with other subsets $X,Y,Z$ has
novel applications as well. We discuss such an application in the next
section. The other three applications we discuss use the full strength of
Theorem 1.1. In fact, for these applications, we rely on an appropriate
generalisation of Theorem 1.1 with a more complicated distribution on the sets
$R^{1},R^{2},R^{3}$. In Section 4, we state this generalised version of
Theorem 1.1.

####  1.1.1 Snevily’s conjecture

Deleting $k$ rows and $k$ columns of a multiplication table, we obtain a
natural Latin array which we call a subsquare of the multiplication table. In
analogy with complete mappings, it is natural to ask which subsquares contain
transversals. One may suspect that deleting rows and columns should only make
it easier to find transversals, and Snevily’s conjecture states that this
indeed should be the case for abelian groups of odd order [53]. However, for
even order abelian groups $G$, one may delete rows and columns so that the
remaining Latin array is in fact the multiplication table of an even order
subgroup $H\subseteq G$ (or a translate of such a multiplication table). Such
subsquares cannot contain transversals as multiplication tables of even order
cyclic groups do no admit transversals. In 1999, Snevily conjectured that this
should be the only subtlety for cyclic even order groups. Below, we formally
state both cases of Snevily’s conjecture. Note that $A\times B$ denotes the
subsquare of a group $G$ obtained by keeping only the rows corresponding to
$A$ and columns corresponding to $B$ in the multiplication table of $G$.

######  Conjecture 1.3 (Snevily, [53]).

Let $S=A\times B$ be a subsquare of the multiplication table of an abelian
group $G$ defined by two $n$-element sets $A,B\subseteq G$.

  1. 1.

If $|G|$ is odd, then $S$ has a transversal.

  2. 2.

If $G\cong\mathbb{Z}_{2k}$ for some $k\in\mathbb{N}$, then $S$ has a
transversal unless there exists $g_{1},g_{2}\in G$ such that $g_{1}+A\cong
g_{2}+B\cong\mathbb{Z}_{2j}$ for some $j\leq k$.

The first case of the conjecture was verified by Alon in 2000 for prime order
cyclic groups [4]. In 2001, Dasgupta, Károlyi, Serra, and Szegedy generalised
Alon’s result to arbitrary odd order cyclic groups [18]. Both of these results
use the celebrated Combinatorial Nullstellensatz [3]. A decade later, Arsovski
fully resolved the first case of Snevily’s conjecture, using character theory
[7]. On the other hand, as far as the authors are aware, no partial progress
has been reported on the second case of the conjecture.

As observed by Wanless [59], the second part of Snevily’s conjecture does not
generalise straightforwardly to all even abelian groups due to the following
construction of Akbari and Alireza [2]. Let $G=(\mathbb{Z}_{2})^{k}$ for some
$k\geq 1$, and let $a_{1},a_{2}\in G$ be distinct and let $b_{1},b_{2}\in G$
be distinct such that $a_{1}+a_{2}+b_{1}+b_{2}=0$. Then, setting
$A=G\setminus\\{a_{1},a_{2}\\}$, $B=G\setminus\\{b_{1},b_{2}\\}$, it is a
simple exercise to check that the subsquare $A\times B$ does not contain a
transversal. We show, perhaps surprisingly, that this is the only other
barrier for an abelian subsquare to contain a transversal.

######  Theorem 1.4.

There exists an $n_{0}\in\mathbb{N}$ such that the following holds for all
$n\geq n_{0}$. Let $G$ be an abelian group, and let $A,B\subseteq G$ with
$|A|=|B|=n$. Then, $A\times B$ has a transversal, unless there exists some
$k\geq 1$, $g_{1},g_{2}\in G$ and a subgroup $H\subseteq G$ such that one of
the following holds.

  1. 1.

$H\cong\mathbb{Z}_{2k}\times H_{odd}$ for some odd size group $H_{odd}$, and
$H\cong g_{1}A\cong g_{2}B$

  2. 2.

$H\cong(\mathbb{Z}_{2})^{k}$, $g_{1}A\cong H\setminus\\{a_{1},a_{2}\\}$,
$g_{2}B\cong H\setminus\\{b_{1},b_{2}\\}$ for some distinct $a_{1},a_{2}\in H$
and distinct $b_{1},b_{2}\in H$ such that $a_{1}+a_{2}+b_{1}+b_{2}=0$.

Note that this confirms both cases of Snevily’s conjecture for sufficiently
large subsquares. Note that $(\mathbb{Z}_{2})^{k}$ contains translates of
$\mathbb{Z}_{2}$, meaning that
$(\mathbb{Z}_{2})^{k}\times(\mathbb{Z}_{2})^{k}$ contains subsquares of order
$2$ without transversals. However, this does not come up in the statement of
Theorem 1.4 as we are only concerned with large subsquares. We discuss proving
a stronger characterisation valid for all $n$ in Section 7.

We take Snevily’s conjecture further by proving a far more general theorem
characterising subsquares without transversals of all groups.

######  Theorem 1.5.

There exists an $n_{0}\in\mathbb{N}$ such that the following holds for all
$n\geq n_{0}$. Let $G$ be a group, and let $A,B\subseteq G$ with $|A|=|B|=n$.
Then, $A\times B$ has a transversal, unless there exists some $k\geq 1$,
$g_{1},g_{2}\in G$ and a subgroup $H\subseteq G$ such that one of the
following holds.

  1. 1.

$H$ is a group that does not satisfy the Hall-Paige condition, and $A\cong
g_{1}H$ and $B\cong Hg_{2}$.

  2. 2.

$H\cong(\mathbb{Z}_{2})^{k}$, $g_{1}A\cong H\setminus\\{a_{1},a_{2}\\}$,
$g_{2}B\cong H\setminus\\{b_{1},b_{2}\\}$ for some distinct $a_{1},a_{2}\in H$
and distinct $b_{1},b_{2}\in H$ such that $a_{1}+a_{2}+b_{1}+b_{2}=0$.

Roughly speaking, Theorem 1.5 states that deleting rows and columns from a
multiplication table only makes it easier to find transversals (supposing we
do not end up with a translate of a multiplication table of a subgroup),
except for a very specific scenario where we delete $2$ rows and $2$ columns
summing to zero from the multiplication table of an elementary abelian
$2$-group. Theorem 1.5 is proved in Section 6.1.

####  1.1.2 Sequenceable and R-sequenceable groups

Given a finite group $G$, a sequencing is an ordering of the elements of $G$
as $b_{1},b_{2},\ldots,b_{n}$ where the partial products $b_{1}$,
$b_{1}b_{2}$, $b_{1}b_{2}\cdots b_{n}$ are all distinct. A group that admits a
sequencing is called sequenceable. A similar notion is that of an
R-sequencing. An R-sequencing is an ordering of the elements of $G$ as
$e,b_{1},b_{2},\ldots,b_{n-1}$ where the partial products $b_{1}$,
$b_{1}b_{2}$, $b_{1}b_{2}\cdots b_{n-1}$ are all distinct and
$b_{1}b_{2}\cdots b_{n-1}b_{n}=e$. A group that admits an R-sequencing is
called R-sequenceable. We will briefly discuss the rich history of the
problems relating to these concepts, and we refer the reader to [47] and [25]
for a more comprehensive survey.

Gordon introduced the problem of determining which groups are sequenceable in
1961 [30]. His motivation was to construct complete Latin squares, a concept
which we now define. A Latin square is called row-complete if every pair of
distinct symbols appears exactly once in each order in adjacent horizontal
cells. A Latin square is called column-complete if it has the same property
with respect to adjacent vertical cells. A Latin square is complete if it is
both row-complete and column-complete. Complete Latin squares possess an
additional layer of symmetry, making them useful in various contexts. For
example, complete Latin squares are useful in graph theory to give
decompositions of complete directed graphs into Hamilton paths (see [47] and
the references therein). Also, some applications to experimental design are
given in [9]. Gordon was motivated by the observation that given a
sequenceable group $G$, we can construct a complete Latin square by
considering the multiplication table of the group $G$.

Ringel had a completely different motivation for studying $R$-sequenceable
groups. Such groups come up naturally in Ringel’s celebrated proof of the
Heawood map colouring conjecture [49]. Hence, Ringel asked for a
classification of all such groups [48].

In Section 6.2, we solve both of these problems for large groups. This
addresses problems reiterated by several authors [25, 47], and confirms a
conjecture of Keedwell [38] (see also Conjecture 7 in [29]). In particular, we
show that any large group with the Hall-Paige condition is R-sequenceable. We
also show that any large non-abelian group is sequenceable. Perhaps
surprisingly, this latter statement does not hold for all non-abelian groups.
In fact, any non-abelian group of order at most $9$ is not sequenceable [30].
Therefore, at least for this problem, some mild assumption on the size of the
group is necessary for a clean characterisation. We also remark that several
partial results towards this characterisation were obtained by other
researchers, see [47] for a survey.

####  1.1.3 Partitioning abelian groups into zero-sum sets

We call a subset $S$ of a group zero-sum if $\sum S=0$. Given a sequence
$a_{1},a_{2},\ldots,a_{k}$ ($a_{i}\geq 2$) with $\sum a_{i}=n-1$, where
$n=|G|$, when can we partition the non-identity elements of an abelian group
into zero-sum sets of size $a_{1},a_{2},\ldots,a_{k}$? A variant of this
natural problem seems to have been first considered in 1957 by Skolem [52],
and in 1960 by Hanani [37]. A complete solution for cyclic groups for
sequences $a_{1},a_{2},\ldots,a_{k}$ with $a_{i}\geq 3$ was given by
Friedlander, Gordon, and Tannenbaum in 1981 [27].

A moment’s reflection reveals that for the necessary partition to exist, we
need that $\sum G=0$. This already rules out even-order cyclic groups, for
example. There is another very natural necessary condition. Let $\ell$ denote
the number of $a_{i}$ such that $a_{i}=2$. We need that $G$ should contain at
least $(n-1-\ell)$-many pairs $\\{x,-x\\}$ where $x\neq-x$ (i.e. $\ell$-many
order $2$ elements). It turns out that for odd order abelian groups, these two
conditions are known to be sufficient as well as necessary [54, 61]. However,
for even order abelian groups, Tannenbaum observed that additional necessary
conditions are required [55]. To see this, we invite the reader to consider
the case when $G=\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, and
the sequence $a_{1},a_{2},\ldots,a_{k}$ is $(2,2,2,3,3,3)$. See [55] for a
solution to why $G$ does not have the desired partition in this case.

Motivated by the previous example, Tannenbaum asked to find a set of necessary
and sufficient conditions guaranteeing a partition of an even order abelian
group into zero-sum sets of prescribed sizes [55]. Despite the apparent lack
of structure in the problem as evidenced by a rich family of counterexamples,
in Section 6.3, we give a complete characterisation of the (large) abelian
groups and integer sequences for which the desired partition exists. Various
special cases of this problem were investigated by several authors, for
example see [16] and all the references therein. In particular, our
characterisation confirms the following conjecture of Cichacz [15].

######  Conjecture 1.6 (Cichacz, [15]).

Let $G$ be an abelian group with at least $3$ involutions and suppose we have
numbers $r_{1},\dots,r_{t}\geq 3$ with $r_{1}+\dots+r_{t}=|G|-1$. Then there
is a partition of $G\setminus{e}=Z_{1}\cup\dots\cup Z_{t}$ where each $Z_{i}$
is a zero-sum set of size $r_{i}$.

####  1.1.4 Harmonious groups

Given a group $G$, not necessarily abelian, a harmonious ordering is an
ordering of the elements of $G$ as $a_{1},a_{2},\ldots,a_{n}$ such that
$a_{1}a_{2},a_{2}a_{3},\ldots,a_{n-1}a_{n},a_{n}a_{1}$ is also an ordering of
the elements of $G$ (i.e. the latter sequence contains no repetitions). Groups
which have harmonious orderings are called harmonious. Harmonious groups were
first introduced in 1991 by Beals, Gallian, Headley, and Jungreis [10]. They
gave a characterisation of all abelian harmonious groups. Evans asked for a
complete characterisation.

######  Problem 1.7 (Evans, [23]).

Which finite groups are harmonious?

In Section 6.2, we give a characterisation of all sufficiently large
harmonious groups. It turns out that a (large) group is harmonious if and only
if it satisfies the Hall-Paige condition, and is not an elementary abelian
$2$-group.

###  1.2 Organisation of the paper

In Section 2, we give a extensive proof sketch. Section 3 collects some
standard concentration/nibble type results, makes precise some key definitions
and notation, and records some group theoretic results we rely on. Section 3.6
in particular is quite central, and is devoted to giving a sufficient set of
conditions allowing us to find various gadgets throughout the paper. In
Section 4, we state a more general version of Theorem 1.1, and we derive
several variants including Theorem 1.1 itself. In Section 5 the generalised
version of the main theorem is proved. Section 6 is devoted to deriving the
applications we have listed in Section 1.1. In Section 7, we discuss further
avenues of research.

##  2 Proof strategy for the main result

In this section, we attempt to give an accessible outline of a special case of
our main result, concerning cyclic groups. We conclude in Section 2.1.4 by
outlining some key difficulties we omit in the simplified discussion.

Firstly, instead of using the language of complete mappings, we will re-frame
Theorem 1.1 as a hypergraph matching problem. Given a group $G$, we define the
$3$-uniform $3$-partite multiplication hypergraph $H_{G}$ as follows. Set
$V(H_{G}):=G_{A}\sqcup G_{B}\sqcup G_{C}$ where $G_{*}$ is a copy of $G$ and
$\sqcup$ indicates a disjoint union. Set $E(G):=\\{(g_{A},h_{B},k_{C})\in
G_{A}\times G_{B}\times G_{C}\colon g_{A}h_{B}k_{C}={e}\\}$. Given
$X,Y,Z\subseteq G$, we denote by $H_{G}[X,Y,Z]$ the induced subgraph of
$H_{G}$ given by the vertex subset $(G_{A}\cap X)\sqcup(G_{B}\cap
Y)\sqcup(G_{C}\cap Z)$. Given equal sized subsets $X,Y,Z$, observe that
finding a bijection $\phi\colon X\to Y$ such that $x\mapsto x\phi(x)$ is a
bijection from $X$ to $Z$ is equivalent to finding a perfect matching in
$H_{G}[X,Y,Z^{-1}]$ where $Z^{-1}=\\{z^{-1}\colon z\in Z\\}$. We will outline
a proof for the following result. For the rest of the outline, fix
$\varepsilon=1/100$.

######  Proposition 2.1.

Let $X,Y,Z\subseteq\mathbb{Z}_{n}$ such that
$|X|=|Y|=|Z|=n-O(n^{1-\varepsilon})$, and $\sum X+\sum Y+\sum Z=0$. Then,
$H_{\mathbb{Z}_{n}}[X,Y,Z]$ has a perfect matching.

Proposition 2.1 is already novel, and would be sufficient, for example, to
deduce Snevily’s conjecture for large subsquares. We remark that Proposition
2.1 is a simple corollary of Theorem 1.1 which can be obtained by setting
$p=1$. We remark that throughout the rest of the paper, when we say that a
subset $S\subseteq G$ is zero-sum, we mean that the product of all elements of
$S$ (in any order) is in $G^{\prime}$, the commutator subgroup. For abelian
groups, this corresponds to $\sum S=0$.

###  2.1 Absorption

Our main tool is the absorption method, a technique codified by Rödl,
Ruciński, Szemerédi [50] (see also the earlier work of Erdős, Gyárfás, and
Pyber [21]), adapted to the setting of hypergraphs defined by groups.
Absorption is a general method that reduces the task of finding spanning
structures to finding almost spanning structures. In most cases, the latter
task is considerably simpler, as evidenced by the celebrated nibble method
which roughly states that pseudorandom hypergraphs contain large matchings
[5]. The main technical innovation in our paper is developing an absorption
strategy for multiplication hypergraphs, which in the setting of Proposition
2.1, culminates in the following lemma.

######  Lemma 2.2 (Simpler version of Lemma 5.32).

$H_{\mathbb{Z}_{n}}[X,Y,Z]$ contains a vertex subset $\mathcal{A}$ of size
$o(n)$ such that for any $S\subseteq
V(H_{\mathbb{Z}_{n}}[X,Y,Z])\setminus\mathcal{A}$ of size
$O(n^{1-\varepsilon})$ intersecting $X$, $Y$ and $Z$ in the same number of
vertices, and satisfying $\sum S=0$, $\mathcal{A}\cup S$ has a perfect
matching.

In Lemma 2.2, $\mathcal{A}$ functions as our absorber, in the sense that it
can absorb small enough subsets by formingperfect matchings when combined with
them. The key premise of the absorption method is that once a suitable
absorber is found and set aside, the only remaining task is to find an almost
perfect matching in the leftover set. Indeed, $\mathcal{A}$ can absorb
whatever small subset $S$ we fail to cover with the almost perfect matching.

We now explain in a bit more detail how Lemma 2.2 reduces the task of proving
Proposition 2.1 to finding a matching of size $n-O(n^{1-\varepsilon})$ in
$V(H_{\mathbb{Z}_{n}}[X,Y,Z])\setminus\mathcal{A}$. First, note that setting
$S=\emptyset$ in Lemma 2.2 implies that $\mathcal{A}$ has a perfect matching,
and thus $\sum\mathcal{A}=0$ (if a subset contains a perfect matching, by
definition the subset can be partitioned into zero-sum sets, and hence is
zero-sum itself). Now, suppose that having fixed the set $\mathcal{A}$, we
were able to find a matching $M_{1}$ in
$V(H_{\mathbb{Z}_{n}}[X,Y,Z])\setminus\mathcal{A}$ covering all but
$O(n^{1-\varepsilon})$ vertices. Let $S$ denote the set of these leftover
vertices. As $\mathcal{A}$ and $V(M)$ are disjoint zero-sum sets contained in
$V(H_{\mathbb{Z}_{n}}[X,Y,Z])$, and $\sum X+\sum Y+\sum Z=0$ by assumption, we
have that $\sum S=0$ as well. So by the property in Lemma 2.2,
$\mathcal{A}\cup S$ spans another perfect matching, $M_{2}$ say. Then,
$M_{1}\cup M_{2}$ is the desired perfect matching of
$H_{\mathbb{Z}_{n}}[X,Y,Z]$.

We remark that, in reality, deleting $\mathcal{A}$ from
$H_{\mathbb{Z}_{n}}[X,Y,Z]$ would damage the pseudorandomness properties of
the hypergraph too greatly to be able to find the desired $M_{1}$ using the
Rödl nibble [5]. Therefore, here we actually need a slightly stronger version
of Lemma 2.2 which can find $\mathcal{A}$ inside small random sets. This way,
deleting $\mathcal{A}$ only spoils the pseudorandomness of a set $R$ much
smaller than the multiplication hypergraph itself. $R\setminus\mathcal{A}$ can
then be dealt with using standard pseudorandomness arguments, see for example
Lemma 3.8.

For Lemma 2.2 to hold, we remark that some condition on the value of $\sum S$
is necessary. Indeed, recall that if a subset admits a perfect matching, it
has to be zero-sum. So, if $S_{1}$ and $S_{2}$ are two sets disjoint with
$\mathcal{A}$ such that $\mathcal{A}\cup S_{1}$ and $\mathcal{A}\cup S_{2}$
both admit perfect matchings, it follows that

$0=\sum\mathcal{A}\cup S_{1}=\sum\mathcal{A}\cup S_{2}$

hence $\sum S_{1}=\sum S_{2}$. Therefore, the set $\mathcal{A}$ can have the
flexibility of combining with any member of a large family of sets
$\mathcal{F}$ to produce perfect matchings only if $\sum S$ is fixed for all
$S\in\mathcal{F}$. For convenience, we fix this sum to be $0$, but Lemma 2.2
would remain true if we replaced $0$ with any other fixed element.

####  2.1.1 Building the absorber from small subgraphs

Our starting point for building the absorber set $\mathcal{A}$, similar in
spirit to most applications of the absorption method, is the existence of
small subgraphs (gadgets) which give local variability. More precisely, we
will rely on the existence of $O(1)$-sized gadgets, $Q$ say, that can combine
with $O(1)$ distinct sets, $F_{1}$ and $F_{2}$ say, each of size $O(1)$, such
that $Q\cup F_{1}$ and $Q\cup F_{2}$ both induce perfect matchings in
$H_{\mathbb{Z}_{n}}[X,Y,Z]$. We say that $Q$ can switch between $F_{1}$ and
$F_{2}$.

The power of the absorption method rests in the fact that small gadgets such
as $Q$ displaying rather limited variability can be combined in a way to build
an absorber displaying global variability. By global variability, we mean the
type of property that $\mathcal{A}$ has in the statement of Lemma 2.2. In
particular, we are referring to how $\mathcal{A}$ can combine with essentially
any subset of size $O(n^{1-\varepsilon})$, as opposed to just a few of size
$O(1)$. To achieve this in our case, we will use a variant of the absorption
technique called distributive absorption, initially developed by Montgomery
[44]. The method has since been applied in numerous settings, notably in the
proof of Ringel’s conjecture by Montgomery, Pokrovskiy, and Sudakov [46]. For
a detailed discussion of how gadgets such as $Q$ can be combined to build an
absorber, we refer the reader to the discussion in [46].

For readers who are familiar with the absorption method, we add a quick remark
that common-place methods of building absorbers, such as those used in [50],
do not work in our context for the following simple reason. Say we have a
subset $S$ and we are interested in subsets $A$ of size $k$ such that both $A$
and $A\cup S$ span a perfect matching. In the usual absorption strategy, we
would require that the number of subsets $A$ with this property is
$\Omega(n^{k})$. However, if $A$ spans a perfect matching, then $\sum A=0$.
The number of zero-sum subsets $A$ of order $k$ is $O(n^{k-1})$ – too little
to appear in abundance when a positive fraction of $k$-subsets are randomly
sampled. On the other hand, with the distributive absorption strategy, one may
build absorbers with fewer gadgets, provided that one can show that the
gadgets are well-distributed within the host structure.

####  2.1.2 Absorption for pairs

Typically, in applications of the distributive absorption method, one works
with gadgets $Q$ switching between $F_{1}$ and $F_{2}$ where $F_{1}$ and
$F_{2}$ are both singletons. This would be impossible to implement in our
context as if $Q\cup F_{1}$ and $Q\cup F_{2}$ both contain perfect matchings,
then $\sum F_{1}=\sum F_{2}$. Thus, if $F_{1}$ and $F_{2}$ were singletons,
$F_{1}$ and $F_{2}$ would consist of the exact same vertex. Hence, if we want
$Q$ to be a gadget that actually gives us some flexibility, we can only hope
to switch between sets of size at least $2$. This motivates us to search for
disjoint sets $Q$, $F_{1}$ and $F_{2}$ such that $Q\cup F_{1}$ and $Q\cup
F_{2}$ both span perfect matchings, $|F_{1}|=|F_{2}|=2$, and $\sum F_{1}=\sum
F_{2}=0$, where the final equality is chosen for convenience as in the
statement of Lemma 2.2.

Finding $Q$ with this property turns out to be rather easy. For example, fix
disjoint sets $F_{1}:=\\{a,-a\\}$ and $F_{2}:=\\{b,-b\\}$ where neither $a$
nor $b$ is an involution. Let us view $F_{1}$ and $F_{2}$ as subsets of
$G_{C}$. Consider some $x\in G_{A}$. Set $y:=-x-a\in G_{B}$, set $z=x+a-b\in
G_{A}$ and $w=-x+b$. Suppose that $x\neq z$ and $y\neq w$. Observe that
$M_{1}=\\{(x,-x-a,a),(x+a-b,-x+b,-a)\\}$ is a matching of $\\{x,y,z,w\\}\cup
F_{1}$ and $M_{2}=\\{(x,-x+b,-b),(x+a-b,-x-a,b)\\}$ is a matching of
$\\{x,y,z,w\\}\cup F_{2}$. Hence, $Q_{x}:=\\{x,y,z,w\\}$ is a gadget with the
desirable property of switching between $F_{1}$ and $F_{2}$. See Figure 1 for
an illustration. Moreover, it is not hard to see that there are many choices
of $x$ for which the corresponding sets $Q_{x}$ are all disjoint, which is
critical for the distributive absorption strategy.

Figure 1: The gadget $Q_{x}$. Matchings $M_{1}$ and $M_{2}$ depicted in solid
and dashed lines, respectively.

Building on the idea detailed in the previous paragraph, we can show that
there exists gadgets like $Q_{x}$ which can combine with any one of $100$ (as
opposed to just $2$) pairs of inverses to produce a matching. This, combined
with the usual distributive absorption strategy, is already sufficient to
prove a version of Lemma 2.2 with additional hypotheses on the set $S$.
Namely, one can show the following.

######  Lemma 2.3 (Simpler version of Lemma 5.29).

Let $S_{1}$ be a $o(n)$-sized vertex subset of $H_{\mathbb{Z}_{n}}[X,Y,Z]$.
Then, $H_{\mathbb{Z}_{n}}[X,Y,Z]$ contains a vertex subset
$\mathcal{A}^{\prime}$ of size $o(n)$ such that for any $S_{2}\subseteq S_{1}$
of size $O(n^{1-\varepsilon})$ intersecting $X$, $Y$ and $Z$ in the same
number of vertices, closed under the function $x\to-x$, and containing no
involutions, we have that $\mathcal{A}^{\prime}\cup(S_{1}\setminus S_{2})$ has
a perfect matching.

In the above lemma, it would arguably be more natural to insist that
$\mathcal{A}^{\prime}\cup S_{2}$ has a perfect matching, as opposed to
$\mathcal{A}^{\prime}\cup(S_{1}\setminus S_{2})$. Such a version of the lemma
would also be correct, and be even easier to prove. We formulate the lemma in
the form above for a reason that will become clear shortly.

####  2.1.3 From absorption for pairs to absorption for arbitrary zero-sum
sets

Now, we discuss how we can derive Lemma 2.2 from Lemma 2.3. The key idea is
encapsulated in the following lemma.

######  Lemma 2.4 (Simpler version of Lemma 5.31).

$H_{\mathbb{Z}_{n}}[X,Y,Z]$ contains a vertex subset $\mathcal{T}$ of size
$o(n)$ such that for any $S\subseteq
V(H_{\mathbb{Z}_{n}}[X,Y,Z])\setminus\mathcal{T}$ of size
$O(n^{1-\varepsilon})$ intersecting $X$, $Y$ and $Z$ in the same number of
vertices, and satisfying $\sum S=0$, there exists a matching $M$ of order
$O(n^{1-\varepsilon})$ with $\mathcal{T}\cup S\supseteq V(M)\supseteq S$
satisfying also that $V(M)\setminus S$ is closed under $x\to-x$.

Deriving Lemma 2.2 from Lemma 2.3 and Lemma 2.4 is a simple exercise. Indeed,
let $\mathcal{T}$ be a vertex subset of $H_{\mathbb{Z}_{n}}[X,Y,Z])$ with the
property in Lemma 2.4. Apply Lemma 2.3 with $S_{1}=\mathcal{T}$ to obtain a
vertex subset $\mathcal{A}^{\prime}$. Set
$\mathcal{A}:=\mathcal{A}^{\prime}\cup\mathcal{T}$. We invite the reader to
check that $\mathcal{A}$ then satisfies the property that Lemma 2.2 requires.

To see how we prove a version of Lemma 2.4, we invite the reader to see
Section 5.3.1. Similar in spirit to the proof of Lemma 2.3, our main trick
here is to reduce (a version of) Lemma 2.4 to the existence of many small
matchings with certain desirable properties (see Lemma 5.30).

####  2.1.4 Additional difficulties

We now point out several complications we omitted in the previous discussion,
along with some technicalities that arise in the level of generality of our
main theorem.

Ensuring distinctness. A fair portion of our arguments rely on the existence
of constant sized matchings with specific properties, such as being closed
under the map $x\to-x$. Often, the properties we require can be written as
solutions to a particular system of linear equations. For example, consider
$Q_{x}$ defined in Section 2.1.2. The requirements from $\\{x,y,z,w\\}$ could
be written as:

$x+y+a=0\hskip 28.45274ptz+w-a=0\hskip 28.45274ptx+w+b=0\hskip
28.45274ptz+y-b=0$

This is a system of equations with $4$ variables and $4$ constraints; however,
any $3$ of these equations imply the fourth, allowing us to easily deduce that
there are many $x,y,z,w$ with the desired properties. However, a solution to
the system of equations is useful to us only when $x\neq z$ and $y\neq w$, as
otherwise $\\{(x,-x+b,-b),(x+a-b,-x-a,b)\\}$ would not be a matching in
$H_{\mathbb{Z}_{n}}$.

In the specific scenario outlined above, getting the relevant coordinates to
be distinct is not particularly challenging. However, throughout the paper, we
will require gadgets with properties significantly more complicated than those
of $Q_{x}$. Furthermore, our main theorem works with subsets $X,Y,Z\subseteq
G$ which are disjoint. Thus, we would have no chance of locating $Q_{x}$
within $H_{G}[X,Y,Z]$ unless all coordinates $x,y,z,w$ are distinct. Due to
these technicalities, finding gadgets with the desired properties can become
quite delicate.

Section 3.6 is entirely devoted to obtaining a sufficient set of conditions
for a system of relations to yield solutions where each coordinate is
distinct. The key result of that section, Lemma 3.32, is used in abundance
throughout the paper.

The elementary abelian $2$-group. The strategy of working with pairs of
inverses $\\{x,-x\\}$ which are not involutions fails for obvious reasons in
the elementary abelian $2$-group. This turns out to be not a serious
complication, as for general groups $G$, we will work with pairs
$\\{x,q_{\phi}x^{-1}\\}$ for a carefully chosen $q_{\phi}$ so that $x\to
q_{\phi}x^{-1}$ does not create too many fixed points.

Nonabelian groups. Although it turns out that the case of general abelian
groups is not significantly more complicated than cyclic groups, there are
serious issues to overcome with nonabelian groups. As just one example,
suppose that we wish to find a gadget similar to $Q_{x}$ from Section 2.1.2 in
$H_{G}$, where $G$ is a non-abelian group. Suppose that
$F_{1}=\\{a,q_{\phi}a^{-1}\\}$, $F_{2}=\\{b,q_{\phi}b^{-1}\\}$. Our goal is
then to find (many) $Q$ such that $Q\cup F_{1}$ and $Q\cup F_{2}$ both can be
perfectly matched. It is quite instructive to try to construct such $Q$, and
we invite the reader to try to do so.

Some reflection shows that while it is difficult to construct $Q$ switching
between $\\{a,q_{\phi}a^{-1}\\}$ and $\\{b,q_{\phi}b^{-1}\\}$, it is
considerably simpler to find some $b^{\prime}$ such that $b^{\prime}$ is in
the same $G^{\prime}$-coset as $q_{\phi}b^{-1}$ such that we can find a $Q$
switching between $\\{a,q_{\phi}a^{-1}\\}$ and $\\{b,b^{\prime}\\}$. This
motivates us to search for gadgets not only switching between pairs, but also
switching between elements of the same $G^{\prime}$-coset. Achieving this
latter task is considerably more technical. We accomplish this by first
devising a strategy for switching between commutator elements (as opposed to
arbitrary elements in the commutator subgroup). To switch between arbitrary
elements of $G^{\prime}$, we have to rely on a non-trivial fact from
representation theory (see Theorem 5.11). The statement we require is that
arbitrary elements in the commutator subgroup can be written as products of
just $O(\log n)$ commutators. Arguably, this is the only point in the proof of
the main theorem where we use a group theoretic result beyond the
undergraduate level. Due to bounds coming from Theorem 5.11 (which are tight),
we are obliged to use gadgets of logarithmic size to switch between elements
of the same $G^{\prime}$-coset. This inflates the error rate in our main
theorem by a polylogarithmic factor. We refer the reader to Section 5.1 for
more details.

##  3 Preliminaries

###  3.1 Probabilistic tools

####  3.1.1 Concentration inequalities

The below is a standard bound that can be found in many probability textbooks,
for example see [5]. We will refer to it as Chernoff’s bound.

######  Lemma 3.1 (Chernoff bound).

Let $X:=\sum_{i=1}^{m}X_{i}$ where $(X_{i})_{i\in[m]}$ is a sequence of
independent indicator random variables with $\mathbb{P}(X_{i}=1)=p_{i}$. Let
$\mathbb{E}[X]=\mu$. Then, for any $0<\gamma<1$, we have that
$\mathbb{P}(|X-\mu|\geq\gamma\mu)\leq 2e^{-\mu\gamma^{2}/3}$.

We use the following corollary of Chernoff’s bound often: that if $R$ is a
$p$-random subset of an $n$-element set, then with high probability we have
that $|pn-|R||\leq\log n\sqrt{n}$.

In almost all instances, the Chernoff bound will be all we need. Otherwise, we
will make use of Azuma’s inequality, which we now state. Given a product
probability space $\Omega=\prod_{i\in[n]}\Omega_{i}$, a random variable
$X\colon\Omega\to\mathbb{R}$ is called $C$-Lipschitz if
$|X(\omega)-X(\omega^{\prime})|\leq C$ whenever $\omega$ and $\omega^{\prime}$
differ in at most $1$-coordinate. We will refer to the following standard
bound as Azuma’s inequality.

######  Lemma 3.2 (Azuma’s inequality).

Let $X$ be $C$-Lipschitz random variable on a product probability space with
$n$ coordinates. Then, for any $t>0$,

$\mathbb{P}(|X-\mathbb{E}(X)|>t)\leq 2e^{\frac{-t^{2}}{nC^{2}}}.$

####  3.1.2 Pseudorandom graphs and the Rödl nibble

Here, we give some tools to find matchings in pseudorandom hypergraphs
covering all but a few vertices. Our approach here is complicated by the fact
that we need to find large matchings in subsets of hypergraphs, and parts of
the subsets we consider might have their elements adversarially chosen. This
comes from the first step of the proof where we set aside an absorber, whose
complement could potentially have poor pseudorandomness properties. The most
important result from this section is Lemma 3.8, which tells us that subsets
of multiplication tables contain large matchings whenever the subset is
obtained by taking unions of two random sets, and one (potentially
adversarially chosen) deterministic set. We now give the details.

For a hypergraph $H$, vertices $u,v$ and a subset $U\subseteq V(H)$, we define
the pair degree of $(u,v)$ into $U$ as the number of vertices in $U$ which are
in the neighbourhood of both $u$ and $v$, i.e. the number of vertices $z$ in
$U$ such that there exists $v,w\in V(H)$ such that $\\{u,z,v\\}$ and
$\\{v,z,w\\}$ are both edges of $H$. We say that a $r$-partite $r$-uniform
hypergraph $H$ is $(\gamma,p,n)$-regular if every part has $(1\pm\gamma)n$
vertices and every vertex has degree $(1\pm\gamma)pn$. We say that $H$ is
$(\gamma,p,n)$-typical if, additionally, every pair of vertices $x,y$ in the
same part of $H$ have pair degree $(1\pm\gamma)p^{2}n$ into every other part
of $H$. We say that a hypergraph is linear if through every pair of vertices,
there is at most one edge. Multiplication hypergraphs have all these
properties.

######  Observation 3.3.

For a group $G$ of order $n$, the multiplication hypergraph $H_{G}$ is
$(0,1,n)$-typical and linear.

###### Proof.

It is immediate that all parts have size $n$. For any two vertices $u,v$ in
different parts, there is a unique edge through $u$ and $v$ (if $u\in A,v\in
B$, then this edge is $(u,v,v^{-1}u^{-1})$. If $u\in B,v\in C$, then this edge
is $(v^{-1}u^{-1},u,v)$. If $u\in A,v\in C$, then this edge is
$(u,u^{-1}v^{-1},v)$), hence $H_{G}$ is linear. This shows that all vertices
have degree exactly $n$ and pair degree exactly $n$ to each part i.e. that the
hypergraph is $(0,1,n)$-typical. ∎

Frankl and Rödl [26] (also Pippenger, unpublished) showed that for all
$\epsilon,p\gg\gamma\gg n^{-1}$ every $(\gamma,p,n)$-regular hypergraph has a
matching of size $(1-\epsilon)n$. We need a well known variant of this where
$\epsilon,p,\gamma$ have polynomial dependencies on $n$.

######  Lemma 3.4.

Let $n$ be sufficiently large. Every $(\gamma,\delta,n)$-regular linear
tripartite hypergraph has a matching covering all but at most
$n^{1-1/500}+3\gamma n$ vertices.

###### Proof.

There are various ways of proving this. We will deduce it from a result of
Molloy-Reed — Theorem 1 from [43]. Applying that theorem with $k=3$,
$\Delta=(1+\gamma)\delta n$ gives us a decomposition of our
$(\gamma,\delta,n)$-regular hypergraph into
$\Delta+c_{k}\Delta^{1-\frac{1}{k}}\log^{4}\Delta\leq\delta n+\gamma\delta
n+n^{6/7}$ matchings (for some constant $c_{k}$). By the pigeonhole principle
one of these has at least $\frac{e(H)}{\delta n+\gamma\delta
n+n^{6/7}}\geq\frac{(1-\gamma)^{2}\delta n^{2}/3}{\delta n+\gamma\delta
n+n^{6/7}}\geq n/3-(n^{1-1/500}+3\gamma n)$ edges as required. ∎

Typical graphs have the following well-known pseudorandomness condition, which
dates back to work of Thomason [57]. Note that for the rest of the section, we
assume that bipartite graphs come with a partition of their vertex set as
$(A,B)$ and similarly tripartite hypergraphs come with a partition $(A,B,C)$.

######  Lemma 3.5.

Let $G$ be a $(\gamma,\delta,n)$-typical bipartite graph. Then for every
$A^{\prime}\subseteq A,B^{\prime}\subseteq B$, we have
$e(A^{\prime},B^{\prime})=\delta|A^{\prime}||B^{\prime}|\pm
5\sqrt{(\delta+\gamma)n^{3}}+\gamma n^{2}$.

###### Proof.

This will be a consequence of Theorem 2 of [57]. First, delete at most $\gamma
n$ vertices from one side of the graph to obtain a balanced bipartite graph.
Now with parameters $p:=\delta-\gamma$ and $\mu:=5\gamma n$ it is easy to see
that the hypothesis of Theorem 2 are satisfied. From the conclusion of Theorem
2, for every $A^{\prime}\subseteq A,B^{\prime}\subseteq B$, we have
$e(A^{\prime},B^{\prime})=p|A^{\prime}||B^{\prime}|\pm
5\sqrt{(\delta+\gamma)n^{3}}$. With another $\gamma n^{2}$ term, we can
account for the deleted vertices in the beginning, implying the desired bound.
∎

Typicality is preserved by taking random subsets, in the following sense.

######  Lemma 3.6.

Let $H=(A,B,C)$ be a tripartite linear hypergraph that is $(0,1,n)$-typical.
Let $p\geq n^{-1/600}$ and let $A^{\prime}\subseteq A$ be $p$-random. Then,
with probability at least $1-1/n^{3}$, the bipartite graph between $B$ and $C$
consisting of edges passing through $A^{\prime}$ is $(n^{-1/5},p,n)$-typical.

###### Proof.

For some $c,c^{\prime}\in C$, let $d_{A^{\prime}}(c)=e(A^{\prime},B,c)$ be the
degree of $c$ into $A^{\prime}$ and let $d_{A^{\prime}}(c,c^{\prime})$ denote
the pair degree of $(c,c^{\prime})$ into $A^{\prime}$. We have
$d_{A}(c)=d_{A}(c,c^{\prime})=n$ (by $(0,1,n)$-typicality of $H$).

Note that $\mathbb{E}(d_{A^{\prime}}(c))=pd_{A}(c)=pn$ and
$\mathbb{E}(d_{A^{\prime}}(c,c^{\prime}))=p^{2}d_{A}(c,c^{\prime})=p^{2}n$
(using linearity of $H$) for all $c,c^{\prime}$. Set $\gamma:=n^{-1/5}$. By
Chernoff’s bound and a union bound, with probability at least $1-1/n^{4}$, for
all $c$ we have $d_{A^{\prime}}(c)=\mathbb{E}(d_{A^{\prime}}(c))\pm\gamma
n=pn\pm\gamma n$. Note that $d_{A^{\prime}}(c,c^{\prime})$ is $2$-Lipschitz.
This is because for each $a$, there is exactly one $b$ with $abc$ an edge, and
one $b$ with $abc^{\prime}$ an edge (using linearity of $H$). Hence by Azuma’s
inequality and a union bound, we have that with probability at least
$1-1/n^{4}$, for each pair $c,c^{\prime}\in C$,
$d_{A^{\prime}}(c,c^{\prime})=\mathbb{E}(d_{A^{\prime}}(c,c^{\prime}))\pm\gamma
n=p^{2}n\pm\gamma n$. Corresponding bounds hold for $b,b^{\prime}\in B$. With
probability at least $1-3/n^{4}$ all these properties hold simultaneously.
Whenever these properties all hold, we have that the bipartite graph $(B,C)$
consisting of edges through $A^{\prime}$ is $(\gamma,p,n)$-typical as desired.
∎

Using the previous pseudorandomness property, we can derive the following
lemma which states most vertices send approximately the expected number of
edges through a random set and a deterministic set.

######  Lemma 3.7.

Let $H=(A,B,C)$ be a tripartite linear hypergraph that is $(0,1,n)$-typical.
Let $p\geq n^{-1/600}$ and let $A^{\prime}\subseteq A$ be $p$-random. Then,
with probability at least $1-1/n^{3}$, the following holds. For any
$B^{\prime}\subseteq B$, there are at most $n^{9/10}$ vertices $c\in C$ with
$e_{H}(A^{\prime},B^{\prime},c)\neq p|B^{\prime}|\pm n^{9/10}$.

###### Proof.

Set $\gamma=n^{-1/5}$. By Lemma 3.6, with probability at least $1-1/n^{3}$, we
have that the bipartite graph between $B$ and $C$ consisting of edges passing
through $A^{\prime}$ is $(n^{-1/5},p,n)$-typical. Supposing this property
holds, by Lemma 3.5, for any $B^{\prime}\subseteq B,C^{\prime}\subseteq C$, we
have $e_{H}(A^{\prime},B^{\prime},C^{\prime})=p|B^{\prime}||C^{\prime}|\pm
5\gamma^{1/2}n^{2}$. Let $C^{-}$ be the set of vertices with
$e_{H}(A^{\prime},B^{\prime},c)<p|B^{\prime}|-{\gamma}^{1/4}n$. We have that
$e_{H}(A^{\prime},B^{\prime},C^{-})<p^{\prime}|B^{\prime}||C^{-}|-{\gamma}^{1/4}n|C^{-}|$
and $e_{H}(A^{\prime},B^{\prime},C^{-})=p^{\prime}|B^{\prime}||C^{-}|\pm
5\gamma^{1/2}n^{2}$ implying $|C^{-}|\leq 10{\gamma}^{1/4}n$. Similarly
letting $C^{+}$ be the set of vertices with
$e_{H}(A^{\prime},B^{\prime},c)>p|B^{\prime}|+\gamma^{1/2}n$, we get
$|C^{+}|\leq 10{\gamma}^{1/4}n$. Plugging in the value of $\gamma$, this
implies the lemma. ∎

The following lemma will allow us to find a large matching whenever we are
given two random subsets and a deterministic subset.

######  Lemma 3.8.

Let $H=(A,B,C)$ be a tripartite linear hypergraph that is $(0,1,n)$-typical.
Let $p\geq n^{-1/600}$ and let $A^{\prime}\subseteq A$ be $p$-random, and let
$B^{\prime}$ a $p$-random subset of $B$, where $A^{\prime}$ and $B^{\prime}$
are not necessarily independent. Then, with probability at least $1-n^{-2}$,
the following holds.

For any $C^{\prime}\subseteq C$ of size $(1\pm n^{-0.2})pn$, there is a
matching covering all but $2n^{1-1/500}$ vertices in $A^{\prime}\cup
B^{\prime}\cup C^{\prime}$.

###### Proof.

With probability at least $1-n^{-2}$, $A^{\prime}$ and $B^{\prime}$ satisfy
the conclusion of Lemma 3.7 and have size $(1\pm n^{-0.2})pn$ (by Chernoff’s
bound). This means that $A^{\prime}\cup B^{\prime}\cup C^{\prime}$ has $\leq
n^{9/10}$ vertices with degree $\neq p^{2}n\pm n^{19/20}$ in
$H[A^{\prime},B^{\prime},C^{\prime}]$.

Deleting all such vertices gives a hypergraph satisfying the hypothesis of
Lemma 3.4 with $\gamma:=n^{-0.01}$, hence the desired matching exists. ∎

In some applications the following formulation which allows for three
deterministic subsets as opposed to just one will be more convenient. The
result follows simply by applying the previous result four times.

######  Lemma 3.9.

Let $H=H_{G}$ be a multiplication hypergraph. Let $p\geq n^{-1/650}$. Let
$A^{\prime},B^{\prime},C^{\prime}$ be $p$-random subsets of $A$, $B$, $C$
respectively, not necessarily independent. Set $R:=A^{\prime}\cup
B^{\prime}\cup C^{\prime}$. With high probability the following holds. Let
$q\leq 5p$. For any $X\subseteq V(H)\setminus R$ with $|X\cap A|,|X\cap
B|,|X\cap C|=(1\pm n^{-0.25})qn$, there is a matching in $R\cup X$ covering
all but at most $n^{1-10^{-4}}$ vertices of $R\cup X$.

###### Proof.

Let $q$ be a fixed rational number between $0$ and $1$ and denominator at most
$n$. Suppose first that $q\leq n^{-1/600}$. We have that Lemma 3.8 holds for
$A^{\prime}$ and $B^{\prime}$ with probability $\geq 1-n^{1.5}$ and by
Chernoff’s bound $C^{\prime}=(1\pm n^{-0.2})pn$, with probability $\geq
1-n^{-2}$. Both properties hold simultaneously with probability $\geq
1-n^{-1.49}$. Then, using Lemma 3.8, $A^{\prime}\cup B^{\prime}\cup
C^{\prime}$ has a matching covering all but $n^{1-10^{-3}}$ vertices. Together
with $X$, this gives $n^{1-10^{-3}}+2n^{599/600}\leq n^{1-10^{-4}}$ vertices.

Suppose now that $q\geq n^{-1/600}$. For each $\diamond\in\\{A,B,C\\}$,
partition $\diamond^{\prime}$ into a $q$-random set $\diamond_{1}$, and a
$q$-random set $\diamond_{2}$, and a $(p-2q)$-random set $\diamond_{3}$. As
$q,p-2q\geq n^{-1/600}$ by assumption, with probability $\geq 1-n^{-1.49}$ the
pairs $(A_{1},B_{1}),(A_{2},C_{1}),(B_{2},C_{2})$ and $(A_{3},B_{3})$ satisfy
the property of Lemma 3.8, and
$|\diamond_{i}|=(1+n^{-0.22})\mathbb{E}[|\diamond_{i}|]$ for each
$\diamond_{i}$.

Let $X_{A}=X\cap A$, $X_{B}=X\cap B$, $X_{C}=X\cap C$ to get sets of size
$(1\pm n^{-0.2})qn$. Using Lemma 3.8, we have matchings
$M_{1},M_{2},M_{3},M_{4}$ covering all, but at most $n^{1-10^{-3}}$ vertices
of $A_{1}\cup B_{1}\cup X_{C}$, $A_{2}\cup X_{B}\cup C_{1}$ , $X_{A}\cup
B_{2}\cup C_{2}$, and $A_{3}\cup B_{3}\cup C_{3}$ respectively. In total, the
number of uncovered vertices does not exceed $4n^{1-10^{-3}}\leq
n^{1-10^{-4}}/10$.

Taking a union bound over all rational $q$ with denominator at most $n$, we
have shown that with high probability, there exists a matching covering all
but $n^{1-10^{-4}}/10$ vertices. The statement for real values of $q$ follows
simply by using the property for the closest rational value $q^{\prime}$ to
$q$ with denominator at most $n$. Indeed, leaving out or deleting few
elements, we can ensure that the set $X$ has $|X\cap A|,|X\cap B|,|X\cap
C|=(1\pm n^{-0.25})q^{\prime}n$, thereby obtaining a matching that covers all
but $n^{1-10^{-4}}/10+n^{1-10^{-4}}/10\leq n^{1-10^{-4}}$ elements of the
original sets $X\cup R$. ∎

###  3.2 The multiplication hypergraph

We make some clarifications regarding our notation with the multiplication
hypergraph $H_{G}$ of a group (recall that this was defined in Section 2).
While referring to the parts of the multiplication hypergraph, we often omit
the $A/B/C$ subscripts and think of $A_{G},B_{G},C_{G}$ simply as copies of
$G$. For example, whenever we have some vertices $v_{1},v_{2},\dots,v_{k}\in
V(H_{G})$, we write $v_{1}v_{2}\dots v_{k}$ to mean the product of the
corresponding group elements in $G$ (as opposed to in any of the copies
$A_{G},B_{G},C_{G}$). Similarly, if $v\in V(H_{G})$ and $U$ is a subset of
$G$, then we use $v\in U$ to mean that $v$ is an element of $G$ after dropping
the $A/B/C$ subscript. For any subset $S\subseteq G$, we use
$S_{A}/S_{B}/S_{C}$ to denote the corresponding subsets of $G_{A}/G_{B}/G_{C}$
respectively.

A subset $S$ of $V(H_{G})$ is called balanced, if $|S\cap G_{\diamond}|$ does
not depend on the value of $\diamond\in\\{A,B,C\\}$.

###  3.3 Basic group theory definitions and results

Throughout the paper we use ${e}$ to denote the identity element of a group
$G$. Recall that we use $G^{\prime}$ to denote the commutator subgroup of a
group $G$. That is, $G^{\prime}$ is the subgroup generated by elements of the
form $[g,h]:=ghg^{-1}h^{-1}$ where $g,h\in G$. We denote the abelianization of
$G$ (quotient of $G$ by $G^{\prime}$) as $G^{\mathrm{ab}}$. We sometimes call
the elements of $G^{\mathrm{ab}}$ $G^{\prime}$-cosets. For $g\in G$, we use
$[g]$ to denote the unique $G^{\prime}$-coset that $g$ is a member of. When
$g\in V(H_{G})$, we think of $[g]$ as the $G^{\prime}$-coset that resides in
the same part $G_{A}/G_{B}/G_{C}$ that $g$ resides in. As mentioned in the
introduction, whenever we use additive notation together with elements of $G$,
all operations take place in $G^{\mathrm{ab}}$. We do this so that we don’t
have to use the $[g]$ notation excessively.

######  Lemma 3.10.

$g\in G^{\prime}$ if, and only if, $g$ can be written as $g=g_{1}\dots g_{t}$
such there’s a permutation $\sigma$ of $[t]$ with $g_{\sigma(1)}\dots
g_{\sigma(t)}={e}$.

###### Proof.

To see the “only if” direction, write $g$ as a product of commutators as

$g=[a_{1},b_{1}]\dots[a_{t},b_{t}]=a_{1}b_{1}a_{1}^{-1}b_{1}^{-1}\dots
a_{t}b_{t}a_{t}^{-1}b_{t}^{-1}.$

Clearly, the latter product can be permuted as
$a_{1}a_{1}^{-1}b_{1}b_{1}^{-1}\dots a_{t}a_{t}^{-1}b_{t}b_{t}^{-1}={e}$, as
required. For the “if” direction, consider some $g_{1}\dots g_{t}$ which
rearranges into $g_{\sigma(1)}\dots g_{\sigma(t)}={e}$. Consider the quotient
homomorphism $\phi:G\to G/G^{\prime}$. Then since $G/G^{\prime}$ is abelian,
we have $\phi(g_{1}\dots
g_{t})=\phi(g_{1})\dots\phi(g_{t})=\phi(g_{\sigma(1)})\dots\phi(g_{\sigma(t)})=\phi(g_{\sigma(1)}\dots
g_{\sigma(t)})=\phi({e})={e}$ i.e. $g_{1}\dots g_{t}\in ker(\phi)=G^{\prime}$
as required. ∎

The following is a well-known property of finite abelian groups.

######  Theorem 3.11 (Fundamental theorem of finite abelian groups).

Let $G$ be an abelian group. Then, $G$ is isomorphic to a product of cyclic
prime-power order groups.

Given $g\in G$, $s(g)$ denotes the size of the set $\\{x\in G\colon
x^{2}=g\\}$.

######  Proposition 3.12 ([56]).

Let $G$ be group such that there exists some $g\in G$ with $s(g)>(3/4)|G|$.
Then, $G$ is an elementary abelian $2$-group and $g=0$.

###### Proof.

We express our gratitude for all participants of the active discussion that
took place on Math Overflow including Emil Jeřábek, Derek Holt, Saúl Rodríguez
Martín, and Terry Tao. Here, we reproduce the argument of GH from MO [56]. Let
$g\in G$, and suppose that $|s(g)|>(3/4)|G|$. Fix some $y\in G$, and define
$S=\\{x\in G\colon x^{2}=g\\}$ and $T=\\{x\in S\colon xy\in S\\}$. Observe
that $|G\setminus T|\leq 2|G\setminus S|$, since $x\notin T$ only if $x\notin
S$ or $xy\notin S$, and there are at most $|G\setminus S|$ many $x$ of either
type. By assumption $|G\setminus S|<|G|/4$, so $|G\setminus T|<|G|/2$.
Consequently, $|T|>|G|/2$.

Observe that for any $x\in T$, we have that $(xy)^{2}=g=x^{2}$, and so we have

$xyx^{-1}=(xy)(xy)^{-2}(xy)^{2}x^{-1}=(xy)^{-1}x^{2}x^{-1}=(xy)^{-1}x=y^{-1}x^{-1}x=y^{-1}.$

We claim that $C=\\{x\in G\colon xyx^{-1}=y^{-1}\\}$ is a coset of $C(y)$, the
centralizer subgroup of $y$. To see this, take $x,w\in C$ and so
$xyx^{-1}=y^{-1}=wyw^{-1}$, and rearranging we have that
$(w^{-1}x)y(x^{-1}w)=y$, which implies that $w^{-1}x$ belongs to $C(y)$.
Hence, $w$ and $x$ belong to the same coset of $C(y)$. Then, we can fix
$C^{\prime}$ to be a coset of $C(y)$ with $C\subseteq C^{\prime}$. Now, take
some $w\in C^{\prime}$. $|C|>|G|/2$ since $T\subseteq C$, so in particular,
$C$ is non-empty, so we can fix some $x\in C$. As $w,x\in C^{\prime}$,
$w^{-1}x\in C(y)$, so $(w^{-1}x)y(x^{-1}w)=y$, hence $xyx^{-1}=wyw^{-1}$. The
left-hand side of the last equation is $y^{-1}$ by definition of $x\in C$, so
$wyw^{-1}=y^{-1}$, implying $w\in C$. So $C^{\prime}=C$, and $C$ is a coset of
the desired form.

As $|C|>|G|/2$, and $C$ is a coset, $C=G$ by Lagrange’s theorem. This implies
that $y=y^{-1}$ for each $y$, hence $G$ is an elementary abelian $2$-group. It
follows that $g=0$, as $s(g)=0$ for some $g\neq 0$ in an elementary abelian
$2$-group. ∎

###  3.4 Generic elements, and choice of of $a_{\phi},b_{\phi},c_{\phi}$

The following definition is critical.

######  Definition 3.13.

A group element $g\in G$ is generic if $g\neq{e}$ and there are at most
$n/10^{9000}$ solutions to $x^{2}=g$ in $G$.

Let $N(G)$ denote the set of non-generic elements and note that $|N(G)|\leq
10^{9000}$. Similarly, we call vertices of $H_{G}$ generic if the
corresponding group element is generic.

As described in Section 2, it is critical to our method to pair up group
elements with a fixed sum, where the fixed sum has some desirable properties.
The following lemma serves to show that the pairing we desire exists.

######  Lemma 3.14.

For group $G$ with $|G|\geq 10^{9900}$, there exist
$a_{\phi},b_{\phi},c_{\phi}\in G$ with

  1. (a)

$a_{\phi}b_{\phi}c_{\phi}={e}$.

  2. (b)

There are at most $30$ solutions to $x^{2}=\\{a_{\phi},b_{\phi},c_{\phi}\\}$.
In particular $a_{\phi},b_{\phi},c_{\phi}$ are generic.

  3. (c)

There are at most $30|G^{\prime}|$ solutions to
$x^{2}\in[a_{\phi}]\cup[b_{\phi}]\cup[c_{\phi}]$. In particular, there are at
most $30$ self-paired cosets (i.e. cosets $[x]$ with
$[x^{2}]=[a_{\phi}]/[b_{\phi}]/[c_{\phi}]$).

  4. (d)

If $|G^{\prime}|\leq 10^{-9}n$, then $a_{\phi},b_{\phi},c_{\phi}\not\in
G^{\prime}$.

###### Proof.

For each $g\in G$, let $S(g)=\\{x:x^{2}=g\\}$, and note that since every $x$
is in precisely one $S(g)$, we have $\sum_{g\in G}|S(g)|=|\bigcup_{g\in
G}S(g)|=|G|=n$. Let $Y_{1}$ be the set of elements $y_{\phi}$ with more than
$10$ solutions to $x^{2}=y_{\phi}$, noting that $10|Y_{1}|\leq\sum_{y\in
Y_{1}}|S(y)|\leq\sum_{y\in G}|S(y)|=n$, we get $|Y_{1}|\leq n/10$. Let $Y_{2}$
be the set of elements $y_{\phi}$ with $>10|G^{\prime}|$ solutions to
$x^{2}\in[y_{\phi}]$. Then $10|G^{\prime}||Y_{2}|=\sum_{y\in
Y_{2}}\sum_{z\in[y]}|S(z)|=\sum_{y\in Y_{2}}\sum_{k\in
G^{\prime}}|S(yk)|=\sum_{k\in G^{\prime}}\sum_{y\in
Y_{2}}|S(yk)|\leq\sum_{k\in G^{\prime}}\sum_{y\in G}|S(yk)|=|G^{\prime}|n$,
which implies $|Y_{2}|\leq n/10$. If $|G^{\prime}|\leq 10^{-9}n$, set
$Y_{3}=G^{\prime}$, and if $|G^{\prime}|>10^{-9}n$. Let
$X=X\setminus(Y_{1}\cup Y_{2})$ to get a set of size $|X|\geq
n-n/10-n/10-10^{-9}n\geq 0.79n$.

Letting $XX=\\{xy:x,y\in X\\}$ and $X^{-1}=\\{z^{-1}:z\in X\\}$, notice that
$|XX|$, $|X^{-1}|\geq|X|\geq 0.79n$. Therefore there must exist some $v\in
XX\cap X^{-1}$ i.e. $v=xy=z^{-1}$ for some $x,y,z\in X$. But then $xyz={e}$,
and so we can set $a_{\phi}=x,b_{\phi}=y,c_{\phi}=z$. ∎

######  Definition 3.15.

We say that an element $x$ is $\phi$-generic if $x,$ $a_{\phi}^{\pm 1}x,$
$b_{\phi}^{\pm 1}x,$ $c_{\phi}^{\pm 1}x,$ $a_{\phi}^{\pm 1}b_{\phi}^{\pm 1}x,$
$b_{\phi}^{\pm 1}c_{\phi}^{\pm 1}x,$ $c_{\phi}^{\pm 1}a_{\phi}^{\pm 1}x$ are
all generic.

Notice that the number of elements which aren’t $\phi$-generic is $\leq
30|N(G)|\leq 10^{9010}$. We call a subset $\phi$-generic if all elements of
that subset are $\phi$-generic.

For each group $G$, we fix a triple $a_{\phi},b_{\phi},c_{\phi}$ with the
properties as in Lemma 3.14. We call two vertices $v$ and $w$ of $H_{G}$
coming from the same part a pair if $v\cdot w\in[x_{\phi}]$ where $x=a,b,c$
depending on whether $v,w\in A,B,C$.

We call a subset $S$ of $V(H_{G})$ coset-paired if $S$ can be partitioned into
a disjoint union of pairs. This is equivalent to the following statement.
$|S\cap[g]|=|S\cap[x_{\phi}g^{-1}]|$ for every non-self-paired coset $[g]$ and
$|S\cap[g]|$ is even for every self-paired coset $[g]$.

###  3.5 Symmetric sets

Recall that a $p$-random subset of set $S$ is one obtained by sampling each
element of $S$ independently with probability $p$. Similarly, we say a
collection of random sets $R_{1},\ldots,R_{k}\subseteq S$ is disjoint
$p$-random if each element of $S$ belongs to each $R_{i}$ with probability
$p$, and to none of the $R_{i}$ with probability $1-pk$, and these decisions
are made independently for each element of $S$. Considering such disjoint
distributions complicates our approach as it makes various gadgets
significantly more difficult to find. The reason we are interested in such
distributions is the applications we give later on in the paper. Indeed, all
applications we give other than the alternative proof of Hall-Paige conjecture
and Snevily’s conjecture require that we work with such disjoint
distributions.

In fact, we need to generalise the concept of a disjoint distribution even
further so that we can work with random sets $X,Y,Z$ where $X,Y$ and
$Z^{-1}=\\{z^{-1}\colon z\in Z\\}$ are sampled disjointly. This need comes
from the applications to sequenceability and $R$-sequenceability. Thankfully,
this generalisation does not create many additional combinatorial
difficulties. However, we still need the following definitions to state a
single theorem that covers all of the applications we want to give.

For $g\in G$, define $\hat{g}:=\\{g,g^{-1}\\}$, noting that $\hat{g}$ has size
1 or 2 (depending on whether $g$ is an involution or not). For a subset
$T\subseteq G$, let $\hat{T}=\\{\hat{t}:t\in T\\}$ and
$\bigcup\hat{T}=\bigcup_{t\in T}\hat{t}=T\cup T^{-1}$. We say that a subset
$T\subseteq G$ is symmetric if $T^{-1}=T$ (or equivalently if
$T=\bigcup\hat{T}$). We call a subset $S\subseteq V(H_{G})$ symmetric if
$S\cap A,S\cap B,S\cap C$ are all symmetric. We say that $R$ is a symmetric
$p$-random subset of $G$ if $R$ is always symmetric and $\hat{R}$ is a
$p$-random subset of $\hat{G}$ (or equivalently if $R$ is formed by flipping
an independent coin for each $\hat{g}\in\hat{G}$ and taking the union of all
group elements for which heads comes up). We say that $R^{1},R^{2},R^{3}$ are
disjoint symmetric $p$-random subsets of $G$ if additionally the joint
distribution of $\hat{R}^{1},\hat{R}^{2},\hat{R}^{3}$ is that of disjoint
$p$-random subsets of $\hat{G}$. The following two lemmas are useful as they
allow us to jump between these definitions.

######  Lemma 3.16.

Let $R_{1},R_{2},R_{3}$ be disjoint $p$-random sets. Then there are
$S_{1}\subseteq R_{1}$, $S_{2}\subseteq R_{2}$, $S_{3}\subseteq R_{3}$ so that
the joint distribution on $S_{1},S_{2},S_{3}$ is that of disjoint symmetric
$p^{2}$-random sets.

###### Proof.

Let $T$ be a $p$-random subset of $G$, independent of $R_{1},R_{2},R_{3}$. For
non-involutions $g$, place $g,g^{-1}$ into $S_{i}$ whenever
$\\{g,g^{-1}\\}\subseteq R_{i}$. For involutions $g$, place $g$ into $S_{i}$
whenever $g\in R_{i}\cap T$. Notice that for each $g\in G$, this gives
$\mathbb{P}(\hat{g}\subseteq S)=p^{2}$. Also, these events are mutually
independent for different $\hat{g},\hat{h}$ since they depend on different
coordinates. ∎

######  Lemma 3.17.

Let $Q_{1},Q_{2},Q_{3},R$ be random sets with $Q_{1},Q_{2},Q_{3}$ being
disjoint symmetric $q$-random and $R$ being $p$-random and independent of
$Q_{1},Q_{2},Q_{3}$. Then, there are $S_{1}\subseteq Q_{1}\cap R$,
$S_{2}\subseteq Q_{2}\cap R$, $S_{3}\subseteq Q_{3}\cap R$ so that the joint
distribution on $S_{1},S_{2},S_{3}$ is that of disjoint symmetric
$p^{2}q$-random sets.

###### Proof.

Let $T$ be a $p$-random subset of $G$, independent of $R,Q_{1},Q_{2},Q_{3}$.
For non-involutions $g$, place $g,g^{-1}$ into $S_{i}$ whenever
$\\{g,g^{-1}\\}\subseteq Q_{i}\cap R$. For involutions $g$, place $g$ into
$S_{i}$ whenever $g\in Q_{i}\cap R\cap T$. Notice that for each
$\hat{g}\in\hat{G}$, this gives $\mathbb{P}(\hat{g}\subseteq S_{i})=p^{2}q$.
Also, these events are mutually independent for different $\hat{g},\hat{h}$
since they depend on different coordinates. ∎

###  3.6 Free products

The goal of this section is to prove Lemma 3.32, which is our main tool to
find vertex-disjoint copies of constant sized substructures in multiplication
hypergraphs. We first remind the reader of some standard group theoretic
terminology. We use $F_{k}$ to denote the free group on $k$ generators
$v_{1},\dots,v_{k}$.

For a group $G$, we use $G\ast F_{k}$ to denote the free product of $G$ and
$F_{k}$. We call $v_{1},\dots,v_{k}$ the free variables of the free product
$G\ast F_{k}$. A word is simply an element of $G\ast F_{k}$. For $w\in G\ast
F_{k}$, we define the length of $w$ to be the minimum number $\ell$ needed to
write $w=x_{1}x_{2}\dots x_{\ell}$ for
$x_{i}\in\\{v_{i},v_{i}^{-1}:i=1,\dots,k\\}\cup G$. A word $w\in G\ast F_{k}$
is called reduced if it cannot be made shorter using the group operations i.e.
if it doesn’t contain consecutive elements of $G$, doesn’t contain ${e}$, and
doesn’t contain consecutive $v_{i},v_{i}^{-1}$ or $v_{i}^{-1},v_{i}$ for any
$i$. It is a standard property of free products that every $g\in G\ast F_{k}$
is uniquely expressible as a reduced word.

######  Lemma 3.18.

For $w\in G\ast F_{k}$, there’s a unique way of writing
$w=g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ with
$x_{i}\in\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$ and $g_{i}\in G$
such that we don’t have “$x_{i}=x_{i+1}^{-1}\text{ and }g_{i}={e}$” for any
$i\in\\{0,1,\ldots,t-1\\}$.

###### Proof.

Let $W$ be the set of words which can be written of the form
$g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ with
$x_{i}\in\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$ and $g_{i}\in G$
such that we don’t have “$x_{i}=x_{i+1}^{-1}\text{ and }g_{i}={e}$” for any
$i\in\\{0,1,\ldots,t-1\\}$. Let $R$ be the set of reduced words of $G\ast
F_{k}$. Let $f:W\to R$ be defined by mapping $w=g_{0}x_{1}g_{1}\dots
x_{t}g_{t}$ to the word formed by removing all copies of ${e}$ from $w$. Let
$g:R\to W$ be defined by mapping $w^{\prime}=y_{1}y_{2}\dots y_{k}$ to the
word formed by inserting ${e}$ between any $y_{i},y_{i+1}$ which are both in
$\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$. It is easy to see that
$f(g(w^{\prime}))=w^{\prime}$ and $g(f(w))=w$ for any $w\in W$ and
$w^{\prime}\in R$ i.e. both functions are bijections. Thus, since every $g\in
G\ast F_{k}$ is uniquely expressible as a reduced word, it is also uniquely
expressible as a word in $W$. ∎

From the above, we get that every $w\in G\ast F_{k}$ can be written as
$w=g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ with
$x_{i}\in\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$ and $g_{i}\in
G$. We say that $w\in G\ast F_{k}$ is linear in $v_{i}$ there’s a way of
writing $w$ like this with precisely one occurrence of $v_{i}$ (meaning one
occurrence $v_{i}$ or $v_{i}^{-1}$, but not both). We say that $w$ is linear
if all variables occur at most once in $w$, and some variable occurs exactly
once in $w$. A useful fact is that for a linear $w$, there’s a unique way of
writing it as $w=g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ (with
$x_{i}\in\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$ and $g_{i}\in
G$) such that there’s at most one occurrence of each variable. This comes from
Lemma 3.18, because in a linear $w=g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ it is
impossible to have $x_{i}=x_{i+1}^{-1},g_{i}={e}$ (since this would create two
occurrences of the free variable $x_{i}$).

A homomorphism $\pi:G\ast F_{k}\to G$ is a projection if $\pi(g)=g$ for all
$g\in G$.

######  Lemma 3.19.

For each function $f:\\{v_{1},\dots,v_{k}\\}\to G$, there is precisely one
projection $\pi_{f}:G\ast F_{k}\to G$ which agrees with $f$ on
$\\{v_{1},\dots,v_{k}\\}$. In particular, there are precisely $n^{k}$
projections $G\ast F_{k}\to G$.

###### Proof.

Let $f:\\{v_{1},\dots,v_{k}\\}\to G$ be a function. By the universal property
of free groups, there is a unique homomorphism $\phi_{f}:F_{k}\to G$ which
agrees with $f$ on $\\{v_{1},\dots,v_{k}\\}$. Let ${e}_{G}:G\to G$ be the
identity homomorphism. By the universal property of free products there is a
unique homomorphism $\pi_{f}$ which agrees with $\phi_{f}$ on $F_{k}$ and
agrees with ${e}_{G}$ on $G$. Such a homomorphism is exactly a projection from
$G\ast F_{k}$ to $G$.

For the “in particular” part, note that the number of functions
$\\{v_{1},\dots,v_{k}\\}\to G$ is exactly $n^{k}$, and so there are this many
projections $G\ast F_{k}\to G$ by the first part. ∎

We use $\pi_{0}:G\ast F_{k}\to G$ to denote the projection which maps all
$w\in F_{k}$ to ${e}$ (i.e. the map coming from Lemma 3.19 via the function
$f$ mapping all $v_{i}$ to ${e}$).

######  Observation 3.20.

For all $g,h\in G$ there are the same number of solutions to $x^{2}\in[g]$ and
$x^{2}\in[h^{2}g]$.

In particular, for any $w,w^{\prime}\in G\ast F_{k}$, there are the same
number of solutions to $x^{2}\in[\pi_{0}(w^{-1}w^{\prime})]$ an
$x^{2}\in[\pi_{0}(ww^{\prime})]$ in $G$).

###### Proof.

We have that $x^{2}\in[g]$ if, and only if $(hx)^{2}\in[h^{2}g]$. Therefore,
if $S$ is the set of solutions to $x^{2}\in[g]$, then $hS$ is the set of
solutions to $(hx)^{2}\in[h^{2}g]$. Since $S$ and $hS$ always have the same
size in a group, this gives what we want.

The “in particular” part follows from the above by taking
$g=\pi_{0}(w^{-1}w^{\prime}),h=\pi_{0}(w)$, and noting that, since $\pi_{0}$
is a homomorphism, we have $\pi_{0}(ww^{\prime})=h^{2}g$ ∎

######  Definition 3.21.

Let $w,w^{\prime}\in G\ast F_{k}$. We say that $w$ and $w^{\prime}$ are
strongly separable if any of the following hold.

  1. (a)

$w^{-1}w^{\prime}$ is linear in some free variable $v_{i}$. Note that this is
equivalent to asking that a free variable $v_{i}$ appears once in one of
$w/w^{\prime}$, and never in the other.

  2. (b)

$w,w^{\prime}$ are linear, contain at least one free variable, and there is a
$g\in G$ with $g$ generic so that
$w^{\prime}\in\\{gw,g^{-1}w,gw^{-1},g^{-1}w^{-1},wg,wg^{-1},w^{-1}g,w^{-1}g^{-1}\\}$.

  3. (c)

All of the following hold.

     * •

$|G^{\prime}|\leq 10^{-9}n$

     * •

$w$ and $w^{\prime}$ are linear and have the same free variables (potentially
with different signs).

     * •

We either have $\pi_{0}(ww^{\prime})\not\in G^{\prime}$ or some free variable
occurs with the same sign in $w,w^{\prime}$.

     * •

We either have $\pi_{0}(w^{-1}w^{\prime})\not\in G^{\prime}$ or some free
variable occurs with the opposite sign in $w,w^{\prime}$.

     * •

There are $\leq 90|G^{\prime}|$ solutions to $x^{2}\in[\pi_{0}(ww^{\prime})]$
(or equivalently by Observation 3.20, there are $\leq 90|G^{\prime}|$
solutions to $x^{2}\in[\pi_{0}(w^{-1}w^{\prime})]$ in $G$).

######  Definition 3.22.

We say that two sets $S,T\subseteq G$ are strongly separable if every pair of
elements $s\in S,t\in T$ are strongly separable.

The following observation is quite critical, and justifies why considering
symmetric disjoint random sets doesn’t create additional complications when
compared to disjoint random sets.

######  Observation 3.23.

$w,w^{\prime}$ are strongly separable $\iff w^{-1},w^{\prime}$ are strongly
separable $\iff$ $\hat{w},\hat{w}^{\prime}$ are strongly separable.

###### Proof.

Within this proof, we say separable to mean strongly separable. For
“$w,w^{\prime}$ are separable $\iff w^{-1},w^{\prime}$ are separable”:
Consider the possible cases of Definition 3.21. If $w,w^{\prime}$ are
separable by (a), then $w^{-1},w^{\prime}$ are also separable by (a) (this is
immediate when one considers the “a free variable $v_{i}$ appears once in one
of $w/w^{\prime}$, but not both” version of (a)). If $w,w^{\prime}$ are
separable by (b), then $w^{-1},w^{\prime}$ are also separable by (b) — this is
true because the set
$\\{gw,g^{-1}w,gw^{-1},g^{-1}w^{-1},wg,wg^{-1},w^{-1}g,w^{-1}g^{-1}\\}$
doesn’t change if you replace each “$w$” with “$w^{-1}$”. If $w,w^{\prime}$
are separable by (c), then $w^{-1},w^{\prime}$ are also separable by (c). (The
first bullet point doesn’t involve $w,w^{\prime}$. The second bullet point
doesn’t change by replacing $w$ with $w^{-1}$ because $w,w^{-1}$ are always
linear in the same free variables. The 3rd and 4th bullet points get exchanged
when replacing $w$ by $w^{-1}$. The 5th bullet point doesn’t change when
replacing w by $w^{-1}$ since there is the same number of solutions to
$x^{2}\in[\pi_{0}(ww^{\prime})]$ and $x^{2}\in[\pi_{0}(w^{-1}w^{\prime})]$ by
Observation 3.20).

The direction “$\hat{w},\hat{w}^{\prime}$ are separable $\implies$
$w,w^{\prime}$ are separable” is immediate from the definition of “$S,T$ are
separable”. For “ $w,w^{\prime}$ are separable $\implies$
$\hat{w},\hat{w}^{\prime}$ are separable”, note that once we know that
$w,w^{\prime}$ are separable, we also know that the pairs
$(w^{-1},w^{\prime})$, $(w,(w^{\prime})^{-1})$, $(w^{-1},(w^{\prime})^{-1})$
are separable (all coming from “$w,w^{\prime}$ are separable $\iff
w^{-1},w^{\prime}$ are separable”). This gives that $\hat{w},\hat{w}^{\prime}$
are separable. ∎

######  Observation 3.24.

Let $S\subseteq G\ast F_{k}$ be a set of linear elements. For each
$T\subseteq\\{v_{1},\dots,v_{k}\\}$, let $S_{T}$ be the set of $w\in W$ such
that the free variables in $w$ are exactly the set $T$. Then the sets
$S_{T},S_{T^{\prime}}$ are strongly separable for distinct $T,T^{\prime}$.

###### Proof.

If $T,T^{\prime}$ are distinct, then there’s some $v_{i}\in T\Delta
T^{\prime}$ say $v_{i}\in T\setminus T^{\prime}$. For any $w\in
S_{T},w^{\prime}\in S_{T^{\prime}}$, we have that $v_{i}$ appears in $w$ (just
once by linearity) but not $w^{\prime}$, and so part (a) of the definition of
“strongly separable” applies. ∎

######  Definition 3.25.

Let $w,w^{\prime}\in G\ast F_{k}$. We say that $w$ and $w^{\prime}$ are
weakly-separable if either they are strongly-separable, or they satisfy the
following property.

  * $(b^{\prime})$

For some non-identity element $g$, the equation $w=w^{\prime}$ rearranges into
${e}=g$.

We remark that the key difference between strong and weak separability comes
from the property $(b^{\prime})$ not necessarily holding when $w$ is replaced
with $w^{-1}$, i.e. Observation 3.23 fails for weak separability. This will
not be an issue while we search for gadgets, as we rely on weak separation
only to separate elements coming from the same set $A_{G},B_{G},C_{G}$.

######  Definition 3.26.

Let $S\subseteq G\ast F_{k}$. We say that a homomorphism $\phi:G\ast F_{k}\to
G$, separates $S$ if for every weakly-separable $w,w^{\prime}\in S$ we have
$\phi(w)\neq\phi(w^{\prime})$.

Recall that $(G\ast F_{k})^{\prime}$ denotes the commutator subgroup of
$(G\ast F_{k})$.

######  Lemma 3.27.

For a group $G$, let $w,w^{\prime}\in G\ast F_{k}$ satisfy part (c) of the
definition of “strongly separable”. Then $w=w^{\prime}$ rearranges to
$u^{2}=\pi_{0}(w^{-1}w^{\prime})k$ for some $k\in(G\ast F_{k})^{\prime}$ and
some $u\in F_{k}$ which is either linear or equals ${e}$. Additionally,
$u={e}$ only if the free variables occur with the same signs in
$w,w^{\prime}$.

###### Proof.

Let $w=g_{0}x_{1}g_{1}\dots x_{t}g_{t}$ and
$w^{\prime}=g_{0}^{\prime}x_{1}^{\prime}g_{1}^{\prime}\dots
x_{t^{\prime}}^{\prime}g_{t^{\prime}}^{\prime}$ (with
$x_{i},x_{i}^{\prime}\in\\{v_{1},\dots,v_{k},v_{1}^{-1},\dots,v_{k}^{-1}\\}$
and $g_{i},g_{i}^{\prime}\in G$). Note that the assumption “$w$ and
$w^{\prime}$ are linear and have the same free variables” implies that
$t=t^{\prime}$, and that there is a permutation $\sigma$ of $[t]$ so that
$x_{i}^{\prime}\in\\{x_{\sigma(i)},x_{\sigma(i)}^{-1}\\}$ for $i=1,\dots,t$.
Partition $[t]=I^{+}\cup I^{-}$ with
$I^{+}=\\{i:x_{i}^{\prime}=x_{\sigma(i)}\\}$ and
$I^{-}=\\{i:x_{i}^{\prime}=x_{\sigma(i)}^{-1}\\}$. Set $u=\prod_{i\in
I^{-}}(x_{i}^{\prime})^{-1}$, noting that $u$ is in $F_{k}$, and that
$u={e}\iff I^{-}=\emptyset\iff$ the free variables occur with the same signs
in $w,w^{\prime}$. This also implies that if $u\neq e$, then $u$ is linear.
Note that $w=w^{\prime}$ rearranges to $u^{2}=\pi_{0}(w^{-1}w^{\prime})k$
where $k=\pi_{0}(w^{-1}w^{\prime})^{-1}u^{2}w^{\prime}w^{-1}$. Notice that

$\displaystyle\pi_{0}($ $\displaystyle
w^{-1}w^{\prime})^{-1}u^{2}w^{\prime}w^{-1}=\pi_{0}(w^{\prime})^{-1}\pi_{0}(w)u^{2}w^{\prime}w^{-1}$
$\displaystyle=(g_{t}^{\prime-1}\dots
g_{1}^{\prime-1}g_{0}^{\prime-1})(g_{0}\dots g_{t-1}g_{t})(\prod_{i\in
I^{-}}(x_{i}^{\prime})^{-1})(\prod_{i\in
I^{-}}(x_{i}^{\prime})^{-1})(g_{0}^{\prime}x_{1}^{\prime}g_{1}^{\prime}\dots
x_{t}^{\prime}g_{t}^{\prime})(g_{t}^{-1}x_{t}^{-1}g_{t-1}^{-1}\dots
x_{1}^{-1}g_{0}^{-1})$

Notice that the above product can be permuted into the identity. Indeed each
$g_{i}^{\prime-1}$ in the 1st bracket cancels with $g_{i}^{\prime}$ in the 5th
bracket, each $g_{i}$ in the 2nd bracket cancels with $g_{i}^{-1}$ 6th
bracket, for $i\in I^{-}$ each $(x_{i}^{\prime})^{-1}$ in the 3rd bracket
cancels with $x_{i}^{\prime}$ in the 5th bracket, each $(x_{i}^{\prime})^{-1}$
in the 4th bracket cancels with $(x_{\sigma(i)})^{-1}=x_{i}^{\prime}$ in the
6th bracket, and for $i\in I^{+}$ each $x_{i}^{\prime}$ in the 5th bracket
cancels with $x_{\sigma(i)}^{-1}=(x_{i}^{\prime})^{-1}$ in the 6th bracket.
Thus, by Lemma 3.10, $k\in(G\ast F_{k})^{\prime}$. ∎

######  Lemma 3.28.

Let $w\in G\ast F_{k}$ be linear in some free variable $v_{i}$ and $g\in G$.
Then there are exactly $n^{k-1}$ projections $\pi:G\ast F_{k}\to G$ having
$\pi(w)=g$.

###### Proof.

Without loss of generality, suppose $i=k$. By Lemma 3.19 there are exactly
$n^{k-1}$ projections $\pi:G\ast F_{k-1}\to G$. We will show that for every
such projection, there is a unique projection $\pi^{\prime}:G\ast F_{k}\to G$
that agrees with $\pi$ on $G\ast F_{k-1}$ and additionally has
$\pi^{\prime}(w)=g$. To see this, note that the equation $w=g$ in the group
$G\ast F_{k}$ rearranges into $v_{k}=h$ where $h\in G\ast F_{k}$ such that the
free variable $v_{k}$ doesn’t occur in $h$ (this is possible because $w$ is
linear in $v_{k}$). This shows that for any projection $\pi^{\prime}$, the
equation $\pi^{\prime}(w)=g$ is equivalent to
$\pi^{\prime}(v_{k})=\pi^{\prime}(h)$ (using that for any $g\in G$
$\pi^{\prime}(g)=g$ for any projection $\pi^{\prime}$). Since $h\in G\ast
F_{k-1}$, the image $\pi(h)\in G$ is defined. Thus a projection $\pi^{\prime}$
agrees with $\pi$ on $F_{k-1}\ast G$ and also has $\pi^{\prime}(w)=g$ if and
only if
$\pi^{\prime}(v_{1})=\pi(v_{i}),\dots,\pi^{\prime}(v_{k-1})=\pi(v_{k-1})$, and
also $\pi^{\prime}(v_{k})=\pi(h)$. By Lemma 3.19, there is a unique projection
satisfying this, as required. ∎

######  Lemma 3.29.

Let $S\subseteq G\ast F_{k}$ be a set of elements which are each linear in at
least one variable, and let $U\subseteq G$. Then the number of projections
$\pi:G\ast F_{k}\to G$ for which $\pi(S)$ intersects $U$ is
$\leq|S||U|n^{k-1}$.

###### Proof.

For each $w\in S$ and $u\in U$, by Lemma 3.28, there are $n^{k-1}$ projections
$\pi:G\ast F_{k}\to G$ with $\pi(w)=u$. Thus, summing over all $w,u$, there
are at most $\leq|S||U|n^{k-1}$ projections with $\pi(S)$ intersecting $U$. ∎

######  Lemma 3.30.

Let $n$ be sufficiently large. Let $S\subseteq G\ast F_{k}$ be a set of size
$\leq 1000$. Then there are at most $0.1n^{k}$ projections $\pi:G\ast F_{k}\to
G$ which do not separate $S$. If $|G^{\prime}|>10^{-9}n$, then this can be
improved to “at most $10^{-8900}n^{k}$ projections”.

###### Proof.

The total number of projections $\pi:G\ast F_{k}\to G$ is $n^{k}$ by Lemma
3.19. Consider two weakly separable words $w,w^{\prime}\in S$. We will count
the number of projections for which $\pi(w)=\pi(w^{\prime})$. There are four
cases, depending on which part of the definition of weakly separable applies
to $w,w^{\prime}$.

  1. $(a)$

Note that the equation $\pi(w)=\pi(w^{\prime})$ can be rearranged into
$\pi(w^{-1}w^{\prime})={e}$. Since in (a), $w^{-1}w^{\prime}$ is linear in
some variable, Lemma 3.28 tells us that there are $n^{k-1}\leq
n^{k}/10^{9000}$ projections $\pi:G\ast F_{k}\to G$ for which
$\pi(w^{-1}w^{\prime})={e}$.

  2. $(b^{\prime})$

Since $w=w^{\prime}$ rearranges into $e=g$, the equation
$\pi(w)=\pi(w^{\prime})$ rearranges into $\pi(e)=\pi(g)$. But this is
impossible for a projection $\pi$ (since the definition of “projection” gives
that $\pi({e})={e}$ and $\pi(g)=g$). Thus there are zero projections with
$\pi(w)=\pi(w^{\prime})$ in this case.

  3. $(b)$

If we are not in some case covered by the previous bullet point, then the
equation $w=w^{\prime}$ rearranges into $(w)^{2}=g$ for a generic group
element $g\in G$. Let $T_{g}$ be the set of solutions to $x^{2}=g$ to get a
set of size $\leq n/10^{9000}$, using the definition of a generic group
element. For a projection $\pi$ to have $\pi(w)=\pi(w^{\prime})$, it must have
(using that $\pi$ is a homomorphism) $\pi(w)^{2}=\pi(g)=g$ and so $\pi(w)\in
T_{g}$. By Lemma 3.29, there are $|T_{g}|n^{k-1}\leq n^{k}/10^{9000}$
projections with $\pi(w)\in T_{g}$.

  4. $(c)$

Using Lemma 3.27, $w=w^{\prime}$ rearranges into
$u^{2}=\pi_{0}(w^{-1}w^{\prime})k$ where $u\in F_{k}$ is either linear or
$u={e}$, and $k\in(G\ast F_{k})^{\prime}$. If $u={e}$, then we know that free
variables occur with the same signs in $w,w^{\prime}$, which tells us that
$\pi_{0}(w^{-1}w^{\prime})\not\in G^{\prime}$. This gives that
$[\pi_{0}(w^{-1}w^{\prime})k]\neq G^{\prime}$, and so
${e}\neq\pi_{0}(w^{-1}w^{\prime})k=u^{2}=e$, a contradiction. Thus in this
case, there are no projections with $\pi(w)=\pi(w^{\prime})$. So we can assume
that $u\neq{e}$ which implies by Lemma 3.27 that $u$ is linear.

Let $T$ be set of solutions to $x^{2}\in[\pi_{0}(w^{-1}w^{\prime})]$ in $G$.
Since we are in (c), we have $|T|\leq 90|G^{\prime}|\leq 90\cdot 10^{-9}n\leq
10^{-7}n$. For $\pi(w)=\pi(w^{\prime})$ to hold, we must have (using that
$\pi$ is a homomorphism) $\pi(u^{2})=\pi(\pi_{0}(w^{-1}w^{\prime})k)$, which
implies (using that $\pi$ is a projection)
$\pi(u)^{2}=\pi_{0}(w^{-1}w^{\prime})\pi(k)$. Since
$\pi_{0}(w^{-1}w^{\prime})\pi(k)\in[\pi_{0}(w^{-1}w^{\prime})]$ for any
projection $\pi$ (we have $\phi(H^{\prime})\subseteq G^{\prime}$ for any group
homomorphism $\phi:H\to G$, since if $x$ is a commutator in $H$, then
$\phi(x)$ is a commutator in $G$), this would imply that $\pi(w)\in T$. By
Lemma 3.29, there are $|T|n^{k-1}\leq 10^{-7}n^{k}$ projections with
$\pi(w)\in T$ as required.

There are at most $\binom{|S|}{2}\leq\binom{1000}{2}\leq 10^{6}$ pairs of
weakly separable $w,w^{\prime}\in S$, and for each of them there are $\leq
n^{k}/10^{7}$ projections with $w=w^{\prime}$. Thus in total there are $\leq
10^{6}n^{k}/10^{7}=0.1n^{k}$ projections which don’t separate $S$. This
implies the lemma when $|G^{\prime}|\leq 10^{-9}n$. When
$|G^{\prime}|>10^{-9}n$, note that case (c) can’t occur, so we actually have
$\leq n^{k}/10^{9000}$ projections with $w=w^{\prime}$ for each separable
$w,w^{\prime}$. This gives a total of $\leq 2\cdot 10^{6}n^{k}/10^{9000}\leq
n^{k}/10^{8900}$ projections which don’t separate $S$. ∎

######  Lemma 3.31.

Let $n$ be sufficiently large, $k\leq 200$, and $S\subseteq G\ast F_{k}$ a set
of $\leq 1000$ elements which are linear in at least one variable. There are
projections $\pi_{1},\dots,\pi_{10^{-3000}n}$ which separate $S$ and have
$\pi_{1}(S),\dots,\pi_{10^{-3000}n}(S)$ disjoint. If $|G^{\prime}|>10^{-9}n$,
then we can additionally ensure that $\pi_{j}(v_{i})\in G^{\prime}$ for all
free variables $v_{i}$ and projections $\pi_{j}$.

###### Proof.

For $|G^{\prime}|\leq 10^{-9}n$ say that a projection $\pi$ is good if it
separates $S$. For $|G^{\prime}|>10^{-9}n$ say that a projection $\pi$ is good
if it separates $S$ and has $\pi(v_{i})\in G^{\prime}$ for all $v_{i}\in
F_{k}$. Our task is to find $10^{-3000}n$ good projections $\pi_{i}(S)$, which
have $\pi_{i}(S)$ disjoint for different $i$. Consider a maximal family
$\pi_{1},\dots,\pi_{t}$ of good projections. which have
$\pi_{1}(S),\dots,\pi_{t}(S)$ disjoint. Let
$T=\pi_{1}(S)\cup\dots\cup\pi_{t}(S)$. By maximality, we have that all good
projections $\pi$ have $\pi(S)\cap T\neq\emptyset$. Lemma 3.29 tells us that
the number of projections with $\pi(S)\cap T\neq\emptyset$ is
$\leq|T|n^{k-1}\leq t|S|n^{k-1}\leq 1000tn^{k-1}$. Thus we established that
there are $\leq 1000tn^{k-1}$ good projections.

Suppose $|G^{\prime}|\leq 10^{-9}$. Lemma 3.30 tells us that there are $\leq
0.1n^{k}$ bad projections, and hence $\geq n^{k}-0.1n^{k}=0.9n^{k}$ good
projections. Thus $t\geq 0.9n/1000\geq 10^{-3000}n$.

Now suppose $|G^{\prime}|>10^{-9}n$: There are $|G^{\prime}|^{k}$ projections
with $\pi(v_{i})\in G^{\prime}$ for all $v_{i}\in F_{k}$ (using Lemma 3.19).
By Lemma 3.30, there are $\leq n^{k}/10^{8900}\leq 0.1(10^{-9}n)^{200}\leq
0.1(10^{-9}n)^{k}\leq 0.1|G^{\prime}|^{k}$ projections that don’t separate
$S$. Hence there remain $\geq 0.9|G^{\prime}|^{k}\geq 0.9\cdot 10^{-9k}n^{k}$
projections that both separate $S$ and have all $\pi(v_{i})\in G^{\prime}$
i.e. there are $\geq 0.9\cdot 10^{-9k}n^{k}$ good projections. Combining with
“there are $\leq 1000tn^{k-1}$ good projections”, this gives $t\geq 0.9\cdot
10^{-9k}n/1000\geq 10^{-3000}n.$ ∎

######  Lemma 3.32.

Let $p\geq n^{-1/700}$. Let $R_{A},R_{B},R_{C}$ be disjoint $p$-random
symmetric subsets of $G$ and set $R=R_{A}\cup R_{B}\cup R_{C}$. With high
probability, the following holds:

Let $k\leq 200$, $S\subseteq G\ast F_{k}$ a set of $\leq 600$ elements of
length $\leq 200$ which are each linear in at least one variable, and
$U\subseteq G$ with $|U|\leq p^{800}n/10^{4000}$. Then there is a projection
$\pi:G\ast F_{k}\to G$ which separates $S$ and has $\pi(S)\subseteq R\setminus
U$. Moreover:

  * •

For any $S_{A},S_{B},S_{C}\subseteq S$, with $S_{A}$, $S_{B}$, $S_{C}$ being
pairwise strongly separable sets, we can ensure $S_{A}\subseteq
R_{A},S_{B}\subseteq R_{B},S_{C}\subseteq R_{C}$.

  * •

If $|G^{\prime}|>10^{-9}n$, then we can additionally ensure that
$\pi(v_{i})\in G^{\prime}$ for all free variables $v_{i}$.

###### Proof.

We can assume that $n$ is sufficiently large (otherwise the lemma is vacuous
since “with high probability” wouldn’t mean anything). First fix $k\leq 200$,
and some set $S\subseteq G$, and $S_{A},S_{B},S_{C}\subseteq S$ as in the
lemma. Note $|\bigcup\hat{S}|\leq 2|S|\leq 800$. Fixing $m:=n/10^{3000}$,
apply Lemma 3.31 to get projections $\pi_{1},\dots,\pi_{m}$ which separate
$\bigcup\hat{S}$ and have
$\pi_{1}(\bigcup\hat{S}),\dots,\pi_{m}(\bigcup\hat{S})$ disjoint (and
additionally, when $|G^{\prime}|>10^{-9}n$, having that $\pi_{j}(v_{i})\in
G^{\prime}$ for all free variables $v_{i}$ and projections $\pi_{j}$).

Note that for each $i$ we have
$\pi_{i}(\hat{S}_{A}),\pi_{i}(\hat{S}_{B}),\pi_{i}(\hat{S}_{C})$ pairwise
disjoint. Indeed if say
$\pi_{i}(\hat{S}_{A})\cap\pi_{i}(\hat{S}_{B})\neq\emptyset$, then there would
be some $a\in S_{A},b\in S_{B}$ with $\pi_{i}(\hat{a})=\pi_{i}(\hat{b})$. We
know that $a,b$ separable, which implies that $\hat{a},\hat{b}$ are separable
(by Observation 3.23). But $\pi_{i}$ separates $\bigcup\hat{S}$, which shows
that $\hat{a},\hat{b}$ are disjoint.

For each $i$, $\hat{g}\in\pi_{i}(\hat{S})$, let

$ABC(\hat{g})=\begin{cases}A\text{ if $\hat{g}\in\pi_{i}(\hat{S}_{A})$}\\\
B\text{ if $\hat{g}\in\pi_{i}(\hat{S}_{B})$}\\\ C\text{ if
$\hat{g}\in\pi_{i}(\hat{S}_{C})$}\\\ C\text{ otherwise}\end{cases}.$

Note that this is well defined by the previous paragraph. For each
$i,\hat{g}\in\pi_{i}(S)$, let $E^{\hat{g}}_{i}$ be the event“$\hat{g}\subseteq
R_{ABC(\hat{g})}$”. Note that we have $P(E^{\hat{g}}_{i})=p$. Note that
$E^{\hat{g}}_{i},E^{\hat{h}}_{j}$ are independent for $\hat{g}\neq\hat{h}$
($E^{\hat{g}}_{i}$ depends only on the coordinate $\hat{g}$, $E^{\hat{h}}_{j}$
depends only on $\hat{h}$). Let
$E_{i}=\bigcap_{\hat{g}\in\pi_{i}(\hat{S})}E_{i}^{\hat{g}}$. We have
$\mathbb{P}(E_{i})=\prod_{\hat{g}\in\pi_{i}(\hat{S})}\mathbb{P}(E_{i}^{\hat{g}})\geq
p^{|S|}$. For all $i=1,\dots,m$, the events $E_{i}$ are independent (since
$E_{i},E_{j}$ depend on the coordinates in
$\pi_{i}(\bigcup\hat{S}),\pi_{j}(\bigcup\hat{S})$ respectively. These are
disjoint for $i\neq j$). By linearity of expectation, the expected number of
indices $i$ for which $E_{i}$ occurs is at least $p^{|S|}m$. By Chernoff’s
Bound, there are at least $p^{|S|}m/2$ indices for which $E_{i}$ occurs with
probability

$\geq 1-2e^{\frac{1}{6}p^{|S|}m}\geq
1-2e^{\frac{1}{6}(n^{-1/700})^{600}n/10^{3000}}\geq
1-2e^{-n^{1/9}/10^{6000}}.$

Since $|U|\leq p^{800}n/10^{4000}\leq p^{600}n/(2\cdot 10^{3000})=p^{|S|}m/2$,
there is at least one such index with $\pi_{i}(S)\cap U=\emptyset$. This
projection $\pi_{i}$ satisfies the lemma.

To get the lemma for all possible families $\\{k,S,S_{A},S_{B},S_{C}\\}$,
notice that there are $o(e^{n^{1/7}/36000})$ such families. Indeed, there are
$200$ choices for $k$ and for each $k$, there are $\leq 201(400n)^{201}$
length $\leq 200$ elements $w\in G\ast F_{k}$. There are
$\leq(201(400n)^{201})^{600}$ sets of $\leq 600$ such words. Hence, there are
$\leq((201(400n)^{201})^{600})^{4}=o(e^{n^{1/37}/36000})$ families of
$4$-tuples of such subsets. So we can take a union bound over all such
families. ∎

######  Corollary 3.33.

Let $p\geq 3n^{-1/1400}$. Let $R$ be random set which is either $p$-random or
symmetric $p$-random. With high probability, the following holds:

Let $k\leq 200$, $S\subseteq G\ast F_{k}$ a set of $\leq 600$ elements of
length $\leq 200$ which are each linear in at least one variable, and
$U\subseteq G$ with $|U|\leq p^{1600}n/10^{4002}$. Then there is a projection
$\pi:G\ast F_{k}\to G$ which separates $S$ and has $\pi(S)\subseteq R\setminus
U$.

###### Proof.

Using Lemma 3.16, we can choose random sets $R_{A},R_{B},R_{C}\subseteq R$
such that the joint distribution on $R_{A},R_{B},R_{C}$ is that of disjoint
symmetric $p^{2}/9$-random sets. Now, the lemma follows from Lemma 3.32. ∎

We end with a simple application of the above lemma for later use.

######  Lemma 3.34.

Let $p\geq n^{-1/700}$. Let $G$ be a group $R$ a symmetric $p$-random subset
of $G$. With high probability, the following holds.

For any generic $x_{\phi}\in G$ and $U\subseteq V(H_{G})$ with $|U|\leq
p^{800}n/10^{4001}$, there are distinct and $\phi$-generic $x,x^{\prime}\in
R\setminus U$ with $xx^{\prime}=x_{\phi}$.

###### Proof.

With high probability, Lemma 3.32 applies. Let $x_{\phi}$, $U$ be as in the
lemma. Add all non-$\phi$-generic elements to $U$ in order to get a set
$U^{\prime}$ with $|U^{\prime}|\leq p^{800}n/10^{4000}$. Let $x_{\phi}\in G$
and consider the set $\\{v_{1},x_{\phi}v_{1}^{-1}\\}\subseteq G\ast F_{1}$.
Note that $v_{1},x_{\phi}v_{1}^{-1}$ are separable (by part (b) of the
definition), and so Lemma 3.32 gives a projection $\pi:G\ast F_{1}\to G$ with
$\pi(v_{1}),\pi(x_{\phi}v_{1}^{-1})$ distinct and contained in $R\setminus
U^{\prime}$ setting $x=\pi(x_{\phi}v_{1}^{-1}),x^{\prime}=\pi(v_{1})$ gives
the lemma. ∎

##  4 The main theorem and its variants

This section is devoted to stating the main technical result of the paper, and
collecting various consequences thereof (including Theorem 1.1) which will be
more convenient to use for various applications we give. For the applications,
we need variants of Theorem 1.1, where the probability distributions on
$R^{1},R^{2},R^{3}$ are different from the one given (e.g. it is sometimes
useful to sample $R^{1},R^{2},R^{3}$ disjointly rather than independently). We
begin by stating a more technical version of Theorem 1.1 which covers all the
different distributions of these sets that we might need. The following
definition is the most general case.

######  Definition 4.1.

Let $G$ be a group and let $R_{1},R_{2},R_{3}$ be random subsets of $G$. We
say that $R_{1},R_{2},R_{3}$ are $q$-slightly-independent, if there random
subsets $Q^{1}\subseteq R^{1}$, $Q^{2}\subseteq R^{2}$, $Q^{3}\subseteq R^{3}$
such that the joint distribution on $Q^{1},Q^{2},Q^{3}$ is that of disjoint
symmetric, $q$-random subsets of $G$.

The following observation about this definition is useful.

######  Observation 4.2.

If $R_{1},R_{2},R_{3}$ are $q$-slightly-independent, then so are
$R_{1},R_{2}^{-1},R_{3}$.

###### Proof.

We have $Q^{1}\subseteq R^{1}$, $Q^{2}\subseteq R^{2}$, $Q^{3}\subseteq R^{3}$
such that the joint distribution on $Q^{1},Q^{2},Q^{3}$ is that of disjoint,
symmetric, $q$-random subsets of $G$. Note that since $Q^{2}$ is symmetric,
$Q^{2}=(Q^{2})^{-1}$. Also, $(Q^{2})^{-1}\subseteq(R^{2})^{-1}$. Thus,
$Q^{1},Q^{2},Q^{3}$ witness $R_{1},R_{2}^{-1},R_{3}$ being $q$-slightly-
independent. ∎

The following is the strongest version of the main theorem that we prove in
this paper. It is proved in Section 5.

######  Theorem 4.3.

Let $q\geq n^{-1/10^{101}}$. Let $G$ be a group of order $n$. Let
$R^{1},R^{2},R^{3}\subseteq G$ be $p$-random, $q$-slightly-independent
subsets. Then, with high probability, the following holds.

Let $X,Y,Z$ be equal-sized subsets of $G_{A}$, $G_{B}$, and $G_{C}$
respectively, satisfying the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\Delta(X\cup Y\cup Z)|\leq
q^{10^{17}}n/\log(n)^{10^{17}}$

  * •

$\sum X+\sum Y+\sum Z=0$ (in $G^{\mathrm{ab}}$)

  * •

${e}_{G}\notin X\cup Y\cup Z$

Then, $H_{G}[X,Y,Z]$ contains a perfect matching.

We now state and prove a number of consequences of this theorem, where the
distributions on $R^{1},R^{2},R^{3}$ are more natural. Firstly, the following
theorem is equivalent to Theorem 1.1 (we will prove this formally later on in
the section).

######  Theorem 4.4.

Let $p\geq n^{-1/10^{102}}$. Let $G$ be a group of order $n$. Let
$R^{1},R^{2},R^{3}\subseteq G$ be $p$-random subsets, sampled independently.
Then, with high probability, the following holds.

Let $X,Y,Z$ be equal-sized subsets of $G_{A}$, $G_{B}$, and $G_{C}$
respectively, satisfying the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\Delta(X\cup Y\cup Z)|\leq
p^{10^{18}}n/\log(n)^{10^{18}}$

  * •

$\sum X+\sum Y+\sum Z=0$ (in $G^{\mathrm{ab}}$)

Then, $H_{G}[X,Y,Z]$ contains a perfect matching.

When $R^{1},R^{2},R^{3}$ are sampled disjointly, then the statement of the
theorem needs to change slightly. In this case, when the group is
$\mathbb{Z}_{2}^{k}$, then it is impossible to cover ${e}$ with a hyperedge
contained in $R^{1}\cup R^{2}\cup R^{3}$. Thus to get a matching, we need to
additionally have the condition “${e}_{G}\notin X\cup Y\cup Z$ if
$G\cong\mathbb{Z}_{2}^{k}$” (Proposition 3.12 shows that this is the only
local obstruction of this type).

######  Theorem 4.5.

Let $q\geq n^{-1/10^{102}}$. Let $G$ be a group of order $n$. Let
$R^{1},R^{2},R^{3}\subseteq G$ be $p$-random disjoint subsets. Then, with high
probability, the following holds.

Let $X,Y,Z$ be equal-sized subsets of $G_{A}$, $G_{B}$, and $G_{C}$
respectively, satisfying the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\Delta(X\cup Y\cup Z)|\leq
p^{10^{18}}n/\log(n)^{10^{18}}$

  * •

$\sum X+\sum Y+\sum Z=0$ (in $G^{\mathrm{ab}}$)

  * •

${e}_{G}\notin X\cup Y\cup Z$ if $G\cong\mathbb{Z}_{2}^{k}$.

Then, $H_{G}[X,Y,Z]$ contains a perfect matching.

Finally, we have two versions of the theorem which are intermediate between
the previous two. First one which asks $R^{1},R^{2}$ to be sampled disjointly,
and $R^{3}$ to be sampled independently.

######  Theorem 4.6.

Let $p\geq n^{-1/10^{102}}$. Let $G$ be a group of order $n$. Let
$R^{1},R^{2}\subseteq G$ be disjoint $p$-random subsets, and let
$R^{3}\subseteq G$ be a $p$-random subset, sampled independently with $R^{1}$
and $R^{2}$. Then, with high probability, the following holds.

Let $X,Y,Z$ be subsets of $G_{A}$, $G_{B}$, and $G_{C}$ be equal sized subsets
satisfying the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\triangle(X\cup Y\cup Z)|\leq
p^{10^{18}}n/\log(n)^{10^{18}}$

  * •

$\sum X+\sum Y+\sum Z=0$ (in the abelianization of $G$)

  * •

If $G=(\mathbb{Z}_{2})^{k}$ for some $k$, suppose that ${e}\notin Z$.

Then, $H_{G}[X,Y,Z]$ contains a perfect matching.

The next theorem is almost the same as the previous one, with the difference
that we sample $(R^{1})^{-1},R^{2}$ disjointly (as opposed to $R^{1},R^{2}$).

######  Theorem 4.7.

Let $p\geq n^{-1/10^{102}}$. Let $G$ be a group of order $n$. Let
$(R^{1})^{-1},R^{2}\subseteq G$ be disjoint $p$-random subsets, and let
$R^{3}\subseteq G$ be a $p$-random subset, sampled independently with $R^{1}$
and $R^{2}$. Then, with high probability, the following holds.

Let $X,Y,Z$ be subsets of $G_{A}$, $G_{B}$, and $G_{C}$ be equal sized subsets
satisfying the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\triangle(X\cup Y\cup Z)|\leq
p^{10^{18}}n/\log(n)^{10^{18}}$

  * •

$\sum X+\sum Y+\sum Z=0$ (in the abelianization of $G$)

  * •

If $G=(\mathbb{Z}_{2})^{k}$ for some $k$, suppose that ${e}\notin Z$.

Then, $H_{G}[X,Y,Z]$ contains a perfect matching.

These theorems all have almost the same proof. The idea is to first show that
the distribution of $R_{1},R_{2},R_{3}$ is $q$-slightly-independent (and so
Theorem 4.3) applies. When the sets $X,Y,Z$ don’t contain the identity, then
this already gives what we want. When $X,Y,Z$ do contain the identity, then we
first find a small matching covering all copies of the identity in $X,Y,Z$,
and then find another matching covering all remaining vertices using Theorem
4.3.

###### Proof of Theorem 4.5.

Note that $R_{1},R_{2},R_{3}$ are $q$-slightly-independent for $q=p^{2}/9$. To
see this, consider disjoint $1/3$-random sets $T_{1},T_{2},T_{3}\subseteq G$,
chosen independently of $R_{1},R_{2},R_{3}$. We have that $R_{1}\cap
T_{1},R_{2}\cap T_{2},R_{3}\cap T_{3}$ are disjoint $p/3$-random subsets of
$G$. Indeed for every $g\in G$, we have $\mathbb{P}(g\in R_{i}\cap
T_{i})=\mathbb{P}(g\in R_{i})\mathbb{P}(g\in T_{i})=p/3$, and $\mathbb{P}(g\in
R_{i}\cap T_{i}\cap R_{j}\cap T_{j})\leq\mathbb{P}(g\in T_{i}\cap T_{j})=0$.
These imply $\mathbb{P}(g\not\in\bigcup_{i=1}^{3}R_{i}\cap T_{i})=1-3\alpha
p$. Also for different $g,h$, their locations are independent of each other
(since there was no correlations between distinct $g,h$, in any of
$R_{1},R_{2},R_{3},T_{1},T_{2},T_{3}$), giving that $R_{1}\cap T_{1},R_{2}\cap
T_{2},R_{3}\cap T_{3}$ are disjoint $p/3$-random subsets of $G$. Use Lemma
3.16 to pick disjoint, symmetric, $q$-random subsets $Q_{1}\subseteq R_{1}\cap
T_{1},Q_{2}\subseteq R_{2}\cap T_{2},Q_{3}\subseteq R_{3}\cap T_{3}$. Now
$Q_{1},Q_{2},Q_{3}$ demonstrate $R_{1},R_{2},R_{3}$ being $q$-slightly-
independent.

So Theorem 4.3 applies to $R_{1},R_{2},R_{3}$. We also have the following
property if $G\neq\mathbb{Z}_{2}^{k}$:

  * P:

For each $i,j\in\\{1,2,3\\}$, $i\neq j$, $R^{i}\times R^{j}$ contains $\geq
p^{2}n/1000$ pairs of the form $(x,x^{-1})$ where for each such pair
$\\{x,x^{-1}\\}\cap\\{y,y^{-1}\\}=\emptyset$ (this follows by Chernoff’s
bound).

Now consider sets $X,Y,Z$ as in the theorems. Use $(P)$ to pick distinct
elements $g_{A},g_{B},g_{C}$ with $g_{A}\in R^{2}$, $g_{A}^{-1}\in R^{3}$,
$g_{B}\in R^{1}$, $g_{B}^{-1}\in R^{3}$, $g_{C}\in R^{1}$, $g_{C}^{-1}\in
R^{2}$. Noting that we have $p^{2}n/1000$ choices for each
$g_{A},g_{B},g_{C}$, we can choose them to have
$\\{g_{A},g_{A}^{-1}\\},\\{g_{B},g_{B}^{-1}\\},\\{g_{C},g_{C}^{-1}\\}$
disjoint from each other and from $R^{1}\setminus X,R^{2}\setminus
Y,R^{3}\setminus Z$. The result is that the three edges
$f_{A}:=({e}_{A},g_{A},g_{A}^{-1}),f_{B}:=(g_{B},{e}_{B},g_{B}^{-1}),f_{C}:=(g_{C},g_{C}^{-1},{e}_{C})\\}$
form a matching with all vertices, other than possibly
${e}_{B},{e}_{B},{e}_{C}$ contained in $X\cup Y\cup Z$. Let
$N=\\{f_{i}:{e}_{i}\in X\cup Y\cup Z\\}$ to get a matching contained in $X\cup
Y\cup Z$ covering all copies of the identity in $X\cup Y\cup Z$.

Let $X^{\prime}=X\setminus N,Y^{\prime}=Y\setminus N,Z^{\prime}=Z\setminus N$,
noting that these have the same size and have $\sum X^{\prime}+\sum
Y^{\prime}+\sum Z^{\prime}=0$ in $G^{ab}$ (due to $N$ being a matching). Thus
the property of Theorem 4.3 applies to give a perfect matching $M$ in
$H_{G}[X^{\prime},Y^{\prime},Z^{\prime}]$. Now $M\cup N$ satisfies the
theorem. ∎

Next we show how to modify the above proof to obtain Theorems 4.4, 4.6, 4.7.

###### Proof of Theorems 4.4, 4.6, 4.7.

First notice that in all three theorems, we have that $R^{1},R^{2},R^{3}$ are
$q$-slightly-independent. In Theorems 4.4, 4.6 this is exactly the first
paragraph of the proof of Theorem 4.5. For Theorem 4.7, that paragraph shows
that $(R^{1})^{-1},R^{2},R^{3}$ are $q$-slightly-independent. But, then by
Observation 4.2, we have that $R^{1},R^{2},R^{3}$ are $q$-slightly-
independent.

Next note that property (P) holds in the following cases:

  * •

Theorem 4.4: here property (P) always holds.

  * •

Theorem 4.6: here property (P) always holds for $(i,j)=(2,3)$ and
$(i,j)=(1,3)$. For $(i,j)=(1,2)$ property (P) holds when
$G\neq\mathbb{Z}_{2}^{k}$.

  * •

Theorem 4.7: here property (P) always holds for $(i,j)=(2,3)$ and
$(i,j)=(1,3)$. For $(i,j)=(1,2)$ property (P) holds when
$G\neq\mathbb{Z}_{2}^{k}$.

The rest of the proofs are the same as in Theorem 4.5 — property (P) produces
a matching of size $\leq 3$ covering all copies of the identity in $X\cup
Y\cup Z$, and then the property of Theorem 4.3 gives a matching covering the
rest of $X\cup Y\cup Z$. ∎

Finally we show how to derive Theorem 1.1 as stated in the introduction.

###### Proof of Theorem 1.1 via Theorem 4.4.

Let $R^{1},R^{2},R^{3}\subseteq G$ be $p$-random subsets, independently
sampled. Observe that $R^{1},R^{2},(R^{3})^{-1}\subseteq G$ are also
$p$-random subsets, independently sampled, hence with high probability Theorem
4.4 holds. Let $X,Y,Z\subseteq G$ be subsets with the properties as in the
statement of Theorem 1.1. Then, the sets $X,Y,Z^{-1}\subseteq G$ clearly
satisfy the two properties required by Theorem 4.4 with respect to
$R^{1},R^{2},(R^{3})^{-1}\subseteq G$. Thus, $H_{G}[X,Y,Z^{-1}]$ contains a
perfect matching, say $M$. Define the bijection $\phi\colon X\to Y$ so that
$x$ maps to the unique element $y$ of $Y$ such that $x$ and $y$ are contained
in an edge together in $M$. As for each edge $(x,\phi(x),z)$ of $M$,
$x\phi(x)z={e}$, $x\mapsto x\phi(x)$ is a bijection $X\to(Z^{-1})^{-1}=Z$, as
desired. ∎

###  4.1 Complete mappings and orthomorphisms

We conclude this section with a version of the main theorem that fits better
with the results proved in Section 6.2. Given a triple of subsets of a group
$G$ as $(X,Y,Z)$, a complete mapping is a bijection $\phi\colon X\to Y$ such
that the induced map from $X$ to $Z$ via $x\to x\phi(x)$ is also a bijection,
whereas an orthomorphism is a bijection $\phi\colon X\to Y$ such that the
induced map from $X$ to $Z$ via $x\to x^{-1}\phi(x)$ is also a bijection.

######  Observation 4.8.

Let $X,Y,Z$ be subsets of a group $G$. Then,

  * •

$(X,Y,Z)$ admits a complete mapping if and only if $H_{G}[X,Y,Z^{-1}]$ has a
perfect matching.

  * •

$(X,Y,Z)$ admits an orthomorphism if and only if $H_{G}[X^{-1},Y,Z^{-1}]$ has
a perfect matching.

###### Proof.

Note that $x\phi(x)=z$ if and only if $x\phi(x)z^{-1}={e}$. As $z\to z^{-1}$
is a bijection between $Z$ and $Z^{-1}$, we have that whenever $\phi$ is a
complete mapping of $X,Y,Z$, we have a perfect matching of $H_{G}[X,Y,Z^{-1}]$
given by the edges of the form $(x,\phi(x),\phi(x)^{-1}x^{-1})$. Given a
perfect matching of $H_{G}[X,Y,Z^{-1}]$, we can similarly define $\phi$ so
that $\phi$ maps the $G_{A}$ coordinate of each matched edge to the $G_{B}$
coordinate to get a complete mapping of $(X,Y,(Z^{-1})^{-1})=(X,Y,Z)$. This
proves the first bullet point.

Similarly, $x^{-1}\phi(x)=z$ if and only if $x^{-1}\phi(x)z^{-1}={e}$. Since
$x\to x^{-1}$ is also a bijection between $X$ and $X^{-1}$, if $\phi$ is an
orthomorphism of $X,Y,Z$, we have a perfect matching of
$H_{G}[X^{-1},Y,Z^{-1}]$ given by the edges of the form
$(x^{-1},\phi(x),z^{-1})$. And given a perfect matching of
$H_{G}[X^{-1},Y,Z^{-1}]$, taking $\phi$ to map the inverse of the $G_{A}$
coordinate of each matched edge into the $G_{B}$ coordinate of that same
matched edge, we obtain an orthomorphism of
$((X^{-1})^{-1},Y,(Z^{-1})^{-1})=(X,Y,Z)$. This proves the second bullet
point. ∎

######  Theorem 4.9.

Let $p\geq n^{-1/10^{102}}$. Let $G$ be a group of order $n$. Let
$R^{1},R^{2}\subseteq G$ be disjoint $p$-random subsets, and let
$R^{3}\subseteq G$ be a $p$-random subset, sampled independently with $R^{1}$
and $R^{2}$. Then, with high probability, the following holds.

Let $X,Y,Z$ be equal-sized subsets of $G_{A}$, $G_{B}$, and $G_{C}$ satisfying
the following properties.

  * •

$|(R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C})\triangle(X\cup Y\cup Z)|\leq
p^{10^{18}}n/\log(n)^{10^{18}}$

  * •

One of the following identities holds in the abelianization of $G$.

    * C.

$\sum X+\sum Y=\sum Z$

    * O.

$\sum Y-\sum X=\sum Z$

  * •

If $G=(\mathbb{Z}_{2})^{k}$ for some $k$, then ${e}\notin Z$.

Then, if C holds, $(X,Y,Z)$ admits a complete mapping, and if O holds,
$(X,Y,Z)$ admits an orthomorphism.

###### Proof.

Observe that $R^{1},R^{2},(R^{3})^{-1}\subseteq G$ are each $p$-random
subsets, and $(R^{3})^{-1}$ is also a random subset sampled independently with
$R^{1}$ and $R^{2}$. So Theorem 4.6 applies to $R^{1},R^{2},(R^{3})^{-1}$ with
high probability. Also, the random sets $(R^{1})^{-1},R^{2},(R^{3})^{-1}$ have
the property that the inverse of the first random set is sampled disjointly
with the second, and the third is sampled independently with the first two. So
Theorem 4.7 applies to these random subsets.

Suppose both properties above hold, and fix $X,Y,Z$ be given with the listed
properties. Suppose C holds. Then, $X,Y,Z^{-1}$ satisfy the properties
required with respect to $R^{1},R^{2},(R^{3})^{-1}$ so $H_{G}[X,Y,Z^{-1}]$ has
a perfect matching by Theorem 4.6, implying that $(X,Y,Z)$ has a complete
mapping by Observation4.8. Suppose instead that C holds. Then,
$X^{-1},Y,Z^{-1}$ satisfy the properties required with respect to
$(R^{1})^{-1},R^{2},(R^{3})^{-1}$ so $H_{G}[X^{-1},Y,Z^{-1}]$ has a perfect
matching by Theorem 4.7, implying that $(X,Y,Z)$ has an orthomorphism by
Observation 4.8. ∎

##  5 Proof of the main theorem

In this section, we prove the main result of the paper, Theorem 4.3. We begin
by clarifying that for every (sufficiently large) group $G$, we fix
$a_{\phi},b_{\phi},c_{\phi}\in G$ with properties as in Section 3.4.
Definitions such as $\phi$-generic, pair, and coset-paired are with respect to
these fixed choices of $a_{\phi},b_{\phi},c_{\phi}\in G$ given by Lemma 3.14.

###  5.1 Absorbers

In this section we give constructions of absorbers i.e. subsets $R\subseteq
V(H_{G})$ which can be extended into a matching in several different ways.
Lemma 5.24 is the main result of this section, and the only result we need for
the rest of the paper. The following definition precisely describes what we
will be looking for.

######  Definition 5.1.

Let $\mathcal{F}=\\{S_{1},\dots,S_{t}\\}$ be a family of subsets of $V(H)$ for
a hypergraph $H$. We say that a set of vertices $R$ $m$-absorbs $\mathcal{F}$
if for every subfamily $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of size $m$,
there is a hypergraph matching whose vertex set is exactly
$R\cup\bigcup_{S_{i}\in\mathcal{F}^{\prime}}S_{i}$.

It will be convenient to note that when $t=2$ and $m=1$, then the above
definition is equivalent to “Let $X,Y$ be sets of vertices in a hypergraph
$H$. We say that a set of vertices $R$ $1$-absorbs $\\{X,Y\\}$ if there are
hypergraph matchings $R^{-},R^{+}$ whose vertex sets are exactly
$V(R^{-})=R\cup X$ and $V(R^{+})=R\cup Y$.”

The following lemma shows how the parameter $h$ changes when we pass to a
subfamily of $\mathcal{F}$.

######  Lemma 5.2.

Let $\mathcal{F}$ be a family of disjoint subsets of $V(H)$ and
$\mathcal{F}^{\prime}\subseteq F$ a subfamily with
$|\mathcal{F}\setminus\mathcal{F}^{\prime}|=t$. If $R$ $h$-absorbs
$\mathcal{F}$ then

  1. 1.

$R$ $h$-absorbs $\mathcal{F}^{\prime}$.

  2. 2.

$R\cup\bigcup_{S\in\mathcal{F}\setminus\mathcal{F}^{\prime}}S$ $(h-t)$-absorbs
$\mathcal{F}^{\prime}$.

###### Proof.

Part (1) is immediate from the definition of absorbing. For part (2), notice
that for any subfamily
$\mathcal{F}^{\prime\prime}\subseteq\mathcal{F}^{\prime}$ of size $h-t$, the
subfamily
$\mathcal{F}^{\prime\prime}\cup(\mathcal{F}\setminus\mathcal{F}^{\prime})$ has
size $h$. Therefore there is a matching with vertex set
$R\cup\bigcup_{S\in\mathcal{F}^{\prime\prime}\cup(\mathcal{F}\setminus\mathcal{F}^{\prime})}S=(R\cup\bigcup_{S\in\mathcal{F}\setminus\mathcal{F}^{\prime}}S)\cup\bigcup_{S\in\mathcal{F}^{\prime\prime}}S$.
∎

We build larger absorbers from smaller ones. The following lemma allows us to
take unions of $1$-absorbers to get another $1$-absorber.

######  Lemma 5.3.

Suppose that
$\\{R_{1},\dots,R_{t}\\},\\{X_{1},\dots,X_{t}\\},\\{Y_{1},\dots,Y_{t}\\}$ are
three families of disjoint sets with $\bigcup R_{i}$ disjoint from
$\bigcup(X_{i}\cup Y_{i})$. Suppose that $R_{i}$ 1-absorbs $\\{X_{i},Y_{i}\\}$
for $i=1,\dots,t$. Set $Z=(\bigcup X_{i})\cap(\bigcup Y_{i})$. Then, $\bigcup
R_{i}\cup Z$ 1-absorbs $\\{\bigcup X_{i}\setminus Z,\bigcup Y_{i}\setminus
Z\\}$.

###### Proof.

By the definition of $1$-absorbs we have matchings $R_{i}^{-}$ and $R_{i}^{+}$
with vertices $V(R_{i}^{-})=R_{i}\cup X_{i}$ and $V(R_{i}^{+})=R_{i}\cup
Y_{i}$. Note that $\bigcup R_{i}^{-}$ and $\bigcup R_{i}^{+}$ are matchings
(since
$\\{R_{1},\dots,R_{t}\\},\\{X_{1},\dots,X_{t}\\},\\{Y_{1},\dots,Y_{t}\\}$ are
families of disjoint sets with $\bigcup R_{i}$ disjoint from
$\bigcup(X_{i}\cup Y_{i})$). Also $V(\bigcup R_{i}^{-})=\bigcup
R_{i}\cup\bigcup X_{i}=(\bigcup R_{i}\cup Z)\cup(\bigcup X_{i}\setminus Z)$
and $V(\bigcup R_{i}^{+})=\bigcup R_{i}\cup\bigcup Y_{i}=(\bigcup R_{i}\cup
Z)\cup(\bigcup Y_{i}\setminus Z)$. Thus $\bigcup R_{i}^{-}$ and $\bigcup
R_{i}^{+}$ are matchings satisfying the definition of “$\bigcup R_{i}\cup Z$
1-absorbs $\\{\bigcup X_{i}\setminus Z,\bigcup Y_{i}\setminus Z\\}$”. ∎

We state a technical consequence of the above lemma for later use.

######  Lemma 5.4.

Suppose that we have distinct vertices $a,b,c,d\in V(H_{G})$, vertices
$w_{1},\dots,w_{k}\in V(H_{G})\setminus\\{a,b,c,d\\}$ and disjoint sets
$R_{0},R_{1},\dots,R_{k-1}\subseteq
V(H_{G})\setminus\\{w_{1},\dots,w_{k},a,b,c,d\\}$ with $R_{0}$ 1-absorbing
$\\{\\{a,w_{1},b\\},\\{a,w_{k},b\\}\\}$ and $R_{i}$ 1-absorbing
$\\{w_{i},w_{i+1}\\}$ for $i=1,\dots,k-1$. Then, there is a subset
$R^{\prime}\subseteq\bigcup_{i=0}^{k-1}R_{i}\cup\\{w_{1},\dots,w_{k}\\}$ which
1-absorbs $\\{\\{a,b\\},\\{c,d\\}\\}$.

###### Proof.

Without loss of generality, we can assume that $w_{1},\dots,w_{k}$ are
distinct (by passing to a subset of $\\{w_{1},\dots,w_{k}\\}$ of distinct
vertices, and a corresponding subfamily of $\\{R_{1},\dots,R_{k-1}\\}$). Now,
the lemma follows from Lemma 5.3 with $\\{R_{0},\dots,R_{k}\\}$,

$\\{X_{0},\dots,X_{k}\\}:=\\{\\{a,w_{1},b\\},\\{w_{2}\\},\\{w_{3}\\},\dots,\\{w_{k}\\}\\},$

and

$\\{Y_{1},\dots,Y_{t}\\}:=\\{\\{c,w_{k},d\\},\\{w_{1}\\},\\{w_{2}\\},\dots,\\{w_{k-1}\\}\\}.$

∎

####  5.1.1 Constructing $1$-absorbing sets

The following lemma shows that there are many edges through generic vertices
in $H_{G}$.

######  Lemma 5.5.

Let $p\geq n^{-1/700}$. Let $H_{G}$ be a multiplication hypergraph,
$R^{1},R^{2},R^{3}$ disjoint, symmetric $p$-random subsets of $G$ and set
$R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$. With high probability, the
following holds:

For any generic $v\in V(H_{G})$ and $U\subseteq V(H_{G})$ with $|U|\leq
p^{800}n/10^{4000}$, there is an edge $e$ of $H_{G}$ passing through $v$ and
having the other two vertices in $R\setminus U$.

###### Proof.

With high probability, Lemma 3.32 applies. We’ll just look at the case $v\in
G_{A}$, the other two cases are symmetric. Fix some generic $v\in G_{A}$.
Thinking of $b$ as a free variable, consider the set
$S=\\{b,b^{-1}v^{-1}\\}\subseteq G\ast F_{1}$. Note that this is a set of
linear elements with $w=b,w^{\prime}=b^{-1}v^{-1}$ separable (by (b) since
$v^{-1}$ is generic). Lemma 3.32 now implies what we want. ∎

The following is the basic building block for the absorbers that we construct.
It shows that we can $1$-absorb sets of the form $\\{[a,b]c,c\\}$.

######  Lemma 5.6.

Let $p\geq n^{-1/700}$. Let $H_{G}$ be a multiplication hypergraph,
$R^{1},R^{2},R^{3}$ disjoint, symmetric $p$-random subsets of $G$ and set
$R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$. With high probability, the
following holds:

For any $a,b,c\in G_{A}$ with
$c,c^{-1}bab^{-1}a^{-1},c^{-1}bab^{-1},c^{-1}ba,c^{-1}b$ generic and
$U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4010}$, there is a set
$R^{\prime}\subseteq R\setminus U$ of size $\leq 14$ which $1$-absorbs
$\\{[a,b]c,c\\}$.

###### Proof.

With high probability, the properties of Lemmas 3.32 and 5.5 hold. Fix some
$a,b,c\in G_{A}$ with

$c,c^{-1}bab^{-1}a^{-1},c^{-1}bab^{-1},c^{-1}ba,c^{-1}b$

all being generic and $U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4010}$.
First suppose that $[a,b]={e}$ i.e. that $[a,b]c=c$. From Lemma 5.5 we know
that there is an edge $e=\\{c,s,t\\}$ of $H_{G}$ with $s,t\in R\setminus U$.
Then $R^{\prime}=\\{s,t\\}$ satisfies the lemma (with both $M^{-}$ and $M^{+}$
for the definition of “$1$-absorbs” equal to the single edge $e$).

Figure 2: The set $S\subseteq G\ast F_{3}$ in Lemma 5.6. Black letters $x,y,z$
are free variables, while pink letters are elements of $G$. The two elements
$[a,b]c$, $c$ are not part of $S$ (and are just pictured to show how $S$
$1$-absorbs $\\{[a,b]c,c\\}$).

$S_{x}:$ $x$ $x^{-1}\color[rgb]{1,0,1}c^{-1}$
$x^{-1}{\color[rgb]{1,0,1}c^{-1}bab^{-1}a^{-1}}$
$x^{-1}{\color[rgb]{1,0,1}c^{-1}bab^{-1}}$
$x^{-1}{\color[rgb]{1,0,1}c^{-1}ba}$ $x^{-1}{\color[rgb]{1,0,1}c^{-1}b}$ $x$
$\color[rgb]{1,0,1}c^{-1}$ ${\color[rgb]{1,0,1}c^{-1}bab^{-1}a^{-1}}$
${\color[rgb]{1,0,1}c^{-1}bab^{-1}}$ ${\color[rgb]{1,0,1}c^{-1}ba}$
${\color[rgb]{1,0,1}c^{-1}b}$ $x^{-1}\color[rgb]{1,0,1}c^{-1}$
$\color[rgb]{1,0,1}c^{-1}$ ${\color[rgb]{1,0,1}bab^{-1}a^{-1}}$
${\color[rgb]{1,0,1}bab^{-1}}$ ${\color[rgb]{1,0,1}ba}$
${\color[rgb]{1,0,1}b}$ $x^{-1}{\color[rgb]{1,0,1}c^{-1}bab^{-1}a^{-1}}$
${\color[rgb]{1,0,1}c^{-1}bab^{-1}a^{-1}}$
${\color[rgb]{1,0,1}bab^{-1}a^{-1}}$ ${\color[rgb]{1,0,1}a^{-1}}$
${\color[rgb]{1,0,1}b^{-1}a^{-1}}$ ${\color[rgb]{1,0,1}ab^{-1}a^{-1}}$
$x^{-1}{\color[rgb]{1,0,1}c^{-1}bab^{-1}}$
${\color[rgb]{1,0,1}c^{-1}bab^{-1}}$ ${\color[rgb]{1,0,1}bab^{-1}}$
${\color[rgb]{1,0,1}a^{-1}}$ ${\color[rgb]{1,0,1}b^{-1}}$
${\color[rgb]{1,0,1}ab^{-1}}$ $x^{-1}{\color[rgb]{1,0,1}c^{-1}ba}$
${\color[rgb]{1,0,1}c^{-1}ba}$ ${\color[rgb]{1,0,1}ba}$
${\color[rgb]{1,0,1}b^{-1}a^{-1}}$ ${\color[rgb]{1,0,1}b^{-1}}$
${\color[rgb]{1,0,1}a}$ $x^{-1}{\color[rgb]{1,0,1}c^{-1}b}$
${\color[rgb]{1,0,1}c^{-1}b}$ ${\color[rgb]{1,0,1}b}$
${\color[rgb]{1,0,1}ab^{-1}a^{-1}}$ ${\color[rgb]{1,0,1}ab^{-1}}$
${\color[rgb]{1,0,1}a}$

$S_{x,y}:$ $y^{-1}{\color[rgb]{1,0,1}aba^{-1}b^{-1}c}x$
$y^{-1}{\color[rgb]{1,0,1}b^{-1}c}x$
$y^{-1}{\color[rgb]{1,0,1}aba^{-1}b^{-1}c}x$ ${\color[rgb]{1,0,1}aba^{-1}}$
$y^{-1}{\color[rgb]{1,0,1}b^{-1}c}x$ ${\color[rgb]{1,0,1}aba^{-1}}$ $S_{y}:$
$y$ ${\color[rgb]{1,0,1}a^{-1}}y$ $y$ ${\color[rgb]{1,0,1}a^{-1}}$
${\color[rgb]{1,0,1}a^{-1}}y$ ${\color[rgb]{1,0,1}a^{-1}}$ $S_{x,z}:$
$z^{-1}{\color[rgb]{1,0,1}ba^{-1}b^{-1}c}x$ $z^{-1}{\color[rgb]{1,0,1}c}x$
$z^{-1}{\color[rgb]{1,0,1}ba^{-1}b^{-1}c}x$
${\color[rgb]{1,0,1}ba^{-1}b^{-1}}$ $z^{-1}{\color[rgb]{1,0,1}c}x$
${\color[rgb]{1,0,1}ba^{-1}b^{-1}}$ $S_{z}:$ $z$ ${\color[rgb]{1,0,1}b^{-1}}z$
$z$ ${\color[rgb]{1,0,1}b^{-1}}$ ${\color[rgb]{1,0,1}b^{-1}}z$
${\color[rgb]{1,0,1}b^{-1}}$

Figure 3: Proofs for weak/strong separability and linearity of all pairs
$w,w^{\prime}\in S$ in Lemma 5.6 to justify the application of Lemma 3.32. For
separability, first we have partitioned $S$ into five subsets $S=S_{x}\cup
S_{x,y}\cup S_{x,z}\cup S_{z}\cup S_{y}$ based on which free variables appear
in each $w\in S$ (as in Observation 3.24). By Observation 3.24, any
$w,w^{\prime}$ in different subsets are strongly separable by part (a) of the
definition. For each of the sets $S_{x},S_{x,y},S_{x,z},S_{z},S_{y}$ we give a
table explaining why the $w,w^{\prime}$ in that set are strongly/weakly-
separable. Note that for words coming from different $S_{A}/S_{B}/S_{C}$ we
need to show strong separability, but for words coming from the same part,
weak separability suffices. Blue cells represent $w,w^{\prime}$ being
separable via part (b) of the definition of “separable”, green cells represent
$w,w^{\prime}$ being weakly separable via part (b’), and grey cells represent
$w,w^{\prime}$ not being separable/weakly-separable. The group element inside
each blue cell is a generic element $g$ so that
$w^{\prime}\in\\{gw,g^{-1}w,gw^{-1},g^{-1}w^{-1},wg,wg^{-1},w^{-1}g,w^{-1}g^{-1}\\}$
(thus checking (b) for $w,w^{\prime}$). The group element inside the green
cells is a non-identity element $g$ so that $w=w^{\prime}$ rearranges into
${e}=g$ (thus checking (b’) for $w,w^{\prime}$). Observe that green cells are
used only between pairs of words coming from the same part of
$S_{A}/S_{B}/S_{C}$, meaning that we have strong separation for pairs of words
coming from different parts $S_{A}/S_{B}/S_{C}$, as needed. To see that every
$s\in S$ is linear notice that every word pictured has no repetitions of black
letters.

Now suppose $[a,b]\neq{e}$. Notice that this implies that
$a,b,bab^{-1}a^{-1},bab^{-1},ba,b^{-1}a^{-1},ab^{-1}a^{-1},ab^{-1}\neq{e}$
also. Thinking of $x,y,z$ as free variables in $G\ast F_{3}$, consider the set
$S$ given in Figure 2, with partition $S=S_{A}\cup S_{B}\cup S_{C}$. Notice
that all words in $S$ are linear, all pairs of words weakly-separable, and
$S_{A},S_{B},S_{C}$ are pairwise strongly separable (see Figure 3 for
justification). Using Lemma 3.32, there is some projection $\pi:G\ast F_{3}\to
G$ which separates $S$ and has $\pi(S)\subseteq R\setminus U$. Any such
$\pi(S)$ $1$-absorbs $\\{[a,b]c,c\\}$ (using the red/blue matchings in Figure
2). ∎

The following lemma is identical to the previous one, except that it weakens
the assumption on what elements are generic.

######  Lemma 5.7.

Let $p\geq n^{-1/700}$. Let $H_{G}$ be a multiplication hypergraph,
$R^{1},R^{2},R^{3}$ disjoint, symmetric $p$-random subsets of $G$ and set
$R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$. With high probability, the
following holds:

For any $a,b,x\in G_{B}$ with $x,x[a,b]$ generic and $U\subseteq V(H_{G})$
with $|U|\leq p^{800}n/10^{4020}$, there is a set $R^{\prime}\subseteq
R\setminus U$ of size $\leq 16$ which $1$-absorbs $\\{x[a,b],x\\}$.

###### Proof.

With high probability, the properties of Lemmas 3.32, 5.5 and 5.6 hold. Fix
some $a,b,x\in G_{B}$ with $x,x[a,b]$ generic and $U\subseteq V(H_{G})$ with
$|U|\leq p^{800}n/10^{4020}$. As in Lemma 5.6, the conclusion trivially
follows from Lemma 5.5 if $[a,b]={e}$, so assume that this doesn’t happen.
With $v$ the free variable in $G\ast F_{1}$, consider the sets of words
$T:=\\{v,[b,a]x^{-1}v^{-1},x^{-1}v^{-1}\\}$ and
$S=\\{x^{-1}v^{-1},vxaba^{-1}b^{-1},vxaba^{-1},vxab,vxa\\}$. Define
$T_{A}=\\{v\\},T_{B}=\\{[b,a]x^{-1}v^{-1},x^{-1}v^{-1}\\}$, $T_{C}=\emptyset$
to get a partition of $T$. It is easy to check that all $w\in T\cup S$ are
linear (since $v$ appears precisely once in each $w\in T\cup S$), that
$T_{A},T_{B}$ separable (by part (b) of the definition, using that $x,x[a,b]$
are generic), and that $[b,a]x^{-1}v^{-1},x^{-1}v^{-1}$ are weakly separable
(since $[b,a]x^{-1}v^{-1}=x^{-1}v^{-1}$ rearranges into $[b,a]={e}$). By Lemma
3.32, there is a projection $\pi$ which separates $T\cup S$ and has $\pi(T\cup
S)\subseteq R\setminus(U\cup N(G))$. Since all pairs of words in $T$ are
separable, we have that the vertices in $\pi(T)$ are distinct (and so
$e^{-}=(\pi(v),x[a,b],[b,a]x^{-1}\pi(v)^{-1})$ and
$e^{+}=(\pi(v),x,x^{-1}\pi(v)^{-1})$ are edges of $H_{G}$ contained in
$R\cup\\{x,x[a,b]\\}$).

Using Lemma 5.6 with $a^{\prime}=b,b^{\prime}=a,c=x^{-1}\pi(v^{-1})$ we find a
set $Q$ disjoint from $U\cup\pi(T)$ which 1-absorbs
$\\{[b,a]x^{-1}\pi(v)^{-1},x^{-1}\pi(v)^{-1}\\}$ (all the required elements
are generic for that lemma as a consequence of $\pi(S)\cap N(G)=\emptyset$).
Now $Q\cup\pi(T)$ 1-absorbs $\\{x[a,b],x\\}$. This can be seen directly or by
first noticing that $\\{\pi(v)\\}$ 1-absorbs
$\\{\\{x[a,b],[b,a]x^{-1}\pi(v)^{-1}\\},\\{x,x^{-1}\pi(v)^{-1}\\}\\}$ (the
single-edge matchings $e^{-},e^{+}$ witness this). Then Lemma 5.3 shows that
$Q\cup\pi(T)$ 1-absorbs $\\{x[a,b],x\\}$. ∎

For two sets $X,Y\subseteq G$ and $s\in G$, use $XsY$ to denote $\\{xsy:x\in
X,y\in Y\\}$. The following lemma lets us $1$-absorb a pair of size $3$ sets.

######  Lemma 5.8.

Let $p\geq n^{-1/700}$. Let $H_{G}$ be a multiplication hypergraph,
$R^{1},R^{2},R^{3}$ disjoint, symmetric $p$-random subsets of $G$ and set
$R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$. With high probability, the
following holds:

For any distinct, generic $a,b,c,d\in G_{B}$ and $X,Y,U\subseteq V(H_{G})$
with $|U|\leq p^{800}n/10^{4000},|X|,|Y|\leq 5$, there is a
$R^{\prime}\subseteq R\setminus U$ of size $6$ and $s$ with $XsY\subseteq
R\setminus(U\cup R^{\prime})$ such that $R^{\prime}$ $1$-absorbs
$\\{\\{a,dsc,b\\},\\{c,bsa,d\\}\\}$.

###### Proof.

With high probability, the property of Lemma 3.32 holds. Suppose we have
generic $a,b,c,d\in G_{B}$ and $X,Y,U\subseteq V(H_{G})$ with $|U|\leq
p^{800}n/10^{4000},|X|,|Y|\leq 5$. Let
$X^{\prime}=X\cup\\{b,d\\},Y^{\prime}=Y\cup\\{a,c\\}$. For free variables
$u,w$, consider the sets of words
$S=\\{u,{a^{-1}}u^{-1},{c^{-1}}u^{-1},w,{b^{-1}}w^{-1},{d^{-1}}w^{-1}\\}$ with
$S_{A}=\\{u,{b^{-1}}w^{-1},{d^{-1}}w^{-1}\\},S_{B}=\emptyset,S_{C}=\\{w,{a^{-1}}u^{-1},{c^{-1}}u^{-1}\\}$.
Notice that all words in $S\cup(X^{\prime}wuY^{\prime})$ are linear, all pairs
of words in $S$ are weakly separable (see Figure 5), and $S_{A},S_{B},S_{C}$
are pairwise strongly separable. Also the pair of sets
$(S,X^{\prime}wuY^{\prime})$ is strongly separable (using part (a) of the
definition of separable). By Lemma 3.32, there is some projection $\pi$