separating $S\cup(X^{\prime}wuY^{\prime})$ and having
$S\cup(X^{\prime}wuY^{\prime})\subseteq R\setminus U$. For any such
projection, $R^{\prime}=\pi(S)$ and $s:=\pi(wu)$ satisfy the lemma (with the
red/blue matchings in Figure 4 satisfying the definition of $R^{\prime}$
1-absorbing $\\{\\{a,dsc,b\\},\\{c,bsa,d\\}\\}$. Note that this works
regardless of whether $dwuc=bwua$ or not).

Figure 4: The set of words $S\subseteq G\ast F_{2}$ for Lemma 5.8. First,
second, and third row of words represent $S_{A}$, $S_{B}$, and $S_{C}$,
respectively. Black letters $u,w$ are free variables of $F_{2}$, while pink
letters are elements of $G$. The elements $a,b,c,d,bwua,dwuc$ are not part of
$S$ (and are pictured just to demonstrate how the absorption works).

∎

$S_{u}:$ $u$ ${\color[rgb]{1,0,1}a^{-1}}u^{-1}$
${\color[rgb]{1,0,1}c^{-1}}u^{-1}$ $u$ ${\color[rgb]{1,0,1}a^{-1}}$
${\color[rgb]{1,0,1}c^{-1}}$ ${\color[rgb]{1,0,1}a^{-1}}u^{-1}$
${\color[rgb]{1,0,1}a^{-1}}$ ${\color[rgb]{1,0,1}ac^{-1}}$
${\color[rgb]{1,0,1}c^{-1}}u^{-1}$ ${\color[rgb]{1,0,1}c^{-1}}$
${\color[rgb]{1,0,1}ac^{-1}}$ $S_{w}:$ $w$ $w^{-1}\color[rgb]{1,0,1}b^{-1}$
$w^{-1}\color[rgb]{1,0,1}d^{-1}$ $w$ ${\color[rgb]{1,0,1}b^{-1}}$
${\color[rgb]{1,0,1}d^{-1}}$ $w^{-1}\color[rgb]{1,0,1}b^{-1}$
${\color[rgb]{1,0,1}b^{-1}}$ ${\color[rgb]{1,0,1}bd^{-1}}$
$w^{-1}\color[rgb]{1,0,1}d^{-1}$ ${\color[rgb]{1,0,1}d^{-1}}$
${\color[rgb]{1,0,1}bd^{-1}}$

Figure 5: Justification for linearity and separability of pairs
$(w,w^{\prime})$ in $S$ in Lemma 5.8. For separability, first split $S$ into
$S_{u}=\\{u,{a^{-1}}u^{-1},{c^{-1}}u^{-1}\\}$,
$S_{w}=\\{w,{b^{-1}}w^{-1},{d^{-1}}w^{-1}\\}$ based on which free variables
appear in the elements (as in Observation 3.24). By Observation 3.24, pairs
$(w,w^{\prime})$ with $w,w^{\prime}$ in different sets $S_{u}/S_{w}$ fall
under part (a) of the definition of strongly separable, so it remains to check
pairs inside $S_{u}$ and $S_{w}$. Justification for this is given in the two
tables above (with the same conventions as in Figure 3, in particular, green
cells are used only between pairs of vertices coming from the same part
$S_{A}/S_{B}/S_{C}$). Relevant elements are generic/non-identity as a
consequence of $a,b,c,d$ being distinct and generic). To see that each $w\in
S$ is linear, note that there are no repetitions of black letters in each $w$
(and each $w\in S$ contains at least one black letter).

The following technical lemma allows us to $1$-absorb certain pairs of sets of
size $2$.

######  Lemma 5.9.

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 $g,x,y,a,b\in G_{B}$ with $yg,x,y,x[a,b]g$ distinct, generic and
$U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4030}$, there is a set
$R^{\prime}\subseteq R\setminus U$ of size $\leq 60$ which $1$-absorbs
$\\{\\{yg,x\\},\\{y,x[a,b]g\\}\\}$.

###### Proof.

With high probability, the properties of Lemmas 5.7 and 5.8 hold. Let
$g,x,y,a,b$ and $U$ be as in the lemma. Fix $a^{\prime}=yg$, $b^{\prime}=x$,
$c^{\prime}=y$, $d^{\prime}=x[a,b]g$ and note these are distinct and generic
by assumption. Define $X=\\{x,x[a,b]g,x[a,b],x[a,b]yg,{e}\\}$,
$Y=\\{yg,y,g[a,b],yg[a,b],{e}\\}$. By Lemma 5.8, we get $R^{\prime}$ and $s$
with $R_{0}\cup(XsY)\subseteq V(H_{G})\setminus(U\cup
N(G)\cup\\{a^{\prime},b^{\prime},c^{\prime},d^{\prime}\\})$ with $R_{0}$
1-absorbing
$\\{\\{a^{\prime},d^{\prime}sc^{\prime},b^{\prime}\\},\\{c^{\prime},b^{\prime}sa^{\prime},d^{\prime}\\}\\}$.

Define $w_{1}=d^{\prime}sc^{\prime}=x[a,b]gsy=x[a,b]ygs[y,gs]$,
$w_{2}=x[a,b]ygs=x[a,b]syg[s,yg]$, $w_{3}=x[a,b]syg=xsyg[a,b][syg,[a,b]]$,
$w_{4}=xsyg[a,b]$, and $w_{4}=b^{\prime}sa^{\prime}=xsyg$, noting that all of
these are in $XsW$ and so are generic and disjoint from
$R_{0}\cup\\{a^{\prime},b^{\prime},c^{\prime},d^{\prime}\\}$. So we can use
Lemma 5.7 to find disjoint sets $R_{1},R_{2},R_{3},R_{4}\subseteq
R\setminus(R^{\prime}\cup U)$ with $R_{i}$ $1$-absorbing
$\\{w_{i},w_{i+1}\\}$. We also have $R_{0}$ 1-absorbing
$\\{\\{a^{\prime},w_{1},b^{\prime}\\},\\{c^{\prime},w_{5},d^{\prime}\\}\\}$.
By Lemma 5.4, there is a subset
$R^{\prime}\subseteq\bigcup_{i=0}^{4}R_{i}\cup\\{w_{1},w_{2},w_{3},w_{4},w_{5}\\}$
which $1$-absorbs
$\\{\\{a^{\prime},b^{\prime}\\},\\{c^{\prime},d^{\prime}\\}\\}$. ∎

The following lemma gives us a collection of distinct, generic elements.

######  Lemma 5.10.

Let $p\geq n^{-1/700}$ and $t\leq p^{800}n/10^{4020}$. Let $G$ be a group and
$R$ a symmetric $p$-random subset. With high probability, the following holds:

Let $g_{1},\dots,g_{t}\neq{e}$ be distinct and $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4020}$. There are $y_{1},\dots,y_{t-1}\in G$ such that the
elements $y_{1},y_{2},\dots,y_{t-1},y_{1}g_{2},y_{2}g_{3},\dots,y_{t-1}g_{t}$
are distinct, generic elements in $R\setminus U$.

###### Proof.

Lemma 3.32 applies with $R_{A}=R$, and $R_{B},R_{C}$ arbitrary disjoint
symmetric $p$-random subsets (which won’t be used in the proof). Let
$g_{1},\dots,g_{t}\neq{e}$ be distinct and $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4020}$. Thinking of $y$ as the free variable in $G\ast F_{1}$,
let $S_{i}=\\{y,yg_{i}\\}$. Note all $w,w^{\prime}\in S_{i}$ are linear and
strongly separable (by part (b) since $g_{i}$ is generic). For $i=1,\dots,t$,
use Lemma 3.32 to pick projections $\pi_{1},\dots,\pi_{i}$ such that
$\pi_{i}(S_{i})$ is separated and disjoint from $U^{\prime}:=U\cup
N(G)\cup\bigcup_{j<i}\pi_{j}(S_{j})$ (noting that
$|U^{\prime}|\leq|U|+|N(G)|+2t\leq 3p^{800}n/10^{4020}+10^{9000}\leq
n/10^{4010}$). Now $y_{1}=\pi_{1}(y),\dots,y_{t-1}=\pi_{t-1}(y)$ satisfy the
lemma. ∎

The following theorem of Gallagher is key to our approach and shows that
elements of the commutator subgroup can be written as a product of a small
number of commutators. Its proof uses character theory.

######  Theorem 5.11 (Gallagher, [28]).

Let $G$ be a group. Any $g\in G^{\prime}$ can be written as
$g=\prod_{i=1}^{t}[a_{i},b_{i}]$ for some $a_{i},b_{i}\in G$ and
$t\leq\log_{4}|G^{\prime}|\leq 10\log n$.

We now prove one of the main lemmas in this section. It strengthens several
earlier lemmas and shows that we can 1-absorb any pair of elements as long as
they are in the same coset of $G^{\prime}$.

######  Lemma 5.12.

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 $h,k\in G_{A},G_{B},$ or $G_{C}$ with $[h]=[k]$ and
$U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4040}$, there is a set
$R^{\prime}\subseteq R\setminus U$ of size $\leq 400\log n$ which $1$-absorbs
$\\{h,k\\}$.

###### Proof.

With high probability, the properties of Lemmas 5.5, 5.7, 5.9, and 5.10 hold.
We just prove the lemma for $h,k\in G_{B}$, the other two cases follow by
symmetry. Let $h,k\in G_{B}$ be generic with $[h]=[k]$ and $U\subseteq
V(H_{G})$ with $|U|\leq p^{800}n/10^{4040}$. As in Lemma 5.6, the conclusion
trivially follows from Lemma 5.5 if $h=k$, so assume $h\neq k$. Write $h=kg$
for some $g\in G^{\prime}$. By Theorem 5.11, we have
$g=\prod_{i=1}^{t}[a_{i},b_{i}]$ for some $a_{i},b_{i}\in G$ and $t\leq 10\log
n$. Assume this product is as short as possible i.e. that $t$ is minimal. For
each $s=0,\dots,t-1$, define $g_{s}=\prod_{i=s}^{t}[a_{i},b_{i}]$. By
minimality of $t$, we have $[a_{i},b_{i}]\neq{e}$ and $g_{i}\neq{e}$ for all
$i$. Set $y_{0}=k$ and note that $y_{0},y_{0}g_{1}$ are distinct, generic
(since $k,h$ are distinct, generic).

Note that $t\leq 10\log n\leq n^{1/8}/10^{4010}\leq p^{800}n/10^{4010}$ (using
that $n$ is large which follows from “with high probability”). Use Lemma 5.10
with $U^{\prime}=U\cup\\{y_{0},y_{0}g_{1}\\}$ to get elements
$y_{1},\dots,y_{t-1}$, noting that now

$y_{0},y_{1},\dots,y_{t-1},y_{0}g_{1},y_{1}g_{2},\dots,y_{t-1}g_{t}$

are distinct, generic.
$U^{\prime}=U\cup\\{y_{i},y_{i}g_{i+1}:i=1,\dots,t-1\\}$. Using Lemma 5.9 with
$y=y_{i}$, $x=y_{i-1}$, $g=g_{i+1},a=a_{i},b=b_{i}$ for all $i$ (the
conditions “$y_{i}g_{i+1},y_{i-1},y_{i},y_{i-1}[a_{i},b_{i}]g_{i+1}$ distinct,
generic” coming from Lemma 5.10), gives a set $R_{i}$ which $1$-absorbs
$\\{\\{y_{i}g_{i+1},y_{i-1}\\},\\{y_{i},y_{i-1}[a_{i},b_{i}]g_{i+1}\\}\\}=\\{\\{y_{i}g_{i+1},y_{i-1}\\},\\{y_{i},y_{i-1}g_{i}\\}\\}$.
Using Lemma 5.7 with $x=y_{t-1}$, $a=a_{t},b=b_{t}$ (condition
“$y_{t-1},y_{t-1}[a_{t},b_{t}]$ generic” coming from Lemma 5.10), gives a set
$R_{t}$ which $1$-absorbs
$\\{y_{t-1}[a_{t},b_{t}],y_{t-1}\\}=\\{y_{t-1}g_{t},y_{t-1}\\}$. By enlarging
the set $U$ during the application of these lemmas, we can assume that
$R_{1},\dots,R_{t-1},R_{t},\\{y_{i},y_{i}g_{i+1}:i=1,\dots,t-1\\}$ are all
disjoint (there’s space to do this because $|R_{1}\cup\dots\cup R_{i-1}|\leq
400\log n<10^{800}n^{1/8}/10^{4020}\leq p^{800}n/10^{4030}$).

Set $R=R_{1}\cup\dots\cup R_{t-1}\cup
R_{t}\cup\\{y_{i},y_{i}g_{i+1}:i=1,\dots,t-1\\}$. Set
$X_{i}=\\{y_{i}g_{i+1},y_{i-1}\\}$, $Y_{i}=\\{y_{i},y_{i-1}g_{i}\\}$ for
$i=1,\dots,t-1$, and $X_{t}=\\{y_{t-1}\\}$, $Y_{t}=\\{y_{t-1}g_{t}\\}$. Notice
that the sets in the families $\\{R_{1},\dots,R_{t-1}\\}$,
$\\{X_{1},\dots,X_{t-1}\\}$, $\\{Y_{1},\dots,Y_{t-1}\\}$ are disjoint, that
$\bigcup R_{i}$ is disjoint from $\bigcup X_{i},\bigcup Y_{i}$ and that
$(\bigcup X_{i})\cap(\bigcup Y_{i})=\\{y_{i},y_{i}g_{i+1}:i=1,\dots,t-1\\}$.
By Lemma 5.3 $R$ $1$-absorbs $\\{y_{0}g_{1},y_{0}\\}=\\{kg,k\\}=\\{h,k\\}$. ∎

The following lemma is similar to the previous one, except it allows us to
1-absorb pairs of sets of size $2$.

######  Lemma 5.13.

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_{A},G_{B},$ or $G_{C}$ with
$[ab]=[cd]$ and $U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4050}$, there
is a set $R^{\prime}\subseteq R\setminus U$ of size $\leq 500\log n$ which
$1$-absorbs $\\{\\{a,b\\},\\{c,d\\}\\}$.

###### Proof.

With high probability, the properties of Lemmas 5.8 and 5.12 hold. We just
prove the lemma for $a,b,c,d\in G_{B}$. The other two cases follow by
symmetry. Suppose that we have distinct, generic $a,b,c,d\in B(H_{G})$ with
$[ab]=[cd]$, and $U\subseteq G$ with $|U|\leq p^{800}n/10^{21}$. Let
$X=\\{d,b\\},Y=\\{c,a\\}$. Using Lemma 5.8, pick some $R^{\prime},s$ with
$R^{\prime}\cup XsY\subseteq R\setminus(U\cup N(G))$ and $R^{\prime}$
1-absorbing $\\{\\{a,dsc,b\\},\\{c,bsa,d\\}\\}$. When $dsc=bsa$,
$R^{\prime}\cup dsc$ 1-absorbs $\\{\\{a,b\\},\\{c,d\\}\\}$ and so satisfies
the lemma. So suppose $dsc\neq bsa$. Notice that $[ab]=[cd]$ implies
$[bsa]=[dsc]$ and so using Lemma 5.12 we can choose a $Q\subseteq
V(H_{G})\setminus(U\cup R^{\prime}\cup\\{dsc,bsa\\})$ which 1-absorbs
$\\{bsa,dsc\\}$ ($bsa,dsc$ are generic because they are contained in $XsC$).
Set $R^{\prime\prime}=R^{\prime}\cup Q\cup\\{bsa,dsc\\}$ to get a set which
1-absorbs $\\{\\{a,b\\},\\{c,d\\}\\}$ by Lemma 5.3. ∎

####  5.1.2 Distributive absorption for pairs

In this section we prove a variety of lemmas about $h$-absorbing sets of the
form $\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}$ where
$[a_{1}b_{1}]=\dots=[a_{k}b_{k}]$. The following does this for $h=k-1$.

######  Lemma 5.14.

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:

Let $k\leq 200$ and $x_{1},y_{1},\dots,x_{k},y_{k}\in G_{A},G_{B}$ or $G_{C}$
be distinct, generic with $[x_{1}y_{1}]=\dots=[x_{k}y_{k}]$ and let
$U\subseteq G$ with $|U|\leq p^{800}n/10^{4060}$. Then there is a set
$R^{\prime}\subseteq R\setminus U$ of size $\leq 600k\log n$ which
$(k-1)$-absorbs $\\{\\{x_{1},y_{1}\\},\dots,\\{x_{k},y_{k}\\}\\}$.

###### Proof.

With high probability, the property of Lemma 5.13 holds. Let
$x_{1},y_{1},\dots,x_{k},y_{k}$ be distinct, generic with
$[x_{1}y_{1}]=\dots=[x_{k}y_{k}]$ and let $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4060}$. Apply the property of Lemma 5.12 to get disjoint sets
$R_{1},\dots,R_{k-1}\subseteq R\setminus U$ which $1$-absorb
$\\{\\{x_{i},y_{i}\\},\\{x_{i+1},y_{i+1}\\}\\}$ for each $i\in[k-1]$ (for
disjointness use $U^{\prime}=U\cup\bigcup_{j=1}^{i-1}R_{j}$ at each
application. This set has size $\leq|U|+k500\log n\leq p^{800}n/10^{4060}$).
Set $R^{\prime}=R_{1}\cup\dots\cup R_{k-1}$. For each $i$, we have matchings
$R_{i}^{-}$ and $R_{i}^{+}$ with vertex sets $R_{i}\cup\\{x_{i},y_{i}\\}$ and
$R_{i}\cup\\{x_{i+1},y_{i+1}\\}$. Now the matchings
$M_{i}=(\bigcup_{j=1}^{i-1}R_{i}^{-})\cup(\bigcup_{j=i}^{|Y|-1}R_{i}^{+})$
have vertex sets exactly $V(M_{i})=R^{\prime}\cup
Y\setminus\\{x_{i},y_{i}\\}$, and so they satisfy the definition of
$R^{\prime}$ $(k-1)$-absorbing $Y$. ∎

We’ll need the following lemma which finds a common neighbour of a set of
vertices in $H_{k}$.

######  Lemma 5.15.

Let $p\geq n^{-1/700}$ and 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:

Let $k\leq 200$ and $a_{1},\dots,a_{k}\in G_{A}$ be distinct and generic and
let $U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4001}$. Then there are
distinct, generic $b,c_{1},\dots,c_{k}\in G\setminus U$ such that for each
$i$, $\\{a_{i},b,c_{i}\\}$ is an edge of $H_{G}$.

###### Proof.

With $b$ the free variable in $G\ast F_{1}$, consider the set
$S=\\{b,b^{-1}a_{1}^{-1},\dots,b^{-1}a_{k}^{-1}\\}$, $S_{A}=\emptyset$,
$S_{B}=\\{b\\}$, $S_{C}=\\{b^{-1}a_{1}^{-1},\dots,b^{-1}a_{k}^{-1}\\}$. Notice
that all $w\in S$ are linear, that $S_{A},S_{B},S_{C}$ are pairwise separable
(by part (b) of the definition since $a_{1},\dots,a_{k}$ are generic), and all
$w,w^{\prime}\in S_{C}$ are weakly separable (by (b’) since equalities between
$w,w^{\prime}$ rearrange to ${e}=a_{i}a_{j}^{-1}$ and we know
$a_{i}a_{j}^{-1}\neq{e}$ by distinctness). Thus the lemma follows from Lemma
3.32 applied with $U^{\prime}=U\cup N(G)$. ∎

The following lemma 1-absorbs a set of $k$ pairs.

######  Lemma 5.16.

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:

Let $k\leq 200$ and $x_{1},y_{1},\dots,x_{k},y_{k}\in G_{A}$ be distinct,
generic with $[x_{1}y_{1}]=\dots=[x_{k}y_{k}]$ and let $U\subseteq G$ with
$|U|\leq p^{800}n/10^{4070}$. Then there is a set $R^{\prime}\subseteq R$ of
size $\leq 600k\log n$ which $1$-absorbs
$\\{\\{x_{1},y_{1}\\},\dots,\\{x_{k},y_{k}\\}\\}$.

###### Proof.

With high probability, the conclusions of Lemmas 5.15 and 5.14 apply. Let
$x_{1},y_{1},\dots,x_{k},y_{k}\in G_{A}$ be distinct, generic with
$[x_{1}y_{1}]=\dots=[x_{k}y_{k}]$ and let $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4070}$. Use the conclusion of Lemma 5.15 twice to get elements
$b^{x},b^{y}$ and $c_{1}^{x},c_{1}^{y},\dots,c_{k}^{x},c_{k}^{y}$ outside $U$,
such that $x_{1},y_{1},\dots,x_{k},y_{k}$, $b^{x},b^{y}$,
$c_{1}^{x},c_{1}^{y},\dots,c_{k}^{x},c_{k}^{y}$ are all distinct, generic and
also $x_{i}b^{x}c_{i}^{x},y_{i}b^{y}c^{y}_{i}$ are edges for all $i$ (to get
distinctness of all the vertices, enlarge $U$ to include previously found
vertices between the two applications). Notice that this implies that
$[c_{i}^{x}c_{i}^{y}]=[x_{i}^{-1}b_{x}^{-1}y_{i}^{-1}b_{y}^{-1}]=[x_{1}^{-1}b_{x}^{-1}y_{1}^{-1}b_{y}^{-1}]$
for all $i$ (using $[x_{1}y_{1}]=\dots=[x_{k}y_{k}]$). Thus using the
conclusion of Lemma 5.14, we get a set $R$ which $(k-1)$-absorbs
$\\{\\{c_{1}^{x},c_{1}^{y}\\},\dots,\\{c_{k}^{x},c_{k}^{y}\\}\\}$. In other
words we have matchings $M_{1},\dots,M_{k}$ with
$V(M_{i})=R\cup\\{\\{c_{j}^{x},c_{j}^{y}\\}:j\neq i\\}$. Set
$R^{\prime\prime}=R^{\prime}\cup\\{b^{x},b^{y},c_{1}^{x},c_{1}^{y}\dots,c_{k}^{x},c_{k}^{y}\\}$.
Now for each $i$, $M_{i}\cup\\{x_{i}b^{x}c_{i}^{x},y_{i}b^{y}c_{i}^{y}\\}$ is
a matching with vertex set exactly $R^{\prime\prime}\cup\\{x_{i},y_{i}\\}$,
verifying the definition of “$1$-absorbs”. ∎

The below was shown by Montgomery in [44], and is the essence of the
distributive absorption approach.

######  Lemma 5.17 (Montgomery, [44]).

There is a constant $h_{0}$ such that for every $h\geq h_{0}$ there exists a
bipartite graph $K$ with maximum degree at most $100$ and vertex classes $X$
and $Y\cup Y^{\prime}$ with $|X|=3h$, $|Y|=|Y^{\prime}|=2h$, so that the
following holds. For any $Y_{0}\subseteq Y^{\prime}$ with $|Y_{0}|=h$, there
is a perfect matching between $X$ and $Y\cup Y_{0}$.

Graphs produced by this lemma are called robustly matchable bipartite graphs.
Combining this lemma with the previous one, we can $h$-absorb sets of pairs.

######  Lemma 5.18.

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:

Consider sets $Y,Y^{\prime}$ of disjoint pairs of generic elements
$(a_{1},a_{2})\in(A\setminus{e})\times(A\setminus{e})$ having
$[a_{1}a_{2}]=[a_{1}^{\prime}a_{2}^{\prime}]$ for
$(a_{1},a_{2}),(a_{1}^{\prime},a_{2}^{\prime})\in Y,Y^{\prime}$ and also
$2h=|Y|=|Y|^{\prime}\leq\frac{p^{800}n}{10^{4080}\log n}$. Let $U\subseteq G$
with $|U|\leq p^{800}n/10^{4080}$. Then there is a subset $R^{\prime}\subseteq
R\setminus U$ of size $\leq 800|Y|\log n$ such that $R^{\prime}\cup
Y^{\prime}$ $h$-absorbs $Y$.

###### Proof.

With high probability the property of Lemma 5.16 holds.

Let $Y,Y^{\prime}$ be disjoint sets of pairs of elements $(a_{1},a_{2})\in
A\times A$ having $[a_{1}a_{2}]=[a_{1}^{\prime}a_{2}^{\prime}]$ for
$(a_{1},a_{2}),(a_{1}^{\prime},a_{2}^{\prime})\in Y$ and also
$2h:=|Y|=|Y|^{\prime}\leq\frac{p^{800}n}{10^{4080}\log n}$. Let $U\subseteq G$
with $|U|\leq p^{800}n/10^{4080}$. Consider a robustly matchable bipartite
graph $D$ with $\Delta(D)\leq 100$ whose sets are $Y,Y^{\prime}$ and $X$ as in
Lemma 5.17 (here $X$ is just an abstract set of size $3h$ unrelated to the
hypergraph we have). For all $x\in X$ use Lemma 5.16 to pick a set
$R_{x}\subseteq R\setminus(U\cup Y\cup Y^{\prime})$ which 1-absorbs $N(x)$. We
can choose all these sets to be disjoint by enlarging $U$ to contain the union
of previously picked sets at each application (whose total size is at most
$100|X|\times 700\log n\leq p^{800}n/10^{4070}$).

Letting $R^{\prime}\bigcup_{x\in X}R_{x}$ we claim that $R^{\prime}\cup
Y^{\prime}$ will $h$-absorb $Y$, and so satisfy the lemma. Let $Y_{0}\subseteq
Y$ be a set of $|Y|/2=h$ pairs. Since $D$ is robustly matchable, there is a
matching $M$ with vertex set $Y_{0}\cup Y^{\prime}\cup X$. For each $x\in X$,
let $xy_{x}$ be the matching edge of $M$ through $x$, and let $N_{x}$ be a
matching with vertex set $R_{x}\cup y_{x}$ (which exists because $R_{x}$
1-absorbs $N(x)$). Now $\bigcup_{x\in X}N_{x}$ is a matching with vertex set
$Y_{0}\cup R^{\prime}\cup Y^{\prime}$. ∎

The following is a version of the previous lemma with more versatility with
choosing $h$.

######  Lemma 5.19.

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:

Consider sets $Y,Z$ of disjoint pairs of generic elements $(a_{1},a_{2})\in
A\times A$ having $[a_{1}a_{2}]=[a_{1}^{\prime}a_{2}^{\prime}]$ for
$(a_{1},a_{2}),(a_{1}^{\prime},a_{2}^{\prime})\in Y,Z$ and
$4|Y|\leq|Z|=\frac{p^{800}n}{10^{4090}\log n}$. Let $h\in\mathbb{N}$. Let
$U\subseteq G$ with $|U|\leq p^{800}n/10^{4090}$. Then there is a subset
$R^{\prime}\subseteq R\setminus U,Y^{\prime}\subseteq Z$ of size $\leq
800|Y|\log n$ such that $R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y$.

###### Proof.

With high probability Lemma 5.18 applies. If $h>|Y|$, then the definition of
“$h$-absorbs $Y$” is vacuous, so we can suppose that $h\leq|Y|$. If $|Y|/2\leq
h\leq|Y|$, pick subsets $\hat{Y},Y^{\prime}\subseteq Z$ with
$|\hat{Y}|=2h-|Y|$ and $|Y^{\prime}|=2h$. Apply Lemma 5.18 to $g$,
$Y\cup\hat{Y}$, $Y^{\prime}$, and $h$ to get a set $R^{\prime}$ such that
$R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y\cup\hat{Y}$. By Lemma 5.2 (1),
$R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y$ also.

If $h\leq|Y|/2$, pick subsets $\hat{Y},Y^{\prime}\subseteq Z$ with
$|\hat{Y}|=|Y|-2h$ and $|Y^{\prime}|=2|Y|-2h$. Apply Lemma 5.18 to $g$,
$Y\cup\hat{Y}$, $Y^{\prime}$, and $h^{\prime}=|Y|-h$ to get a set $R^{\prime}$
such that $R^{\prime}\cup Y^{\prime}$ $(|Y|-h)$-absorbs $Y\cup\hat{Y}$. By
Lemma 5.2 (2) with $t=|\hat{Y}|=|Y|-2h$, $R^{\prime}\cup
Y^{\prime}\cup\hat{Y}$ $(|Y|-h-|\hat{Y}|)$-absorbs $Y$. This implies the lemma
since $|Y|-h-|\hat{Y}|=h$. ∎

####  5.1.3 Distributive absorption for singletons

Everything in this section is almost identical to the previous one (though
often a bit easier). We give constructions of $h$-absorbers of sets vof
vertices $Y$ contained in a coset of $G^{\prime}$. The following lemma does
this with $h=|Y|-1$.

######  Lemma 5.20.

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 $g\in G$, let $Y\subseteq G_{A},G_{B}$, or $G_{C}$ with $Y\subseteq[g]$ be
a set of generic elements with $|Y|\leq\frac{p^{800}n}{10^{4100}\log n}$ and
let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4100}$. Then there is a set
$R^{\prime}\subseteq R\setminus U$ of size $\leq 700|Y|\log n$ which
$(|Y|-1)$-absorbs $Y$.

###### Proof.

With high probability, the property of Lemma 5.12 holds.

Let $g\in G$ and $Y=\\{y_{1},\dots,y_{|Y|}\\}\subseteq[g]$ with
$|Y|\leq\frac{p^{800}n}{10^{4100}\log n}$ and $U$ with $|U|\leq
p^{800}n/10^{17}$. Apply the property of Lemma 5.12 to get disjoint sets
$R_{1},\dots,R_{|Y|-1}\subseteq R\setminus U$ which $1$-absorb
$\\{y_{i},y_{i+1}\\}$ (for disjointness use
$U^{\prime}=U\cup\bigcup_{j=1}^{i-1}R_{j}$ at each application. This set has
size $\leq|U|+|Y|500\log n\leq p^{800}n/10^{4090}$). Set
$R^{\prime}=R_{1}\cup\dots\cup R_{|Y|-1}$. For each $i$, we have matchings
$R_{i}^{-}$ and $R_{i}^{+}$ with vertex sets $R_{i}\cup\\{y_{i}\\}$ and
$R_{i}\cup\\{y_{i+1}\\}$. Now the matchings
$M_{i}=(\bigcup_{j=1}^{i-1}R_{i}^{-})\cup(\bigcup_{j=i}^{|Y|-1}R_{i}^{+})$
have vertex sets exactly $V(M_{i})=R^{\prime}\cup Y\setminus\\{y_{i}\\}$, and
so they satisfy the definition of $R^{\prime}$ $(|Y|-1)$-absorbing $Y$. ∎

The next lemma builds 1-absorbers of small sets $Y$.

######  Lemma 5.21.

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:

Let $k\leq 200$ and $s_{1},\dots,s_{k}\in G_{A}$ be distinct, generic with
$[s_{1}]=\dots=[s_{k}]$ and let $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4110}$. Then there is a set $R^{\prime}\subseteq R\setminus U$ of
size $\leq 700k\log n$ which $1$-absorbs $\\{s_{1},\dots,s_{k}\\}$.

###### Proof.

With high probability, the conclusions of Lemmas 5.15 and 5.20 apply. Let
$s_{1},\dots,s_{k}\in G$ be distinct, generic with $[s_{1}]=\dots=[s_{k}]$ and
let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4110}$. Use the conclusion of
Lemma 5.15 to get distinct, generic elements $b$ and $c_{1},\dots,c_{k}\in
G\setminus U$, such that also $s_{i}bc_{i}$ are edges for all $i$. Thus using
the conclusion of Lemma 5.20, we get a set $R$ which $(k-1)$-absorbs
$\\{c_{1},\dots,c_{k}\\}$. From the definition of $(k-1)$-absorbs, we have
matchings $M_{1},\dots,M_{k}$ with
$V(M_{i})=R\cup\\{c_{1},\dots,c_{i-1},c_{i+1},\dots,c_{k}\\}$. Set
$R^{\prime\prime}=R^{\prime}\cup\\{b,c_{1},\dots,c_{k}\\}$. Now for each $i$,
$M_{i}\cup s_{i}bc_{i}$ is a matching with vertex set exactly
$R^{\prime\prime}\cup\\{s_{i}\\}$, verifying the definition of “$1$-absorbs”.
∎

The next lemma uses distributive absorption to build $h$-absorbers.

######  Lemma 5.22.

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:

Let $g\in G$, and consider disjoint sets $Y,Y^{\prime}\subseteq[g]$ of generic
elements of $G_{A}$ of size
$2h:=|Y|=|Y^{\prime}|\leq\frac{p^{800}n}{10^{4120}\log n}$. Let $U\subseteq G$
with $|U|\leq p^{800}n/10^{4120}$. Then there is are subset
$R^{\prime}\subseteq R\setminus U$ of size $\leq 10^{5}|Y|\log n$ such that
$R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y$.

###### Proof.

With high probability the property of Lemma 5.21 holds. Let $g\in G$, every
disjoint sets $Y,Y^{\prime}\subseteq[g]$ of size
$2h=|Y|=|Y^{\prime}|\leq\frac{p^{800}n}{10^{4120}\log n}$. Let $U\subseteq G$
with $|U|\leq p^{800}n/10^{4120}$. Consider a robustly matchable bipartite
graph $D$ with $\Delta(D)\leq 100$ whose sets are $Y,Y^{\prime}$ and $X$ as in
Lemma 5.17 (here $X$ is just an abstract set of size $3h$ unrelated to the
hypergraph we have). For all $x\in X$ fix a set $R_{x}\subseteq R$ which
1-absorbs $N(x)$. We can choose all these sets to be disjoint by letting $U$
be the union of previously picked sets at each application (whose total size
is at most $100|X|\times 700\log n\leq p^{800}n/10^{4110}$).

We claim that for $R^{\prime}:=\bigcup_{x\in X}R_{x}$, we have $R^{\prime}\cup
Y^{\prime}$ $h$-absorbing $Y$, and so satisfying the lemma. Let
$Y_{0}\subseteq Y$ be a set of $|Y|/2=h$ pairs. Since $D$ is robustly
matchable, there is a matching $M$ with vertex set $Y_{0}\cup Y^{\prime}\cup
X$. For each $x\in X$, let $xy_{x}$ be the matching edge of $M$ through $x$,
and let $N_{x}$ be a matching with vertex set $R_{x}\cup y_{x}$ (which exists
because $R_{x}$ 1-absorbs $N(x)$). Now $\bigcup_{x\in X}N_{x}$ is a matching
with vertex set $Y_{0}\cup R^{\prime}\cup Y^{\prime}$. ∎

The next lemma is a version of the previous one which allows for more
flexibility in the value of $h$.

######  Lemma 5.23.

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:

Let $g\in G$, and consider disjoint sets $Y,Z\subseteq[g]$ of generic elements
of $G_{A}$ with $4|Y|\leq|Z|=\frac{p^{800}n}{10^{4130}\log n}$. Let
$h\in\mathbb{N}$. Let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4130}$. Then
there is are subset $R^{\prime}\subseteq R\setminus U,Y^{\prime}\subseteq Z$
of size $\leq 10^{5}|Y|\log n$ such that $R^{\prime}\cup Y^{\prime}$
$h$-absorbs $Y$.

###### Proof.

With high probability Lemma 5.22 applies. If $h>|Y|$, then the definition of
“$h$-absorbs $Y$” is vacuous, so we can suppose that $h\leq|Y|$. If $|Y|/2\leq
h\leq|Y|$, pick subsets $\hat{Y},Y^{\prime}\subseteq Z$ with
$|\hat{Y}|=2h-|Y|$ and $|Y^{\prime}|=2h$. Apply Lemma 5.22 to $g$,
$Y\cup\hat{Y}$, $Y^{\prime}$, and $h$ to get a set $R^{\prime}$ such that
$R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y\cup\hat{Y}$. By Lemma 5.2 (1),
$R^{\prime}\cup Y^{\prime}$ $h$-absorbs $Y$ also.

If $h\leq|Y|/2$, pick subsets $\hat{Y},Y^{\prime}\subseteq Z$ with
$|\hat{Y}|=|Y|-2h$ and $|Y^{\prime}|=2|Y|-2h$. Apply Lemma 5.22 to $g$,
$Y\cup\hat{Y}$, $Y^{\prime}$, and $h^{\prime}=|Y|-h$ to get a set $R^{\prime}$
such that $R^{\prime}\cup Y^{\prime}$ $(|Y|-h)$-absorbs $Y\cup\hat{Y}$. By
Lemma 5.2 (2) with $t=|\hat{Y}|=|Y|-2h$, $R^{\prime}\cup
Y^{\prime}\cup\hat{Y}$ $(|Y|-h-|\hat{Y}|)$-absorbs $Y$. This implies the lemma
since $|Y|-h-|\hat{Y}|=h$. ∎

####  5.1.4 Main absorption lemma

The following lemma summarises everything from Section 5.1 that we use in
other sections.

######  Lemma 5.24.

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:

Let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4140}$. Let $\ast=A/B/C$.
Suppose that $Y$ and $h$ are one of the following:

  1. (1)

For some $g\in G$, $Y\subseteq[g]\cap\ast\setminus N(G)$ with
$|Y|\leq\frac{p^{800}|G^{\prime}|}{10^{4140}\log n}$, and $h\leq|Y|$.

  2. (2)

For some $g\in G$, $Y\subseteq[g]\cap\ast\setminus N(G)$ with
$|Y|\leq\frac{p^{800}n}{10^{4140}\log n}$, and $h=|Y|-1$.

  3. (3)

For some generic $a_{\phi}$, we have $Y\subseteq G\setminus G$ a set of
$|Y|\leq\frac{p^{800}n}{10^{4140}\log n}$ disjoint pairs of generic elements,
with $[a_{1}a_{2}]=[a_{\phi}]$ for $(a_{1},a_{2})\in Y$, and $h\leq|Y|$.

Then there is a subset $R^{\prime}\subseteq R\setminus U$ of size $\leq
10^{6}|Y|\log n$ which $h$-absorbs $Y$.

###### Proof.

With high probability, Lemmas 3.34, 5.20, 5.19, and 5.23 apply. Additionally
when $|G^{\prime}|\geq 10^{4140}p^{-{800}}\log n$, we can assume that
$|R_{i}\cap[g]|\geq p|G^{\prime}|/2\geq 4\times
p^{800}|G^{\prime}|/10^{4140}\log n$ for all cosets $[g]$ and $i=1,2,3$ (using
Chernoff’s bound).

  1. (1)

We can suppose that $|G^{\prime}|\geq 10^{4140}p^{-{800}}\log n$, since
otherwise $Y$ would have to be empty and the conclusion is vacuous. In this
case, we have that for every $g$, there is a subset $Z_{g}\subseteq[g]$ of
size $4\times p^{800}|G^{\prime}|/10^{4140}\log n$. Let $g\in G$,
$Y\subseteq[g]\cap\ast$ of size
$|Y|\leq\frac{p^{800}|G^{\prime}|}{10^{4140}\log n}$, and $h\leq|Y|$. The
result follows from Lemma 5.23 applied to $Y,Z_{g},U$.

  2. (2)

This is strictly weaker than Lemma 5.20.

  3. (3)

We’ll just prove the lemma when $Y\subseteq G_{A}\times G_{A}$, the other
cases are symmetric. Use Lemma 3.34 in order to find a set
$Z\subseteq(R_{A}\setminus U)\times(R_{A}\setminus U)$ of
$4\times\frac{p^{800}n}{10^{4140}\log n}$ pairs $(a,a^{\prime})$ of generic
elements having $aa^{\prime}=a_{\phi}$. Using Lemma 5.19, there is a
$R^{\prime}\subseteq R\setminus(U\cup Z)$ and $Z^{\prime}\subseteq Z$ with
$R^{\prime}\cup Z^{\prime}$ $h$-absorbing $Y$.

∎

###  5.2 Absorbing coset-paired sets

In this section we prove results about absorbing coset-paired sets. The main
lemmas in this section are all along the lines of “given a set $Q$, there
exists a set $R^{\prime}$ with the property that for every coset-paired
$S\subseteq Q$, there is a matching with vertex set $R^{\prime}\cup(Q\setminus
S)$”.

For all $g\in G$, define $i_{[g]}=2$ if $[g]$ is self-paired and $1$
otherwise. The following lemma allows us to absorb the complement of a coset-
paired set.

######  Lemma 5.25.

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:

Let $s\in(0,1]$. Let $m\in\mathbb{N}$. Let $U\subseteq G$ and $Q\subseteq
G_{\diamond}$ (for some $\diamond\in\\{A,B,C\\}$) be disjoint, and suppose
$|U|\leq p^{800}n/10^{4150}$. Suppose also that $Q$ is generic,
$|Q|\leq\frac{p^{800}n}{10^{4150}\log n}$, and that $Q$ satisfies:

  1. (i)

For all pairs $g,h$ either $Q\cap[g]=Q\cap[h]=\emptyset$ or
$|Q\cap[g]|,|Q\cap[h]|\geq i_{[g]}\lceil 12s|G^{\prime}|\rceil$.

  2. (ii)

If $|G^{\prime}|>s^{-1}/12$ then for all pairs $g,h$
$|Q\cap[g]|,|Q\cap[h]|\leq\frac{p^{800}|G^{\prime}|}{10^{4150}\log n}$

  3. (iii)

If $|G^{\prime}|\leq s^{-1}/12$, then $Q$ doesn’t intersect any self-paired
cosets.

Then, there exists an $R^{\prime}\subseteq R\setminus U$ such that for all
coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded $S\subseteq Q$ of
size $m$, there is a matching with vertex set $R^{\prime}\cup(Q\setminus S)$.

###### Proof.

With high probability Lemma 5.24 applies to $R$. Let $s,m,U,Q$ be as in the
lemma. Let $K$ be the set of cosets $[g]$ with $Q\cap[g]$ nonempty. Partition
$Q=Q_{1}\cup Q_{2}$ where, for each coset $[g]\in K$, we have
$|Q_{1}\cap[g]|=i_{[g]}\lceil 12s|G^{\prime}|\rceil$ (and so
$|Q_{2}\cap[g]|=i_{[g]}|Q\cap[g]|-\lceil 12s|G^{\prime}|\rceil$). Note that
$Q_{1}$ is coset-paired (since it has even intersection with self-paired
cosets and intersection $\lceil 12s|G^{\prime}|\rceil$ with other pairs of
cosets) and so we can partition it into a set of
$|Q_{1}|/2\leq|Q|\leq\frac{p^{800}n}{10^{4150}\log n}$ pairs $P_{1}$. For each
$g$, let $h_{g}=|Q\cap[g]|-i_{[g]}\lceil s|G^{\prime}|\rceil$, noting that
this is nonnegative by (i). Use Lemma 5.24 (1) or (2) to pick a subset
$R_{g}\subseteq R$ which $h_{g}$-absorbs $Q\cap[g]$ (if $|G^{\prime}|\geq
s^{-1}/12$, then, using condition (ii), part (1) of that lemma gives this.
Otherwise, we have that $Q$ intersects no self-paired cosets and $\lceil
s|G^{\prime}|\rceil=1$ and so part (2) gives it). Set $h_{P}=\sum_{[g]\in
K}i_{[g]}\lceil s|G^{\prime}|\rceil$, noting that this is even. Also note that
we can assume that $m$ is even and $\leq h_{g}$ (otherwise there could be no
coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded $S$ of size $m$
contained in $Q$). So, we can use Lemma 5.24 (3) to pick a subset $R_{P}$
which $\frac{1}{2}(h_{P}-m)$-absorbs $P_{1}$. We can ensure that these are all
disjoint by enlarging $U$ as we choose them (the maximum total size of sets we
need to avoid is $|U|+\sum_{[g]\in K}|R_{g}|\leq|U|+\sum_{[g]\in K}10^{6}\log
n|Q\cap[g]|\leq|U|+10^{6}\log n|Q|\leq p^{800}n/10^{4150}+10^{6}\log
n(\frac{p^{800}n}{10^{4150}\log n})\leq p^{800}n/10^{4140}$). Let
$R^{\prime}=R_{P}\cup\bigcup P_{1}\cup\bigcup_{g\in K}R_{g}$.

Consider some coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded
$S\subseteq Q$ of size $m$. Since $S$ is coset-paired, $|S\cap[g]|/i_{[g]}$ is
an integer for all $[g]$.

######  Claim 5.25.1.

There is a subset $P_{1}^{\prime}\subseteq P_{1}$ of pairs disjoint from $S$
which have $\lceil s|G^{\prime}|\rceil-|S\cap[g]|/i_{[g]}$ pairs intersecting
each $[g]\in K$.

###### Proof.

First suppose that $\lceil s|G^{\prime}|\rceil=1$. Note that for each $[g]\in
K$ this means that we need to select at most one pair intersecting $[g]$, and
we only need to do so when $S\cap[g],S\cap[\phi(g)]=\emptyset$. In this case
we have $|Q_{1}\cap[g]|=|Q_{1}\cap[\phi(g)]|=i_{[g]}|\lceil
12s|G^{\prime}|\rceil$ and so there is at least one pair in $P_{1}$ contained
$[g]\cup[\phi(g)]$ (and choosing that pair works).

Next suppose that $\lceil s|G^{\prime}|\rceil>1$, which implies that
$s|G^{\prime}|\geq\lceil s|G^{\prime}|\rceil-1\geq\lceil
s|G^{\prime}|\rceil/2$. Then $|Q_{1}\cap[g]|=i_{[g]}\lceil
12s|G^{\prime}|\rceil\geq 12s|G^{\prime}|\geq 6\lceil s|G^{\prime}|\rceil$.
Thus there are at least $3\lceil s|G^{\prime}|\rceil$ pairs contained in
$[g]\cup[\phi(g)]$. At most $2\lceil s|G^{\prime}|\rceil$ of them can
intersect $S\cap([g]\cup[\phi(g)])$ and so we can choose $\lceil
s|G^{\prime}|\rceil-|S\cap[g]|/i_{[g]}$ of them disjointly from $S$. ∎

Note that $|P_{1}^{\prime}|=\frac{1}{2}|\bigcup
P_{1}^{\prime}|=\frac{1}{2}\sum_{[g]\in K}i_{[g]}(\lceil
s|G^{\prime}|\rceil-|S\cap[g]|/i_{[g]})=\frac{1}{2}(h_{P}-m)$. By the property
of $R_{P}$, there is a matching $M_{P}$ with vertex set $R_{P}\cup\bigcup
P_{1}^{\prime}$. For each $g\in K$, note that $|[g]\cap(S\cup\bigcup
P_{1}^{\prime})|=i_{[g]}\lceil s|G^{\prime}|\rceil$ and so
$|[g]\cap(Q\setminus(S\cup\bigcup P_{1}^{\prime}))|=h_{g}$. By the property of
$R_{g}$, there is a matching $M_{g}$ with vertex set
$R_{g}\cup([g]\cap(Q\setminus(S\cup\bigcup P_{1}^{\prime})))$. The union of
these matchings has vertex set $(R_{P}\cup\bigcup
P_{1}^{\prime})\cup\bigcup_{[g]\in K}R_{g}\cup([g]\cap(Q\setminus(S\cup\bigcup
P_{1}^{\prime})))=R^{\prime}\cup\bigcup
P_{1}^{\prime}\cup(Q\setminus(S\cup\bigcup
P_{1}^{\prime}))=R^{\prime}\cup(Q\setminus S)$ as required. ∎

The following simple lemma covers generic sets by matchings.

######  Lemma 5.26.

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 $U\subseteq V(H_{G})$ and any generic $X\subseteq V(H_{G})$ with
$|X|,|U|\leq p^{800}n/10^{4010}$, there is a matching $M$ of size $|X|$ in
$H_{G}$ covering $X$ and having all other vertices in $R\setminus U$.

###### Proof.

With high probability, the property of Lemma 5.5 applies i.e. 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$. Now let $U\subseteq V(H_{G})$ and any generic
$X\subseteq V(H_{G})$ with $|X|,|U|\leq p^{800}n/10^{4010}$. Applying the
property of Lemma 5.5 to each $v\in X$ we get edges $e_{v}$ passing through
$v$ and having other vertices in $R\setminus U$. By enlarging $U$ as we choose
these to include previously found vertices, we can ensure that all $e_{v}$ are
disjoint i.e. they give us a matching like the lemma asks for. ∎

The following is a variant of Lemma 5.25 where $Q$ is a random set.

######  Lemma 5.27.

Let $p\geq n^{-1/701}$ and $q\leq\frac{p^{800}}{10^{4160}\log n}$. Let $H_{G}$
be a multiplication hypergraph, $R^{1},R^{2},R^{3}$ disjoint, symmetric
$p$-random subsets of $G$ and $Q$ a disjoint $q$-random subset. Set
$R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$. With high probability, the
following holds:

Let $s\leq\frac{q^{2}p^{800}}{10^{4160}\log^{3}n}$. For every $m\in\mathbb{N}$
and $U\subseteq G$ with $|U|\leq q^{2}p^{800}n/10^{4160}$, there is a
$U^{\prime}$ with $U\subseteq U^{\prime}\subseteq U\cup Q$, $|U^{\prime}|\leq
5q^{-1}|U|+50s^{-1}$, and $R^{\prime}\subseteq R\setminus U$ such that for all
coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded $S\subseteq
Q\setminus U^{\prime}$ of size $m$, there is a matching with vertex set
$R^{\prime}\cup(Q\setminus(S\cup U^{\prime}))$.

###### Proof.

Randomly split each $R^{i}$ into two disjoint, symmetric $p/2$-random sets
$R^{i}_{-}$, $R^{i}_{+}$. Set $R^{-}=R^{1}_{-A}\cup R^{2}_{-B}\cup R^{3}_{-C}$
and $R^{+}=R^{1}_{+A}\cup R^{2}_{+B}\cup R^{3}_{+C}$. Note that the following
hold with high probability.

  1. (A1)

$R^{-}$ satisfies Lemmas 5.25 while $R^{+}$ satisfies Lemma 5.26.

  2. (A2)

When $|G^{\prime}|\geq q^{-2}\log^{2}n$, then
$|Q\cap[g]|\in[q|G^{\prime}|/2,2q|G^{\prime}|]$ for all $g\in G$ (from
Chernoff’s bound).

  3. (A3)

$|Q|\leq qn+\sqrt{n}\log n\leq\frac{p^{800}n}{10^{4150}\log n}$ (from
Chernoff’s bound).

Now let $s\leq\frac{q^{2}p^{800}}{10^{4160}\log^{3}n}\leq q^{2}\log^{-2}n/12$,
$m\in\mathbb{N}$, and $U\subseteq G$ with $|U|\leq q^{2}p^{800}n/10^{4160}$.
When $|G^{\prime}|\leq s^{-1}/12$, let $U_{1}$ be the union of self-paired
cosets, noting that $|U_{1}|\leq 30|G^{\prime}|\leq 30s^{-1}$. When
$|G^{\prime}|>s^{-1}/12$, let $U_{1}$ be the union of cosets $[g]$ and their
pairs for which $|(U\cup N(G))\cap[g]|\geq q|G^{\prime}|/10$, noting that
$|U_{1}|\leq 2|G^{\prime}|\frac{|U|+|N(G)|}{q|G^{\prime}|/10}$. Set
$U^{\prime}=U\cup N(G)\cup U_{1}$, noting that $|U^{\prime}|\leq
5q^{-1}|U|+6q^{-1}|N(G)|+30s^{-1}\leq 5q^{-1}|U|+6q^{-1}10^{9000}+30s^{-1}\leq
5q^{-1}|U|+50s^{-1}$. Set $Q_{1}=Q\setminus U^{\prime}$. Let $Q_{2}\subseteq
Q_{1}$ be the subset formed by deleting all pairs of cosets for which
$Q_{1}\cap[g]$ or $Q_{1}\cap[\phi(g)]$ is empty. Note that $Q_{2}$ satisfies
all of the following properties.

  1. 1.

$Q_{2}$ is generic (since it’s disjoint from $N(G)$).

  2. 2.

$|Q_{2}|\leq\frac{p^{800}n}{10^{4150}\log n}$ (by (A3) and $Q_{2}\subseteq
Q$).

  3. 3.

When $|G^{\prime}|\leq s^{-1}/12$, $Q_{2}$ doesn’t intersect self-paired
cosets (since it’s disjoint from $U_{1}$).

  4. 4.

When $|G^{\prime}|\leq s^{-1}/12$, for all $g\in G$ we have that either
$Q_{2}\cap[g]=Q_{2}\cap[h]=\emptyset$ or $i_{[g]}\lceil
12s|G^{\prime}|\rceil=1\leq|Q_{2}\cap[g]|,|Q_{2}\cap[h]|$ (by construction of
$Q_{2}$ from $Q_{1}$).

  5. 5.

When $|G^{\prime}|>s^{-1}/12$, for all $[g]$ either
$Q_{2}\cap[g]=Q_{2}\cap[h]=\emptyset$ or we have $i_{[g]}12s|G^{\prime}|\leq
24s|G^{\prime}|\leq q|G^{\prime}|/4\leq
q|G^{\prime}|/2-q|G^{\prime}|/10\leq|Q_{2}\cap[g]|,|Q_{2}\cap[h]|\leq
2q|G^{\prime}|\leq\frac{p^{800}|G^{\prime}|}{10^{4150}\log n}$ (by (A2), since
$Q_{2}$ is disjoint from $U_{1}$, and since
$s\leq\frac{q^{2}p^{800}}{10^{4160}\log^{3}n}$,
$q\leq\frac{p^{800}}{10^{4160}\log n}$).

Thus Lemma 5.25 applies to $Q_{2}$. This gives us a set $R^{\prime-}\subseteq
R^{-}\setminus U$. By Lemma 5.26, there is a matching $M_{1}$ covering
$Q_{1}\setminus Q_{2}$ with $V(M_{1})\setminus(Q_{1}\setminus Q_{2})\subseteq
R^{+}\setminus U$. Set $R^{\prime}=R^{\prime-}\cup(M_{1}\setminus Q)\subseteq
R\setminus U$. This is possible as $Q_{1}\setminus Q_{2}\subseteq Q$ and (A3).

Now consider a coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded
$S\subseteq Q\setminus U^{\prime}=Q_{1}$ of size $m$. Note that we must have
$S\subseteq Q_{2}$ because $S$ is coset paired (and for every $g\in
Q_{1}\setminus Q_{2}$ we have $[\phi(g)]\cap Q_{1}$ empty). Therefore, Lemma
5.25 gives us a matching $M_{2}$ with vertex set
$R^{\prime-}\cup(Q_{2}\setminus S)$. Combining this with $M_{1}$ gives a
matching with vertex set $R^{\prime-}\cup(Q_{2}\setminus S)\cup(M_{1}\setminus
Q)\cup(Q_{1}\setminus Q_{2})=R^{\prime}\cup(Q_{1}\setminus
S)=R^{\prime}\cup(Q\setminus(S\cup U^{\prime}))$ as required. ∎

The following shows that large coset-paired matchings exist inside random
sets.

######  Lemma 5.28.

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:

Let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4140}$. For any
$k\in[1,|G^{\prime}|]$, there is a coset-paired, $k$-coset-bounded matching of
size $\frac{p^{800}nk}{10^{4140}|G^{\prime}|}$ in $R\setminus U$.

###### Proof.

With high probability, Lemma 3.32 applies. When $|G^{\prime}|\leq
n/\log^{10^{20}}n$, consider the set

$S=\\{x,x^{-1}a_{\phi},y,b_{\phi}y^{-1},y^{-1}x^{-1},yc_{\phi}x\\}\subseteq
G\ast F_{2}.$

When $|G^{\prime}|>n/\log^{10^{20}}n$, consider the set

$S=\\{x_{1},x_{2}a_{\phi},y_{1},y_{2}b_{\phi},y_{1}^{-1}x_{1}^{-1},y_{2}c_{\phi}x_{2}\\}\subseteq
G\ast F_{4}.$

Note that in either case all words in $S$ are linear and all pairs of words
are separable (using part (a) or (c) of the definition of “separable”. For
checking (c), we use that for any
$(w,w^{\prime})=(x,x^{-1}a_{\phi}),(y,b_{\phi}y^{-1}),(y^{-1}x^{-1},yc_{\phi}x)$
we have
$\pi_{0}(ww^{\prime}),\pi_{0}(w^{-1}w^{\prime})\in\\{a_{\phi},b_{\phi},c_{\phi},a_{\phi}^{-1},b_{\phi}^{-1},c_{\phi}^{-1}\\}$,
which all satisfy (c) from Lemma 3.14).

Let $U\subseteq G$ with $|U|\leq p^{800}n/10^{4120}$. If $|G^{\prime}|\leq
p^{800}n/10^{4120}$ add all self-paired cosets to $U$ in order to get a set
$U^{\prime}$ with $|U^{\prime}|\leq p^{800}n/10^{4110}$ (otherwise set
$U^{\prime}=U$). Use Lemma 3.32 to get a projection $\pi$ which separates $S$
and has $\pi(S)\subseteq R\setminus U^{\prime}$. This gives us a coset-paired
matching of size $2$ as in the lemma (whose edges are
$(\pi(x),\pi(y),\pi(y^{-1}x^{-1}))$ and
$(\pi(x^{-1}a_{\phi}),\pi(b_{\phi}y^{-1}),\pi(yc_{\phi}x))$). To get one of
size $\frac{p^{800}nk}{10^{4140}|G^{\prime}|}$, keep selecting multiple
matchings like this, enlarging $U$ at every step in order to keep them
disjoint (we can do this as long as $3|G^{\prime}||M|k^{-1}\leq
p^{800}n/10^{4130}$. Indeed for a matching $M$, letting $U_{M}$ be the union
of cosets $[g]$ having $|V(M)\cap[g]|\geq k$, note that
$|U_{M}|/|G^{\prime}|\leq|V(M)|/k$ which gives $|U_{M}|\leq
3|G^{\prime}||M|/k$. For any pair of edges outside $U\cup U_{M}$, adding them
to $M$ gives a bigger matching like we want). ∎

Now we arrive at the main lemma of this section. The following again shows
that we can absorb the complement of a coset-paired set. Unlike Lemmas 5.25
and 5.27, this one allows the coset-paired set to have variable size.

######  Lemma 5.29.

Let $q,p\geq n^{-1/701}$ with $q\leq\frac{p^{801}}{10^{4170}\log n}$. Let
$H_{G}$ be a multiplication hypergraph, let
$R^{1},R^{2},R^{3},Q_{1},Q_{2},Q_{3}$ be disjoint, symmetric subsets of $G$
with $R^{1},R^{2},R^{3}$ $p$-random and $Q_{1},Q_{2},Q_{3}$ $q$-random
subsets. Set $R=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$ and $Q=Q^{1}_{A}\cup
Q^{2}_{B}\cup Q^{3}_{C}$. With high probability, the following holds:

Let $s\leq\frac{q^{1600}p^{10^{7}}}{10^{10^{7}}\log^{2400}n}$, $U\subseteq G$
with $|U|\leq q^{9}p^{800}n/10^{4170}$. There is a $U^{\prime}\subseteq U$
with $|U^{\prime}|\leq 500q^{-3}|U|+10^{10}s^{-3}$, and $R^{\prime}\subseteq
R\setminus U$ such that for all coset-paired, $\lceil
s|G^{\prime}|\rceil$-coset-bounded, balanced $S\subseteq Q\setminus
U^{\prime}$, with $|S|\leq s^{2}n$ there is a matching with vertex set
$R^{\prime}\cup(Q\setminus(S\cup U^{\prime}))$.

###### Proof.

Set $m:=8\lceil sn\rceil$ and $s^{\prime}:=s^{1/800}10^{4140}$. Split $R$ into
three disjoint, symmetric $p/3$-random subsets $R_{1},R_{2},R_{3}$ of
$V(H_{G})$ (by placing each $\hat{g}$ in $R_{1}/R_{2}/R_{3}$ with probability
$1/3$, and making these choices independently of those for the random sets
$R^{1},R^{2},R^{3}$ in the lemma. So now for all $i$ $R_{i}\cap R^{1}_{A}$,
$R_{i}\cap R^{2}_{B}$, $R_{i}\cap R^{3}_{C}$ are three disjoint, symmetric
$p/3$-random subsets of $G$ partitioning $R_{i}$). Lemma 5.27 applies to each
pair $R^{\prime}=R_{i},Q^{\prime}=Q_{i}$ for $i=1,2,3$ (with $R^{\prime
1}=R_{i}\cap R^{1}_{A}$, $R^{\prime 2}=R_{i}\cap R^{2}_{B}$, $R^{\prime
3}=R_{i}\cap R^{3}_{C}$). Lemma 5.28 applies to $Q$. Let $U_{0}:=U$ be as in
the lemma. For $i=1,2,3$ build $U_{1},U_{2},U_{3},R_{1},R_{2},R_{3}$ by
applying Lemma 5.27 to $R_{i},Q_{i}$ with $U=U_{i-1}$, $m=m,s=4s^{\prime}$.
The end result is sets $R_{1}^{\prime}\subseteq R_{1},R_{2}^{\prime}\subseteq
R_{2},R_{3}^{\prime}\subseteq R_{3}$ and a set $U^{\prime}$ with
$|U^{\prime}|\leq 500q^{-3}|U|+10^{10}s^{-3}$ such that for all coset-paired,
$\lceil 4s^{\prime}|G^{\prime}|\rceil$-coset-bounded $S_{i}\subseteq
Q_{i}\setminus U^{\prime}$ of size $m$, there are matchings with vertex sets
$R_{i}^{\prime}\cup(Q_{i}\setminus(S_{i}\cup U^{\prime}))$. Set
$R^{\prime}=R_{1}^{\prime}\cup R_{2}^{\prime}\cup R_{3}^{\prime}$. Use Lemma
5.28 with $k=\lceil s^{\prime}|G^{\prime}|\rceil$ to find a coset-paired,
$\lceil s^{\prime}|G^{\prime}|\rceil$-coset-bounded matching $M_{0}$ of size
$\frac{p^{800}nk}{10^{4140}|G^{\prime}|}\geq q^{800}s^{\prime}n/10^{4140}\geq
8m$ in $Q_{1}\cup Q_{2}\cup Q_{3}\setminus U^{\prime}$.

Now, consider a coset-paired, $\lceil s|G^{\prime}|\rceil$-coset-bounded,
balanced $S\subseteq Q\setminus U^{\prime}$ with $|S|\leq s^{2}n$. Let
$m_{0}=|S\cap G_{A}|=|S\cap G_{B}|=|S\cap G_{C}|\leq s^{2}n$, noting that
these are even by coset-pairedness.

######  Claim 5.29.1.

There is a coset-paired submatching $M_{0}^{\prime}\subseteq M_{0}$ of size
$m-m_{0}$ disjoint from $S$. Additionally when $|G^{\prime}|\leq s^{-1}$, then
$M_{0}^{\prime}$ and $S$ never intersect the same cosets.

###### Proof.

When $|G^{\prime}|\leq s^{-1}$ let $S^{\prime}$ be the union of cosets
intersecting $S$, otherwise let $S^{\prime}=S$. Note that in either case
$|S^{\prime}|\leq|S|s^{-1}\leq sn\leq m$. Since $|M_{0}|\geq 8m$, there is a
paired submatching $M_{0}^{\prime}\subseteq M_{0}$ of size $m-m_{0}$ disjoint
from $S^{\prime}$. ∎

Now set $S_{1}^{\prime}:=(S\cup M_{0}^{\prime})\cap G_{A}$,
$S_{2}^{\prime}:=(S\cup M_{0}^{\prime})\cap G_{B}$, $S_{3}^{\prime}:=(S\cup
M_{0}^{\prime})\cap G_{C}$ and note that these are coset-paired, $\lceil
4s^{\prime}|G^{\prime}|\rceil$-coset-bounded sets of size $m$. By the
properties of $R_{1}^{\prime},R_{2}^{\prime},R_{3}^{\prime}$, we get matchings
$M_{1},M_{2},M_{3}$ with vertex sets
$V(M_{i})=R_{i}^{\prime}\cup(Q_{i}\setminus(S^{\prime}_{i}\cup U^{\prime}))$.
Now $M=M_{0}^{\prime}\cup M_{1}\cup M_{2}\cup M_{3}$ is a matching with vertex
set
$V(M_{0}^{\prime})\cup\bigcup_{i=1}^{3}R_{i}^{\prime}\cup(Q_{i}\setminus(S^{\prime}_{i}\cup
U^{\prime}))=R^{\prime}\cup V(M_{0}^{\prime})\cup(Q\setminus(S\cup
M_{0}^{\prime}\cup U^{\prime}))=R^{\prime}\cup(Q\setminus(S\cup U^{\prime}))$
as required. ∎

###  5.3 Absorbing zero-sum sets

The goal of this section is to prove a lemma which can absorb arbitrary
balanced zero-sum sets (Lemma 5.32). To do this we first prove results about
covering zero-sum sets using coset-paired matchings.

####  5.3.1 Covering zero-sum sets

Here we prove Lemma 5.31, which roughly states that given a random vertex
subset $R$ of $H_{G}$ and a small zero-sum set $S$, there exists a coset-
paired set $R^{\prime}\subseteq R$ such that $S\cup R^{\prime}$ contains a
perfect matching. As explained in Section 2, this will allow us to reduce the
task of absorbing arbitrary zero-sum sets to absorbing coset-paired sets.

The following lemma does the majority of the work for this section. It allows
us to find the desired set $R^{\prime}$ iteratively by reducing the size of
the set of vertices we need to cover by $3$ at every step.

######  Lemma 5.30.

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.

Let $F\subseteq V(H_{G})$ be a balanced $\phi$-generic set of size $6$,
$h\in[\prod F]$, and $U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4001}$.
Then there is a matching $M$ in $H_{G}$ of size $15$ and a disjoint set
$\\{a,b,c\\}$ such that $F\subseteq V(M)$, $\\{a,b,c\\}\cup V(M)\setminus
F\subseteq R\setminus U$, $\\{a,b,c\\}\cup V(M)\setminus F$ is coset-paired
and $abc=h$. Furthermore, if $|G^{\prime}|\leq\log^{5}n/p^{2000}$, then for
each $\diamond\in\\{A,B,C\\}$, and $g\in G$ we have that $|(\\{a,b,c\\}\cup
V(M)\setminus F)\cap G_{\diamond}\cap[g]|\leq 1$.

###### Proof.

With high probability, the property of Lemma 3.32 holds. Let $F\subseteq
V(H_{G})$ be a balanced $\phi$-generic set of size $6$, $h\in[\prod F]$, and
$U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4001}$. Let
$F=\\{a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}\\}$ with $a_{i}\in G_{A},b_{i}\in
G_{B},c_{i}\in G_{C}$. Let
$k=ha_{2}^{-1}c_{1}^{-1}c_{2}^{-1}b_{2}^{-1}b_{1}^{-1}a_{1}^{-1}$ and note
that by the assumption that $h\in[\prod F]$, we know that $k\in G^{\prime}$.
Depending on whether $|G^{\prime}|\geq\log^{5}n/p^{2000}$ or not, consider the
set of words $S$ given in Figure 6 or 7, noting that blue/green/red vertices
represent a partition as $S_{A}/S_{B}/S_{C}$. Note that in either case, all
the words in $S$ are linear and all pairs of words in $S$ are weakly separable
and words in $S$ coming from different $S_{A}/S_{B}/S_{C}$ are strongly
separable (see the figure captions for justification). In fact, it will be the
case that every pair of words are strongly separable, meaning we never use
condition $(b^{\prime})$, so this distinction will not be essential in the
justification.

For $\ast=A,B,C$, let $T_{\ast}=\\{w^{-1}w^{\prime}:w,w^{\prime}\in
S_{\ast}\text{ and $w,w^{\prime}$ do not have the same free variables}\\}$,
noting that $|T_{\ast}|\leq\binom{|S_{\ast}|}{2}=\binom{14}{2}=91$ and that
elements of $T_{\ast}$ are all linear in at least one variable. If
$|G^{\prime}|>\log^{5}n/p^{2000}$, let $U^{\prime}=U\cup F$. If
$|G^{\prime}|\leq\log^{5}n/p^{2000}$, then let $U^{\prime}$ be $U$ together
with all the self-paired cosets and all the cosets intersecting $F$, and
$G^{\prime}$. Note that in both cases,
$|U^{\prime}|\leq|U|+36\log^{5}n/p^{2000}\leq p^{800}n/10^{4000}$.

Use Lemma 3.32 to get a projection $\pi$ with $\pi(S\cup T_{A}\cup T_{B}\cup
T_{C})\subseteq R\setminus(U\cup F)$ that separates $S\cup T_{A}\cup T_{B}\cup
T_{C}$ and ensures that $S_{A}\subseteq R_{1}$, $S_{B}\subseteq R_{2}$,
$S_{C}\subseteq R_{3}$ (so the matching is contained in $R$).

First, we prove the lemma without the “furthermore” part. Since all
$w,w^{\prime}\in S$ are separable, this means that all the vertices of
$\pi(S)$ are distinct. Recall that $S_{A}/S_{B}/S_{C}$ are the blue/green/red
vertices in the figures. Note that $F\cup\pi(S)$ has a partition into a
matching $M$ (given by the black triangles in Figures 8 and 9) and a set
$\\{a,b,c\\}$ having $abc=h$ (given by the pink triangle in the same figures
where $a$ is the top left vertex, $b$ is the bottom vertex, and $c$ is the top
right vertex). We claim that this matching $M$ together with the set
$\\{a,b,c\\}$ satisfy the lemma. The things that need to be verified by
inspecting the figure are as follows.

  * •

Each black triangle has that if its vertices are multiplied in the order
blue/green/red ($G_{A}/G_{B}/G_{C}$), we obtain ${e}$. This shows that the
black triangles are in fact edges of $H_{G}$.

  * •

The product of the top left, bottom, and top right vertices of the yellow
(central) triangle is $h$ (here, use the definition of $k$). This gives that
$abc=h$.

  * •

The product of the blue/green/red edges belongs to
$[a_{\phi}]/[b_{\phi}]/[c_{\phi}]$. In the case where $|G^{\prime}|\geq
10^{-9}n$, note that we select the black (free) variables from $G^{\prime}$,
hence they can be ignored while performing this check. This shows that
$\\{a,b,c\\}\cup V(M)\setminus F$ is coset-paired.

For the “furthermore” part, we have that $|G^{\prime}|\leq\log^{5}n/p^{2000}$.
For $\ast=A,B,C$, notice that for all $w,w^{\prime}\in S_{\ast}$ we either
have that $(\pi(w),\pi(w^{\prime}))$ is a pair, or there is a free variable
which appears in one of $w/w^{\prime}$, but not both (to check this, note that
for any vertices $w,w^{\prime}$ of the same colour in Figure 8, either
$w,w^{\prime}$ are joined by an edge or $w$ and $w^{\prime}$ have different
combinations of black letters). In the first case we have that
$[\pi(w)]\neq[\pi(w^{\prime})]$ since $\pi(S)$ is disjoint from all self-
paired cosets. In the second case we have $w^{-1}w^{\prime}\in T_{\ast}$,
which implies $\pi(w^{-1}w^{\prime})\not\in G^{\prime}$ (since
$G^{\prime}\subseteq U^{\prime}$), or equivalently
$[\pi(w)]\neq[\pi(w^{\prime})]$. ∎

Figure 6: The set $S$ when $|G^{\prime}|\leq 10^{-9}n$. Black letters
represent free variables, while pink ones represent elements of $G$. The words
are grouped into rectangles $S_{T}$ based on which free variables occur where,
as in Observation 3.24. To see that all words in $S$ are linear, check that
there are no repetitions of black letters in any word (and every word has at
least one black letter). To see that any pair $w,w^{\prime}$ is strongly
separable, note that by Observation 3.24, any $w,w^{\prime}$ coming from
different rectangles fall under part (a) of the definition of separable. In
the coloured rectangles, there are always two words $w,w^{\prime}$ which fall
under part (c) of the definition of strongly separable (to check this first
notice that $w,w^{\prime}$ have the same free variables, verifying the 2nd
bullet point. The free variables occur with opposite signs in $w,w^{\prime}$
verifying the 4th bullet point. We have
$\pi_{0}(ww^{\prime})\in[a_{\phi}]\cup[b_{\phi}]\cup[c_{\phi}]$ so in
particular $\pi_{0}(ww^{\prime})\not\in G^{\prime}$, verifying the 3rd bullet
point. Finally, since
$\pi_{0}(ww^{\prime})\in[a_{\phi}]\cup[b_{\phi}]\cup[c_{\phi}]$, there are
$\leq 90|G^{\prime}|$ solutions to
$x^{2}\in[a_{\phi}]\cup[b_{\phi}]\cup[c_{\phi}]$ verifying the last bullet
point). This leaves the grey rectangles. In each such rectangle the four
elements are $v,v^{-1}d_{i}^{-1},v^{-1}e_{\phi},d_{i}f_{\phi}v$ for a free
variable $v$, $i\in\\{1,2\\}$, and $(d,e,f)$ some permutation of $(a,b,c)$.

  * •

The pair $w=v^{-1}d_{i}^{-1},w^{\prime}=d_{i}f_{\phi}v$ falls under (c)
because
$\pi_{0}(ww^{\prime})=\pi_{0}(v^{-1}d_{i}^{-1}d_{i}f_{\phi}v)=f_{\phi}$.

  * •

All other pairs fall under (b), as witnessed by the following equations
$v=v^{-1}d_{i}^{-1}$, $v=d_{i}f_{\phi}v$, $v=v^{-1}e_{\phi}$,
$v^{-1}d_{i}^{-1}=(v^{-1}e_{\phi})(e_{\phi}^{-1}d_{i}^{-1})$,
$v^{-1}e_{\phi}=(d_{i}f_{\phi}v)^{-1}(d_{i}f_{\phi}e_{\phi})$. The elements
$g$ in these equations are $e_{\phi},d_{i}$,
$d_{i}f_{\phi},e_{\phi}^{-1}d_{i}^{-1},d_{i}f_{\phi}e_{\phi}$, which are all
generic (since $d_{i}$ is $\phi$-generic).

Figure 7: The set $S$ when $|G^{\prime}|\geq n/10^{9}$. Black letters
represent free variables, while pink ones represent elements of $G$. The words
here are exactly the same as in Figure 6, except that there are more free
variables e.g. instead of the free variable $x$, we have free variables
$x_{1},x_{2},x_{11},x_{12}$ with $x$ replaced by one of
$x_{1},x_{2},x_{11},x_{12}$ wherever it occurred. The words are grouped into
rectangles $S_{T}$ based on which free variables occur where, as in
Observation 3.24. To see that all words in $S$ are linear, check that there
are no repetitions of black letters in every word (and every word has at least
one black letter). To see that all $w,w^{\prime}\in S$ are strongly separable,
note that from Observation 3.24 this holds when $w,w^{\prime}$ come from
different rectangles. This leaves only the pairs inside
$S_{x_{1}},S_{y_{3}},S_{z_{5}},S_{w_{7}},S_{s_{9}},S_{t_{16}}$, which are
separable by (b) since $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}$ are generic.
Figure 8: The set $S$ when $|G^{\prime}|\leq 10^{-9}n$. Blue, green, and red
vertices give a partition of $S$ into sets $S_{A}/S_{B}/S_{C}$ which are
pairwise strongly separable. Black letters represent free variables, while
pink ones represent elements of $G$. The elements
$a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}$ are not part of $S$, they are depicted
only to illustrate the matching. The black triangles are matching edges, while
the yellow triangle is the set $\\{a,b,c\\}$. Note that the yellow triangle is
an edge if and only if $k={e}$. Figure 9: The set $S$ when
$|G^{\prime}|>10^{-9}n$. Blue, green, and red vertices give a partition of $S$
into sets $S_{A}/S_{B}/S_{C}$ which are pairwise strongly separable. Black
letters represent free variables, while pink ones represent elements of $G$.
The elements $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}$ are not part of $S$. This
set is exactly the same as Figure 8, except that there are more free
variables. More precisely, for every black/pink triangle we introduce new
variables and use them only in words occurring inside that triangle. The black
triangles are matching edges, while the yellow triangle is the set
$\\{a,b,c\\}$ where $a$ is the top left vertex, $b$ is the bottom vertex, and
$c$ is the top right vertex.

Now, we may prove the main result of this section.

######  Lemma 5.31.

Let $p\geq n^{-1/10^{20}}$. 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:

Let $S\subseteq V(H_{G})$ be a balanced and $\phi$-generic subset with $\prod
S\in G^{\prime}$ and $|S|\leq\frac{p^{10^{13}}}{10^{10^{6}}\log(n)^{10^{8}}}$.
Let $U\subseteq V(H_{G})$ with $|U|\leq p^{800}n/10^{4100}$. Then, there
exists a matching $M$ in $H_{G}$ with the following properties.

  1. Q1

$S\subseteq V(M)$

  2. Q2

$V(M)\setminus S\subseteq R\setminus U$

  3. Q3

$V(M)\setminus S$ is coset-paired

  4. Q4

If $|G^{\prime}|\leq\log(n)^{8000}/p^{10^{10}}$, then for each
$\diamond\in\\{A,B,C\\}$, and $g\in G$ we have that $|(V(M)\setminus S)\cap
G_{\diamond}\cap[g]|\leq 1$.

###### Proof.

With high probability, the property of Lemma 5.30 holds and Lemma 3.34 applies
to each $R^{1},R^{2},R^{3}$. Let $S\subseteq V(H_{G})$ be a balanced and
$\phi$-generic subset with $\prod S\in G^{\prime}$ and
$|S|\leq\frac{p^{10^{13}}}{10^{10^{6}}\log(n)^{10^{8}}}$ and $U\subseteq
V(H_{G})$ with $|U|\leq p^{800}n/10^{4010}$. Without loss of generality, we
can assume that $|S|\geq 6$ (if this doesn’t hold, then pick $\phi$-generic
vertices $a,a^{\prime},b,b^{\prime},c,c^{\prime}\in R\setminus(S\cup U)$ with
$aa^{\prime}=a_{\phi},bb^{\prime}=b_{\phi},cc^{\prime}=c_{\phi}$ using Lemma
3.34, and define
$S^{\prime}=S\cup\\{a,a^{\prime},b,b^{\prime},c,c^{\prime}\\}$. Now
$S^{\prime}$ is a set with $|S^{\prime}|\geq 6$, so we can continue the proof
with $S^{\prime}$ rather than $S$. (In the case when
$|G^{\prime}|\leq\log(n)^{8000}/p^{10^{10}}$ we can include in $U$ the
$30|G^{\prime}|\ll\sqrt{n}$ many elements of $G$ in self-paired cosets before
applying Lemma 3.34 to guarantee that the pairs we are adding come from
distinct cosets. This way, Q4 is not violated.)

Set $t=|S|/3$. Since $S$ is balanced we can write
$S=\\{a_{1},\dots,a_{t},b_{1},\dots,b_{t},c_{1},\dots,c_{t}\\}$ with $a_{i}\in
G_{A},b_{i}\in G_{B},c_{i}\in G_{C}$.

We build matchings $M_{2},\dots,M_{t}$ and $\phi$-generic vertices
$\\{a_{2}^{\prime},\dots,a_{t}^{\prime},b_{2}^{\prime},\dots,b_{t}^{\prime},c_{2}^{\prime},\dots,c_{t}^{\prime}\\}$
as follows. Define
$a^{\prime}_{2}=a_{1},b^{\prime}_{2}=b_{1},c^{\prime}_{2}=c_{1}$. Given a
subset $S\subseteq G$, denote by $\psi(S)$ the set of all $g$ in $G$ such that
there exists some $s\in S$ with $[s]=[g]$. Observe that
$|\psi(S)|\leq|S|\cdot|G^{\prime}|$. For $i=2,\dots,t-1$ apply Lemma 5.30 to
$F_{i}=\\{a_{i},b_{i},c_{i},a^{\prime}_{i},b^{\prime}_{i},c^{\prime}_{i}\\}$
and

$U=U\cup N(G)\cup\bigcup_{j<i}\psi(V(M_{i}))$

in the case when $|G^{\prime}|\leq\log(n)^{8000}/p^{10^{10}}$ and

$U=U\cup N(G)\cup\bigcup_{j<i}V(M_{i})$

otherwise. This way, we obtain a matching $M_{i}$ and a set
$\\{a_{i+1}^{\prime},b_{i+1}^{\prime},c_{i+1}^{\prime}\\}$ (use an arbitrary
choice of $h$ from the corresponding $G^{\prime}$-coset for these
applications). Further, Q4 is maintained for $\bigcup_{j\leq i}M_{i}$ in the
case when $|G^{\prime}|\leq\log(n)^{8000}/p^{10^{10}}$ by our inclusion in $U$
of all previously used $G^{\prime}$-cosets. To see that the necessary upper
bound on $U$ holds for this application, note that when
$|G^{\prime}|\leq\log(n)^{8000}/p^{10^{10}}$, we have that
$|\bigcup_{j<i}\psi(V(M_{i}))|\leq 100t|G^{\prime}|\leq
100\left(\frac{p^{10^{13}}}{10^{10^{6}}\log(n)^{10^{8}}}\right)(\log(n)^{8000}/p^{10^{10}})\ll
p^{800}n/10^{4001}$. Otherwise, when $|G^{\prime}|$ is large, we have that
$|\bigcup_{j<i}V(M_{i})|\leq 100t\ll p^{800}n/10^{4001}$ as well.

Notice that $a^{\prime}_{t}b^{\prime}_{t}c^{\prime}_{t}a_{t}b_{t}c_{t}\in
G^{\prime}$ (to see this, show that for all $i$ we have
$a^{\prime}_{i}b^{\prime}_{i}c^{\prime}_{i}a_{i}b_{i}c_{i}a_{i+1}b_{i+1}c_{i+1}\dots
a_{t}b_{t}c_{t}\in G^{\prime}$ by induction. The initial case is just the
assumption $\prod S\in G^{\prime}$. For the induction step use that Lemma 5.30
gives
$[a^{\prime}_{i}b^{\prime}_{i}c^{\prime}_{i}a_{i}b_{i}c_{i}]=[a^{\prime}_{i+1}b^{\prime}_{i+1}c^{\prime}_{i+1}]$).
Now apply Lemma 5.30 to
$F_{t}=\\{a_{t},b_{t},c_{t},a^{\prime}_{t},b^{\prime}_{t},c^{\prime}_{t}\\}$
with $h={e}\in G^{\prime}$ and $U=U\cup N(G)\cup\bigcup_{j<t}V(M_{i})$ in
order to obtain a matching $M_{t}$ and a set $\\{a,b,c\\}$ with $abc={e}$. Let
$M=\bigcup_{i=2}^{t}M_{i}\cup\\{abc\\}$ in order to get a matching satisfying
the lemma. Checking Q1-Q2 is routine. To verify Q3, note that Lemma 5.30 tells
us that $N_{i}:=\\{a_{i+1}^{\prime},b_{i+1}^{\prime},c_{i+1}^{\prime}\\}\cup
V(M_{i})\setminus F_{i}$ is coset-paired for $i=2,\dots,t-1$ and also that
$N_{t}:=\\{a,b,c\\}\cup M_{t}\setminus F_{t}$ is coset-paired. Note that
$\bigcup_{j<i}N_{i}\subseteq F_{i}\cup\bigcup_{j<i}V(M_{i})$ for each $i$,
which shows that $N_{1},\dots,N_{t}$ are disjoint ($N_{i}$ is trivially
disjoint from $F_{i}$, and is disjoint from $\bigcup_{j<i}V(M_{i})$ by choice
of $U$ when applying Lemma 5.30). Also, $\bigcup_{i=1}^{t}N_{i}=V(M)\setminus
S$, which shows that this set is coset-paired as well.

∎

####  5.3.2 The zero-sum absorption lemma

Now we arrive at the main lemma of this section.

######  Lemma 5.32.

Let $n^{-1/10^{100}}\leq p$. Let $R^{1},R^{2},R^{3}\subseteq G$ be disjoint,
symmetric $p$-random subsets and set $R=R^{1}_{A}\cup R^{2}_{B}\cup
R^{3}_{C}$. With high probability, the following holds.

Let $U\subseteq G$ with $|U|\leq p^{10^{14}}n/\log(n)^{10^{14}}$. Then, there
exists a subset $R^{\prime}\subseteq R\setminus U$ such that for all balanced
and $\phi$-generic subsets $S\subseteq V(H_{G})\setminus R^{\prime}$ with
$|S|\leq\frac{p^{10^{13}}}{10^{10^{8}}\log(n)^{10^{8}}}$, $\sum S=0$, there
exists a matching with vertex set $R^{\prime}\cup S$.

We remark that the set $R^{\prime}$ in this lemma is always balanced and zero-
sum. To see this, notice that the conclusion of the lemma applies with
$S=\emptyset$ (since the empty set is balanced and zero-sum). This gives a
matching with vertex set $R^{\prime}\cup\emptyset=R^{\prime}$. Since matchings
are balanced and zero-sum, we get that $R^{\prime}$ is balanced and zero-sum.

###### Proof.

Let $q=\frac{p^{801}}{10^{4180}\log n}$ and
$s=\frac{q^{1600}p^{10^{7}}}{10^{10^{6}}\log^{2400}n}$. For each
$i\in\\{1,2,3\\}$, let $Q^{i},W^{i}$ be $q$-random and $s^{4}$-random,
symmetric subsets of $G$ respectively, satisfying $W^{i}\subseteq
Q^{i}\subseteq R^{i}$. Note that $Q^{1},Q^{2},Q^{3}$ and $W^{1},W^{2},W^{3}$
are disjoint, symmetric $q$-random and disjoint, symmetric $s$-random subsets
of $G$, respectively. The following all hold simultaneously with high
probability.

  1. 1.

Lemma 5.29 holds for $R^{1},R^{2},R^{3}$ and $Q^{1},Q^{2},Q^{3}$.

  2. 2.

Lemma 5.31 holds for $W^{1},W^{2},W^{3}$ (observe that $s^{4}\geq
n^{-1/10^{20}}$).

  3. 3.

If $|G^{\prime}|\geq s^{-5}$, each $W^{i}$ is $\lceil
2s^{4}|G^{\prime}|\rceil$-coset-bounded. (This follows by Chernoff’s bound, as
$1/s\gg\log(n)^{10}$.)

  4. 4.

$|\bigcup W_{i}|\leq 100s^{4}n$, by Chernoff’s bound.

Fix some $U\subseteq G$ such that $|U|\leq p^{10^{14}}n/\log(n)^{10^{14}}$ as
in the statement of the lemma. Note that it also follows that $|U|\leq
q^{9}p^{800}n/10^{4170}$. Then, Lemma 5.29 gives us a set $U^{\prime}\supseteq
U$ with $|U^{\prime}|\leq 500q^{-3}|U|+10^{10}s^{-3}$ and $R^{\prime}\subseteq
R\setminus U$ with the property that for all coset-paired, $\lceil
s|G^{\prime}|\rceil$-coset-bounded, balanced, $S\subseteq Q\setminus
U^{\prime}$, with $|S|\leq s^{2}n$ there is a matching with vertex set
$R^{\prime}\cup(Q\setminus(S\cup U^{\prime}))$.

We claim that $R^{\prime}\cup\bigcup_{i\in[3]}Q^{i}\setminus U^{\prime}$
satisfies the property required of $R^{\prime}$ in the statement of the lemma,
and the rest of the proof will justify this. Fix some set $S^{\prime}$ with
the properties of $S$ as in the statement of the lemma, that is, $S^{\prime}$
is $\phi$-generic, balanced, disjoint with
$R^{\prime}\cup\bigcup_{i\in[3]}W^{i}$,
$|S^{\prime}|\leq\frac{p^{10^{13}}}{10^{10^{8}}\log(n)^{10^{8}}}$, and
$S^{\prime}$ is zero-sum. Note it easily follows that $|S|\leq
p^{4000}n/\log(n)^{10}$, and we also have that $|U^{\prime}|\leq
p^{800}/10^{4100}$, so we may invoke the property of $W^{i}$ coming from Lemma
5.31 with $S=S^{\prime}$ and $U=U^{\prime}$ to deduce the existence of a
matching $M_{1}$ with properties Q1-Q4. Then, the set
$S^{\prime\prime}:=\bigcup W^{i}\cap(V(M_{1})\setminus S^{\prime})$ is coset-
paired by Q3, $\lceil s|G^{\prime}|\rceil$-coset-bounded (if $|G^{\prime}|\geq
s^{-5}$, this follows by (3), and if
$|G^{\prime}|<s^{-5}\leq\log(n)^{8000}/p^{10^{10}}$ this follows by Q4, as we
have $1$-coset-boundedness in this case), balanced, and have size at most
$s^{2}n$ (as $S^{\prime\prime}\subseteq\bigcup W^{i}$ and (4)). By property of
the set $R^{\prime}$, we have that $R^{\prime}\cup(Q\setminus(S\cup
U^{\prime}))$ has a perfect matching, $M_{2}$ say. Then, $M_{1}\cup M_{2}$ is
a perfect matching of $(R^{\prime}\cup\bigcup_{i\in[3]}Q^{i}\setminus
U^{\prime})\cup S^{\prime}$, as desired. ∎

###  5.4 Proof of Theorem 4.3

Our goal in this section is to prove the main result of the paper, Theorem
4.3, as stated in Section 4. We first prove the following slight variant which
changes the 3rd bullet point from “${e}\not\in X,Y,Z$” to the more restrictive
condition “$X,Y,Z$ are $\phi$-generic”.

######  Theorem 5.33.

Let $\alpha\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, $\alpha$-slightly-independent
subsets. Then, with high probability, the following holds.

Let $X,Y,Z$ be equal-sized subsets of $R^{1}_{A}$, $R^{2}_{B}$, and
$R^{3}_{C}$ respectively, satisfying the following properties.

  * •

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

  * •

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

  * •

All elements of $X$, $Y$ and $Z$ are $\phi$-generic.

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

###### Proof.

By the definition of $R^{1},R^{2},R^{3}$ being $\alpha$-slightly-independent,
we have $Q^{1}\subseteq R^{1},Q^{2}\subseteq R^{2},Q^{3}\subseteq R^{3}$ such
that the joint distribution of $Q^{1},Q^{2},Q^{3}$ is that of disjoint
$\alpha$-random subsets of $G$.

Partition $G$ into a $(1/10^{5})$-random subset $G_{-}$ and disjoint
$(1-1/10^{5})$-random subset $G_{+}$, making the choices independently of
$R^{1},R^{2},R^{3},Q^{1},Q^{2},Q^{3}$. For each $i=1,2,3$, let
$R^{i}_{+}=R^{i}\cap G_{+}$ to get three $(1/10^{5})p$-random subsets. Use
Lemma 3.17 to pick $Q^{1}_{-}\subseteq Q^{1}\cap G_{-},Q^{2}_{-}\subseteq
Q^{2}\cap G_{-},Q^{3}_{-}\subseteq Q^{3}\cap G_{-}$, so that their joint
distribution is that of disjoint, symmetric $\alpha/10^{10}$-random subsets of
$G$. Let $Q_{-}:=(Q^{1}_{-})_{A}\cup(Q^{2}_{-})_{B}\cup(Q^{3}_{-})_{C}$,
$R:=R^{1}_{A}\cup R^{2}_{B}\cup R^{3}_{C}$, and
$R_{+}:=(R^{1}_{+})_{A}\cup(R^{2}_{+})_{B}\cup(R^{3}_{+})_{C}$. With high
probability, the property in Lemma 5.32 holds for $Q_{-}$. As the
multiplication hypergraph $H_{G}$ is $(0,1,n)$-typical, with high probability,
the property in Lemma 3.9 holds with the random sets
$(A^{\prime},B^{\prime},C^{\prime})=(R^{1}_{+},R^{2}_{+},R^{3}_{+}$). Finally,
as a consequence of Chernoff’s bound, with high probability,
$|Q_{-}|\leq|R_{+}|/100$, and for $i$ we have $|R^{i}_{+}|=(p(1-/10^{5})\pm
n^{-0.27})n$ and $|R^{i}|(p\pm n^{-0.27})n$

Now, given subsets $X,Y,Z$, define $U:=(R^{1}_{A}\cup R^{2}_{B}\cup
R^{3}_{C})\setminus(X\cup Y\cup Z)$ and note
$|U|\leq\alpha^{10^{15}}n/\log(n)^{10^{15}}$. From the property in Lemma 5.32,
we find a set $Q^{\prime}_{-}\subseteq Q_{-}\setminus U$ that can combine with
balanced zero-sum sets to produce perfect matchings. By the remark after Lemma
5.32, $Q_{-}^{\prime}$ is balanced and zero-sum.

Let $L:=R\setminus(Q_{-}^{\prime}\cup R_{+})$. Note that as
$R_{+}^{1},R_{+}^{2},R_{+}^{3}$ each have size $(p(1-/10^{5})\pm n^{-0.27})n$,
and $Q_{-}^{\prime}$ is a balanced set contained in $R$, there exists a $q\leq
p/10^{5}$ such that $L\cap X$, $L\cap Y$, $L\cap Z$ each have size $(q\pm
n^{-0.26})n$. Note that $q\leq(1-10^{-5})p/100$, so we may apply Lemma 3.9, to
conclude that there exists a matching $M_{1}^{\prime}$ with
$V(M_{1}^{\prime})\subseteq L\cup R_{+}$ covering all but $n^{1-10^{-4}}$
vertices of $L\cup R_{+}$. Of the edges forming this matching, at most
$\alpha^{10^{15}}n/\log(n)^{10^{15}}$ many of them can meet $U$, hence we find
a matching $M_{1}$ of $H_{G}[X,Y,Z]$ covering all but at most
$\alpha^{10^{15}}n/\log(n)^{10^{15}}+n^{1-10^{-4}}\leq(\alpha/10^{10})^{10^{14}}/\log(n)^{10^{14}}$
vertices of $(X\cup Y\cup Z)\setminus Q^{\prime}_{-}$. Call this uncovered set
of vertices $S$.

We claim that $S$ is a balanced zero-sum set. This is as the sets
$Q^{\prime}_{-}$, $V(M_{1})$, and $X\cup Y\cup Z$ are each balanced and zero-
sum, and $S$ is obtained by removing all of the former two sets from the
latter set, and the former two sets are disjoint. Further, $S$ is
$\phi$-generic, as by assumption, $X\cup Y\cup Z$ is $\phi$-generic. Then, by
property of the set $Q^{\prime}_{-}$, $S\cup Q^{\prime}_{-}$ spans a perfect
matching, $M_{2}$ say. $M_{1}\cup M_{2}$ then is the desired perfect matching
of $X\cup Y\cup Z$. ∎

It remains to prove Theorem 4.3. We will need the following intermediary
result.

######  Lemma 5.34.

Let $p\geq n^{-1/10^{100}}$. Let $G$ be a group of order $n$. Let
$Q^{1},Q^{2},Q^{3}\subseteq G$ be disjoint, symmetric $p$-random subsets and
set $Q=Q^{1}_{A}\cup Q^{2}_{B}\cup Q^{3}_{C}$. With high probability, the
following holds.

Let $S,U\subseteq V(H_{G})$ with $|S|,|U|\leq p^{10^{10}}n/\log(n)^{10^{10}}$
and ${e}\not\in S$. Then, there exists a matching $M$ in $H_{G}[Q]\setminus U$
of size at most $2p^{10^{10}}n/\log(n)^{10^{10}}$ saturating $S$.

###### Proof.

Let $g\in G$ be an arbitrary element of the group such that $g\neq{e}$. Then,
by Proposition 3.12, it follows that $g$ is contained in at least $n/5$ edges
$\\{g,x,y\\}$ such that $x\not\in\\{y,y^{-1}\\}$, regardless of whether $g\in
G_{A}$, $G_{B}$, or $G_{C}$. For any $i$, $j$, and any such $\\{x,y\\}$, $x\in
Q^{i}$ and $y\in Q^{j}$ with probability $p^{2}$. For each of the $n/5$ such
edges, the corresponding pairs $\\{x,y\\}$ are disjoint. Hence, we may apply
Chernoff’s bound to deduce that with probability at least $1-1/n^{2}$, $g$ has
degree at least $p^{2}n/1000$ in $H_{G}[Q^{1}_{A},Q^{2}_{B},Q^{3}_{C}]$, as
long as $g\in V(H_{G}[Q^{1}_{A},Q^{2}_{B},Q^{3}_{C}])$. By a union bound, this
property holds for all $g\in G$ such that $g\neq{e}$ in the case that
$G=(\mathbb{Z}_{2})^{k}$ for some $k$.

Now, let $S,U$ be given. By the minimum degree property from the previous
paragraph, all elements of $S$ have degree at least
$p^{2}n/1000-2p^{10^{10}}n/\log(n)^{10^{10}}\geq p^{2}n/2000$ in
$H_{G}[Q]\setminus U$. As $p^{2}n\gg|S|$, we may greedily pick a matching
saturating $S$ and disjoint from $U$ of size $|S|\leq
2p^{10^{10}}n/\log(n)^{10^{10}}$ as claimed. ∎

We can now give the final proof of the section.

###### Proof of Theorem 4.3 from Theorem 5.33 and Lemma 5.34.

By the definition of $q$-slightly-independent, we have disjoint, symmetric,
$q$-random sets $Q^{1},Q^{2},Q^{3}$ with $Q^{1}\subseteq R^{1},Q^{2}\subseteq
R^{2},Q^{3}\subseteq R^{3}$. With high probability Theorem 5.33 holds $R^{1}$,
$R^{2}$ and $R^{3}$ and Lemma 5.34 holds for $Q^{1},Q^{2},Q^{3}$. Given
$X,Y,Z$, let $S=(X\cup Y\cup Z)\setminus(R^{1}_{A}\cup R^{2}_{B}\cup
R^{3}_{C})$ together with the non-$\phi$-generic elements of $X\cup Y\cup Z$
(of which there are at most $10^{9010}$ many). Let $U=(R^{1}_{A}\cup
R^{2}_{B}\cup R^{3}_{C})\setminus(X\cup Y\cup Z)$. Note that $|S|,|U|\leq
p^{10^{16}}n/\log(n)^{10^{16}}$ and ${e}\not\in S$ in the case that
$G=\mathbb{Z}_{2}^{k}$. Apply Lemma 5.34 to find a matching $M$, and set
$X^{\prime},Y^{\prime},Z^{\prime}$ to be $X\setminus V(M),Y\setminus
V(M),Z\setminus V(M)$ respectively. Observe that
$X^{\prime},Y^{\prime},Z^{\prime}$ satisfy the hypothesis of $X,Y,Z$ in
Theorem 4.3. Indeed, $X^{\prime}/Y^{\prime}/Z^{\prime}$ is contained in
$R^{1}/R^{2}/R^{3}$ and does not contain non-$\phi$-generic elements since all
such elements are in $S\subseteq V(M)$. We have $\sum X^{\prime}+\sum
Y^{\prime}+\sum Z^{\prime}=0$, as $\sum X+\sum Y+\sum Z=0$, and $\sum V(M)=0$
(as $V(M)$ spans a perfect matching). We have
$|X^{\prime}|=|Y^{\prime}|=|Z^{\prime}|$ for the same reason. Hence,
$H_{G}[X^{\prime},Y^{\prime},Z^{\prime}]$ spans a perfect matching by Theorem
4.3, and this together with $M$ gives a perfect matching of $H_{G}[X,Y,Z]$ as
desired. ∎

##  6 Applications

###  6.1 Characterising subsquares with transversals

The goal of this section is to prove a far-reaching generalisation of
Snevily’s conjecture as stated in the introduction. [53]

####  6.1.1 Preliminaries

The below lemma allowing us to find zero-sum sets of prescribed size will also
be useful in Section 6.3.

######  Lemma 6.1.

Let $k\in\\{3,4,5\\}$. Let $p\geq n^{-1/100}$. Let $G$ be an abelian group,
and let $R$ be a $p$-random subset of $G$. Then, the following holds with high
probability.

Let $X\subseteq R$ with $|R\setminus X|\leq p^{8000}n/10^{6000}$. Then, there
exists at least $p^{800}n/10^{4010}$ many disjoint zero-sum sets of size $k$
in $G$.

###### Proof.

With high probability, Lemma 3.32 apply to $R$ (with $R=R_{A}$, set $R_{B}$
and $R_{C}$ arbitrarily for this application). Let $X$ be given. If it is the
case that $k=3$, consider the set $S=\\{xy,x^{-1},y^{-1}\\}\subseteq G\ast
F_{2}$ and note that all pairs of words in $S$ are linear and separable (by
part (a) of the definition of separable). Thus, setting $U:=R\setminus X$
there is a projection $\pi:G\ast F_{2}\to G$ which has $\pi(S)\subseteq X$ and
which separates $S$. Resetting $U$ to include the vertices in the projection,
and invoking Lemma 3.32 iteratively, we can conclude that there exists at
least $(p^{800}n/10^{4000}-p^{8000}n/10^{6000})/10\gg p^{800}n/10^{4010}$
disjoint zero-sum sets of size $3$ contained in $X$. If $k=4$ set
$S=\\{xyz,x^{-1},y^{-1},z^{-1}\\}$, and if $k=4$ set
$S=\\{xyzw,x^{-1},y^{-1},z^{-1},w^{-1}\\}$ to obtain sets of words which are
linear and pairwise separable, and proceed in the same way as the case $k=3$.
∎

For this section, we will only need the following easy corollary of Lemma 6.1

######  Lemma 6.2.

Let $G$ be a group with $|G|=n\geq 10^{50}$, let $3\leq t\leq n/\log(n)$, and
let $g\in G$. Then, there exists distinct $c_{1},\ldots,c_{t}\in G$ such that
$\sum c_{i}=g$ in $G^{\mathrm{ab}}$.

###### Proof.

Apply Lemma 6.1 with $R=G$ ($p=1$). Write $t\geq 3$ as a sum of at most
$n/\log(n)$ many copies of $3$, $4$, and $5$. By Lemma 6.1, we can greedily
choose the correct number of disjoint zero-sum sets of size $3$, $4$, or $5$
as $p^{800}n/10^{4010}=n/10^{4010}\gg n/\log(n)$ to produce the desired zero-
sum set of size $t$. ∎

The below result has essentially appeared in [45]. For our application here,
we provide a more precise formulation as well as a full proof for the sake of
completeness.

######  Lemma 6.3.

Let $n$ be sufficiently large and set $\gamma:=1/\log(n)^{10^{100}}$. Let
$S=A\times B$ be a subsquare of a multiplication table of a group $G$ defined
by two $n$-element sets $A,B\subseteq G$. Then, either $S$ has at most
$(1-\gamma)n$ symbols occurring more than $(1-\gamma)n$ times or there is a
subgroup $H\subseteq G$ and elements $g,g^{\prime}\in G$ such that $|A\Delta
gH|,|B\Delta Hg^{\prime}|\leq\gamma^{1/10}n$.

###### Proof.

We will use a theorem of Fournier as stated as Theorem 1.3.3 in the lecture
notes of Green [34]. Towards that goal, we recall the definition of
multiplicative energy of a subset $A$ of a group. It is defined to be the
quantity $E(A)=|\\{(a_{1},a_{2},b_{1},b_{2})\in A^{4}\colon
a_{1}a_{2}^{-1}=b_{1}b_{2}^{-1}\\}|$.

Suppose now that $S$ has more than $(1-\gamma)n$ symbols occurring more that
$(1-\gamma)n$ times. Call a subset $S^{\prime}$ of $S$ a monoversal if all
entries in $S^{\prime}$ are equal. By properties of groups, no two entry in a
monoversal can share a row or a column. Our assumption is then equivalent to
stating that there exists at least $(1-\gamma)n$ monoversals $S^{\prime}$ each
of size $(1-\gamma)n$. Label these monoversals $S_{1},\cdots,S_{(1-\gamma)n}$.
Call an ordered pair of rows of $S$, $(a_{1},a_{2})$ say, good, if there
exists at least $(1-\sqrt{\gamma})n$ many monoversals $S_{i}$ meeting both
$a_{1}$ and $a_{2}$. Let $\alpha$ denote the number of good pairs of ordered
rows. Let $K$ denote the the number of tuples $(i,(s_{1},s_{2}))$ where
$i\in[(1-\gamma)n]$ and $\\{s_{1},s_{2}\\}\subseteq S_{i}$, and observe that
$K\geq(1-\gamma)n(1-\gamma)n((1-\gamma)n-1)\geq(1-5\gamma)n^{3}$. On the other
hand, $\alpha n+(n^{2}-\alpha)(1-\sqrt{\gamma})n\geq K$. Combining the two
inequalities, we find that $\alpha\geq(1-10\sqrt{\gamma})n^{2}$.

For each good ordered pair of rows, $(a_{1},a_{2})$ say, we claim there exists
$(1-5\sqrt{\gamma})n^{2}$ distinct elements of the set
$\\{(b_{1},b_{2},b_{3},b_{4})\in B^{4}\colon
b_{1}b_{2}^{-1}=b_{3}b_{4}^{-1}\\}$. Indeed, for each monoversal meeting both
$a_{1}$ and $a_{2}$, we have an ordered pair $(b_{1},b_{2})$ and an equality
of the form $a_{1}b_{1}=a_{2}b_{2}$, equivalently
$a_{2}^{-1}a_{1}=b_{2}b_{1}^{-1}$. Hence, we have $(1-\sqrt{\gamma})n$
distinct ordered pairs $(b_{1},b_{2})\in B^{2}$ for which $b_{2}^{-1}b_{1}$ is
constant. For each ordered pair of such ordered pairs, of which there are
$(1-\sqrt{\gamma}n)^{2}\geq(1-5\sqrt{\gamma})n^{2}$ many, we get a distinct
element of $\\{(b_{1},b_{2},b_{3},b_{4})\in B^{4}\colon
b_{1}b_{2}^{-1}=b_{3}b_{4}^{-1}\\}$, as claimed.

Summing over all of the good ordered pair of rows, this gives
$(1-10\sqrt{\gamma})n^{2}(1-5\sqrt{\gamma})n^{2}\geq(1-20\sqrt{\gamma})n^{4}$
potential elements of $\\{(b_{1},b_{2},b_{3},b_{4})\in B^{4}\colon
b_{1}b_{2}^{-1}=b_{3}b_{4}^{-1}\\}=X$. We double count a $4$-tuple
$(b_{1},b_{2},b_{3},b_{4})$ of $X$ in two distinct ordered pair of rows
$(a_{1},a_{2})$ and $(a^{\prime}_{1},a^{\prime}_{2})$ only if
$a_{2}^{-1}a_{1}={a^{\prime}_{2}}^{-1}a^{\prime}_{1}=b_{1}b_{2}^{-1}$, and
there are at most $n$ such distinct ordered pair of rows. We deduce that
$E(B)\geq(1-20\sqrt{\gamma})n^{3}$. By a symmetric argument,
$E(A)\geq(1-20\sqrt{\gamma})n^{3}$ as well.

From Theorem 1.3.3 in [34], it follows immediately that there exists a
subgroup $H$ and $g\in G$ such that $|A\Delta gH|\leq\gamma^{1/9}n$. Consider
an element $t$ of $S$ that repeats at least $(1-\gamma)n$ times. So we have
$a_{1}b_{1}=\cdots=a_{(1-\gamma)n}b_{(1-\gamma)n}=t$. Let $i\in[(1-\gamma)n]$
so that $a_{i}\in gH$, and note that there are at least $(1-2\gamma^{1/9})n$
indices $i$ with this property. So we have that $t=(gh)b_{i}$ for some $h\in
H$. Then, $b_{i}=h^{-1}g^{-1}t$, so $b_{i}\in H(g^{-1}t)$ for each such $i$.
Then, the statement holds for $g^{\prime}=g^{-1}t$.

∎

######  Observation 6.4.

Let $A\times B$ be a subsquare of a multiplication table of a group $G$
defined by two $n$-element sets $A,B\subseteq G$. Let $g,g^{\prime}\in G$.
Suppose that $A\times B$ contains a transversal. Then, $gA\times Bg^{\prime}$
also contains a transversal.

###### Proof.

Let $(a_{i},\phi(a_{i}))$, $i\in[n]$ be a transversal of $A\times B$, where
$\phi$ is a bijection $A\to B$. Then, $(ga_{i},\phi(a_{i})g^{\prime})$ is a
transversal of $gA\times Bg^{\prime}$, since $a_{i}\phi(a_{i})\neq
a_{j}\phi(a_{j})$ implies that $ga_{i}\phi(a_{i})g^{\prime}\neq
ga_{j}\phi(a_{j})g^{\prime}$. ∎

######  Lemma 6.5.

Let $\varepsilon>0$ be sufficiently small and let $n$ be sufficiently large.
Let $\gamma\geq n^{-\varepsilon}$. Let $S$ be a subsquare of a group $G$ of
order $n$ such that $S$ has at most $(1-\gamma)n$ symbols occuring more than
$(1-\gamma)n$ times. Then, $S$ contains a transversal.

###### Proof.

As subsquares of $G$ correspond to edge-coloured balanced complete graphs,
this lemma is a direct corollary of Lemma 8.1.3 from [45]. ∎

####  6.1.2 The characterisation

We first prove the following weakening of the main theorem which characterises
when subsquares which are close to the whole multiplication table have
transversals.

######  Lemma 6.6.

Let $t\leq n/\log(n)^{10^{30}}$. Let $G$ be a sufficiently large group and
$A,B\subseteq G$ with $|A|=|B|=n-t$. Then $A\times B$ has a transversal unless
one of the following holds

  1. 1.

$H$ is a group that does not satisfy the Hall-Paige condition, and $A=B=H$.

  2. 2.

$H\cong(\mathbb{Z}_{2})^{k}$, $A=G\setminus\\{a_{1},a_{2}\\}$,
$B=G\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$.

###### Proof.

If $t=0$ then there is a transversal (by any proofs of the Hall-Paige
Conjecture e.g. by Theorem 4.4 with $p=1$). Thus, we can suppose that $1\leq
t\leq n/\log(n)^{10^{30}}$. Let $\alpha:=\prod G(\prod A\prod B)^{-1}$ (where
the terms in the products are multiplied in any fixed order).

######  Claim 6.6.1.

There are distinct elements $c_{1},\ldots,c_{t}\in G$ such that
$c_{1}+\cdots+c_{t}=\alpha$ in $H^{\mathrm{ab}}$.

###### Proof.

If $t=1$, one can trivially choose $c_{1}=\alpha$. If $t=2$, and
$\alpha\neq{e}$, then we could select $c_{1}={e}$ and $c_{2}=\alpha$. The case
$t=2$, $\alpha={e}$, $G=(\mathbb{Z}_{2})^{k}$ is excluded by the lemma (indeed
in this case we’d have $A=G\setminus\\{a_{1},a_{2}\\}$,
$B=G\setminus\\{b_{1},b_{2}\\}$ for some distinct $a_{1},a_{2}\in H$ and
distinct $b_{1},b_{2}\in H$. But then in $G^{ab}$ we’d have $0=\alpha=\sum
H-\sum A-\sum
B=a_{1}+a_{2}+b_{1}+b_{2}-\sum(\mathbb{Z}_{2})^{k}=a_{1}+a_{2}+b_{1}+b_{2}$).
When $t=2$, $\alpha={e}$, $G\neq(\mathbb{Z}_{2})^{k}$, then, there must exist
distinct $c_{1},c_{2}\in G$ such that $c_{1}c_{2}={e}$. Finally, when $t\geq
3$, then the claim follows from Lemma 6.2. ∎

Let $C=G\setminus\\{c_{1},\dots,c_{t}\\}$ to get a set with $|C|=|A|=|B|$. Now
Theorem 4.4 applies with $p=1$ to give a perfect matching
$\\{(a_{1},b_{1}c_{1}^{\prime}),\dots,(a_{n-1}),b_{n-t},c_{n-t}^{\prime}\\}$
in $H_{G}[A,B,C^{-1}]$. The entries $(a_{1},b_{1}),\dots,(a_{n-t},b_{n-t})$
give a transversal in $A\times B$. ∎

We now prove the main result of this section.

######  Theorem 6.7.

There exists a $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=g_{1}H$
and $B=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$.

###### Proof of Theorem 6.7.

Set $\gamma=1/\log(n)^{10^{100}}$. Suppose that $A\times B$ does not have a
transversal. Then, by Lemma 6.5, we may assume that $A\times B$ contains more
than $(1-\gamma)n$ symbols occuring more than $(1-\gamma)n$ times. By Lemma
6.3, it follows that there is a subgroup $H\subseteq G$ and elements
$g,g^{\prime}\in G$ such that $|A\Delta gH|,|B\Delta
Hg^{\prime}|\leq\gamma^{1/10}n$. As $A\times B$ does not contain a
transversal, by Observation 6.4, $g^{-1}A\times Bg^{\prime-1}$ does not
contain a transversal either. Set $A^{\prime}\times B^{\prime}=g^{-1}A\times
Bg^{\prime-1}$ and observe that $|A^{\prime}\Delta H|,|B^{\prime}\Delta
H|\leq\gamma^{1/10}n$.

Set $A_{1}=A^{\prime}\cap H$, $A_{2}=A^{\prime}\setminus H$,
$B_{1}=B^{\prime}\cap H$, $B_{2}=B^{\prime}\setminus H$, noting that
$|A_{2}|,|B_{2}|\leq\gamma^{1/10}n$. If $A_{2}=B_{2}=\emptyset$, then the
theorem follows from Lemma 6.6 applied with $G=H$. Thus we can suppose that
$A_{2}$ and/or $B_{2}$ are nonempty. Note that all the elements in the
multiplication table in $A_{1}\times B_{2}$ and $A_{2}\times B_{1}$ are
outside $H$. Let $A_{2}=\\{a_{1},\dots,a_{|A_{2}|}\\}$,
$B_{2}=\\{b_{1},\dots,b_{|B_{2}|}\\}$. We can greedily select a partial
transversal
$T_{1}=\\{(a_{1},b_{1}^{\prime}),\dots,(a_{|A_{2}|},b_{|A_{2}|}^{\prime})$ ,
$(a_{1}^{\prime},b_{1}),\dots,(a_{|B_{2}|}^{\prime},b_{|B_{2}|})\\}$ by
selecting elements $b_{1}^{\prime},\dots,b_{|A_{2}|}^{\prime}\in
B_{1},a_{1}^{\prime},\dots,a_{|B_{2}|}^{\prime}\in A_{1}$ in order (to see
this note that there are at least $\min(|A_{1}|,|B_{1}|)\geq n/2$ choices for
each element and so there’s room to avoid the
$|A_{2}|+|B_{2}|\leq\gamma^{1/10}n$ rows/columns/symbols previously used).
Note that since there are at least $n/4$ choices for the last element
$a_{|B_{2}|}^{\prime}$, we can additionally ensure that $\sum
A_{1}\setminus\\{a_{1}^{\prime},\dots,a_{|B_{2}|}^{\prime}\\}+\sum
B_{1}\setminus\\{b_{1}^{\prime},\dots,b_{|A_{2}|}^{\prime}\\}\neq 0$ in
$G^{ab}$ in the case where $G^{ab}$ has at least $100$ elements. Thus Lemma
6.6 applies to give a transversal $T_{2}$ in
$(A_{1}\setminus\\{a_{1}^{\prime},\dots,a_{|B_{2}|}^{\prime})\times(B_{1}\setminus\\{b_{1}^{\prime},\dots,b_{|A_{2}|}^{\prime}\\})$
(to apply Lemma 6.6, we need to know that we are not in cases 1 and 2. We’re
not in case 1 because we’re assuming $A_{2}\cup B_{2}\neq\emptyset$. We’re not
in case 2 because in this case we have $|G^{ab}|\geq 100$, and also that $\sum
A+\sum B=0$, and we selected $a_{i}^{\prime}$ and $b_{i}^{\prime}$ to avoid
this scenario). Now $T_{1}\cup T_{2}$ is a transversal in $A^{\prime}\times
B^{\prime}$ as required. ∎

###  6.2 Path-like structures in groups

The goal of this section is to give a characterisation of sequenceable,
R-sequenceable, and harmonious groups which are sufficiently large. It will be
convenient to rephrase all three of these problems as finding rainbow
structures in edge-coloured digraphs. Towards this aim, we give some
definitions.

Given a group $G$, by $K^{+}_{G}$ we denote the complete directed edge-
coloured graph with vertex set $G$, edge set $\\{\vec{ab}\colon a\neq b\text{
and }a,b\in G\\}$, where the edge $\vec{ab}$ gets assigned the colour $ab\in
G$. We call this the multiplication digraph of $G$. Similarly, by $K^{-}_{G}$
we denote the division digraph of $G$. In the division digraph, the edge
$\vec{ab}$ gets assigned the colour $a^{-1}b\in G$, and all other properties
of $K^{-}_{G}$ are same with those of $K^{+}_{G}$. We sometimes use the
notation $K^{\pm}_{G}$ to make statements and definitions about $K^{+}_{G}$
and $K^{-}_{G}$ simultaneously. For subsets $R,R^{\prime}\subseteq G$, we will
use $K^{\pm}_{G}[R;R^{\prime}]$ to denote the subgraph of $K^{\pm}_{G}$
induced on vertex set $R$ consisting of all edges of colours in $R^{\prime}$.
For disjoint subsets $V_{1},V_{2}\subseteq G$, by
$K^{\pm}_{G}[V_{1},V_{2};R^{\prime}]$ we denote the bipartite subgraph of
$K^{\pm}_{G}$ obtained by keeping only the edges between $V_{1}$ and $V_{2}$
with colour in $R^{\prime}$.

The main trick in this section is to use our main theorem iteratively to build
paths out of matchings. One key issue with this idea is that this does not
give us to freedom to construct paths connecting specified end-points, which
is critical for building a Hamilton path, instead of an arbitrary path/cycle-
factor. To remedy this, in Section 6.2.1, based on ideas of Kühn, Lapinskas,
Osthus, and Patel [42], we introduce a way of building path systems allowing
us to construct path-factors with specified end-points. The key result of that
section, combined with a variant of our main theorem, allows us to deduce the
following theorem.

######  Theorem 6.8.

Let $G$ be a sufficiently large group on $n$ vertices. Let $V,C\subseteq G$
and $x,y\in G$ be such that $|V|+1=|C|\geq n-n^{1/2}$, $x\neq y$, and $\sum C$
is equal either to $x+y+2\sum V$ or to $y-x$ in $G^{\mathrm{ab}}$. Also,
suppose that $e\notin C$ if $G$ is an elementary abelian $2$-group. Then,
$K^{\ast}_{G}[\\{x,y\\}\cup V;C]$ has a Hamilton path from $x$ to $y$ where
$\ast=-$ in the former case and $\ast=+$ in the latter case.

When $\ast=+$, this gives the following characterisation of which rainbow
Hamilton paths can be found in $K^{+}_{G}$.

######  Corollary 6.9.

Let $G$ be a sufficiently large group not isomorphic to a elementary abelian
$2$-group. Let $c,x_{1},x_{2}\in G$ such that $0=\sum G+c-x_{1}-x_{2}$ in
$G^{\mathrm{ab}}$. Then, $K^{+}_{G}$ contains a directed rainbow Hamilton path
using the colour set $G-c$ and with endpoints $x_{1}$ and $x_{2}$.

###### Proof.

This is immediate by applying Theorem 6.8 with
$V:=G\setminus\\{x_{1},x_{2}\\}$ and $(x,y)=(x_{1},x_{2})$ and
$C=G\setminus\\{c\\}$. ∎

This gives a characterisation of groups where $K^{+}_{G}$ has a directed
rainbow Hamilton cycle which is easily seen to be equivalent to $G$ being
harmonious.

######  Corollary 6.10.

Let $G$ be a sufficiently large group satisfying the Hall-Paige condition, and
suppose $G$ is not isomorphic to an elementary abelian $2$-group. Then,
$K^{+}_{G}$ has a directed rainbow Hamilton cycle, i.e. $G$ is harmonious.

###### Proof.

Let $x_{1}$ and $x_{2}$ be such that $x_{1}x_{2}={e}$ and $x_{1}\neq x_{2}$.
Such $x_{1}$ and $x_{2}$ exist as $G$ is not isomorphic to an elementary
abelian $2$-group. By assumption, $\sum G={e}$ in $G^{\mathrm{ab}}$. Then,
$0={e}-x_{1}-x_{2}=\sum G+{e}-x_{1}-x_{2}$ in $G^{\mathrm{ab}}$, hence by
Corollary 6.9 we have a directed rainbow Hamilton path from $x_{1}$ to $x_{2}$
using all colours but ${e}$. Combined with the edge $x_{2}\to x_{1}$, this
gives the desired directed rainbow Hamilton cycle, that is, a harmonious
ordering. ∎

We now characterise sequenceable groups.

######  Theorem 6.11.

Let $G$ be a sufficiently large group. If $G$ is abelian, suppose that $\sum
G\neq 0$, or equivalently, $G$ has a unique element of order $2$. Then, $G$ is
sequenceable.

###### Proof.

First suppose $G$ is abelian. Let $k\neq 0$ be the unique element of order $2$
in $G$. Apply Theorem 6.8 with $\ast=-$, $C=G-0$, $(x,y)=(0,k)$, $V=G-0-k$,
noting this is possible as $y-x-k-0=k=\sum G=\sum C$. This gives us a path
with vertex set $(0,x_{1},x_{2},\ldots,x_{n-2},k)$, and a colour sequence
$(x_{1},-x_{1}+x_{2},\ldots,-x_{n-2}+k)$. We claim that
$(0,x_{1},-x_{1}+x_{2},\ldots,-x_{n-2}+k)$ is a sequencing of $G$. Indeed, the
partial sums give the sequence $(0,x_{1},x_{2},x_{3},x_{n-2},k)$, and these
are all distinct as this sequence also is a Hamilton path in $K^{-}_{G}$.

If $G$ is nonabelian, let $y$ be such that $y=\sum G$ in $G^{\mathrm{ab}}$ and
$y\neq e$. Such a $y$ exists since each coset of the commutator subgroup has
at least $2$ elements. We can now invoke Theorem 6.8 with $C=G-{e}$,
$(x,y)=({e},y)$ and $V=G-{e}-y$, this is possible as $y-{e}=\sum C=\sum G$ in
$G^{\mathrm{ab}}$ by choice of $y$. The colour sequence corresponding to the
Hamilton path gives us a sequencing of the group as before. ∎

Using similar ideas, we characterise R-sequenceable groups.

######  Theorem 6.12.

Let $G$ be a sufficiently large group satisfying the Hall-Paige condition,
that is, $\sum G=0$ in $G^{\mathrm{ab}}$. Then, $G$ is $R$-sequenceable.

###### Proof.

Let $x,y$ be two arbitrary elements of the group $G$ such that
$yx^{-1}\neq{e}$, and apply Theorem 6.8 with $\ast=-$ and
$C=G\setminus\\{e,yx^{-1}\\}$, $(x,y)=(x,y)$ and $V=G\setminus\\{x,y\\}$, this
application is valid as $\sum G=0$. This gives a path from $x$ to $y$, and
combined with the edge from $y\to x$, we obtain a directed rainbow Hamilton
cycle in $K^{-}_{G}$ using all colours but $e$. Let
$(c_{1},c_{2},\ldots,c_{n-1})$ be the colours that appear on the cycle in
cyclic order (the choice for $c_{1}$ can be made arbitrarily). Now,
$(e,c_{1},c_{2},\ldots,c_{n-1})$ is an $R$-sequencing of $G$. ∎

In the rest of this section, we are focused on proving Theorem 6.8.

####  6.2.1 Sorting networks

In [42] (see in particular Lemma 4.3), an ingenious method was introduced in
order to construct path systems which can connect specified endpoints. The key
idea is to consider use an appropriate sorting network as a template while
building the path system. In this section, we adapt the arguments from [42] to
our context. First, we introduce some terminology. For a more detailed
treatment, we refer the reader to [17].

######  Definition 6.13.

A comparison network is a union of four types of objects: input nodes
$x_{1},\dots,x_{m}$, output nodes $y_{1},\dots,y_{m}$, comparators
$C_{1},\dots,C_{t}$ and wires $w_{1},\dots,w_{s}$.

  * •

Comparators are sets of $4$ nodes
$C_{i}=\\{y_{i}^{-},y_{i}^{+},x_{i}^{-},x_{i}^{+}\\}$ (which are disjoint with
the input and output nodes).

  * •

Each wire joins an $x$-node to a $y$-node. Additionally, each node is in
precisely one wire, and the directed graph formed by contracting comparators
into single nodes is acyclic.

Figure 10: A comparison sorting network for sorting four numbers. The black
circles represent nodes, the green rectangles are comparators, and the red
arrows are wires. Here the network was given input values
$v(x_{1})=1,v(x_{2})=3,v(x_{3})=4,v(x_{4})=1$ (represented by the yellow
numbers inside those nodes). Then all other nodes get a value based on the
rules in Definition 6.14 (represented by the yellow numbers in the other
nodes). The network correctly sorted the numbers, which can be seen by the
fact that each $y_{i}$ contains yellow number $i$.

######  Definition 6.14.

A comparison sorting network is a comparison network with the following
additional property. Let $\sigma$ be any permutation of $[m]$. Assign each
$x_{i}$ the value $v(x_{i})=\sigma(i)$. Assign the values of the other nodes
via the following rules.

  1. 1.

If $xy$ is a wire then $v(y):=v(x)$.

  2. 2.

If $C_{i}=\\{y_{i}^{-},y_{i}^{+},x_{i}^{-},x_{i}^{+}\\}$ is a comparator, then
$v(x_{i}^{-}):=\min(v(y_{i}^{-}),v(y_{i}^{+}))$ and
$v(x_{i}^{+}):=\max(v(y^{-}),v(y^{+}))$.

Then, all nodes get assigned a value and moreover, $v(y_{i})=i$ for
$i=1,\dots,m$.

See Figure 10 for an example of these definitions. A classical result due to
Batcher [8] states that for all $m\in\mathbb{N}$, there is a sorting network
with $m$ input/outputs and $100m\log^{2}m$ comparators. In fact, there are
sorting networks with $O(m\log m)$ comparators thanks to a celebrated result
of Ajtai, Komlós, and Szemerédi [1] but we will not need this sharper bound
here. However, it will be convenient for us to have sorting networks with
symmetry in the following sense.

######  Lemma 6.15 ([1]).

For all $m\in\mathbb{N}$, there is a sorting network such that the length of
every path from $x_{i}$ to $y_{j}$ is exactly $\lceil 100\log^{2}m\rceil$ (in
the directed graph formed by contracting every comparator into a single node).

The above can be proved by inspecting any common method of constructing a
sorting network, for example the method of Batcher [8]. Indeed, the bound of
Batcher is in terms of the depth of the network as opposed to the total number
of comparators, so we can simply add redundant comparators to ensure the
conclusion of Lemma 6.15.

We now show how to simulate the task of a comparator in a sorting network via
a collection of paths.

######  Lemma 6.16.

Let $p\geq n^{-1/700}$. Let $R^{1},R^{2}$ be disjoint $p$-random subsets of
$G$.

With high probability, for any $U\subseteq G$ with $|U|\leq
p^{800}n/10^{4010}$, there is a subgraph $C\subseteq
K^{\pm}_{G}[R_{1}\setminus U;R_{2}\setminus U]$ consisting of $12$ vertices
and $10$ colours containing vertices $x^{-},x^{+},y^{-},y^{+}$ and directed
paths $Q_{x^{-},y^{-}},Q_{x^{+},y^{+}},Q_{x^{-},y^{+}},Q_{x^{+},y^{-}}$ with
each $Q_{x,y}$ having length 5 and going from $x$ to $y$. Additionally the
vertices and colours of the path pairs $(Q_{x^{-},y^{-}},Q_{x^{+},y^{+}})$ and
$(Q_{x^{-},y^{+}},Q_{x^{+},y^{-}})$ both partition the $12$ vertices and $10$
colours of $C$.

###### Proof.

We prove the lemma when $K_{G}^{\pm}=K_{G}^{+}$. A slight change in variables
in Figure 11 proves the lemma also when $K_{G}^{\pm}=K_{G}^{-}$. With high
probability, Lemma 3.32 applies. Thinking of $x,y,a,b,c,d,f$, as free
variables consider the set
$S=\\{x,y,a,b,xd,yd,d^{-1}b,d^{-1},c,xf,yf,f^{-1}a,f^{-1}c,xa,yb,axd,byd,xb,ya,xc,yc,d^{-1}bxf,d^{-1}cyf\\}$
(see Figure 2). Note that all pairs $w,w^{\prime}$ are linear and separable
(by (a), since they’re all linear in different combinations of free
variables). Lemma 3.32 gives a projection $\pi$ which separates $S$ and has
$\pi(S)\subseteq R$. This means that $\pi(w)$ are distinct for all $w\in S$.
Now the graph given in Figure 11 satisfies the lemma with
$x^{-}=\pi(x),x^{+}=\pi(y),y^{-}=\pi(f^{-1}a),y^{+}=\pi(f^{-1}c)$, with paths
as shown.

Figure 11: The coloured graph produced by Lemma 6.16 for $K_{G}^{+}$. Each
edge is directed towards the right. Notice that all vertices/edges are
labelled by elements of $S$. Since all $w,w^{\prime}\in S$ are separable, this
means that the $\pi$-image of this graph has all vertices/colours distinct
(and so in particular has 12 vertices and 10 colours as required). To see that
it satisfies the lemma, we need to exhibit paths
$Q_{x^{-},y^{-}},Q_{x^{+},y^{+}},Q_{x^{-},y^{+}},Q_{x^{+},y^{-}}$ between
$x^{-}=x,x^{+}=y,y^{-}=f^{-1}a,y^{+}=f^{-1}c$. The solid lines in the picture
give the two paths $Q_{x^{-},y^{+}},Q_{x^{+},y^{-}}$. Replacing the coloured
solid lines for the coloured dashed lines (and keeping all grey lines) gives
the two paths $Q_{x^{-},y^{-}},Q_{x^{+},y^{+}}$.

∎

We now show how to simulate the task of a wire in a sorting network via short
paths.

######  Lemma 6.17.

Let $p\geq n^{-1/700}$. Let $H_{G}$ be a multiplication hypergraph,
$R^{1},R^{2}$ disjoint $p$-random subsets of $G$. With high probability, for
any $x,y\in V(K^{\pm}_{G})$, $U\subseteq G$ with $|U|\leq p^{800}n/10^{4010}$,
there is a length $3$ $x$ to $y$ path $xuvy$ in $K^{\pm}_{G}$ with $u,v\in
R_{1}\setminus U,c(xv),c(vy)\in R_{2}\setminus U$.

###### Proof.

We prove the lemma when $K_{G}^{\pm}=K_{G}^{+}$. A slight change in the
upcoming definition of $S$ proves the lemma also when $K_{G}^{\pm}=K_{G}^{-}$.

With high probability, Lemma 3.32 applies. Consider the set
$S=\\{u,v,uv,xu,uy\\}\subseteq G\ast F_{3}$. Note that all pairs
$w,w^{\prime}$ are linear also the pairs $(u,v),(xu,uy),(xu,uv),(uv,uy)$ are
separable (since they’re all linear in different combinations of free
variables). Lemma 3.32 gives a projection $\pi$ which separates $S$. Now the
path $P=x\pi(u)\pi(v)y$ satisfies the lemma — the vertices are distinct since
$u,v$ were separable, while the colours are distinct since $uv,xu,uy$ were
pairwise separable. ∎

We now prove the analogue of Lemma 4.3 from [42] adapted to a setting where
the host structure is $K^{\pm}_{G}$.

######  Lemma 6.18.

Let $p\geq n^{-1/800}$. Let $t=8\lceil 100\log^{2}n\rceil$. Let $R_{V}$ and
$R_{C}$ be $p$-random subsets of $G$, sampled independently. Then, the
following holds with high probability.

Let $A,B\subseteq G$ be subsets with
$|A|=|B|\leq\frac{p^{1000}n}{10^{5000}\log(n)^{3}}$, and let $U\subseteq G$
with $|U|\leq\frac{p^{1000}n}{10^{5000}}$. Then, there exists $V\subseteq
R_{V}\setminus U$ and $C\subseteq R_{C}\setminus U$ such that for any
bijection $\phi\colon A\to B$, there exists a system of paths using exactly
the vertices/colours of $K^{\pm}_{G}[A\cup B\cup V;C]$ from $A$ to $B$, each
of length $t$, and connecting $a$ to $\phi(a)$ for each $a\in A$.

###### Proof.

With high probability, Lemmas 6.16 and 6.17 apply. Let $N$ be a sorting
network given by Lemma 6.15, with $m:=|A|=|B|$, noting this sorting network
has $\leq 200m\log^{2}m$ comparators. For each comparator
$C_{i}=\\{x_{i}^{-},x_{i}^{+},y_{i}^{-},y_{i}^{+}\\}$, use Lemma 6.16 to find
a subgraph $C_{i}^{\prime}$ in $R\setminus(A\cup B)$. Identify the nodes
$x_{i}^{-},x_{i}^{+},y_{i}^{-},y_{i}^{+}$ of the comparator with the vertices
$x_{i}^{-},x_{i}^{+},y_{i}^{-},y_{i}^{+}$ of $C_{i}^{\prime}$. Let
$A=\\{x_{1},\dots,x_{m}\\},B=\\{y_{1},\dots,y_{m}\\}$. For each wire $xy$ of
the sorting network use Lemma 6.17 to find a rainbow length 3 path $P_{xy}$
joining corresponding vertices of $A\cup B\cup\bigcup C_{i}$. By enlarging the
set $U$ at all these applications, we can ensure that the subgraphs
$C_{i}^{\prime}$ are all disjoint, and that the paths $P_{xy}$ are all
internally disjoint and colour-disjoint from the subgraphs $C_{i}^{\prime}$
and from each other. We claim that $V=A\cup B\cup\bigcup V(C_{i})\cup\bigcup
V(P_{w})$ and $C=\bigcup C(C_{i})\cup\bigcup C(P_{w})$ satisfy the lemma.

Consider a bijection $\phi\colon A\to B$. This gives a permutation $\sigma$ of
$[m]$ so that $\phi(x_{i})=y_{\sigma(i)}$. Assign value $v(a_{i}):=\sigma(i)$.
This gives a value to each node and wire of the sorting network as in
Definition 6.14. We now translate this into values for the corresponding
paths/vertices in $K^{\pm}_{G}$. The values we assign come from the set
$\\{1,\dots,m\\}\cup\\{0\\}$. For each wire $xy$ of the sorting network,
define $v(P_{xy})=v(x)=v(y)$ and give all vertices/edges of $P_{xy}$ this
value. For each comparator $C=\\{y_{i}^{-},y_{i}^{+},x_{i}^{-},x_{i}^{+}\\}$
we have either $v(y_{i}^{-})=v(x_{i}^{-}),v(y_{i}^{+})=v(x_{i}^{+})$ or
$v(y_{i}^{-})=v(x_{i}^{+}),v(y_{i}^{+})=v(x_{i}^{-})$. In the former case,
define $v(Q_{y_{i}^{-},x_{i}^{-}})=v(y_{i}^{-})=v(x_{i}^{-})$,
$v(Q_{y_{i}^{+},x_{i}^{+}})=v(y_{i}^{+})=v(x_{i}^{+})$, and give the vertices
and edges of the corresponding paths the same value. Give the paths
$Q_{y_{i}^{-},x_{i}^{+}}$ and $v(Q_{y_{i}^{+},x_{i}^{-}})$ as well as the
unused edges of $C_{i}^{\prime}$ (those edges of $C_{i}^{\prime}$ not on
$Q_{y_{i}^{-},x_{i}^{-}}$ or $Q_{y_{i}^{+},x_{i}^{+}}$) value $0$. In the
latter case, define $v(Q_{y_{i}^{-},x_{i}^{+}})=v(y_{i}^{-})=v(x_{i}^{+})$,
$v(Q_{y_{i}^{+},x_{i}^{-}})=v(y_{i}^{+})=v(x_{i}^{-})$, and give the vertices
and edges of the corresponding paths the same value. As before, give the other
two paths and the unused edges value $0$. Note that this way every vertex/edge
of $U$ gets a value, and these values match those that corresponding
nodes/wires have in $N$. For every $i=1,\dots,m$, let

$P_{i}=\bigcup_{v(P_{xy})=i}P_{xy}\cup\bigcup_{v(Q_{y_{i}^{\diamond_{1}},x_{i}^{\diamond_{2}}})=i}Q_{y_{i}^{\diamond_{1}},x_{i}^{\diamond_{2}}}.$

We clarify that above $xy$ is quantified over the set of wires, and
$\diamond_{j}$ is quantified over $\\{+,-\\}$. We claim that
$P_{1},\dots,P_{m}$ are each paths and have all the required properties.

First note that every vertex in $V\setminus(A\cup B)$ has exactly one in-going
edge of non-zero value and exactly one outgoing edge of non-zero value. The
vertices $a_{i}$ have no in-going edges and one out-going edge (whose value is
$\sigma(i)$). The vertices $b_{i}$ have no out-going edges and one in-going
edge (whose value is $i$). Combined with the whole graph being acyclic (which
holds due to the sorting network being acyclic), this shows that $\bigcup
P_{i}$ is a union of paths.

Since $v(a_{i})=\sigma(i)$ and $v(b_{i})=i$, path $P_{\sigma(i)}$ goes from
$a_{i}$ to $b_{\sigma(i)}$. In particular, each $P_{i}$ is a path. Also, this
shows that the paths partition the vertices $V$ and have the correct
endpoints. We now show that their union is rainbow using exactly the colours
$C$. The fact that every colour of $\bigcup C(P_{xy})$ is used exactly once
comes from the fact that every wire has a value, and so every edge of each
$P_{xy}$ as a value. So such colours are used at least once (and hence exactly
once because these colours occur once in the whole graph). The colours on the
comparators $C_{i}^{\prime}$ are used once as a consequence of Lemma 6.16. To
see this, note each such colour comes up exactly twice — once in the paths
$Q_{x_{i}^{-},y_{i}^{-}}\cup Q_{x_{i}^{+},y_{i}^{+}}$ and once in the paths
$Q_{x_{i}^{-},y_{i}^{+}}\cup Q_{x_{i}^{+},y_{i}^{-}}$. By the assignment of
the values to the comparator one of these always has value $0$.

Finally, to see that each $P_{i}$ has length exactly $t$, observe that by
Lemma 6.15 we know each $P_{i}$ has length $\lceil 100\log^{2}n\rceil$ when
viewed as a path in the sorting network. As each wire gadget corresponds to a
path of length $3$ and each comparator corresponds to a path of length $5$, it
follows that each $P_{i}$ has length $8\lceil 100\log^{2}n\rceil$, as
required. ∎

####  6.2.2 Deducing Lemma 6.21

We will need the following technical lemma, which allows us to use the nibble
method to shrink sets of large deterministic vertices. This is necessary, as
after applying Lemma 6.18 to a random subset, we will be left with a large set
of deterministic vertices which do not immediately fit into the setting of our
main theorem.

######  Lemma 6.19.

Let $a,b,c\geq n^{-1/10^{-20}}$ and let $\ell\in\mathbb{N}$ be such that
$\ell\geq\max\\{an,bn,cn\\}-n^{0.7}$ and letting $(x,y,z)=(\ell-an,\ell-
bn,\ell-cn)$ suppose that we have $x+y\leq cn/2$, $x+z\leq bn/2$ and $y+z\leq
an/2$. Let $A,B,C\subseteq G$ be $a,b,c$-random subsets of $G$ respectively,
sampled with $A$ and $B$ disjoint, and $C$ independent of $A,B$. Let
$k:=\lfloor n^{1-10^{-5}}\rfloor$. Then, with probability at least $1-1/n$ the
following holds.

Let $A^{\prime},B^{\prime},C^{\prime}\subseteq G$ with $|B\setminus
B^{\prime}|,|A\setminus A^{\prime}|,|C\setminus C^{\prime}|\leq n^{0.78}$,
$|C^{\prime}|-k=|A^{\prime}|=|B^{\prime}|=\ell$. Then, there is a perfect
directed $C^{\prime}$-matching in
$K^{\pm}_{G}[A^{\prime},B^{\prime};C^{\prime}]$.

To prove the above lemma, we will make use of the following result of
Montgomery, Pokrovskiy, and Sudakov. We use the notation
$x\stackrel{{\scriptstyle\mathclap{\mbox{\scalebox{0.5}{POLY}}}}}{{\ll}}y$ to
mean that $x,y\in(0,1]$ and there is some absolute constant $C\geq 1$ such
that the proof works with $x\leq y^{C}/C$. Recall that an edge-coloured graph
is globally $K$-bounded if each colour occurs at most $K$ times in the
colouring. When we say an edge-coloured bipartite graph is typical, we refer
to the typicality of the underlying uncoloured bipartite graph.

######  Lemma 6.20 ([45], Corollary 8.12).

Let $n,\delta,p,\gamma$ be such that
$n^{-1}\stackrel{{\scriptstyle\mathclap{\mbox{\scalebox{0.5}{POLY}}}}}{{\ll}}\gamma\stackrel{{\scriptstyle\mathclap{\mbox{\scalebox{0.5}{POLY}}}}}{{\ll}}p,\delta\leq
1$. Every properly coloured, $(\gamma,\delta,n)$-typical, globally
$(1-p)\delta n$-bounded, balanced bipartite graph $G$ of order $2n$ has
$(1-p)\delta n$ edge-disjoint rainbow perfect matchings.

###### Proof of Lemma 6.19.

Let $\ell^{\prime}=\max\\{an,bn,cn\\}$ noting that
$\ell^{\prime}\leq\ell+n^{0.7}$. Set $p=\ell^{\prime}/n$ and $q=k/n$. Note
that combining the given inequalities we obtain that $a+b+c\geq
12(\ell/n)/5\geq 11p/5$. We define the following random sets.

  * •

Let $A_{1},A_{2}\subseteq A$ be disjoint $p-b$ and $(p-c+q)$-random subsets of
$A$. Let $A_{3}:=A\setminus A_{1}\setminus A_{2}$ noting that this set is
$(a-2p+b+c-q)=:\alpha$-random.

  * •

Let $B_{1},B_{2}\subseteq B$ be $(p-a)$ and $(p-c+q)$-random subsets of $B$.
Let $B_{3}:=B\setminus B_{1}\setminus B_{2}$ noting that this set is
$(b-2p+a+c-q)=\alpha$-random.

  * •

Let $C_{1},C_{2}\subseteq B$ be $(p-a)$ and $(p-b)$-random subsets. Let
$C_{3}:=C\setminus C_{1}\setminus C_{2}$ noting that this set is
$(c-2p+a+b)=\beta$-random.

Note there is space to sample these sets disjointly due to the assumptions on
the size of $\ell$ and $a,b,c$. In particular, $\alpha,\beta\geq p/5-q\geq
n^{-1/10^{-20}}/100$ and $p-a,p-c+q,p-b\geq 0$ so the random sets with these
parameters are well-defined. For each pair of random sets $(A_{2},B_{2})$,
$(A_{1},C_{2})$, and $(B_{1},C_{1})$ such that the corresponding randomness
parameter is at least $n^{-1/600}$, we have that with probability at least
$1-5/n^{1.5}$, Lemma 3.8 holds (the linearity and typicality of the
corresponding $3$-uniform hypergraph of $K^{\pm}_{G}$ follows by a
straightforward modification of Observation 3.3, which we omit). By Chernoff’s
bound, the sizes of all these random sets are at most $n^{0.6}$ elements away
from their expectations with probability at least $1-1/n^{5}$.

Set $\gamma:=n^{-0.25}$. For any $v\in G$, the expected number of
(out-)neighbours of $v$ in $K^{\pm}_{G}[\\{v\\}\cup B_{3};C_{3}]$ is
$\alpha\beta(n-1)$, as $C$ is sampled independently with $B$ and the analogous
statement holds for expected number of neighbours of $v$ in
$K^{\pm}_{G}[A_{3}\cup\\{v\\};C_{3}]$. By Chernoff’s bound and a union bound,
both of these random variables are at most $\gamma n$ away from their
expectation with probability at least $1-1/n^{3}$. Let $d_{A}(a,a^{\prime})$
denote the pair degree of $a$ and $a^{\prime}$ in
$K^{\pm}_{G}[\\{a,a^{\prime}\\}\cup B_{3};C_{3}]$ (viewed as an uncoloured
bipartite graph), and let $d_{B}(b,b^{\prime})$ denote the pair degree of $b$
and $b^{\prime}$ in $K^{\pm}_{G}[A_{3}\cup\\{b,b^{\prime}\\};C_{3}]$. For each
$a,a^{\prime}$ and $b,b^{\prime}$, we have that
$\mathbb{E}(d_{A}(a,a^{\prime}))=\mathbb{E}(d_{B}(b,b^{\prime}))=\alpha\beta^{2}n$.
Further, observe that $d_{A}(a,a^{\prime})$ and $d_{B}(b,b^{\prime})$ are
$2$-Lipschitz random variables. Hence, by Azuma’s inequality and a union
bound, with probability at least $1-1/n^{3}$, for each $a,a^{\prime}$ and
$b,b^{\prime}$,
$d_{B}(b,b^{\prime})=d_{A}(a,a^{\prime})=(\alpha\beta^{2}\pm\gamma)n$. This
establishes in particular that $K^{\pm}_{G}[A_{3},B_{3};C_{3}]$ is
$(\gamma,\beta,\alpha n)$-typical as an uncoloured bipartite graph. Let $d(c)$
denote the number of times $c$ occurs in $K^{\pm}_{G}[A_{3},B_{3},\\{c\\}]$.
Then $\mathbb{E}(d(c))\leq\alpha^{2}n$ for each $c$. By Chernoff’s bound and a
union bound, $d(c)\leq(1\pm\gamma)\alpha^{2}n$ for each $c\in G$. In
particular, this implies that $K^{\pm}_{G}[A_{3},B_{3},C_{3}]$ is globally
$(\alpha^{2}+\gamma)n$-bounded, which implies that it is globally
$(1-q)\beta(\alpha n)$-bounded.

With probability $\geq 1-1/n$, all of the previous properties hold. Let
$A^{\prime},B^{\prime},C^{\prime}$ be given with the indicated properties. By
properties coming from Lemma 3.8, $(A_{2},B_{2},C^{\prime}\setminus C)$,
$(A_{1},B^{\prime}\setminus B,C_{2})$ and $(A^{\prime}\setminus
A,B_{1},C_{1})$ each contain matchings covering all but $n^{1-1/499}$
vertices. Here, if the corresponding random sets have parameters smaller than
$n^{-1/600}$ (so we cannot apply Lemma 3.8) we simply take an empty matching.
This is sufficient as in this case by Chernoff’s bound, the random sets
themselves cannot contain more than $n^{1-1/499}$ elements. Accounting for
differences $A\setminus A^{\prime}$, $B\setminus B^{\prime}$, $C\setminus
C^{\prime}$ (each of size $\leq n^{0.78}$)., we have a matching covering all
but $n^{1-1/498}$ vertices of $(A_{2}\cap A^{\prime},B_{2}\cap
B^{\prime},C^{\prime}\setminus C)$, $(A_{1}\cap A^{\prime},B^{\prime}\setminus
B,C_{2}\cap C^{\prime})$ and $(A^{\prime}\setminus A,B_{1}\cap
B^{\prime},C_{1}\cap C^{\prime})$.

The set of leftover vertices of $A^{\prime}$, $B^{\prime}$ and $C^{\prime}$
have a symmetric difference with $A_{3},B_{3}$ and $C_{3}$ (respectively) of
size at most $n^{1-1/495}$. By the pair-degree and vertex-degree bounds we
obtained earlier, this implies that the associated properly coloured bipartite
graph with the leftover vertices is $(\gamma^{\prime},\beta,\alpha n)$-typical
and globally $(1-q/10)\beta(\alpha n)$-bounded where
$\gamma^{\prime}:=n^{-1/498}$. Then, by Lemma 6.20 we can find a matching
saturating the remaining vertices of $A^{\prime}$ and $B^{\prime}$ using the
leftover colours from $C^{\prime}$ as desired. ∎

We can now give the proof of the key lemma of this section.

######  Lemma 6.21.

Let $1/n\ll p\leq 1$, let $t$ be a positive integer between $\log^{7}(n)$ and
$\log^{8}(n)$, and let $q$ satisfy $p=(t-1)q$. Let $G$ be a group of order
$n$. Let $V_{str},V_{mid},V_{end}$ be disjoint random subsets with
$V_{str},V_{end}$ $q$-random and $V_{mid}$ $p$-random. Let $C$ be a
$(q+p)$-random subset, sampled independently with the previous sets. Then,
with high probability, the following holds.

Let $V_{str}^{\prime}$, $V_{end}^{\prime}$, $V_{mid}^{\prime}$ be disjoint
subsets of $G$, let $C^{\prime}$ be a subset of $G$, and let
$\ell=|V^{\prime}_{mid}|/(t-2)$. Suppose all of the following hold.

  1. 1.

For each random set $R\in\\{V_{str},V_{mid},V_{end},C\\}$, we have that
$|R\Delta R^{\prime}|\leq n^{0.6}$.

  2. 2.

Either O. $\sum V_{end}^{\prime}-\sum V_{str}^{\prime}=\sum C^{\prime}$ or C.
$\sum V_{end}^{\prime}+\sum V_{str}^{\prime}+\sum V^{\prime}_{mid}+\sum
V^{\prime}_{mid}=\sum C^{\prime}$ holds in the abelianization of $G$.

  3. 3.

${e}\notin C^{\prime}$ if $G$ is an elementary abelian $2$-group.

  4. 4.

$\ell:=|V_{str}^{\prime}|=|V_{end}^{\prime}|=|V^{\prime}_{mid}|/(t-1)=|C^{\prime}|/t$

Then, given any bijection $f\colon V_{str}^{\prime}\to V_{end}^{\prime}$, we
have that $K^{\ast}_{G}[V_{str}^{\prime}\cup V_{end}^{\prime}\cup
V_{mid}^{\prime};C^{\prime}]$ has a rainbow $\vec{P}_{t}$-factor where each
path starts on some $v\in V_{str}^{\prime}$ and ends on $f(v)\in
V_{end}^{\prime}$ where $\ast=+$ if C holds and $\ast=-$ if O holds.

###### Proof.

Set $m=8\lceil 100\log^{2}n\rceil$, $k=\lfloor n^{1-10^{-5}}\rfloor$,
$r=10^{-100}$.

Partition $V_{mid}$ into random subsets $R_{V},V_{1},\ldots,V_{t-m}$ where
$R_{V}$ is $rp$-random, $V_{1},V_{2},V_{3}$ and $V_{t-m}$ are $q$-random and
the rest are $((1-r)p-4q)/(t-m-4)$-random. Note that
$9q/10\leq((1-r)p-4q)/(t-m-4)\leq q$. Independently with the previous sets,
partition $C$ into $R_{C},C_{1},\ldots,C_{t-m}$ where $R_{C}$ is $rp$-random,
$C_{1},C_{2}$ and $C_{t-m}$ are $q$-random, and the rest are
$((1-r)p-3q)/(t-m-3)$-random. Note similarly that
$9q/10\leq((1-r)p-3q)/(t-m-3)\leq q$.

With high probability, Theorem 4.9 applies with the $q$-random sets
$(V_{2},V_{3},C_{2})$, Lemma 6.18 applies with $R_{V},R_{C}$ and Lemma 6.19
applies with all potential values of $\ell\in[qn-n^{0.61},qn+n^{0.61}]$ (via a
union bound) for

$(V_{str},V_{1},C_{1}),(V_{3},V_{4},C_{3}),(V_{4},V_{5},C_{4}),\ldots,(V_{t-m-1},V_{t-m},C_{t-m-1}),(V_{t-m},V_{end},C_{t-m})$

We remark that here we use a union bound over all of the $<n^{0.8}$ potential
values of $\ell$ as well as all of the $\leq\log^{5}n$ listed triples. This is
possible as the failure probability of Lemma 6.19 is at most $1/n$. Also, an
easy check shows that the hypothesis of Lemma 6.19 on the randomness
parameters holds for each listed triple. Indeed, each random set listed above
has parameter at most $q$, and we have $\ell\geq qn-n^{0.61}$ which checks the
first inequality in Lemma 6.19. Also, each random set listed has parameter at
least $9q/10$ and $\ell\leq qn+n^{0.61}$ which implies the second inequality
in Lemma 6.19. Finally, with high probability, all the random sets have sizes
within $n^{0.6}$ of their expectations.

Fix all the random sets and the integer $\ell$ so they have all of the
collected properties. Fix also the sets
$V_{str}^{\prime},V_{mid}^{\prime},V_{end}^{\prime},C^{\prime}$ so that they
satisfy properties (1-4). Note that as the random sets have size close to
their expectations, and property $(1)$ holds for
$V_{str}^{\prime}/V_{mid}^{\prime}/V_{end}^{\prime}$, this implies in
particular that $\ell=[qn-n^{0.6},qn+n^{0.6}]$.

We can find disjoint subsets
$R_{V}^{\prime},V_{1}^{\prime},V_{2}^{\prime},\ldots,V_{t-m}^{\prime}\subseteq
G$ and a subset $R_{C}^{\prime}\subseteq R_{C}\cap C^{\prime}$ with the
following properties.

  1. 1.

$R_{V}^{\prime},V_{1}^{\prime},V_{2}^{\prime},\ldots,V_{t-m}^{\prime}$
partition $V_{mid}^{\prime}$, $R_{V}^{\prime}\subseteq R_{V}$,
$|V_{i}^{\prime}|=\ell$, $|V_{i}\setminus V_{i}^{\prime}|\leq n^{0.65}$ and
$|V_{i}\Delta V_{i}^{\prime}|\leq n^{0.7}$ for each $i=1,2,3$ and $t-m$.

  2. 2.

$R_{V}^{\prime}$ has the property from Lemma 6.18 with respect to
$V_{1}^{\prime}$ and $V_{2}^{\prime}$ with the colour set
$R_{C}^{\prime}\subseteq R_{C}$. That is, for any bijection $\phi\colon
V_{1}^{\prime}\to V_{2}^{\prime}$, there exists a system of rainbow paths
using exactly the vertices/colours of $K^{\pm}_{G}[V_{1}^{\prime}\cup
V_{2}^{\prime}\cup R_{V}^{\prime};C^{\prime}]$ from $V_{1}^{\prime}$ to
$V_{2}^{\prime}$, each of length $m=8\lceil 100\log^{2}n\rceil$, and
connecting $v$ to $\phi(v)$ for each $v\in V_{1}^{\prime}$.

Note that the relevant inequalities hold while applying Lemma 6.18 with
$(A,B)=(V_{1}^{\prime},V_{2}^{\prime})$ and $R_{V}$ and $R_{C}$, since
$|V_{1}^{\prime}|=|V_{2}^{\prime}|=\ell\leq
n/\log^{7}n\ll(rp)^{1000}n/\log^{4}n$ since $1/n\ll rp$.

Similarly, we can find disjoint subsets
$C_{1}^{\prime},C_{2}^{\prime},\cdots,C_{t-m}^{\prime}\subseteq G$
partitioning $C^{\prime}\setminus R_{C}^{\prime}$ with the following property.
$|C^{\prime}_{i}|=\ell+k$ for each $i\neq 2$, $|C_{i}\setminus
C_{i}^{\prime}|\leq n^{0.72}$ and $|C_{2}\Delta C_{2}^{\prime}|\leq
n^{1-10^{-10}}$.

Invoke Lemma 6.19 with sets
$(V_{str}^{\prime},V_{1}^{\prime},C_{1}^{\prime})$,
$(V_{3}^{\prime},V_{4}^{\prime},C_{3}^{\prime})$,
$(V_{4}^{\prime},V_{5}^{\prime},C_{4}^{\prime})$, $\ldots$,
$(V_{t-m-1}^{\prime},V_{t-m}^{\prime},C_{t-m-1}^{\prime}),(V_{t-m}^{\prime},V_{end}^{\prime},C_{t-m}^{\prime})$
to find perfect matchings (saturating the vertex sets, and using all but $k$
of the colours from each of the colour sets). For each $i\neq 2$, denote the
colour subset of $C_{i}^{\prime}$ used in the corresponding perfect matching
by $C_{i}^{\prime\prime}$. Let $C_{2}^{\prime\prime}$ be the union of
$C_{2}^{\prime}$ and all of the unused colours from each $C_{i}^{\prime}$,
that is, $C_{i}^{\prime}\setminus C_{i}^{\prime\prime}$ ($i\neq 2$), noting
that there are $k(t-m-1)\ll n^{1-10^{-4}}$ such unused colours.

######  Claim 6.21.1.

$|C_{0}^{\prime\prime}|=\ell$ and if O holds, we have $\sum
V_{3}^{\prime}-\sum V_{2}^{\prime}=\sum C_{2}^{\prime\prime}$, and if C holds,
we have $\sum V_{3}^{\prime}+\sum V_{2}^{\prime}=\sum C_{2}^{\prime\prime}$.

###### Proof.

To see this, it is convenient to apply the property of $R_{V}^{\prime}$ and
$R_{C}^{\prime}$ coming from Lemma 6.18 with an arbitrary choice of $\phi$.
This gives a packing of rainbow paths in $K^{\pm}_{G}$ with the set of
endpoints of the paths being $V_{1}^{\prime},V_{2}^{\prime}$ and
$R_{C}^{\prime}$ being the set of colours used on the paths. This, together
with assumption $(4)$, and that the colours in $C^{\prime}\setminus
R_{C}^{\prime}\setminus C_{2}^{\prime\prime}$ have been used to find perfect
matchings in the specified sets implies the first part of the claim. In the
case that we work with the division digraph, considering all the directed
paths we have found so far, this implies that $\sum V_{2}^{\prime}-\sum
V_{str}=\sum C_{1}^{\prime\prime}+\sum R_{C}^{\prime}$ and $\sum V_{end}-\sum
V_{3}^{\prime}=\sum C_{3}^{\prime\prime}\cup
C_{4}^{\prime\prime}\cup\cdots\cup C_{t-m}^{\prime\prime}$. Combining these
equalities with O, we obtain the second part of the claim. In the case that we
work with the multiplication digraph instead, a similar argument shows the
second part of the claim. ∎

The previous claim allows us to apply Theorem 4.9 with
$(V_{2}^{\prime},V_{3}^{\prime},C_{2}^{\prime\prime})$ to find a perfect
matching directed from $V_{2}^{\prime}$ towards $V_{3}^{\prime}$ both in the
case of division digraphs and multiplication digraphs (note
$C_{2}^{\prime\prime}$ cannot contain $e$ if $G$ is Boolean by assumption).
Now, we invoke the property of the sets $R_{V}^{\prime}$ and $R_{C}^{\prime}$
with a choice of $\phi$ so that we produce a $\vec{P}_{t}$-factor connecting
each $v\in V_{str}$ to $f(v)\in V_{end}$. To define such a $\phi$, for each
$v\in V_{1}$, let $v^{\prime}$ be the matched neighbour of $v$ in $V_{str}$.
Consider the vertex $v^{\prime\prime}$ which is obtained by starting with
$f(v^{\prime})\in V_{end}$, and following each matched edge until we reach a
vertex of $V_{2}$. Set $\phi(v)=v^{\prime\prime}$. It is easy to see that this
function $\phi$ has the desired behaviour, concluding the proof.

∎

####  6.2.3 Deducing Theorem 6.8

###### Proof.

Set $t=\lfloor 2\log^{7}(n)\rfloor$. Let $w$ be the remainder when $n$ is
divided by $t+1$, and set $\ell$ so that $n=(t+1)\ell+w$. Note that $w\leq
t+1\leq 2\log^{7}n$. Set $q:=(\ell-1)/n$ and set $p:=(t-1)q$, noting
$2q+p=1\pm\frac{3t}{n}$. Take random disjoint sets $V_{str}$, $V_{end}$, and
$V_{mid}$ where the former two are $q$-random and the latter is $p$-random
(noting that this is essentially a partition of $G$). Independently, take
disjoint random sets $C_{1}$ and $C_{0}$ where $C_{1}$ is $(q+p)$-random and
$C_{0}$ is $q$-random (hence $C_{0}$ and $C_{1}$ almost partition $G$). With
high probability, Lemma 6.21 applies with $V_{str}$, $V_{end},V_{mid}$ and
$C_{1}$ (set to be $C$ in the statement of Lemma 6.21) and $t$. With high
probability, Lemma 6.19 applies with $(V_{str},V_{end},C_{0})$ and $\ell-1$
(in this application, $a=b=c=q$ and $\ell:=\ell-1$ so the relevant
inequalities hold for Lemma 6.19 to apply). With high probability, all the
random sets have size close to their expectations. Fix sets $V,C$ and vertices
$x,y$ as in the statement of the theorem.

As $w=o(n)$, we can greedily find a rainbow directed path using vertices from
$V\setminus\\{y\\}$ and colours from $C$, say $P_{0}$, on $w+1$ vertices,
starting on $x$ and terminating on some $x^{\prime}$ where $x^{\prime}$. Now,
we may partition $(V\setminus V(P_{0}))\cup\\{x^{\prime}\\}$ as
$V_{str}^{\prime}$, $V_{end}^{\prime}$ and $V_{mid}^{\prime}$ so that
$x^{\prime}\in V_{str}^{\prime}$ and $y\in V_{end}^{\prime}$,
$\ell=|V_{str}^{\prime}|=|V_{end}^{\prime}|=|V_{mid}^{\prime}|/(t-1)$
(possible due to the divisibility condition coming from the size of $P_{0}$)
and for each random set $R$, $R$ and $R^{\prime}$ have small symmetric
difference. For this, it is important that $2q+p=1\pm\frac{3t}{n}$. Set
$k:=\lfloor n^{1-10^{-5}}\rfloor$. We may partition $C\setminus C(P_{0})$ as
$C^{\prime}$ and $C_{0}^{\prime}$ so that $C_{0}^{\prime}=\ell+k-1$, and
$C^{\prime}:=C\setminus C_{0}^{\prime}$ where the pairs of sets
$(C_{0}^{\prime},C_{0})$ and $(C_{1},C^{\prime})$ have small symmetric
difference.

Now, invoke Lemma 6.19 with the sets
$(V^{\prime}_{end}-y,V^{\prime}_{str}-x^{\prime},C_{0}^{\prime})$ to find a
perfect directed matching from $V^{\prime}_{end}-y$ to
$V^{\prime}_{str}-x^{\prime}$ using $\ell-1$ colours coming from
$C_{0}^{\prime}$, calling this set $C_{0}^{\prime\prime}$. Re-define (without
relabelling) $C^{\prime}$ to include the $k$ unused colours from
$C_{0}^{\prime}$, noting that $C^{\prime}$ still has small symmetric
difference with $C_{1}$. Note that $C^{\prime}:=C\setminus C(P_{0})\setminus
C_{0}^{\prime\prime}$.

######  Claim 6.21.2.

Hypothesis 2. of Lemma 6.21 holds with the sets
$V_{str}^{\prime},V_{end}^{\prime},V_{mid}^{\prime},C^{\prime}$.

###### Proof.

Suppose first that $K_{G}^{\pm}=K_{G}^{-}$, that is, we work with the division
digraph. Then, it must be that
$\sum(V_{str}^{\prime}-x^{\prime})-\sum(V_{end}^{\prime}-y)=\sum
C_{0}^{\prime\prime}$ from the perfect matching we found. We also have $\sum
C_{0}^{\prime\prime}=\sum C-\sum C^{\prime}-\sum C(P_{0})$, and that $\sum
C(P_{0})=x^{\prime}-x$ (again using that we work with the division digraph).
By assumption of the theorem, we also have $\sum C=y-x$. Adding up all of
these equalities, we obtain $\sum V_{end}^{\prime}-\sum V_{str}^{\prime}=\sum
C^{\prime}$ as desired. An analogous argument works for multiplication
digraphs and we omit the details. ∎

The other hypotheses are easy to verify and thus we can invoke Lemma 6.21 with
an appropriate choice of a bijection $f\colon V_{str}^{\prime}\to
V_{end}^{\prime}$ so that the union of the path system we obtain combined with
the initial perfect matching creates a path directed from $x^{\prime}$ to $y$.
Combined with $P_{0}$, we obtain the desired path from $x$ to $y$, concluding
the proof. ∎

###  6.3 Zero sum partitions

In this section we apply our main theorem to solve a conjecture of Cichacz and
a problem of Tannenbaum about partitions of abelian groups into zero-sum sets.

####  6.3.1 The Cichacz Conjecture

The following lemma makes our main theorem easier to apply by slightly
modifying a set into a zero-sum sets of specified size.

######  Lemma 6.22.

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