# Cycle type in Hall-Paige: A proof of the Friedlander-Gordon-Tannenbaum
conjecture

Alp Müyesser

###### Abstract

An orthomorphism of a finite group $G$ is a bijection $\phi\colon G\to G$ such
that $g\mapsto g^{-1}\phi(g)$ is also a bijection. In 1981, Friedlander,
Gordon, and Tannenbaum conjectured that when $G$ is abelian, for any $k\geq 2$
dividing $|G|-1$, there exists an orthomorphism of $G$ fixing the identity and
permuting the remaining elements as products of disjoint $k$-cycles. We prove
this conjecture for all sufficiently large groups.

##  1 Introduction

An orthomorphism of a finite group $G$ is a bijection $\phi\colon G\to G$ such
that $g\mapsto g^{-1}\phi(g)$ is also bijective. Orthomorphisms have attracted
much interest in recent years, not least due to their link with Latin squares.
The multiplication tables of groups with orthomorphisms yield Latin squares
with orthogonal mates, which in turn give useful constructions in design
theory (see the book of Evans [17] for an overview of the area). A fundamental
conjecture in the area is the Hall-Paige conjecture [22] which states that a
group $G$ admits an orthomorphism if and only if the product of all elements
in the group (in any order) belongs to the commutator subgroup (this property
is henceforth referred to as the Hall-Paige condition). For abelian groups,
the Hall-Paige condition simply means that the sum of all elements in the
group is the identity. The conjecture was confirmed by Wilcox [35], Evans
[16], and Bray [10] in 2009. It is not too difficult to see that the Hall-
Paige condition is necessary, but the fact that it is also sufficient is quite
remarkable.

The proof of Wilcox, Evans and Bray has the disadvantage that it relies
extensively on the classification of finite simple groups. Recently, two new
proofs of the Hall-Paige conjecture have been found which do not rely on this
classification, with the caveat that both proofs require the group to be
sufficiently large. On the other hand, both proofs strengthen the original
statement of the Hall-Paige conjecture in a distinct, novel direction. The
first of these proofs is due to Eberhard, Manners, and Mrazović [14]. This
proof uses tools from analytic number theory, and it yields a strikingly
accurate asymptotic on the number of orthomorphisms for groups with the Hall-
Paige condition. The second proof is due to the author and Pokrovskiy [29],
and this proof has the advantage of finding orthomorphisms in random-like
subsets of groups. This flexibility turns out to be quite fruitful as
demonstrated by the numerous applications of the “random Hall-Paige
conjecture” given in [29].

The current paper is focused a third way to strengthen the Hall-Paige
conjecture, this time by asserting the existence of orthomorphisms with
specific cycle types. Recall that the cycle type of a permutation $\pi$
encodes how many cycles of each length are present when $\pi$ is written as a
product of disjoint cycles. For example, orthomorphisms that consist of a
single cycle come up naturally in Ringel’s resolution of the Heawood map
colouring conjecture, which motivated Ringel to ask for a classification of
all groups with such orthomorphisms (see [33, 19, 3, 32]). Several other
problems of a similar flavour concerning “sequenceable groups” were raised by
numerous authors with the motivation to construct Latin squares with
additional properties (see [31] and Section 1.1.2 in [29]). There are also
motivations to study orthomorphisms with other cycle types. For example,
orthomorphisms that are products of disjoint $6$-cycles give constructions
such as “cyclic” Steiner triple systems [25].

A unifying conjecture in the area was given by Friedlander, Gordon, and
Tannenbaum in 1981 [18].

######  Conjecture 1.1 (The Friedlander-Gordon-Tannenbaum (FGT) conjecture,
1981).

Let $G$ be an abelian group of order $n$ satisfying the Hall-Paige condition.
Suppose for some integer $k\geq 2$ that $k$ divides $n-1$. Then, there exists
an orthomorphism of $G$ that fixes the identity element, and permutes the
remaining elements as products of disjoint cycles of length $k$.

The Hall-Paige conjecture is not very laborious to verify for abelian groups,
and this was already achieved by Hall and Paige when they posed their
conjecture. The FGT conjecture, on the other hand, has remained open for more
than forty years. There are several partial results towards the FGT conjecture
in the literature. Friedlander, Gordon, and Tannenbaum themselves confirmed
their conjecture for groups of order at most $15$, and abelian $p$-groups
where $p\geq 3$ [18]. We refer the reader to [17] for a more detailed overview
(see also [7, 8, 34] for results about the very related concept of complete
mappings). We just remark that the $k=3$ and the cyclic group case of the FGT
conjecture is open, signifying the difficulty of the problem. In this paper,
we resolve the FGT conjecture for sufficiently large groups.

######  Theorem 1.2.

The Friedlander-Gordon-Tannenbaum conjecture is true for all sufficiently
large groups.

We use methods from probabilistic combinatorics, so our proof needs large
groups just to get concentration for some random variables with fairly simple
distributions. We do not make this constant explicit to make the presentation
neater. We make three further remarks.

######  Remark 1.3.

At the time the FGT conjecture was posed, the Hall-Paige conjecture was known
to be true for abelian groups, but not in general, which perhaps explains why
Conjecture 1.1 is concerned only with abelian groups. Given the present work,
it seems reasonable to suspect that the FGT conjecture can be extended to non-
abelian groups, perhaps even quasi-groups/Latin squares, which would
generalise the famous Ryser-Brualdi-Stein conjecture. We discuss this further
in the concluding remarks, Section 7.

######  Remark 1.4.

Our proof of Theorem 1.2 actually gives much more, and can be used to give
many other cycle types that can be realised via orthomorphisms. We discuss
this further in Section 7.

######  Remark 1.5.

A very related notion is that of a complete mapping, which is a permutation
$\phi$ of a group $G$ such that $g\to g\phi(g)$ is also bijective. A group
admits a complete mapping if and only if it admits an orthomorphism,
essentially because the map $g\to g^{-1}$ is a bijection. Therefore, the Hall-
Paige conjecture is sometimes stated with respect to complete mappings instead
of orthomorphisms. However, this equivalence does not hold when we make
restrictions on the cycle type. For example, in an abelian group, there cannot
be a complete mapping inducing any cycle of length $2$, therefore the FGT
conjecture does not hold when orthomorphisms are replaced with complete
mappings (for a more detailed discussion of cycle types of complete mappings,
see [7, 8]). However, some appropriate modification of the FGT conjecture
likely holds for complete mappings as well, and we discuss this further in
Section 7. We should also remark that, confusingly, orthomorphisms are called
complete mappings in [18], but the convention in the current paper seems to be
standard following the book of Evans [17].

The next section serves as a skeleton for the paper. In this section, we give
a bird’s eye view of the proof of Theorem 1.2, and break up the task into
proving two key lemmas.

##  2 Main theorem and overview of the proof

###  2.1 Definitions of key auxiliary graphs and hypergraphs

It is customary in combinatorics to rephrase statements such as Conjecture 1.1
in terms of finding perfect matchings in hypergraphs, or finding rainbow
structures in edge-coloured graphs, and we follow this tradition in the
current paper.

Given a group of order $n$, we denote by $\vec{K}_{G}$ the edge-coloured
directed graph defined as follows. $V(\vec{K}_{G}):=G$, and
$E(\vec{K}_{G}):=\\{(a,b)\in G\times G\colon a\neq b\\}$, and the colour of an
edge $(a,b)$ is the group element $ab^{-1}$. Given subsets $V,C\subseteq G$,
by $\vec{K}_{G}[V;C]$ we denote the subgraph of $\vec{K}_{G}$ obtained by
keeping only the vertices in $V$, and the directed edges with colours in $C$.
Occasionally, the following related definition will also be useful. Given
multiple subsets $V_{1},V_{2},\ldots,V_{k}\subseteq G$, we denote by
$\vec{K}_{G}[V_{1},V_{2},\ldots,V_{k}]$ the edge-coloured directed graph with
vertex set $V_{1}\sqcup V_{2}\sqcup\cdots\sqcup V_{k}$ ($\sqcup$ indicates
that we are taking a disjoint union) and edge set consisting of edges of the
form $e=(v,w)\in V_{i}\times V_{i+1}$ (with colour $vw^{-1}$) for some
$i\in\\{1,2,\ldots,k\\}$ (where $k+1=1$). By
$\vec{K}_{G}[V_{1},V_{2},\ldots,V_{k};C]$, we denote the same graph obtained
by keeping only edges whose colour is in $C$.

Recall that a subgraph of an edge-coloured graph is called rainbow if all
edges have distinct colours. Given $V,C\subseteq G$, let
$\mathcal{H}_{k}[V;C]$ be the $2k$-uniform hypergraph on the vertex set
$V\sqcup C$ where $v\sqcup c$ is an edge whenever $v\subseteq V$ induces a
rainbow directed cycle of length $k$ in $\vec{K}_{G}$ with the colour set of
the cycle being precisely $c$. $\mathcal{H}_{k}$ denotes
$\mathcal{H}_{k}[G;G]$. Sometimes we overload the terms vertex and colour by
referring to elements of $V(\mathcal{H}_{k}[V;C])$ which come from $V$ as
vertices and those which come from $C$ as colours. The following observation
is quite critical.

######  Observation 2.1.

If $c$ is the colour set of an edge in $\mathcal{H}_{k}$, or the colour set of
some directed rainbow cycle in $\vec{K}_{G}$ (of any length), then the sum of
all the elements of $c$ must equal $0$, i.e. $c$ is a zero-sum set.

###### Proof.

As in a directed cycle each vertex has one in-edge and one out-edge, when we
take a sum of all the colours of a cycle in $\vec{K}_{G}$, each vertex appears
twice, once positive, and once negative. The statement follows. ∎

Given graphs $H$ and $G$, we say that $G$ contains an $H$-factor if there
exists a collection of copies of $H$ in $G$ that partition the vertex set of
$G$. For example, a $K_{2}$-factor in a graph is a perfect matching.
$\vec{P}_{k}$ denotes a directed path of length $k$ (meaning with $k$ edges).
$\vec{C}_{k}$ denotes a directed cycle of length $k$ (meaning with $k$
vertices and $k$ edges). The following proposition follows from all the
definitions presented thus far.

######  Proposition 2.2.

Let $G$ be a finite abelian group and let $k$ be an integer with $k\geq 2$.
The following are equivalent.

  * •

$G$ admits an orthomorphism fixing the identity and permuting the remaining
elements as products of disjoint $k$-cycles.

  * •

$\vec{K}_{G}[G\setminus\\{0\\};G\setminus\\{0\\}]$ contains a rainbow
$\vec{C}_{k}$-factor.

  * •

$\mathcal{H}_{k}[G\setminus\\{0\\};G\setminus\\{0\\}]$ has a perfect matching.

We invite the reader to verify the above proposition. Thanks to Proposition
2.2, we can phrase our main result in the language of hypergraph matchings in
the next subsection.

###  2.2 Main theorem and its proof modulo key lemmas

Recall that a $p$-random subset of set $S$ is one obtained by sampling each
element of $S$ independently with probability $p$. Similarly, we say a
collection of random sets $R_{1},\ldots,R_{k}\subseteq S$ is disjoint
$p$-random if each element of $S$ belongs to each $R_{i}$ with probability
$p$, and to none of the $R_{i}$ with probability $1-pk$, and these decisions
are made independently for each element of $S$. We reserve the letter $n$ for
the size of the ambient group throughout the paper. When we say that an event
holds “with high probability”, we mean that the probability of the event
approaches $1$ as $n$ tends to infinity.

######  Theorem 2.3 (Main theorem).

There exists an absolute constant $\varepsilon_{\ref{thm:mainthm}}>0$ such
that the following holds. Let $G$ be an abelian group of order $n$, let $p\geq
n^{-\varepsilon_{\ref{thm:mainthm}}}$, and suppose $k$ is some integer such
that $3\leq k\leq\log^{10}n$. Let $R_{1},R_{2}\subseteq G$ be $p$-random
subsets, sampled independently. Then, the following holds with high
probability.

Let $V,C\subseteq G$ be equal-sized subsets with $|V\Delta R_{1}|,|C\Delta
R_{2}|\leq n^{3/4}$. Suppose $k$ divides $|V|$ (and thus, $|C|$), and suppose
$\sum C=0$. Then, $\mathcal{H}_{k}[V;C]$ has a perfect matching.

Theorem 2.3 turns into a deterministic statement when applied with $p=1$. This
statement, when $n$ is sufficiently large, implies Conjecture 1.1 (when $3\leq
k\leq\log^{10}n$, the “low-girth case”) by setting $V=C=G\setminus\\{0\\}$.
Theorem 2.3 can thus be interpreted as a randomised version of Conjecture 1.1.
As far as our proof method is concerned, it does not take extra work to prove
Theorem 2.3 compared to Conjecture 1.1. Theorem 2.3 also has further
applications. Using its full strength, one can find orthomorphisms with other
cycle types, see Section 7 for more details.

The $k=2$ case of Conjecture 1.1 is proven implicitly in [18], where the
authors give orthomorphisms of odd-order cyclic groups which are products of
disjoint transpositions (see also [17] for a proof of the $k=2$ case). The
case of $k>\log^{10}n$ (the “high-girth case”), on the other hand, can be
resolved by using some tools from [29]. In fact, the $k=n$ case (the Hamilton
cycle case) was implicitly solved in [29] already, and it turns out the method
is general enough to handle cycles of length at least polylogarithmic in $n$.
We give the details for this in Section 6. We remark that for the methods of
[29], this polylogarithmic lower bound on the cycle length is a hard barrier,
essentially because any sorting network (see [6, 1]) must have depth at least
$\log n$.

For the rest of this section, we focus on Theorem 2.3, which is concerned with
the “low-girth” case of the FGT conjecture. The key lemma used to prove
Theorem 2.3 is the following, which states the existence of an “absorber for
zero-sum subsets”. Roughly speaking, this lemma states that random subsets
contain “absorbers” which have the ability to combine with any small enough
set to produce matchings (we say that the small set is “absorbed”), provided
that this small set satisfies some straightforward necessary conditions.

######  Lemma 2.4 (Zero-sum absorption).

There exist absolute constants
$\varepsilon=\varepsilon_{\ref{lem:zerosumabsorption}}>0$ and
$K=K_{\ref{lem:zerosumabsorption}}\geq 1$ with $\varepsilon K\leq 10^{-10}$
such that the following holds. Let $3\leq k\leq\log^{10}n$, $p\geq
n^{-\varepsilon}$. Let $R_{1},R_{2}\subseteq G$ be $p$-random subsets, sampled
independently. Let $m\in k\cdot\mathbb{N}$ with $m\leq(p/k\log n)^{K}n$. Then,
the following holds with high probability.

Let $U\subseteq G$ with $|U|\leq n^{4/5}$. Then, there exist $V\subseteq
R_{1}\setminus U$ and $C\subseteq R_{2}\setminus U$ with the following
property. For any $V^{\prime}\subseteq G\setminus V$ and $C^{\prime}\subseteq
G\setminus C$ with $|V^{\prime}|=|C^{\prime}|=m$, $\sum C^{\prime}=0$,
$0\notin C^{\prime}$, we have that $\vec{K}_{G}[V\cup V^{\prime};C\cup
C^{\prime}]$ has a rainbow $\vec{C}_{k}$-factor, or equivalently,
$\mathcal{H}_{k}[V\cup V^{\prime};C\cup C^{\prime}]$ has a perfect matching.

A lemma of this form, guaranteeing some rainbow directed $2$-factor (a
partition of the vertex set into cycles) was already proved in [29], and we
refer the reader there for more context regarding the absorption method. Our
goal here is to achieve precise control over the cycle sizes of the $2$-factor
we find, which corresponds to controlling the cycle type of the underlying
orthomorphism. This is a delicate task requiring several novel ideas, and we
discuss the proof of Lemma 2.4 in Section 2.3. We now discuss how Lemma 2.4
allows us to prove Theorem 2.3.

Absorbers are helpful because after they are found and removed from the
hypergraph, one can usually find a nearly spanning matching $M_{1}$ covering
all but a vanishing proportion of the vertices. The few uncovered vertices
then combine with the absorber to produce another matching, $M_{2}$, which
means that $M_{1}\cup M_{2}$ is a perfect matching in the original hypergraph.
To find a matching like $M_{1}$, a typical tool to use would be the Rödl
nibble [2], which by this point refers to a wide variety of results of the
following form: Let $\mathcal{H}$ be nearly regular, have small maximum co-
degree111Co-degree of a pair of vertices in a hypergraph is the number of
edges which contain both vertices. and small uniformity, then $\mathcal{H}$
contains a matching covering all but a vanishing proportion of the vertices.
$\mathcal{H}_{k}$ has the first two of these properties but not necessarily
the last property when $k\gg\log n$, but let us put this technicality aside
for now. An equally important technicality is that greedily removing an
absorber from $\mathcal{H}_{k}$ might damage the regularity of
$\mathcal{H}_{k}$ too much for the Rödl nibble to work. To remedy this, we
find the absorber inside smaller random subsets, so that when the absorber is
removed, it is only a small section of the hypergraph whose regularity gets
spoiled. Indeed, the complement of the smaller random set is still random, and
therefore inherits almost regularity by standard concentration arguments. To
finish, we need a version of Rödl nibble that works with regular hypergraphs
plus a few “junk vertices”, which correspond to the leftover in the smaller
random sets after the absorber is removed. The following lemma encapsulates
this idea.

######  Lemma 2.5.

There exists an absolute constant
$\varepsilon_{\ref{lem:deterministicnibble}}>0$ such that the following holds.
Let $G$ be an abelian group of order $n$. Let $3\leq k\leq\log^{10}n$, and let
$p\geq n^{-\varepsilon_{\ref{lem:deterministicnibble}}}$. Let $R_{1}$ and
$R_{2}$ be $p$-random subsets of $G$, sampled independently. The following
holds with high probability.

For any $|V_{D}|=|C_{D}|\subseteq G$ with
$|V_{D}|,|V_{C}|\leq\varepsilon_{\ref{lem:deterministicnibble}}p^{3}n/k^{100}$,
$\mathcal{H}_{k}[R_{1}\cup V_{D};R_{2}\cup C_{D}]$ contains a matching
covering all but at most $n^{1-1/10^{8}}$ vertices.

The proof of Lemma 2.5 comes down to establishing certain pseudorandomness
properties of $\mathcal{H}_{k}$. Checking pseudorandomness in hypergraphs is
notoriously tricky, for example see [23] for a useful criterion for dense
hypergraphs. Unfortunately, $\mathcal{H}_{k}$ is quite sparse, and potentially
has large uniformity, so [23] is not immediately useful in our set-up. For
this reason, we have to put a fair bit of care into the proof of Lemma 2.5.

We can now give the proof of our main theorem, assuming these two lemmas. We
remark that often in our proofs, we have random subsets $R^{\prime}\subseteq
R$ where $R$ itself is a random subset of the group $G$. When we say that
$R^{\prime}$ is a $q$-random subset, we always mean that $R^{\prime}$ is a
$q$-random subset of the group $G$, and not of $R$.

###### Proof of Theorem 2.3.

Pick a value of $\varepsilon_{\ref{thm:mainthm}}$ such that
$0<\varepsilon_{\ref{thm:mainthm}}\ll\varepsilon_{\ref{lem:zerosumabsorption}},\varepsilon_{\ref{lem:deterministicnibble}},1/K_{\ref{lem:zerosumabsorption}}$.
For each $i\in\\{1,2\\}$, partition $R_{i}$ into $R_{i}^{(1)}$ and
$R_{i}^{(2)}$ which are disjoint $p_{1}$-random and $p_{2}$-random sets
respectively, where
$p_{1}=(1/10)\varepsilon_{\ref{lem:deterministicnibble}}p^{4}/k^{100}$ (and
$p_{2}=p-p_{1}$). We have that $p_{1}\geq
n^{-\varepsilon_{\ref{lem:zerosumabsorption}}}$ and $p_{2}\geq
n^{\varepsilon_{\ref{lem:deterministicnibble}}}$ if
$\varepsilon_{\ref{thm:mainthm}}$ is small enough. Select some $m\in
k\cdot\mathbb{N}$ such that $10n^{1-1/10^{8}}\leq m\leq(p_{1}/k\log n)^{K}n$
(there exists such values of $m$ as
$\varepsilon_{\ref{lem:zerosumabsorption}}K_{\ref{lem:zerosumabsorption}}\leq
10^{-10}$). With high probability, Lemma 2.4 holds with
$(R_{1}^{(1)},R_{2}^{(1)})$ with this value of $m$ and Lemma 2.5 holds with
$(R_{1}^{(2)},R_{2}^{(2)})$. Also with high probability, the size of each
random set is at most $\sqrt{n}\log n$ away from its expectation (by
Chernoff’s bound, see Lemma 3.1). With high probability, all of these
properties hold simultaneously.

Now, fix random sets having all these properties and let $V$ and $C$ be given
as in the statement of the theorem. Set $U:=(R_{1}\setminus
V)\cup(R_{2}\setminus C)$ noting $|U|\leq 2n^{3/4}$. Apply Lemma 2.4 to find
absorbing subsets $V_{A}\subseteq R_{1}^{(1)}\setminus U\subseteq V$ and
$C_{A}\subseteq R_{2}^{(1)}\setminus U\subseteq C$ which can combine with
$m$-sized vertex-sets and $m$-sized zero-sum colour-sets to produce perfect
matchings. Note this implies in particular that $|V_{A}|=|C_{A}|$. Set
$V_{D}:=(R_{1}^{(1)}\cap V)\setminus V_{A}$ and $C_{D}:=(R_{2}^{(1)}\cap
C)\setminus C_{A}$, noting $|V_{D}|,|C_{D}|\leq
2p_{1}n\leq\varepsilon_{\ref{lem:deterministicnibble}}p_{2}^{3}n/k^{100}$.
Note also that $||V_{D}|-|C_{D}||\leq 10n^{3/4}$. By Lemma 2.5,
$\mathcal{H}_{k}[V_{D}\cup(R_{1}^{(2)}\cap V);C_{D}\cup(R_{2}^{(2)}\cap C)]$
has a matching $M_{1}$ covering all but at most $10n^{1-1/10^{8}}$ vertices
(formally, we delete $\leq 10n^{3/4}$ elements from $C_{D}$ or $V_{D}$ so that
$|V_{D}|=|C_{D}|$, also we initially find the matching inside
$\mathcal{H}_{k}[V_{D}\cup R_{1}^{(2)};C_{D}\cup R_{2}^{(2)}]$ and delete the
$\leq|U|$ matched edges that use a vertex/colour from $U$). If necessary,
unmatch some edges of $M_{1}$ so that the number of leftover vertices
$V^{\prime}:=V\setminus V(M_{1})$ and colours $C^{\prime}:=C\setminus
V(M_{1})$ are both equal to $m$ (possible as $k$ divides $|V|,|C|$ and $m$ and
$|V_{A}|=|C_{A}|$). Note that the matching $M_{1}$ guarantees that all colours
in $C\setminus C^{\prime}$ admit a partition $C_{1},C_{2},\ldots$ where each
$C_{i}$ is the colour set of a rainbow cycle in $\vec{K}_{G}$, meaning that
$\sum C_{i}=0$ for each $i$ (see Observation 2.1). So we must have $\sum
C\setminus C^{\prime}=0$ also. As $\sum C=0$ by assumption, this implies that
$\sum C^{\prime}=0$, so we can invoke the property coming from Lemma 2.4. This
means that $V^{\prime}$ and $C^{\prime}$ combine with $V_{A}$ and $C_{A}$ to
produce a matching, $M_{2}$. $M_{1}\cup M_{2}$ is then the desired perfect
matching. ∎

###  2.3 Overview of proof of the absorption lemma

We now discuss the proof of Lemma 2.4, the key technical result in the paper.
The general framework for constructing absorbers is (1) finding “many” small
(meaning typically $O(1)$-sized) “gadget” subgraphs which give “local
variability”, and (2) aligning various gadgets effectively to obtain a large
structure with “global variability” such as $V,C$ in Lemma 2.4. We now expand
on what such a strategy entails in the context of $\mathcal{H}_{k}$.

To give an example of a “gadget with local variability”, let us focus on the
case where $k=3$ and $G=\mathbb{Z}_{n}$, the cyclic group with $n$ elements.
Consider distinct $a,b,c,d\in\mathbb{Z}_{n}$ such that $(a,b,c)$ and $(b,c,d)$
both induce a rainbow $\vec{C}_{3}$ in $\vec{K}_{\mathbb{Z}_{n}}$ and suppose
these two rainbow triangles use the same exact colour set which we’ll call $C$
(this means that $a-b=c-d$ and $c-a=d-b$, and also that
$C=\\{a-b,b-c,c-a\\}=\\{b-c,c-d,d-b\\}$). Then, we can say that
$\\{b,c\\}\sqcup C$ is a gadget that can locally vary between $a$ and $d$ in
the sense that $\\{a\\}\cup\\{b,c\\}\sqcup C$ and $\\{d\\}\cup\\{b,c\\}\sqcup
C$ both induce matchings in $\mathcal{H}_{k}$. One can interpret being able to
combine with both $a$ and $d$ to create perfect matchings as a severe
weakening of the property demanded by Lemma 2.4.

What we mean when we say there are “many” gadgets of this sort is the
following. For any fixed $a$ and $d$ and small subset
$S\subseteq\mathbb{Z}_{n}$ (think of size $o(n)$), we want that there exists a
choice for $b,c\in\mathbb{Z}_{n}\setminus S$ and
$C\subseteq\mathbb{Z}_{n}\setminus S$ so that $\\{b,c\\}\sqcup C$ can locally
vary between $a$ and $d$. So we want to be able to find gadgets that vary
between fixed vertices even after a small portion of the group is deleted by
an adversary. This requirement can be rephrased as saying we want our gadgets
to be “well-distributed” within our host structure. Such a property is very
helpful as it plays nicely with the existence of robustly matchable bipartite
graphs, which is a highly versatile tool devised by Montgomery to construct
absorbers [27]. This approach is sometimes called “distributive absorption”,
and was also used to settle Ringel’s tree packing conjecture, see [28] for
more details.

One can prove by hand that for any $a,d$, the gadgets $\\{b,c\\}\sqcup C$
satisfying the desired properties in $\mathbb{Z}_{n}$ are well-distributed in
the above sense. Indeed, letting $b$ range over $\mathbb{Z}_{n}$, and setting
$c=d+a-b$ will have the desired outcome. However, this strategy would fail in
$(\mathbb{Z}_{2})^{k}$, the elementary abelian $2$-group, for the following
reason. With this strategy, the colour of the edge $(b,c)$ is always
$b-(d+a-b)=2b-d-a=a+d$. We think of $a$ and $d$ as constants, so in this sense
letting $b$ range over $(\mathbb{Z}_{2})^{k}$ does not change the colour of
the edge $(b,c)$. This means that if the colour $a+d$ is deleted by an
adversary, we cannot find a gadget switching between $a$ and $d$ in
$(\mathbb{Z}_{2})^{k}$.

This exemplifies just one type of technicality we need to watch out for while
designing gadgets. What we ask for from our gadgets can be encoded by systems
of linear equations, and we want there to be a a well-distributed set of
solutions to this system. On top of that, we want the solutions to have
distinct coordinates. Indeed, if $b=c$, the gadget $\\{b,c\\}\sqcup C$ would
be useless, as $(a,b,c)$ wouldn’t correspond to a $\vec{C}_{3}$ in
$\vec{K}_{G}$. In Section 3.2.1, we introduce a set of sufficient conditions
for a system of equations to correspond to a well-distributed collection of
gadgets. The tricky part of the task is finding gadgets that are powerful
enough to display some local variability, but also weak enough to satisfy
these sufficient conditions. We refer the reader to Figure 1 which contains
the building blocks of most of the gadgets we use in the paper.

Given the ease with which we found a somewhat useful gadget, perhaps the
reader might be tempted to guess that finding gadgets in problems of this type
should not be very arduous, at least in cyclic groups. We now make a small
aside providing evidence towards the contrary, which we hope will make it
somewhat surprising that the FGT conjecture is true, already for $k=3$ and
cyclic groups.

Firstly, what we mean by “problems of this type” are hypergraph matching
problems where vertices represent group elements and edges represent solutions
to linear equations. For example, in the $k=3$ case of the FGT conjecture,
$\mathcal{H}_{3}$ is a $6$-uniform hypergraph where the edges $(a,b,c,d,e,f)$
have to satisfy $d=b-a$, $e=c-b$, and $f=a-c$ (so $a,b,c$ represent vertices
and $d,e,f$ represent colours). This is arguably more complex than the
corresponding hypergraph for the Hall-Paige conjecture, where the edges
$(a,b,c)$ would be $3$-uniform and satisfy $b-a=c$.

Another critical example comes from the toroidal version of the $n$-queens
problem for which Bowtell and Keevash [9] recently made a break-through. We
won’t give much context for this problem here, it suffices to know that the
problem is about finding perfect matchings in hypergraphs where edges are of
the form $(a,b,c,d)$ where $c=a+b$ and $d=a-b$ and the vertices come from
cyclic groups222It turns out that such a perfect matching corresponds to
placement of mutually non-attacking queens on a toroidal chessboard.. It’s not
easy to say a priori whether this problem should be easier or harder than
finding perfect matchings in $\mathcal{H}_{3}$. Just like for the FGT
conjecture, the Hall-Paige condition is a necessary condition for the
$n$-queens hypergraph to have a perfect matching. As the underlying group is
cyclic, this means that the group must be of odd-order.

However, in stark contrast with the FGT conjecture and the Hall-Paige
conjecture, the $n$-queens problem has another necessary condition which comes
from squaring the group elements (see [9] for details, and note that squaring
refers to multiplication modulo $n$, as opposed to addition modulo $n$), which
makes it impossible for the cyclic group to be of order $3$ modulo $6$ if it
is to contain a perfect matching. Any gadget-based strategy as described here,
without serious modifications, would not be able to detect this obstruction
that comes from squaring group elements. Perhaps, this explains why gadgets
displaying any sort of useful local variability are very difficult to find in
the $n$-queens problem (in [9], Bowtell and Keevash use a more involved
strategy combining randomised algebraic constructions and iterative
absorption).

Given the similarity between the constraints in the $n$-queens problem and the
$k=3$ case of the FGT conjecture, it is surprising that the FGT conjecture
does not have any more necessary conditions in addition to the Hall-Paige
condition. It is hard to give a satisfying explanation for why this is the
case, and there seems to be interesting open problems in this area which we
discuss in Section 7. To conclude this digression, we just reiterate that the
existence of gadgets in hypergraph matching problems is quite delicate and
sensitive to slight changes in the constraints that define the edge sets.

Returning to our overview of the proof of Lemma 2.4, we’ve already discussed
the rudiments of how to find gadgets, and that we combine the gadgets using
the distributive absorption technique. These techniques are sufficient to
prove a version of Lemma 2.4 where the subsets to be absorbed ($V^{\prime}$
and $C^{\prime}$) are contained in another subset $A$ which we get to choose,
as long as it is sufficiently small (see Lemma 5.19). To prove Lemma 2.4, we
would in fact want $A$ to be the whole group, and not just a subset. To go
from this weaker statement to Lemma 2.4, we apply the former with $A$ set to
be a random set, and we show that for any $V^{\prime},C^{\prime}$ (with
$C^{\prime}$ being zero-sum) we can find a matching in $A\cup V^{\prime}\cup
C^{\prime}$ saturating $V^{\prime}\cup C^{\prime}$ (see Section 5.1 for
various lemmas of this sort). By the property of $A$, the unused vertices in
$A$ which are not a part of this matching can be absorbed. This way, we reduce
the task of absorbing arbitrary subsets of $\mathcal{H}_{k}$ to absorbing
subsets that live within a small set that we get to choose. This step is
analogous to the “cover-down” step in applications of the “iterative
absorption” method (see for example [5]), though we will not require any
iterative strategy here.

There are very important challenges that arise in the implementation of this
cover-down step, especially for large $k$ (meaning $k$ tends to infinity as
$n$ tends to infinity). For example, to be able to saturate colours, the
following question is very relevant. For which $k$-subsets $C\subseteq G$ does
$\mathcal{H}_{k}$ have an edge with $C$ as its colour set? Equivalently, which
colour sets induce directed rainbow $k$-cycles in $\vec{K}_{G}$? It is not
hard to see that we need that $\sum C=0$ (see Observation 2.1), but
thankfully, this is not so difficult to ensure. Using some techniques from
[29], we can without loss of generality (roughly speaking) assume that
$C^{\prime}$ (from the statement of Lemma 2.4) comes with a partition into
$k$-sets which are all zero-sum. Note this is feasible because $C^{\prime}$ is
itself zero-sum by assumption.

Further thought reveals that to find a directed rainbow $k$-cycle in
$\vec{K}_{G}$ with colour set $C$, we need to be able to order $C$ as
$(c_{1},\ldots,c_{k})$ such that $c_{1}$, $c_{1}+c_{2}$, $c_{1}+\cdots c_{k}$
are all distinct. This property comes from the necessity that each of the $k$
vertices of the rainbow cycle need to be distinct. Does such an ordering
always exist333We would also need that $0\notin C$, but this is built into the
statement of the FGT conjecture, so we ignore this technicality here.? It
turns out that even for cyclic groups of prime order, this is an open problem,
posed initially by Ronald Graham in 1971. Surprisingly little is known about
this problem (see Problem 10 from [21], see also [4, 13, 12, 11]). For
example, the problem is already open for $k=13$ and cyclic groups of prime
order.

The large $k$ case is further complicated by an entirely different problem
that is probabilistic in nature. Even if we start with a zero-sum $k$-subset
that admits a permutation making its partial sums distinct, there still
remains the problem of finding many cycles with this colour set inside a
random vertex-subset of $\mathcal{H}_{k}$. When $k=o(\log n)$, standard
concentration tools such as Chernoff’s bound resolve this issue, but for
larger $k$, the situation is much less clear. Finding a cover-down strategy
that avoids both of these issues for large $k$ together with a compatible
distributive absorption strategy is arguably the most difficult aspect of our
proof.

That said, neither of these issues come up when $k=3$, and in this case we
obtain a more transparent proof. For this reason, we recommend the reader
interested in inspecting the proof to start with assuming $k=3$ throughout on
an initial read-through, ignoring any lemmas with hypotheses such as “let
$k\geq 10$”.

###  2.4 Organisation of the rest of the paper

We collect some preliminary tools in Section 3. We have already broken up the
task of proving Theorem 2.3 into proving Lemma 2.5 and Lemma 2.4. The former
is done in Section 4 and the latter is done in Section 5. In Section 6, we
show how the high-girth case of the FGT conjecture can be derived from results
from [29], as promised earlier on in this section. In Section 7, we discuss
some directions for future research.

##  3 Preliminaries

###  3.1 Probabilistic tools

####  3.1.1 Concentration inequalities

We need the following two basic concentration inequalities. We will refer to
the following as Chernoff’s bound.

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

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

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

Sometimes the random variables we consider have slight dependencies. In this
case, we rely on Azuma’s inequality which we now cite. Given a product
probability space $\Omega=\prod_{i\in[n]}\Omega_{i}$, a random variable
$X\colon\Omega\to\mathbb{R}$ is called $C$-Lipschitz if
$|X(\omega)-X(\omega^{\prime})|\leq C$ whenever $\omega$ and $\omega^{\prime}$
differ in at most $1$-coordinate.

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

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

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

####  3.1.2 Nibble-type lemmas

We say that a $r$-partite $r$-uniform hypergraph $H$ is
$(\gamma,p,n,k)$-regular if every part has $(1\pm\gamma)n$ vertices and every
vertex has degree $(1\pm\gamma)pn^{k}$. For a $3$-uniform $3$-partite
hypergraph $H$, vertices $u,v$ and a subset $U\subseteq V(H)$, we define the
pair degree of $(u,v)$ into $U$ as the number of vertices in $U$ which are in
the neighbourhood of both $u$ and $v$, i.e. the number of vertices $z$ in $U$
such that there exists $y,w\in V(H)$ such that $\\{u,z,y\\}$ and $\\{v,z,w\\}$
are both edges of $H$. A $3$-uniform $3$-partite hypergraph $H$ is
$(\gamma,p,n)$-typical if it is $(\gamma,p,n,1)$-regular and every pair of
vertices $u,v$ coming from the same part has pair degree $(1\pm\gamma)p^{2}n$
into every other part of $H$. A hypergraph is linear if it maximum co-degree
at most $1$.

The following nibble-type result due to Ehard, Glock, and Joos is convenient
to use for our application here.

######  Theorem 3.3 ([15]).

Suppose $\delta\in(0,1)$ and $r\in\mathbb{N}$ with $r\geq 2$, and let
$\varepsilon:=\delta/50r^{2}$. Then there exists $\Delta_{0}$ such that for
all $\Delta\geq\Delta_{0}$, the following holds. Let $\mathcal{H}$ be an
$r$-uniform hypergraph with $\Delta(\mathcal{H})\leq\Delta$ and
$\Delta^{c}(\mathcal{H})\leq\Delta^{1-\delta}$ as well as
$e(\mathcal{H})\leq\exp(\Delta^{\varepsilon^{2}})$. Suppose that $\mathcal{W}$
is a set of at most $\exp(\Delta^{\varepsilon^{2}})$ weight functions on
$E(\mathcal{H})$. Then, there exists a matching $\mathcal{M}$ in $\mathcal{H}$
such that
$\omega(\mathcal{M})=(1\pm\Delta^{-\varepsilon})\omega(E(\mathcal{H}))/\Delta$
for all $\omega\in\mathcal{W}$ with $\omega(E(\mathcal{H}))\geq\max_{e\in
E(\mathcal{H})}\omega(e)\Delta^{1+\delta}$.

Applying Theorem 3.3 with a single uniform weight function, we obtain the
following.

######  Corollary 3.4.

Let $n$ be sufficiently large and let $p\geq n^{-1/10000}$.

  1. 1.

Let $\mathcal{H}$ be a $6$-uniform $6$-partite hypergraph on $n$ vertices
which is $(n^{-0.01},p,n,2)$-regular with maximum co-degree at most $10n$.
Then, $\mathcal{H}$ has a matching covering all but $n^{1-10^{-5}}$ vertices.

  2. 2.

For any $\gamma\geq 0$, every $(\gamma,\delta,n)$-regular linear tripartite
hypergraph has a matching covering all but at most $n^{1-1/500}+3\gamma n$
vertices.

The below lemma allows us to incorporate some non-random vertices/colours into
the nibble process. It unfortunately does not directly imply Lemma 2.5, but it
will be an important ingredient in its proof.

######  Lemma 3.5 ([29]).

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
$\vec{K}_{G}[A^{\prime},B^{\prime};C^{\prime}]$.

###  3.2 Group theoretic tools

Given a sequence $\vec{c}=(c_{1},c_{2},\ldots,c_{k})$ of group elements, and
another group element $v$, we define the following sequences:

  * •

$P_{out}(v,\vec{c}):=(v,v-c_{1},v-c_{1}-c_{2},\ldots,v-c_{1}-c_{2}-\cdots-
c_{k})$

  * •

$P_{in}(v,\vec{c}):=(v,v+c_{1},v+c_{1}-c_{2},\ldots,v+c_{1}+c_{2}+\cdots+c_{k})$

Observe that in $\vec{K}_{G}$, $P_{out}(v,\vec{c})$ denotes the vertex
sequence obtained by starting a walk from $v$, and following the out-edges
given by the sequence $\vec{c}$. $P_{in}(v,\vec{c})$ is analogous, except it
follows the in-edges.

We call a sequence of group elements $\vec{c}=(c_{1},c_{2},\ldots,c_{k})$ a
path-candidate if the partial sums $\sum_{i\in[j]}c_{i}$ for each $j\in[k]$
(including $j=0$) are all distinct. Equivalently, all non-empty partial sums
(of consecutive elements) are non-zero. Observe that $\vec{c}$ being a path-
candidate simply means that for any vertex $v\in G$, the walks
$P_{out}(v,\vec{c})$ and $P_{in}(v,\vec{c})$ both give paths in $\vec{K}_{G}$.

We call a sequence of group elements $\vec{c}=(c_{1},c_{2},\ldots,c_{k})$ a
cycle-candidate if $(c_{1},c_{2},\ldots,c_{k-1})$ is a path-candidate and
$\sum_{i\in[k]}c_{i}=0$. This means that $P_{out}(v,\vec{c})$ and
$P_{in}(v,\vec{c})$ both give cycles (of length $k$) in $\vec{K}_{G}$.

We call a sequence of group elements rainbow if all coordinates are distinct.
Notice that a necessary condition for solving the FGT conjecture is a
partition of $G\setminus\\{0\\}$ into rainbow cycle-candidates, each of length
$k$.

The following two definitions only come up in the cover-down strategy for
$k\geq 10$.

We call a collection of length $k$ sequences dissociable if for any two
distinct sequences $\vec{c}=(c_{1},c_{2},\ldots,c_{k})$ and
$\vec{b}=(b_{1},b_{2},\ldots,b_{k})$ and $j,j^{\prime}\in[k]$,
$\sum_{i\in[j]}c_{i}\neq\sum_{i\in[j^{\prime}]}b_{i}$. This means that
$P_{out}(v,\vec{c})$ and $P_{out}(v,\vec{b})$ are disjoint except on $v$. We
call such a collection near-dissociable if the previous property holds for
each $j,j^{\prime}\leq k-1$ (or equivalently, the sequences obtained by
removing the last element from each tuple gives a dissociable family). This
means that the corresponding directed walks are disjoint except on the
endpoints.

We call two length $k$ sequences $(c_{1},c_{2},\ldots,c_{k})$ and
$\vec{b}=(b_{1},b_{2},\ldots,b_{k})$ separable at distance $d$ if for all
$j,j^{\prime}\in[k]$,
$\sum_{i\in[j]}c_{i}+\sum_{i\in[j^{\prime}]}b_{i}\notin\\{-d,d\\}$. This means
that for $v$ and $w$ where $v-w=d$, $P_{out}(v,\vec{c})$ and
$P_{in}(w,\vec{b})$ are disjoint (except potentially on $v$ or $w$).

The following simple lemma is key to the gadget finding strategy presented in
Section 3.2.1.

######  Lemma 3.6.

Let $G$ be abelian of order $n$. Then either the map $x\to 2x$ or the map
$x\to 3x$ has an image of size at least $n^{1/5}$.

###### Proof.

For an integer $k$ and an abelian group $G$ let $G_{k}$ denote the number of
distinct images of the map $G\to G$ via $x\to k\cdot x$. Observe that
$(G\times H)_{k}=G_{k}\cdot H_{k}$. By the fundamental theorem of finite
abelian groups, $G\cong(\mathbb{Z}_{2})^{\ell}\times(\mathbb{Z}_{3})^{j}\times
H$ where $H$ is a product of cyclic groups none of which are of order $2$ or
$3$. Note that $(\mathbb{Z}_{t})_{2}\geq t/2$ if $t\neq 2$ and
$(\mathbb{Z}_{t})_{3}\geq t/3$ if $t\neq 3$. This, together with the
observation, implies that $H_{2}\geq|H|/2^{\log_{4}|H|}=|H|^{0.5}$ and
$H_{3}\geq|H|/3^{\log_{4}|H|}\geq|H|^{0.2}$ (using that $H$ has at most
$\log_{4}|H|$ many cyclic factors in its decomposition as each factor needs to
have size at least $4$). Also, $(\mathbb{Z}_{2})^{\ell}_{3}=2^{\ell}$ and
$(\mathbb{Z}_{3})^{j}_{2}=3^{j}$, as multiplying by $3$ in $\mathbb{Z}_{2}$
and multiplying by $2$ in $\mathbb{Z}_{3}$ are both bijections.

Note that $|G|=n=2^{\ell}\cdot 3^{j}\cdot|H|$. If $j\geq\ell$, we have that
$n\leq 6^{j}|H|$ and $|G_{2}|\geq 3^{j}|H|^{0.5}$, so $|G_{2}|\geq n^{1/2}$.
Otherwise, if $j<\ell$, we have that $n\leq 6^{\ell}|H|$ and $|G_{3}|\geq
2^{\ell}|H|^{0.2}$, so $|G_{3}|\geq n^{1/5}$. ∎

####  3.2.1 Finding gadgets

In this section, we adapt some tools from Section 3.6 of [29] and refine them
in the setting of $\vec{K}_{G}$ where $G$ is an abelian group. The main result
of the section is Lemma 3.19, which is key to our gadget finding strategy.

By $F_{k}$, we denote the free abelian group on $k$ generators, the free
variables are denotes as $v_{1},\dots,v_{k}$ (recall that
$F_{k}\cong\mathbb{Z}^{k}$). $G\ast F_{k}$ denotes the free product, and
$(G\ast F_{k})^{\mathrm{ab}}$ denotes the abelianization of the free product
(recall that the abelianization $G^{\mathrm{ab}}$ of a group $G$ is defined by
the property that any homomorphism $G\to H$ where $H$ is abelian factors
uniquely through $G^{\mathrm{ab}}$). A word is simply an element of $(G\ast
F_{k})^{\mathrm{ab}}$. As all groups $G$ are abelian in this paper, $(G\ast
F_{k})^{\mathrm{ab}}\cong G\times F_{k}$, where the latter denotes a direct
product. However, the former perspective makes it clear that each word $w$ can
be represented as

$w=z_{1}\cdot v_{1}+\cdots+z_{t}\cdot v_{t}+g$

where each $v_{i}$ is a free variable, each $z_{i}$ is a (non-zero) integer,
and $g\in G$, and this representation is unique up to reordering the summands.

A word $w$ is constant if $w\in G$, i.e. $w$ does not include any free
variables. We say that $z_{i}$ is the coefficient of $v_{i}$. We say that $w$
is linear in $v_{i}$ if $z_{i}\in\\{1,-1\\}$. We say that $w$ is linear if
each $z_{i}\in\\{1,-1\\}$, and $w$ is not constant. That is, $w$ is linear in
each free variable, and there exists at least one free variable in $w$.

A homomorphism $\pi:(G\ast F_{k})^{\mathrm{ab}}\to G$ is a projection if
$\pi(g)=g$ for all $g\in G$. We show two basic properties of projections. We
remind the reader that throughout, $G$ is a finite abelian group of order $n$.

######  Lemma 3.7.

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

###### Proof.

By the universal property of free abelian groups, there is a unique
homomorphism $g\colon F_{k}\to G$ which agrees with $f$ on
$\\{v_{1},\dots,v_{k}\\}$. By the universal property of free products, there
is a unique homomorphism $h\colon G\ast F_{k}\to G$ that agrees with $g$ on
$F_{k}$ and with the identity homomorphism $G\to G$. As $G$ is abelian, $h$
can be written uniquely as $h=h^{\prime}\circ p$ where $p\colon(G\ast
F_{k})\to(G\ast F_{k})^{\mathrm{ab}}$ is the quotient map, and
$h^{\prime}\colon(G\ast F_{k})^{\mathrm{ab}}\to G$ is a projection that agrees
with $f$ on $\\{v_{1},\dots,v_{k}\\}$. This gives the desired one to one
correspondence. ∎

######  Lemma 3.8.

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

###### Proof.

Suppose that $i=k$, without loss of generality. By Lemma 3.7 there are exactly
$n^{k-1}$ projections $\pi:(G\ast F_{k-1})^{\mathrm{ab}}\to G$. For each such
$\pi$, we show that there is a unique projection $\pi^{\prime}$ that agrees
with $\pi$ and additionally has $\pi^{\prime}(w)=g$. By linearity of $w$ in
$v_{k}$, the equation $w=g$ rearranges into $v_{k}=h$ for some $h\in(G\ast
F_{k})^{\mathrm{ab}}$ and $v_{k}$ does not appear in $h$. So,
$\pi^{\prime}(w)=g$ is equivalent to $\pi^{\prime}(w)=\pi^{\prime}(g)$ (as
$\pi^{\prime}$ is a projection) which is equivalent to
$\pi^{\prime}(v_{k})=\pi^{\prime}(h)$ (as $\pi$ is a homomorphism). As
$\pi^{\prime}$ agrees with $\pi$ and $h\in(G\ast F_{k-1})^{\mathrm{ab}}$, we
have that $\pi^{\prime}(v_{k})=\pi(h)\in G$. Therefore, $\pi^{\prime}$ has
that $\pi^{\prime}(v_{k})=\pi(h)$, and $\pi^{\prime}(v_{i})=\pi(v_{i})$ for
$1\leq i<k$. By Lemma 3.7, there is a unique projection with this property. ∎

The following is a simple consequence of the previous lemma.

######  Lemma 3.9.

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

######  Definition 3.10.

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

  1. (a)

$w^{\prime}-w$ is linear in some free variable $v_{i}$. Note that this is
equivalent to asking that there exists a free variable $v$ with coefficient
$z$ in $w$ and $z^{\prime}$ in $w^{\prime}$ and we have $|z-z^{\prime}|=1$.

  2. (b)

The equation $w=w^{\prime}$ rearranges into $g=0$ for some non-zero group
element $g\in G$.

  3. (c)

The equation $w=w^{\prime}$ rearranges into $3v_{i}-2v_{j}=g$ for some group
element $g\in G$ and distinct free variables $v_{i}$ and $v_{j}$.

######  Definition 3.11.

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

######  Lemma 3.12.

Let $n\geq 10^{100}$. Let $S\subseteq(G\ast F_{k})^{\mathrm{ab}}$ be a set of
size $\leq 1000$. Then there are at most $|S|^{2}n^{k-1/5}$ projections
$\pi:(G\ast F_{k})^{\mathrm{ab}}\to G$ which do not separate $S$.

###### Proof.

Let $w$ and $w^{\prime}$ be two separable words in $S$. We case on which of
the conditions (a)/(b)/(c) makes $w$ and $w^{\prime}$ separable, and count the
projections which do not separate them in each case.

  * (a)

In this case, $\pi(w)=\pi(w^{\prime})$ is equivalent to $\pi(w-w^{\prime})=e$
(using that $\pi$ is a homomorphism). By Lemma 3.8, there are $n^{k-1}$
projections $\pi$ satisfying this latter identity.

  * (b)

We can rearrange $\pi(w)=\pi(w^{\prime})$ into $\pi(g)=\pi(e)$ using that
$\pi$ is a homomorphism. The latter implies that $g=e$ using that $\pi$ is a
projection, which is a contradiction. Hence there can be no projections $\pi$
with $\pi(w)=\pi(w^{\prime})$ in this case.

  * (c)

Similarly to the previous cases, we can rearrange $\pi(w)=\pi(w^{\prime})$
into $3\pi(v_{i})-2\pi(v_{j})=g$. Using Lemma 3.6, suppose first that $x\to
3x$ has at least $n^{1/5}$ images, and suppose $\pi$ also satisfies
$\pi(v_{j})=g^{\prime}$ for some $g^{\prime}\in G$, so we have
$3\pi(v_{i})=g^{\prime\prime}\in G$ (where $g^{\prime\prime}=g+2g^{\prime}$).
As $x\to 3x$ is a homomorphism ($G$ is abelian) and has at least $n^{1/5}$
images, the preimage of $g^{\prime\prime}$ under the map $x\to 3x$ has size at
most $n^{4/5}$ (each non-empty preimage must have the same size in a group
homomorphism). This means $\pi(v_{i})$ must live in a set $T_{g^{\prime}}$ of
size at most $n^{4/5}$ assuming that $\pi(w)=\pi(w^{\prime})$ and
$\pi(v_{j})=g^{\prime}$. Thus, if $\pi(w)=\pi(w^{\prime})$, $\pi$ must agree
with one of $n^{k-1}n^{4/5}$ functions $f\colon\\{v_{1},\ldots,v_{k}\\}\to G$,
meaning that there are at most $n^{k-1/5}$ such projections, using Lemma 3.7.
A symmetric argument works when $x\to 2x$ has at least $n^{1/5}$ images.

As there are at most $\binom{|S|}{2}$ pairs of separable words in $S$, the
desired bound follows. ∎

######  Lemma 3.13.

Let $n\geq 10^{10}$, and let $S\subseteq(G\ast F_{k})^{\mathrm{ab}}$ be a set
of at most $100$ elements which are all linear in at least one variable. Then,
there are projections $\pi_{1},\dots,\pi_{n/200}$ which separate $S$ and have
$\pi_{1}(S),\dots,\pi_{n/200}(S)$ disjoint.

###### Proof.

Call a projection good if it separates $S$. Let $\pi_{1},\ldots,\pi_{t}$ be a
maximal collection of good projections with the sets $\pi_{i}(S)$ being
pairwise disjoint. Set $T=\pi_{1}(S)\cup\cdots\cup\pi_{t}(S)$ noting
$|T|=|S|t$. For any good projection $\pi$, we must have $\pi(S)\cap
T\neq\emptyset$ by maximality, so by Lemma 3.9, we have that there are at most
$100tn^{k-1}$ good projections. On the other hand, there are at most
$|S|^{2}n^{k-1/5}\leq n^{k}/2$ projections which are not good by Lemma 3.12,
so there are at least $n^{k}/2$ good projections (there are $n^{k}$
projections total). Combining, we have $n^{k}/2\leq 100tn^{k-1}$, meaning
$t\geq n/200$, as desired. ∎

Combining the previous lemma with a standard application of Chernoff’s bound,
we obtain the following.

######  Lemma 3.14.

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

Let $S\subseteq(G\ast F_{k})^{\mathrm{ab}}$ a set of $\leq 100$ elements which
are each linear in at least one variable, and let $U\subseteq G$ with $|U|\leq
p^{100}n/1000$. Then there is a projection $\pi:(G\ast F_{k})^{\mathrm{ab}}\to
G$ which separates $S$, has $\pi(S)\cap U=\emptyset$ and $\pi(S)\subseteq R$.

We now package everything we have so far into a lemma (Lemma 3.19) that fits
nicely with our application in the setting of $\vec{K}_{G}$.

######  Definition 3.15.

Given a group $G$, a pattern $P$ is a directed (simple) graph equipped with a
vertex and edge labelling $\phi$ with the following properties.

  1. 1.

$\phi$ maps vertices and edges to $(G\ast F_{k})^{\mathrm{ab}}$ for some
positive integer $k$.

  2. 2.

Each vertex gets a distinct label via $\phi$ (i.e. $\phi|_{V(P)}$ is
injective, but distinct edges can potentially receive the same label)

  3. 3.

If $\vec{e}\in E(P)$ is a directed edge from $v$ to $w$ for $v,w\in V(P)$, we
have that $\phi(v)-\phi(w)=\phi(\vec{e})$.

In Figure 1 we have several examples of patterns. We can naturally view the
edge-labels as colours, hence each pattern can also be viewed as an edge-
coloured graph.

A pairwise separable subset $S$ is a subset where any two distinct words $w$
and $w^{\prime}$ are separable.

######  Definition 3.16.

We call a pattern $(P,\phi)$ well-distributed if the following two conditions
hold.

  1. 1.

The subsets (viewed as sets, not multisets) $\\{\phi(v)\colon v\in V(P)\\}$
and $\\{\phi(\vec{e})\colon\vec{e}\in E(P)\\}$ are both pairwise separable
subsets of $G\ast F_{k}$.

  2. 2.

Each label is either a constant, or linear in at least one free variable.

Notice that we are not insisting that any $\phi(v)$ and $\phi(\vec{e})$ are
separable for a vertex $v$ and edge $\vec{e}$. This is because in our
applications vertex sets and colour sets are sampled independently, hence we
don’t need any separability properties.

######  Definition 3.17.

A copy of a well-distributed pattern $(P,\phi)$ is a subgraph $S$ of
$\vec{K}_{G}[V;C]$ such that there exists a projection $\pi\colon(G\ast
F_{k})^{\mathrm{ab}}\to G$ (where $k$ is the number of free variables used in
$\phi$) with the following properties.

  1. 1.

$\pi$ maps $\phi[V(P)]$ (the vertex labels) to $V(S)\subseteq V$ and
$\phi[E(P)]$ (the edge labels) to $C$.

  2. 2.

$\pi$ separates $\phi[V(P)]$ and $\pi$ separates $\phi[E(P)]$. In particular,
$\pi$ is injective when restricted to $\phi[V(P)]$.

  3. 3.

The $(v,w)$ is a directed edge of $S$ if and only if there is a directed edge
from the vertex with the label $\pi^{-1}(v)$ to the vertex with the label
$\pi^{-1}(w)$ in $P$.

An edge-coloured directed graph isomorphism $\psi$ between two edge-coloured
simple directed graphs $G_{1},G_{2}$ is a graph isomorphism mapping vertices
of $G_{1}$ to vertices of $G_{2}$ and mapping edges $(v,w)$ of $G_{1}$ to
$(\psi(v),\psi(w))$ that preserves the direction of each edge and respects
colours. This means that $e_{1}$ and $e_{2}$ of $G_{1}$ have the same colour
if and only if $\psi(e_{1})$ and $\psi(e_{2})$ have the same colour.

######  Observation 3.18.

Let $S$ be a copy of $P$. Then, there is a edge-coloured directed graph
isomorphism $\psi$ between $P$ and $S$. Furthermore, if $x$ is the label of a
vertex or colour of $P$, and $x$ is a constant, $\psi(x)=x$.

###### Proof.

The projection $\pi$ witnessing that $S$ is a copy naturally corresponds to a
$\psi$ with the desired properties, as $\pi$ fixes elements of $(G\ast
F_{k})^{\mathrm{ab}}$ which are constants by definition of a projection. ∎

The following is a consequence of the definition of well-distributed, copy,
and applying Lemma 3.14 to $R_{1}$ and $R_{2}$.

######  Lemma 3.19.

Let $p\geq n^{-1/700}$. Let $R_{1}$ and $R_{2}$ be $p$-random subsets of $G$,
sampled independently. With high probability, the following holds.

Let $P$ be a well-distributed pattern with $V(P)+E(P)\leq 100$. Let
$U\subseteq G$ with $|U|\leq p^{150}n/10^{7}$. Let $V^{\prime}$ and
$C^{\prime}$ be the set of labels of vertices and colours in $P$ which are
constants. Then, there is a copy of $P$ in $\vec{K}_{G}[(R_{1}\setminus U)\cup
V^{\prime};(R_{2}\setminus U)\cup C^{\prime}]$.

As an example application of the above result, we recommend the reader to
inspect the proof of Lemma 5.2.

####  3.2.2 Partitioning into sets with fixed sum

In this subsection, we prove some lemmas designed to “cover-down” part of the
absorption strategy. See the proof overview for more context. For the reader
interested in the $k=3$ case, the $k=3$ case of Lemma 3.25 is all that is
required, and this case follows directly from Lemma 3.21 (without having to
use Lemma 3.24). We cite the following three results from [29].

######  Theorem 3.20 ([29]).

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

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

  * •

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

  * •

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

  * •

Suppose that $0\notin X\cup Y\cup Z$

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

######  Lemma 3.21 ([29]).

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

Let $X\subseteq G$ with $|X\triangle R|\leq p^{10^{10}}n/\log(n)^{10^{18}}$,
$0\notin X$, $\sum X=0$, and $|X|\equiv 0\pmod{k}$. Then, $X$ can be
partitioned into zero-sum sets of size $k$.

######  Lemma 3.22 ([29]).

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.

Let $\epsilon\in[2\log n/\sqrt{n},p^{800}/10^{4010}]$. For any $m$ with
$|m-pn|\leq\epsilon n$, $g\in G$ and $Z$ with $|Z|\geq m+3$, $|R\setminus
Z|\leq\epsilon n$, there is a set $R^{\prime}\subseteq Z$ with
$|R^{\prime}|=m$, $|R^{\prime}\triangle R|\leq 6\epsilon n$, and $\sum
R^{\prime}=g$.

######  Corollary 3.23.

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

Let $X\subseteq G$ with $|X\triangle R|\leq p^{10^{10}}n/\log(n)^{10^{22}}$.
Let $\alpha\in G$. $0\notin X$, $|X|\equiv 0\pmod{4}$, $\sum
X=(|X|/4)\cdot\alpha$. Then, $X$ can be partitioned into sets of size $4$ with
sum $\alpha$.

###### Proof.

Let $R_{1},R_{2},R_{3},R_{4}$ be disjoint $(p/4)$-random subsets of $G$ which
partition $R$. Let $S$ be a $(p/4)$-random subset of $G$, sampled
independently with the previous sets. Note that the set $-S-\alpha$ is also a
$(p/4)$-random subset of $G$, which is independent with the previous random
sets (not including $S$). With high probability, Theorem 3.20 holds with the
sets $(R_{1},R_{2},S)$ and $(R_{3},R_{4},-S-\alpha)$, Lemma 3.22 holds for
each random set, and by Chernoff’s bound, each random set is within a
$n^{0.6}$ term of its expectation.

Let $X\subseteq G$ be given. By Lemma 3.22, we can partition $X$ into equal
sized sets $X_{1},X_{2},X_{3},X_{4}$ such that $|X_{i}\Delta R_{i}|\leq
p^{10^{10}}n/\log(n)^{10^{21}}$ and $\sum X_{1}+\sum X_{2}=0$. This readily
implies that $\sum X_{3}+\sum X_{4}=(|X|/4)\cdot\alpha$ by the sum condition
on $X$. Similarly, via Lemma 3.22, we can fix a set $S^{\prime}$ with $\sum
S^{\prime}=0$, $|S^{\prime}|=|X|/4$, and such that $S^{\prime}$ has small
symmetric difference with $S$. This implies that
$\sum(-S^{\prime}-\alpha)=-(|X|/4)\cdot\alpha$, and also we have that
$-S^{\prime}-\alpha$ has small symmetric difference with $-S-\alpha$. Thus we
have that $\sum X_{1}+\sum X_{2}+\sum S^{\prime}=0$ and $\sum X_{3}+\sum
X_{4}+\sum(-S^{\prime}-\alpha)=0$. Also, we remark that $S^{\prime}$ can be
chosen so that both $S^{\prime}$ and $-S^{\prime}-\alpha$ do not contain $0$.
So we can apply Theorem 3.20 twice to deduce that both
$H_{G}[X_{1},X_{2},S^{\prime}]$ and $H_{G}[X_{3},X_{4},-S^{\prime}-\alpha]$
has a perfect matching. For each $s^{\prime}\in S^{\prime}$, consider the
edges $(x_{1},x_{2},s^{\prime})$ and $(x_{4},x_{4},-s^{\prime}-\alpha)$
guaranteed by the two perfect matchings, and observe that
$x_{1}+x_{2}+x_{3}+x_{4}=\alpha$. Combining $4$-tuples of this form, we obtain
the desired partition of $X$. ∎

For technical reasons, our absorption strategy for large $k$ requires the
assumption that $k\geq 10$. This leaves the case of $3\leq k\leq 9$ open. The
previous lemmas already give us a way to partition sets into $k$-sets which
are zero sum in this regime. Once we have access to such a partition, a
natural strategy is to look for an ordering of the $k$-set yielding a cycle-
candidate, in order to be able to perform the cover-down step (see proof
overview). We rely on the following result of Alspach and Liversidge to find
suitable orderings. Similar results for cyclic groups were obtained in [13,
24].

######  Lemma 3.24 (Alspach-Liversidge, [4], Corollary 5.2).

Let $G$ be any abelian group (not necessarily finite). Let $S\subseteq G$ be
of size at most $9$. with $\sum S=0$. Then, $S$ admits an ordering yielding a
rainbow cycle-candidate if $\sum S=0$, and otherwise $S$ admits an ordering
yielding a rainbow path-candidate.

We can now prove the main lemma of this section.

######  Lemma 3.25.

There exists an absolute constant
$\varepsilon_{\ref{lem:generalisedtannenbaum}}$ such that the following holds.
Let $3\leq k\leq 9$. Let $G$ be an abelian group of order $n$, let $p\geq
n^{-\varepsilon_{\ref{lem:generalisedtannenbaum}}}$. Let $R$ be a $p$-random
subset of $G$. With high probability, the following holds. Let
$R^{\prime}\subseteq G$ such that $|R^{\prime}\Delta R|\leq
p^{10^{10}}n/\log(n)^{10^{23}}$. Suppose $k$ divides $|R^{\prime}|$ and that
$0\notin R^{\prime}$.

  1. 1.

Suppose that $\sum R^{\prime}=0$. Then, $R^{\prime}$ can be partitioned into
$k$-tuples which are rainbow cycle-candidates.

  2. 2.

Suppose that $k=4$ and for some $\alpha\in G\setminus\\{0\\}$, $\sum
R^{\prime}=(|R^{\prime}|/k)\cdot\alpha$. Then, $R^{\prime}$ can be partitioned
into $k$-tuples which are rainbow path-candidates with sum $\alpha$.

###### Proof.

Choose some $\varepsilon_{\ref{lem:generalisedtannenbaum}}\leq 10^{-1000}$.
With high probability, Lemma 3.21 and Corollary 3.23 both hold for $R$. Let
$R^{\prime}$ be given. For part (1), we apply Lemma 3.21 to partition
$R^{\prime}$ into $k$-sets which are zero-sum. Then, Lemma 3.24 implies that
each of these $k$ sets can be ordered to obtain a rainbow cycle candidate, as
$k\leq 9$. For part (2), we apply Corollary 3.23 to partition into $4$-tuples
each with sum $\alpha$. As $\alpha\neq 0$, we can order each tuple to be path-
candidates by Lemma 3.24. This concludes the proof. ∎

####  3.2.3 Good families of colours

In this section we have some lemmas designed to deal with the $k\geq 10$ case
of the cover-down step.

######  Lemma 3.26.

Let $G$ be an abelian group of order $n$, let $s\in G\setminus\\{0\\}$ let
$\bar{T}$ be the collection of $k$-tuples $(g_{1},\ldots,g_{k})$ with $\sum
g_{i}=s$ (note $|\bar{T}|=n^{k-1}$). Suppose $n^{0.01}\geq k\geq 2$ and $n\geq
10^{10}$. Let $S$ be a subset of $G$ of size at most $n/(20k)$. Then, all but
at most $n^{k-1}/4$ tuples in $\bar{T}$ are all rainbow path-candidates
disjoint with $S$.

###### Proof.

As $s\neq 0$, we can count that there are at least
$(n-1)(n-2)\cdots(n-k+1)\geq(n-k)^{k-1}\geq n^{k-1}/1.01$ (using that $k$ is
small for the final inequality) path-candidates in $\bar{T}$.

If $k\geq 3$, by a direct counting we can see that there are at most
$k^{2}nn^{k-3}\leq k^{2}n^{k-2}$ tuples in $\bar{T}$ with two coordinates
being equal. If $k=2$, using that $G$ is an abelian group and $s\neq 0$, we
see that there are at most $n/2$ tuples (generously) in $\bar{T}$ with two
coordinates being equal. In either case, all but $n^{k-1}/2$ tuples in
$\bar{T}$ are rainbow (using that $n\gg k$).

For each $g\in G$, there are at most $kn^{k-2}$ elements of $\bar{T}$ having
$g$ in some coordinate, here we used that $k\geq 2$. So, there are at most
$|S|kn^{k-2}\leq n^{k-1}/20$ many tuples $\bar{t}$ not disjoint with
$\mathcal{S}_{G}$.

We derive that there are at least $n^{k-1}/1.01-n^{k-1}/2-n^{k-1}/20\geq
n^{k-1}/4$ tuples in $\bar{T}$ satisfying all the desired properties. ∎

######  Lemma 3.27.

There exists some absolute constant $C_{\ref{lem:biggroupspecialfamily}}$ such
that the following holds. Let $G$ be an abelian group of order $n$, let $n\geq
10^{100}$, and let $k$ be a integer such that $10\leq k\leq n^{0.001}$. Then,
$G$ contains two families $\mathcal{F}_{G}=\mathcal{F}_{G}(k)$ and
$\mathcal{S}_{G}=\mathcal{S}_{G}(k)$ of disjoint tuples
$\mathcal{F}_{1},\ldots,\mathcal{F}_{\lfloor
n/kC_{\ref{lem:biggroupspecialfamily}}\rfloor}$ and
$\mathcal{S}_{1},\ldots,\mathcal{S}_{\lfloor
n/kC_{\ref{lem:biggroupspecialfamily}}\rfloor}$ with the following properties.

  1. (1)

Each $\mathcal{F}_{i}$ is of size $4$ and has the same sum $f=f(G,k)$.

  2. (2)

Each $\mathcal{S}_{i}$ has the same size and sum $s=s(G,k)$. In fact,
$|\mathcal{S}_{i}|=:z_{\mathcal{S}}\in\\{2,3,4,5\\}$.

  3. (3)

Each $\mathcal{S}_{i}$ is a rainbow path candidate, and $\mathcal{S}_{G}$ is
near-dissociable.

  4. (4)

$k-4-z_{\mathcal{S}}$ is divisible by $4$. Furthermore, set
$q:=q_{G,k}=-((k-4-z_{\mathcal{S}})/4)f-s$. We have that $q\neq 0$.

  5. (5)

Each $\mathcal{F}_{i}$ can be partitioned into two tuples,
$\mathcal{F}_{i}^{+}=(f_{i}^{+,1},f_{i}^{+,2})$ and
$\mathcal{F}_{i}^{-}=(f_{i}^{-,1},f_{i}^{-,2})$, both of which are rainbow
path candidates. The resulting collection of $\mathcal{F}_{i}^{+}$ and
$\mathcal{F}_{i}^{-}$ are both dissociable. Also, each $\mathcal{F}_{i}$ is a
rainbow path candidate, and $\mathcal{F}_{G}$ is near-dissociable.

  6. (6)

For each $m\in\\{0,1,2,\ldots,k\\}$ and $i\in\lfloor
n/kC_{\ref{lem:biggroupspecialfamily}}\rfloor$, we have that
$\mathcal{F}_{i}^{+}$ and $\mathcal{F}_{i}^{-}$ are separable at a distance
$q+mf$.

###### Proof.

Pick some $z_{\mathcal{S}}$ between $2$ and $5$ so that $k-4-z_{\mathcal{S}}$
is positive and divisible by $4$, note that this is possible as $k\geq 10$.
Pick any $f\neq 0$. Pick some $s$ so that $q+m\cdot f\neq 0$ for any
$m\in\\{0,1,2,\ldots,k,k+1\\}$ for $q:=-((k-4-z_{\mathcal{S}})/4)f-s$. Indeed,
there are $0.9n$ such choices of $s$, as $k\leq n^{0.001}$.

######  Claim 3.27.1.

We can find $\mathcal{S}_{G}$ satisfying (2) and (3).

###### Proof.

Set $k^{\prime}=z_{\mathcal{S}}$, recalling that $k^{\prime}\geq 2$. Suppose
that we have found a maximal family $\mathcal{S}_{G}$ satisfying (2) and (3)
and suppose that $|\mathcal{S}_{G}|<n/(kC)$ for some $C$. We will derive a
contradiction for $C$ sufficiently large.

Let $\bar{G}$ be the collection of rainbow path candidate $k^{\prime}$-tuples
$(g_{1},\ldots,g_{k^{\prime}})$ with $g_{1}+\cdots+g_{k^{\prime}}=s$ which are
disjoint with $\bigcup\mathcal{S}_{G}$ (observing this set has size at most
$5n/(kC)$ by assumption). $|\bar{G}|\geq n^{k^{\prime}-1}/4$ by Lemma 3.26
(supposing $C\geq 100$). If for some $\bar{t}\in\bar{G}$ we have that
$\mathcal{S}_{G}^{*}$ becomes non-dissociable upon the addition of $\bar{t}$,
there must exist some $\bar{t}^{\prime}\in\mathcal{S}_{G}$
$j,j^{\prime}\in[k^{\prime}-1]$ such that
$\sum_{i\in[j]}\bar{t}^{\prime}_{i}=\sum_{i\in[j^{\prime}]}\bar{t}_{i}$. There
are at most $(n/kC)k^{\prime}n^{k^{\prime}-2}\leq n^{k^{\prime}-1}/C$ such
$\bar{t}$, meaning that there is a $\bar{t}\in\bar{G}$ that we can add to
$\mathcal{S}_{G}$ without breaking (2) and (3), a contradiction. ∎

It remains to construct $\mathcal{F}_{G}$. Suppose $\mathcal{F}_{G}$ is a
family of $4$-tuples satisfying the properties with size at most $n/(kC)-1$
(where $C$ is a sufficiently large constant). We will show that
$\mathcal{F}_{G}$ can be extended.

Fix some $f^{+},f^{-}\in G\setminus\\{0\\}$ such that $f^{+}+f^{-}=f$, and the
following two properties hold.

  1. 1.

For any $\mathcal{F}_{i}\in\mathcal{F}_{G}$ we have that
$f^{+},f^{-}\neq\sum\mathcal{T}_{i}$ for any
$\mathcal{T}_{i}\subseteq\mathcal{F}_{i}$.

  2. 2.

$f^{+}+f^{-}\neq\pm q+mf$ for any $m\in\\{0,1,\ldots,k,k+1\\}$.

Such $f^{+},f^{-}$ with the first property exist as long as $C>50$, as
$\sum\mathcal{T}_{i}^{\pm}$ can take at most $20n/C$ distinct values due to
the assumption on the size of $\mathcal{F}_{G}$. Such $f^{+},f^{-}$
automatically satisfy the second property as $q+m\cdot f\neq 0$ for any
$m\in\\{0,1,\ldots k\\}$.

Let $F^{+}$ denote the set of ordered triples with sum $f^{+}$ and $F^{-}$
denote the set of ordered triples with sum $f^{-}$, noting
$|F^{+}|=|F^{-}|=n$.

######  Claim 3.27.2.

Suppose we delete all triples from $F\in F^{+}$ such that the collection
$\mathcal{F}_{+}\cup\\{F\\}$ fails to be dissociable. This deletes at most
$10n/C$ triples.

###### Proof.

If for some $F\in F^{+}$ we have that $\\{\mathcal{F}_{i}^{+}\\}\cup{F}$ is
not dissociable, there must exist some $F^{\prime}\in\mathcal{F}^{+}$ and
$j^{\prime}\in\\{1,2\\}$ and $j\in\\{1,2\\}$ such that
$\sum_{i\in[j^{\prime}]}F^{\prime}(i)=\sum_{i\in[j]}F(i)$. It cannot be that
$j=2$ by the first property coming from our choice of $f^{+}$. By the bound on
$|\mathcal{F}_{G}|$, there are at most $10n/C$ distinct values the quantity
$\sum_{i\in[j^{\prime}]}F^{\prime}(i)=:w$ can take. For each such $w$, there
is at most one $F\in F^{+}$ with $F^{\prime}(1)=w$. This implies that in total
there are at most the claimed number of triples which make the corresponding
collection not dissociable. ∎

######  Claim 3.27.3.

Suppose we delete all tuples from $F\in F^{+}$ such that $F$ and the $1$-tuple
$(f^{-})$ are not separable at a distance $q+m\cdot f$ for some
$m\in\\{0,\cdots,k\\}$. This deletes at most $2k$ tuples.

###### Proof.

If for some $F\in F^{+}$ we have that $F$ and $(f^{-})$ are not separable at a
distance $q+m\cdot f$ for some $j\in\\{1,2\\}$, then we must have
$\sum_{i\in[j]}F(i)+f^{-}=\pm(q+m\cdot f)$ for some $m\in\\{0,\ldots,k\\}$.
Here, $j=2$ is precluded by the second property of $f^{+}$ and $f^{-}$. For
each of the $2k$ possible values of $\pm(q+m\cdot f)-f^{-}$, there exists at
most one $F\in F^{+}$ such that $F(1)=\pm(q+m\cdot f)-f^{-}$, which implies
the claim. ∎

######  Claim 3.27.4.

There are at least $n/4$ tuples in $F^{+}$ which are rainbow path-candidates
and which contain no coordinate $F(i)$ also present in an element of
$\mathcal{S}_{G}$ or $\mathcal{F}_{G}$.

###### Proof.

This is immediate by Lemma 3.26 and bounding
$|\bigcup\mathcal{S}_{G}\cup\bigcup\mathcal{F}_{G}|$. ∎

######  Claim 3.27.5.

Deleting all tuples $F\in F^{+}$ with $F(1)=\pm\sum\mathcal{T}_{i}$ or
$F(2)=\pm\sum\mathcal{T}_{i}$ for some
$\mathcal{T}_{i}\subseteq\mathcal{F}_{i}\in\mathcal{F}_{G}$, we delete at most
$80n/C$ elements.

###### Proof.

There are at most $20n/C$ possible values for the quantity
$\pm\sum\mathcal{T}_{i}$ by the upper bound on the size of $\mathcal{F}_{G}$.
This implies the claim, as $F(1)$ (and $F(2)$) is a distinct value for each
$F\in F^{+}$. ∎

By the bounds coming from the claims, we can fix $\mathcal{F}_{new}^{+}$ to be
a $2$-tuple from $F^{+}$ which is a rainbow path candidate disjoint with the
earlier sets, keeps $\mathcal{F}^{+}$ dissociable, and is separable with
$(f^{-})$ at a distance $q+m\cdot f$ for each $m\leq k$.

Now, we perform the analogous steps for $F^{-}$. Claim 3.27.2 and 3.27.4
(thinking of $F^{+}_{new}$ as an element of $\mathcal{F}_{G}$ to ensure
disjointness) also hold when $+$ is replaced by $-$, giving us at least $n/5$
potential elements of $F^{-}$ we can select while maintaining dissociability
of $\mathcal{F}^{-}$, disjointness with previous tuples, and rainbow path
candidacy.

In addition, we delete the elements of $F^{-}$ which are not separable with
$\mathcal{F}^{+}_{new}$ at a distance $q+mf$ for some
$m\in\\{0,1,\ldots,k\\}$. For any $F\in F^{-}$, it is already impossible for
$\sum_{i\in[j]}\mathcal{F}^{+}_{new}(i)+\sum_{i\in[j^{\prime}]}F(i)=\pm(q+m\cdot
f)$ when $j^{\prime}=2$ (by the property from Claim 3.27.3). When
$j^{\prime}=1$, note that $\pm(q+m\cdot
f)-\sum_{i\in[j]}\mathcal{F}^{+}_{new}(i)$ can take at most $4k$ distinct
values $v$, and we only need to delete at the at most $4k$ many $F\in F^{-}$
with $F(i)=v$.

For each $F\in F^{-}$, consider the $4$-tuple
$\mathcal{F}_{new}=(\mathcal{F}^{+}_{new}(1),\mathcal{F}^{+}_{new}(2),F(1),F(2))$,
and note that this is always a rainbow sequence. If $F\in F^{-}$ makes
$\mathcal{F}_{G}\cup\\{\mathcal{F}_{new}\\}$ not near-dissociable, we delete
$F$ from $F^{-}$. To count how many such $F$ there are, suppose that for some
$\mathcal{F}\in\mathcal{F}_{G}$, we have that
$\sum_{i\in[j]}\mathcal{F}(i)=\sum_{i\in[j^{\prime}]}\mathcal{F}_{new}(i)$
where $j,j^{\prime}\in[3]$. It is impossible that $j^{\prime}\in\\{1,2\\}$ due
to Claim 3.27.5 and the first property of $f^{+}$. Note there are at most
$20n/C$ potential values of $\sum_{i\in[j]}\mathcal{F}(i)$ due to the bound on
the size of $\mathcal{F}_{G}$. This implies that for the relevant equality to
hold, $F(1)$ needs to belong to a set of size $20n/C$, so in this step we
delete at most $20n/C$ elements from $F^{-}$. Similarly, if
$(\mathcal{F}^{+}_{new}(1),\mathcal{F}^{+}_{new}(2),F(1),F(2))$ is not a path
candidate, it must be that a partial sum of the sequence is $0$. This partial
sum cannot contain both of $F(1)$ and $F(2)$, as the whole sum is $f\neq 0$,
and $\mathcal{F}^{+}_{new}(2)\neq-F(1)-F(2)$ by Claim 3.27.5, and
$(F(1),F(2))$ is a path candidate. But the partial sum has to contain $F(1)$,
as $(\mathcal{F}^{+}_{new}(1),\mathcal{F}^{+}_{new}(2))$ alone gives a path
candidate. This means that at most $2$ extra values of $F(1)$ are forbidden if
$(\mathcal{F}^{+}_{new}(1),\mathcal{F}^{+}_{new}(2),F(1),F(2))$ is to be a
rainbow path candidate.

Selecting $C$ large, we can fix a value of $F\in F^{-}$ so that setting
$\mathcal{F}^{-}_{new}=F$, we successfully extend $\mathcal{F}_{G}$, as
desired. ∎

##  4 Nibble with some determinism

In this section we give a proof of Lemma 2.5.

######  Observation 4.1.

Let $\mathcal{E}$ be an equation of the form $\pm a\pm b\pm c=0$. Let $H$ be a
tripartite hypergraph obtained by taking three copies of some group $G$ of
order $n$, and letting $(a,b,c)\in G^{3}$ be an edge whenever it is a solution
to $\mathcal{E}$. Then, $H$ is $(0,1,n)$-typical.

###### Proof.

For a proof for when $\mathcal{E}$ is $a+b+c=0$, see Observation 3.3 in [29].
For other equations of this form, the proof is essentially identical. ∎

Typical graphs have the following useful pseudorandomness property.

######  Lemma 4.2 ([29]).

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

######  Lemma 4.3.

Let $p\geq n^{-1/600}$ and let $X\subseteq G$ be $p$-random. Then, with
probability at least $1-8/n^{3}$, the following holds. For any $Y\subseteq G$,
for all but at most $8n^{9/10}$ vertices $g\in G$, and for each equation of
the form $\mathcal{E}:=\pm g\pm x\pm y=0$ (where $g$ is a constant and $x$ and
$y$ are free variables), we have that there are $p|Y|\pm n^{9/10}$ many
$(x,y)\in X\times Y$ such that $x,y$ and $g$ satisfy $\mathcal{E}$.

###### Proof.

Thanks to Observation 4.1, we can apply Lemma 4.2 to the corresponding
hypergraph defined by each of the $2^{3}=8$ possible equations $\mathcal{E}$,
and with probability at least $1-8/n^{3}$, we ensure that the conclusion of
Lemma 4.2 holds for each of these hypergraphs. The desired statement follows
immediately. ∎

We say that $g\in G$ is generic if $g\neq{e}$ and there are at most $n^{1/2}$
solutions to $x^{2}=g$ in $G$. Let $N(G)$ denote the set of non-generic
elements and note that $|N(G)|\leq n^{1/2}$.

######  Observation 4.4.

Let $G$ be an abelian group of order $n$ and let $A\subseteq G$ be a multiset
of order $k$. Consider the sets $A+g$ for each $g\in G$. Then, at most
$kn^{-1/10}$ many such sets have more than $n^{3/5}$ many non-generic
elements. Also, there are at most $kn^{-1/10}$ sets $A-g$ with more than
$n^{3/5}$ many non-generic elements.

###### Proof.

There are $\leq kn^{1/2}$ tuples $(a,g)\in A\times G$ where $a+g$ is non-
generic. Let $\\#$ be the number of $g\in G$ such that there are $\geq
n^{3/5}$ many $a\in A$ such that $a+g$ is non-generic. Then, $\\#\cdot
n^{3/5}\leq kn^{1/2}$, so $\\#\leq kn^{-1/10}$. The same argument applies when
$+$ is replaced by $-$. ∎

Recall that given a fixed graph $F$, a packing of $F$ in some other graph $G$
is just a collection of vertex-disjoint copies of $F$ in $G$. When we talk
about rainbow packings, we always mean that there is no colour repetition in
edges across all copies of $F$ in the packing.

######  Lemma 4.5.

There exists an absolute constant
$\varepsilon_{\ref{lem:exhaustingdeterministic}}>0$ such that the following
holds. Let $p\geq n^{1-\varepsilon_{\ref{lem:exhaustingdeterministic}}}$. Let
$G$ be a group of order $n$. Let $V_{2},V_{3}\subseteq G$ be disjoint
$p$-random, let $C_{1},C_{2},C_{3}\subseteq G$ be disjoint $p$-random, sampled
independently with $V_{2},V_{3}$. The following holds with probability at
least $1-1/n^{2.9}$.

Let $V_{1},V_{4}\subseteq G\setminus(V_{2}\cup V_{3})$ with
$|V_{1}|=|V_{2}|=(p\pm n^{-0.1})n$. Let $f\colon V_{1}\to V_{4}$ be a
bijection. Then, $\vec{K}_{G}[V_{1},V_{2},V_{3};C]$ contains a rainbow packing
of at least $n^{1-1/10^{5}}$ paths of length $3$, directed $V_{1}\to V_{2}\to
V_{3}\to V_{4}$, such that for all paths $\vec{P}$ in the packing and
$v_{1}\in V_{1}\cap V(\vec{P})$, we have that $f(v_{1})\in V_{4}\cap
V(\vec{P})$.

###### Proof.

Each of the following holds with probability at least $1-O(1/n^{3})$, thus
they all simultaneously hold with probability at least $1-1/n^{2.9}$.

  1. (1)

Lemma 4.3 holds for $X$ set to be each of $V_{2}$, $V_{3}$, $C_{1}$, $C_{2}$
and $C_{3}$.

  2. (2)

For each $i$, $|V_{i}|,|C_{i}|=(p\pm n^{-0.1})n$, by Chernoff’s bound.

  3. (3)

For every colour $c\in G\setminus\\{0\\}$ and vertex pair $v,w\in G$ such that
$v-w-c$ is generic, we have that there exists $(p^{4}\pm n^{-0.1})n$ many
rainbow paths of length $3$ directed $v\to V_{2}\to V_{3}\to w$ with edge
colours $(c_{1},c,c_{3})$ for some $(c_{1},c_{3})\in C_{1}\times C_{3}$. If
$v-w-c$ is not generic, we have that there exists at most $(p^{4}+n^{-0.1})n$
such paths.

###### Proof.

Consider all tuples $(v,v_{2},v_{3},w,c_{1},c,c_{3})$ where
$v_{2},v_{3},c_{1},c_{3}\in G$, and $v-v_{2}=c_{1}$, $v_{2}-v_{3}=c$ and
$v_{3}-w=c_{3}$. There are $n$ such tuples. Note
$c_{1}+c_{3}=v-v_{2}+v_{3}-w=v-w-c$ which is generic. This means for all but
at most $n^{1/2}$ tuples, $c_{1}\neq c_{3}$. As $c\neq 0$, for all tuples
$v_{2}\neq v_{3}$. For each of the $n-n^{1/2}$ tuples where $c_{1}\neq c_{3}$,
the probability of $(v_{2},v_{3},c_{1},c_{3})\in V_{2}\times V_{3}\times
C_{1}\times C_{3}$ is $p^{4}$. Letting $X$ denote the expected number of paths
of the desired form, we obtain that $\mathbb{E}[X]=(p^{4}\pm n^{-1/2})n$.
Further, $X$ is $2$-Lipschitz, so the desired concentration follows from
Azuma’s inequality. When $v-w-c$ is not generic, the same argument applies
except we only have an upper bound on $\mathbb{E}[X]$. ∎

  4. (4)

For every pair of vertices $v,w\in G$ such that $v-w$ is generic, we have that
there exists $(p^{3}\pm n^{-0.05})n$ many rainbow paths directed $v\to
V_{3}\to w$ with edge colours from $C_{2}\times C_{3}$. If $v-w$ is not
generic, we have that there exists at most $(p^{3}+n^{-0.1})n$ such paths.

  5. (5)

For every pair of vertices $v,w\in G$ such that $v-w$ is generic, we have that
there exists $(p^{3}\pm n^{-0.05})n$ many rainbow paths directed $v\to
V_{2}\to w$ with edge colours from $C_{1}\times C_{2}$. If $v-w$ is not
generic, we have that there exists at most $(p^{3}+n^{-0.1})n$ such paths.

The proofs for (4) and (5) are essentially identical to the proof for (3),
hence we omit them.

Now, suppose $V_{i}$ and $C_{i}$ all of the properties, and fix a bijection
$f\colon V_{1}\to V_{4}$. Let $\mathcal{H}$ be the hypergraph consisting of
edges $(v_{1},v_{2},v_{3},v_{4},c_{1},c_{2},c_{3})\in V_{1}\times V_{2}\times
V_{3}\times V_{4}\times C_{1}\times C_{2}\times C_{3}$ where
$v_{1}-v_{2}=c_{1}$, $v_{2}-v_{3}=c_{2}$, $v_{3}-v_{4}=c_{3}$ and
$f(v_{1})=v_{4}$. Our goal is to find a matching covering all but
$n^{1-1/1000}$ vertices in this hypergraph. We sometimes refer to the edges of
this hypergraph as paths. We will show that there is a set $S$ of $\leq
n^{1-1/100}$ vertices we can delete from $\mathcal{H}$ so that the resulting
hypergraph $\mathcal{H}^{\prime}$ is almost regular, that is, for all $v\in
V(\mathcal{H})$, $d(v)=(p^{5}\pm n^{-0.05})n^{2}$.

Towards that goal, set $S$ to include

  * •

the $\leq 90n^{9/10}$ vertices of $G$ coming from Lemma 4.3 applied with each
of $V_{2},V_{3},C_{1},C_{2},C_{3}$

  * •

the $\leq 2|V_{1}|n^{-1/10}\leq 2n^{9/10}$ elements of $G$ coming from
Observation 4.4 applied with the multiset $\\{v-f(v)\colon v\in V_{1}\\}$ and
both $+$ and $-$

so we have $|S|\leq 100n^{9/10}$. We will show all vertices of $\mathcal{H}$
not in $S$ have degree $(p^{5}\pm n^{-0.05})n^{2}$. Since $S$ is small, this
shows that $S$ has the desired property. We consider several cases.

Let $v_{1}\in V_{1}\setminus S$, and set $v_{4}=f(v_{1})\in V_{4}\setminus S$.
For all but $n^{1/2}$ many $c_{2}\in C_{2}$ we have that $v-w-c_{2}$ is
generic. For such $c_{2}$, we have by $3.$ that there are $(p^{4}+n^{-0.1})n$
paths passing through both $v_{1}$ and $c_{2}$. Combined with the bound on the
size of $C_{2}$ coming from (2), this shows the desired upper and lower bound
on $d(v_{1})$ because through the few $c_{2}$ such that $v-w-c_{2}$ is non-
generic, there exists at most $10n$ paths passing through both $v_{1}$ and
$c_{2}$, giving in total $O(n^{3/2})$ such paths.

If $v_{4}\in V_{4}\setminus S$, set $v_{1}=f^{-1}(v_{4})$ and apply the result
from the previous paragraph.

Let $c_{1}\in C_{1}\setminus S$. From Lemma 4.3, we have that there exists
$p^{2}n\pm n^{9/10}$ directed $c_{1}$ coloured edges from $V_{1}$ to $V_{2}$.
As $c_{1}\notin S$, for all but $n^{3/5}$ many $v\in V_{1}$, $v-w-c_{1}$ is
generic, and so for such $v$, we have that $(v-c_{1})-w$ is generic, so we can
apply (4) to obtain that there exists $(p^{4}+n^{-0.1})n$ paths to $f(v)$
passing through $c_{1}$. Combined with the bound on $|V_{1}|$, this gives the
desired bound on $d(c_{1})$, as the number of paths going through the $c_{1}$
such that $v-w-c_{1}$ is non-generic is too small to influence the count, as
before.

Let $c_{3}\in C_{3}\setminus S$. This case follows by a symmetric argument
with the $c_{1}\in C_{1}\setminus S$ case, using (5) in place of (4).

Let $c_{2}\in C_{2}\setminus S$. Let $(v,w=f(v))\in V_{1}\times V_{2}$ and
suppose that $v-w-c_{2}$ is generic. Then by (3) there are $(p^{4}+n^{-0.1})n$
paths passing through $v$, $w$, and $c_{2}$. As $c_{2}\notin S$, we have that
all but $n^{3/5}$ values of $v\in V_{1}$, $v-w-c_{2}$ is generic. This, with
the bound on $|V_{1}|$ implies the desired bound on $d(c_{2})$, again because
there are few paths passing through $c_{2}$ with $v-w-c_{2}$ non-generic.

So $S$ has the desired properties, making $\mathcal{H}^{\prime}$ almost-
regular. Let $\mathcal{H}^{\prime\prime}$ be the hypergraph obtained by
contracting $v$ and $f(v)$ to a single vertex for each $v_{1}\in V_{1}$. Note
that as $f$ is a bijection, and any edge through $v$ has to pass through
$f(v)$ as well, this does not change the regularity parameters of any of the
other vertices in $\mathcal{H}^{\prime}$. To see that this satisfies the
hypotheses of Corollary 3.4(1), the only thing left to check is the co-degree
condition. This is equivalent to obtaining an upper bound on the number of
tuples $(v_{1},v_{2},v_{3},v_{4},c_{1},c_{2},c_{3})\in\mathcal{H}$ where the
values of $2$ coordinates are fixed, and it is not the case that these two
coordinates are the first and the fourth (since the corresponding vertices
have been contracted). This means that we are counting solutions to a system
of equations with $7$ free variables and $6$ independent constraints, hence
there are at most $n$ such solutions. This gives the desired co-degree bound.
Corollary 3.4(1) then gives the desired result. ∎

###### Proof of Lemma 2.5.

Let $q\leq\varepsilon_{\ref{lem:deterministicnibble}}p^{3}/k^{100}$ be a
rational number with denominator at most $n$, observing that there are at most
$n$ values of such $q$. First, we will show that with probability at least
$1/n^{2}$, the statement holds for any $V_{D},C_{D}\subseteq G$ with
$|V_{D}|=|C_{D}|=qn$.

Suppose first that $k=3$. Let $r=(p-2q)/3$ and let
$R_{1}^{(1)},R_{1}^{(2)},R_{1}^{(3)}$ be disjoint $r$, $r$ and $r+2q$ random
(respectively) sets partitioning $R_{1}$. Let
$R_{2}^{(1)},R_{2}^{(2)},R_{2}^{(3)},R_{2}^{(4)},R_{2}^{(5)}$ be disjoint $q$,
$q$, $r$, $r$ and $r$-random (respectively) sets partitioning $R_{2}$. With
probability at least $1-O(1/n^{2.9})$ (we assume here that $q\geq n^{-1/100}$,
otherwise the argument up to finding $M_{1}$ can be discarded, and the $M_{2}$
found at the end of the argument satisfies the requirements), Lemma 4.3 holds
for $R_{2}^{(1)}$ and $R_{2}^{(2)}$ and Lemma 4.5 holds with
$(V_{2},V_{3})=(R_{1}^{(1)},R_{1}^{(2)})$ and
$(C_{1},C_{2},C_{3})=(R_{2}^{(3)},R_{2}^{(4)},R_{2}^{(5)})$. Also, by
Chernoff’s bound the following holds for all cycle-candidate triples $(a,b,c)$
simultaneously with probability at least $1-1/n^{10}$: there exists at least
$p^{3}n/1000$ vertex-disjoint $3$-cycles in $\vec{K}_{G}[R_{1}^{(3)}]$ with
colour sequence $(a,b,c)$ (this holds with high probability by Lemma 3.19 as
well, indeed see Lemma 5.2, but here we cite Chernoff’s bound directly to
obtain an explicit bound on the probability). Finally, with probability at
least $1-1/n^{10}$, all random sets are at most $n^{0.6}$ elements away from
their expectations. With probability at least $1-1/n^{2}$ all of these
properties hold simultaneously.

Now let $V_{D},C_{D}$ be given. Let $H_{G}[R_{2}^{(1)},R_{2}^{(2)},C_{D}]$
denote the $3$-partite $3$-uniform hypergraph on the indicated parts where
triples are edges if and only if they are zero-sum. From Lemma 4.3 applied
with the equation $g+x+y=0$, we have that all but $n^{99/100}$ vertices of
$H_{G}[R_{2}^{(1)},R_{2}^{(2)},C_{D}]$ do not satisfy the regularity
hypothesis from Corollary 3.4(2). Deleting such vertices, we obtain a
$(n^{-0.01},q^{2},qn)$-regular linear tripartite hypergraph, so Corollary
3.4(2) implies that all but $n^{1-1/700}$ elements of $R_{2}^{(1)}\cup
R_{2}^{(2)}\cup C_{D}$ can be covered by disjoint zero-sum triples, denote
these triples by $\mathcal{T}$. If necessary, delete at most one edge from
$\mathcal{T}$ so that $0$ is not used on any triple, meaning that the
remaining triples can be ordered to be cycle-candidates (see, for example,
Lemma 3.24). Using the property of $R_{1}^{(3)}$ repeatedly for each triple in
$\mathcal{T}$, we can find a matching $M_{1}$ saturating all triples in
$\mathcal{T}$ (and nothing else) in
$\mathcal{H}_{k}[R_{1}^{(3)};\bigcup\mathcal{T}]$. Now, invoke Lemma 4.5 with
$V_{1}=V_{4}=(R_{1}^{(3)}\setminus V(M_{1}))\cup V_{D}$ (noting
$|V_{1}|=|R_{1}^{(3)}|$) and $f$ set to be the identity function. This gives
that $\mathcal{H}_{k}[(R_{1}^{(1)}\cup R_{1}^{(2)}\cup R_{1}^{(3)}\setminus
V(M_{1}))\cup V_{D};R_{2}^{(3)},R_{2}^{(4)},R_{2}^{(5)}]$ has a matching
covering all but $10n^{1-1/10^{5}}$ vertices, say $M_{2}$. Then, $M_{1}\cup
M_{2}$ is the desired matching.

Union bounding over all potential values of $q$, we obtain that with high
probability, for each $q$ the statement holds. This is sufficient to deduce
the assertion, as $qn$ is always an integer.

Now, suppose that $k\geq 4$. For each $i\in[k]$, and $j\in\\{1,2\\}$ let
$R_{j}^{(i)}$ be a $((p+q)/k)$-random set for $i\geq 2$ and
$((p+q)/k-q)$-random set for $i=1$, partitioning $R_{j}$. Similarly to the
$k=3$ case, we will fix some rational $q\leq pn/k^{100}$ with denominator at
most $n$, and prove that the desired statement holds with probability at least
$1-1/n^{1.1}$.

With probability at least $1-1/n^{1.3}$, Lemma 3.5 holds for
$(A,B,C)=(R_{1}^{(i)},R_{1}^{(i+1)},R_{2}^{(i)})$ with $\ell=((p+q)/k)n$ for
each $i\in[k-3]$ (using that $k$ is polylogarithmic in $n$ for the union
bound). With probability at least $1-1/n^{10}$, Lemma 4.5 holds with
$(V_{1},V_{2})=(R_{1}^{(k-1)},R_{1}^{(k)})$,
$(C_{1},C_{2},C_{3})=(R_{2}^{(k-2)},R_{2}^{(k-1)},R_{2}^{(k)})$. With
probability at least $1-1/n^{2}$, each random set is within $n^{0.6}$ elements
of its expected size. With probability at least $1-1/n^{1.1}$, all these
properties hold simultaneously.

Let $V_{D},C_{D}$ be given. Apply Lemma 3.5 with random sets
$(R_{1}^{(1)},R_{1}^{(2)},R_{2}^{(1)})$ and
$(A^{\prime},B^{\prime},C^{\prime})=(R_{1}^{(1)}\cup
V_{D},R_{1}^{(2)},R_{2}^{(1)}\cup C_{D})$ to find a matching that saturates
all but $n^{1-1/10^{7}}$ vertices. Continue invoking Lemma 3.5 with
corresponding random sets and
$(A^{\prime},B^{\prime},C^{\prime})=(R_{1}^{(i)},R_{1}^{(i+1)},R_{2}^{(i)})$
for each $i\in[k-3]\setminus\\{1\\}$. In both of these applications, we may
delete/add $O(n^{0.78})$ elements from the corresponding sets so that they
have size precisely $\ell$ or $\ell+\lfloor n^{1-10^{-5}}\rfloor$ (depending
on whether they are vertex or colours sets), so that the hypotheses of Lemma
3.5 are satisfied, and then if necessary we can delete all edges passing
through a dummy vertices/colours. Deleting all vertices that fail to be
covered by one of the $k-3$ matchings found via the previous applications of
Lemma 3.5, we delete at most $kn^{1-1/10^{7}}\leq n^{1-1/(2\cdot 10^{7})}$
vertices. The remaining vertices form directed paths following sets
$R_{1}^{(1)}\to R_{1}^{(2)}\to\cdots\to R_{1}^{(k-2)}$. Let $V_{1}\subseteq
R_{1}^{(1)}$ and $V_{4}\subseteq R_{1}^{(k-2)}$ be the vertices used by these
directed paths, noting $|V_{1}|=|V_{4}|$, and let $f\colon V_{1}\to V_{4}$ be
the bijection induced by the two endpoints of each directed path. Now, Lemma
4.5 allows us to complete all but $n^{1-1/10^{5}}$ of these paths of length
$k-3$ into a $k$-cycle using the remaining random sets, which gives the
desired matching in $\mathcal{H}_{k}$. Union bounding over the potential
values of $q$, we obtain the desired result, as in the $k=3$ case. ∎

##  5 Zero-sum absorption

In this section we prove Lemma 2.4. Throughout this section, whenever a
constant $C$ appears inside the statement of a lemma, this should be read as
“there is a sufficiently large absolute constant $C$ so that the statement
holds with this value of $C$”.

###  5.1 Cover-down step: saturating vertices and colours

####  5.1.1 Covering vertices

The next lemma gives us a way to find edges of $\mathcal{H}_{k}$ that pass
through a specific set of vertices.

######  Lemma 5.1.

Let $p\geq n^{-1/700}$. Let $3\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

  1. 1.

Let $U\subseteq G$ be a set with $|U|\leq
p^{300}n/C_{\ref{lem:exhaustingvertices}}$ (recall the convention set in the
beginning of Section 5). Let $u,v\in G$ be two vertices, not necessarily
distinct. Let $k^{\prime}$ be such that $2\leq k^{\prime}\leq k$. Then, if
$u\neq v$, there exists a rainbow path of length $k^{\prime}$ directed from
$u$ to $v$ in $\vec{K}_{G}[(R_{1}\setminus U)\cup\\{u,v\\};R_{2}\setminus U]$.
If $u=v$ and $k^{\prime}\geq 3$, there exists a directed rainbow cycle of
length $k^{\prime}$ using the vertex $v$.

  2. 2.

Let $U\subseteq G$ be a set with $|U|\leq
p^{300}n/4C_{\ref{lem:exhaustingvertices}}$. Let $V\subseteq G$ be a set of
vertices with $|V|\leq p^{300}n/(4kC_{\ref{lem:exhaustingvertices}})$. Then,
$\mathcal{H}_{k}[(R_{1}\setminus U)\cup V;R_{2}\setminus U]$ has a matching
saturating $V$ where each matched edge uses exactly one vertex from $V$.

###### Proof.

Fix a large constant $C\geq 10^{7}$ and fix
$C_{\ref{lem:exhaustingvertices}}\gg C$. Fix some distinct vertices of
$\vec{K}_{G}$, $u$ and $v$. Fix a set of $n/10$ triples $(c_{1},x,c_{2})$
where $u\to x\to v$ is a rainbow path of length $2$ with edge sequence
$(c_{1},c_{2})$, and the resulting collection of $x$ and $\\{c_{1},c_{2}\\}$
are both pairwise disjoint. Such a collection exists because there are at
least $n/4$ disjoint $(c_{1},c_{2})$ with $c_{1}\neq c_{2}$ and
$c_{1}+c_{2}=u-v\neq 0$ and $G$ is an abelian group. By Chernoff’s bound, with
exponentially high probability, $\vec{K}_{G}[R_{1}\cup\\{u,v\\};R_{2}]$
contains at least $p^{3}n/10$ such paths. By a union bound over all distinct
$u$ and $v$, we have that $\vec{K}_{G}[R_{1}\cup\\{u,v\\};R_{2}]$ contains at
least $p^{3}n/10$ such paths for any choice of $u$ and $v$ with high
probability. Call this property $(\ast)$. Also, Lemma 3.19 holds with high
probabilty.

We claim that a stronger version of part $(1)$ holds when
$k^{\prime}\in\\{2,3\\}$, with $C_{\ref{lem:exhaustingvertices}}$ replaced
with $C$. For $k^{\prime}=2$, this already follows from the property $(\ast)$
as each element of $U$ (other than $u$ or $v$) can eliminate at most $1$ path.
We claim the $k^{\prime}=3$ case follows from an application of Lemma 3.19. In
the case that $u\neq v$, we can see this by defining a pattern that is a
directed path of length $3$, first vertex labelled $u$, last vertex labelled
$v$, and colour sequence ($c_{1}$, $c_{2}$, $u-v-c_{1}-c_{2}$) (labelled in
order of proximity to $u$) where $c_{1},c_{2}$ are free variables (and $u$ and
$v$ are constants). Note this implies that the vertex sequence is
$(u,u-c_{1},u-c_{1}-c_{2},v)$ (so that the third property in the definition of
a pattern holds). This is a well-defined pattern as each vertex gets a
distinct label. Furthermore, the pattern is well-distributed. The colours are
separable by (a), $u$ and $v$ are separable by (b) (as $u\neq v$) and the rest
of the vertex pairs are separable by (a). Also, each label is either a
constant, or linear in $c_{1}$ or $c_{2}$. Then, Lemma 3.19 gives us a copy of
this pattern, which corresponds to the desired rainbow path thanks to
Observation 3.18. In the case that $u=v$, we can proceed similarly, this time
using a pattern that is a directed cycle of length $3$, with colour sequence
$(c_{1},c_{2},-c_{1}-c_{2})$ and vertex sequence
$(u,u-c_{1},u-c_{1}-c_{2},u)$, where $c_{1},c_{2}$ are free variables.

For larger $k^{\prime}$, $(1)$ follows from repeated applications of the cases
of $k^{\prime}\in\\{2,3\\}$. Indeed, any directed path/cycle of length $\geq
4$ can be broken up into directed paths of length $2$ and $3$. While
iteratively invoking $(1)$ with $k^{\prime}\in\\{2,3\\}$, we extend $U$ at
each step, in total adding at most $k$ new elements to $U$. As we know $(1)$
holds with $k^{\prime}\in\\{2,3\\}$ with the smaller constant $C$, this
reduction is valid, as
$p^{900}n/C_{\ref{lem:exhaustingvertices}}+k<2p^{900}n/C_{\ref{lem:exhaustingvertices}}<p^{900}n/C$
(using that $k$ is small and that $C\ll C_{\ref{lem:exhaustingvertices}}$,
respectively).

Now, let a $U$ be given as in the part $(2)$ of the statement, and include in
$U$ all vertices of $V$ (without relabelling). Given a vertex $z\in V$, we can
invoke part $(1)$ with $z=u=v$ to find a cycle of length $k$ using $z$. For
the next iterations, we apply $(1)$ adding to $U$ the vertices we’ve used so
far, which adds to $U$ at most $k|V|\leq
p^{300}n/(4C_{\ref{lem:exhaustingvertices}})$ elements. This means that $U$
never exceeds a size of $p^{300}n/C_{\ref{lem:exhaustingvertices}}$ in any of
the iterations, making the applications of $(1)$ valid. ∎

####  5.1.2 Covering colours: Small $k$

######  Lemma 5.2.

Let $p\geq n^{-1/700}$. Let $k\leq 50$. Let $R_{1}$ be a $p$-random subset of
$G$. With high probability, the following holds.

Let $S$ be a $k$-tuple which is a rainbow path candidate. Let $U\subseteq G$
with $|U|\leq p^{350}n/C_{\ref{lem:pathcyclecandidates}}$. Then,
$\vec{K}_{G}[R_{1}\setminus U]$ contains a path with colour sequence $S$.
Similarly, if $S$ is a cycle candidate, $\vec{K}_{G}[R_{1}\setminus U]$
contains a cycle with colour sequence $S$.

###### Proof.

With high probability, Lemma 3.19 holds with $R_{1}$ (and $R_{2}$ set to be a
$p$-random set independent with $R_{1}$ – $R_{2}$ will not be relevant in the
proof). Consider a pattern (as in Definition 3.15) consisting of a directed
path on $k+1$ vertices, and label $i$th edge with $c_{i}$ and label the first
vertex of the path with $v$ where $v$ is a free variable. This is enough
information to determine the label of the remaining $k$ vertices: the label of
the $i$th vertex on the path for $2\leq i\leq k+1$ has to be $v-\sum_{1\leq
j<i}c_{i}$ for the pattern to be well-defined (note also that each vertex gets
a distinct label).

This pattern is well-distributed. For pairs of colours, separability follows
by (b) as $c_{i}\neq c_{j}$ when $i\neq j$. For pairs of vertices,
separability follows from (b) once again, this time using that $S$ is a path-
candidate (recall being a path-candidate implies that all partial sums of $S$
are non-zero). Also, all vertices of this pattern are linear in at least one
variable, namely, $v$. Also, all colours are constants. Therefore, by Lemma
3.19, there exists a copy of this pattern in $\vec{K}_{G}[R_{1}\setminus
U,(R_{2}\setminus U)\cup S]$, which corresponds to a directed path in
$\vec{K}_{G}$ with $S$ as its colour sequence. To justify this correspondence,
recall Observation 3.18.

If $S$ was a cycle-candidate instead, an analogous argument works, this time
starting with a pattern that is a directed cycle of length $k$, with colour
labels coming from $S$, and one of the vertices labelled $v$ which is a free
variable. Separability of colours and vertices are by (b), using the
definition of a cycle-candidate. ∎

Our cover-down statement for small groups of colours is the following. The
proof is omitted, it follows easily by iteratively invoking Lemma 5.2.

######  Lemma 5.3.

Let $p\geq n^{-1/700}$. Let $3\leq k\leq 9$. Let $R_{1}$ be a $p$-random
subset of $G$. With high probability, the following holds.

Let $C\subseteq G$ be a set of $k\ell$ colours, admitting a partition into
tuples $C_{1},\ldots,C_{\ell}$ where each $C_{i}$ is a rainbow cycle-
candidate. Suppose $\ell\leq p^{400}n/kC_{\ref{lem:exhaustcolourssmallk}}$.
Then, $\mathcal{H}_{k}[R_{1}\setminus U;C]$ contains a matching of size
$\ell$.

####  5.1.3 Saturating colours: Large $k$

When $k$ is large, the strategy in the previous section fails for two reasons.
Firstly, assuming that the $C_{i}$ are cycle-candidates as in Lemma 5.2 would
be too much of an ask, as in general we do not have a good way of finding
orderings of zero-sum sets in this way (for $k\leq 9$, we get to assume this
without loss of generality, relying on Lemma 3.24). Even if we were able to
find such orderings, there is a second issue which is probabilistic which
comes up only when $k\geq\log n$. The issue is that the expected number of
$k$-cycles using a particular colour sequence contained in a $p$-random set is
$\leq p^{k}n$ – this is too small to have any useful analogue of Lemma 3.19.
Therefore, we pursue a more complicated strategy as follows.

Recall that the families $\mathcal{F}_{G}$ and $\mathcal{S}_{G}$ were defined
in Lemma 3.27.

######  Lemma 5.4.

Let $10\leq k\leq\log^{10}n$. Let $G$ be a group of order $n$, where $n$ is
sufficiently large. The following statements both hold.

  1. 1.

Let $v,w\in G$ be distinct vertices with $v-w=q_{G,k}+m\cdot f_{G,k}$ for some
natural $m\leq k$. Then, there exists a family $\mathcal{P}$ of size $\geq
n/(kC_{\ref{lem:colourpathsseparation}})$ of pairs of rainbow paths
$(P,P^{\prime})$ in $\vec{K}_{G}$ with the following properties.

    1. (a)

For each $(P,P^{\prime})\in\mathcal{P}$, $P$ starts on $v$, and $P^{\prime}$
ends on $w$.

    2. (b)

Each path in $\mathcal{P}$ is rainbow, pairwise colour disjoint, and pairwise
vertex disjoint except on $\\{v,w\\}$.

    3. (c)

For each $(P,P^{\prime})\in\mathcal{P}$, $C(P)\cup
C(P^{\prime})\in\mathcal{F}_{G}$

  2. 2.

Let $v,w\in G$ be distinct vertices with $v-w=s_{G,k}$. Then, there exists a
family of rainbow paths $\mathcal{P}$ of size $\geq
n/(kC_{\ref{lem:colourpathsseparation}})$ in $\vec{K}_{G}$ with the following
properties.

    1. (a)

For each $P\in\mathcal{P}$, $P$ starts on $v$, and $P$ ends on $w$.

    2. (b)

Each path in $\mathcal{P}$ is rainbow, pairwise colour disjoint, and pairwise
vertex disjoint except on $\\{v,w\\}$.

    3. (c)

For each $P\in\mathcal{P}$, $C(P)\in\mathcal{S}_{G}$

###### Proof.

We suppose $C_{\ref{lem:colourpathsseparation}}$ is sufficiently large for the
following calculations to go through.

Let $\mathcal{P}$ be a maximal family with properties $1(a)$, $1(b)$, and
$1(c)$. Suppose $|\mathcal{P}|<n/(kC_{\ref{lem:colourpathsseparation}})$.
Supposing that $C_{\ref{lem:colourpathsseparation}}\ll
C_{\ref{lem:biggroupspecialfamily}}$, there exists at least
$n/(2kC_{\ref{lem:biggroupspecialfamily}})$ many
$\mathcal{F}_{i}\in\mathcal{F}(G)$ which are unused by $\mathcal{P}$. For each
such unused $\mathcal{F}_{i}\in\mathcal{F}(G)$, consider the path $P_{i}$ with
vertex sequence $P_{out}(v,\mathcal{F}_{i}^{+})$ and path $P^{\prime}_{i}$
with vertex sequence $P_{in}(w,\mathcal{F}_{i}^{-})$ (these are defined in
Section 3.2). Note that $P_{i}$ and $P_{i}^{\prime}$ are in fact paths as the
corresponding colour sequences are path-candidates by Lemma 3.27.

Also by Lemma 3.27, the paths $P_{i}$ and $P^{\prime}_{i}$ are vertex disjoint
except possibly on $v$ and $w$, as $\mathcal{F}_{i}^{+}$ and
$\mathcal{F}_{i}^{-}$ are separable at a distance $q+mf$. By the
dissociability property coming from Lemma 3.27, for each $P_{i},P_{j}$ with
$i\neq j$, $P_{i}$ and $P_{j}$ are vertex disjoint except on $v$, and
similarly $P_{i}^{\prime},P_{j}^{\prime}$ are vertex-disjoint except on $w$.
Using these two properties and assuming that
$C_{\ref{lem:colourpathsseparation}}\ll C_{\ref{lem:biggroupspecialfamily}}$
we can find some $i$ for which $\mathcal{F}_{i}$ is unused in $\mathcal{P}$,
$(P_{i},P_{i}^{\prime})$ is vertex-disjoint with all vertices included in
$\mathcal{P}$ (note there are at most
$10n/kC_{\ref{lem:colourpathsseparation}}$ such vertices), and $V(P_{i})\cap
V(P_{i}^{\prime})=\emptyset$, contradicting maximality of $\mathcal{P}$.

An analogous argument shows the second part of the statement. ∎

Lemma 5.4 combined with Chernoff’s bound implies the following easily.

######  Lemma 5.5.

Let $p\geq n^{-1/700}$, let $10\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

Let $U\subseteq G$ be a set with $|U|\leq
p^{50}n/(kC_{\ref{lem:smallcolourpathslargek}})$. Let $v,w\in G$ be distinct
vertices.

  1. 1.

Suppose $v-w=q_{G,k}+m\cdot f_{G,k}$ for some $0\leq m\leq k$. There exists
some $\mathcal{F}\in\mathcal{F}_{G}$ such that $\vec{K}_{G}[(R_{1}\setminus
U)\cup\\{v,w\\};\mathcal{F}]$ has two vertex disjoint rainbow directed paths
of length $2$, one directed away from $v$, one directed into $w$. Furthermore,
$\mathcal{F}$ is disjoint with $U$.

  2. 2.

Suppose $v-w=s_{G,k}$. There exists some $\mathcal{S}\in\mathcal{S}_{G}$ such
that $\vec{K}_{G}[(R_{1}\setminus U)\cup\\{v,w\\};\mathcal{S}]$ contains a
rainbow directed path (of length $z_{\mathcal{S}}$) from $v$ to $w$.
Furthermore, $\mathcal{S}$ is disjoint with $U$.

The next lemma summarises our cover-down strategy for large $k$. The proof
simply iterates parts (1) and (2) of Lemma 5.5, and this works due to
properties acquired in Lemma 3.27.

######  Lemma 5.6.

Let $p\geq n^{-1/700}$, let $10\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

Let $U\subseteq G$ be a set with $|U|\leq
p^{600}n/(kC_{\ref{lem:exhaustingcolourslargek}})$. Suppose $\ell$ is some
positive integer with $\ell\leq
p^{600}n/(k^{2}C_{\ref{lem:exhaustingcolourslargek}})$. Let $C\subseteq G$ be
a set of $4\ell$ colours admitting a partition into $4$-tuples
$C_{1},\ldots,C_{\ell}$ where each $C_{i}$ is a rainbow path candidate with
sum $q_{G,k}$. Then, $\mathcal{H}_{k}[R_{1}\setminus U;(R_{2}\setminus U)\cup
C]$ has a matching saturating $C$, and the set of colours $C^{*}$ used on the
matching other than $C$ is closed under $\mathcal{F}_{G}$ and
$\mathcal{S}_{G}$. Moreover, $C^{*}$ uses exactly
$\ell(k-4-z_{\mathcal{S}})/4$ tuples from $\mathcal{F}_{G}$ and exactly $\ell$
tuples from $\mathcal{S}_{G}$. As a consequence, the matching consists of
exactly $\ell$ edges of $\mathcal{H}_{k}$.

###### Proof.

Fix some large $K$ and some $C_{\ref{lem:exhaustingcolourslargek}}\gg K$. With
high probability, Lemma 5.5 and Lemma 5.2 both hold.

We will first prove the statement when $\ell=1$ with
$C_{\ref{lem:exhaustingcolourslargek}}$ replaced with $K$ (note this
strengthens the statement). Initialise $U_{1}=U$, and for each
$i\in\\{1,\ldots,\ell\\}$, do the following.

In $\vec{K}_{G}[R_{1}\setminus U_{i};(R_{2}\setminus U_{i})\cup C]$, find a
rainbow path $P_{0}$ with colours $C_{1}$ via Lemma 5.2. Note that
$\text{start}(P_{0})-\text{end}(P_{0})=q_{G,k}+m\cdot f_{G,k}$ for some
natural $m\leq k$ (in fact $m=0$). For a natural $i$, while
$k-|P_{i}|>z_{\mathcal{S}}$, apply Lemma 5.5(1) to extend $P_{i}$ into another
rainbow path $P_{i+1}$ using a set of $4$ extra colours coming from an element
of $\mathcal{F}_{G}$ (disjoint with $U_{i}$). Note that this preserves that
$\text{start}(P_{i+1})-\text{end}(P_{i+1})=q_{G,k}+m\cdot f_{G,k}$ for some
$0\leq m\leq k$. Update $U_{i+1}$ to include the new colours and vertices used
in $P_{i+1}$.

In at most $k$ steps, this procedure yields a path $P$ with
$k-|E(P)|=z_{\mathcal{S}}$ due to the divisibility conditions coming from
Lemma 3.27, note also $|U_{i}|\leq|U|+10i$, so we add at most $10k$ new
elements to $U$ throughout the process. At this point, we can apply Lemma
5.5(2) to complete $P$ into a rainbow cycle, say $\mathcal{C}$, and therefore
an edge of $\mathcal{H}_{k}$. Also, observe that while building $\mathcal{C}$,
we used $(k-4-z_{\mathcal{S}})/4$ tuples from $\mathcal{F}_{G}$ and one tuple
from $\mathcal{S}_{G}$.

When $2\leq\ell\leq p^{600}n/(k^{2}C_{\ref{lem:exhaustingcolourslargek}})$, we
can repeat the above procedure for each of $C_{2},\ldots,C_{\ell}$, at each
iteration including in $U$ the set of at most $10k$ vertices and colours used
in the previous step. This would add at most $10k\ell\leq
10p^{600}n/kC_{\ref{lem:exhaustingcolourslargek}}$ new elements to $U$, which
means $U$ will never exceed a size of
$11p^{600}n/kC_{\ref{lem:exhaustingcolourslargek}}\ll p^{600}n/kK$ throughout
the process. Hence at each step, we can invoke (the stronger version of) the
$\ell=1$ case. ∎

Figure 1: Several patterns (see Definition 3.15) used in Section 5.2. Edge
colours correspond to edge labels, so for a collection of edges with the same
colour, the label is written for only one of the edges. Free variables are
denoted in black letters, and elements of $G$ are denoted in pink letters. The
dashed arrows indicate that after a copy of the pattern is found, a rainbow
directed path (of the appropriate length) between the indicated vertices will
be found. For triples tiled with the diagonal lines, in the proof we find a
$2$-absorber for the indicated vertices.

###  5.2 Distributive absorption in $\mathcal{H}_{k}$

######  Definition 5.7.

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

We will build the desired absorbing structures by finding collections of small
subgraphs with certain properties. Each structure found in this section is
formed by combining patterns coming from Figure 1. Therefore, the following
result is crucial, as it will allow us to use Lemma 3.19 numerous times
throughout the section (we remark that $P_{\mathcal{F}}(V)$ is excluded in the
statement of the following lemma as we treat this pattern separately).

######  Lemma 5.8.

In Figure 1, all patterns depicted except for $P_{\mathcal{F}}(V)$ are well-
defined patterns which are well-distributed.

###### Proof.

The definition of a pattern and the second part of the definition of well-
distributed is easy to verify by inspecting the figure, so we focus on
checking pairwise separability for vertices and colours. Hence, we focus on
the first part of the statement for each individual pattern.

  * •

$P_{x,z}(y,\ell_{1},\ell_{2})$. For this pattern and the next, we implicitly
assume that $x\neq z$, making $x$ and $z$ separable by (b). All other pairs of
vertices are separable by (a). Except for the two pairs of colours
$(2\ell_{1}-y-x,y-\ell_{1})$ and $(2\ell_{2}-y-z,z-\ell_{2})$ which are
separable by (c), all pairs of colours are separable by (a).

  * •

$P^{\prime}_{x,z}(y,\ell_{1},\ell_{2})$. This pattern is well-distributed as
it is a strict subset of $P_{x,z}(y,\ell_{1},\ell_{2})$.

  * •

$P_{x}(c_{1},c_{2})$. All pairs of vertices and colours are separable by (a).

  * •

$P_{x}^{(4)}(c_{1},c_{2},c_{3})$. All pairs of vertices and colours are
separable by (a).

  * •

$P_{a}(v,d_{1},d_{2})$. All pairs of vertices and colours are separable by
(a).

Hence, each pattern is well-distributed as desired. ∎

The following remark is crucial to keep in mind as we will make many
references to Figure 1 in the rest of the section.

######  Remark 5.9.

On numerous occasions, we will consider multiple instances of the same pattern
type in Figure 1. For example,
$P_{x,z^{\prime}}(y^{\prime},\ell_{1},\ell_{2})$ refers to the pattern
depicted in Figure 1 denoted $P_{x,z}(y,\ell_{1},\ell_{2})$ with $y$ replaced
with $y^{\prime}$, $z$ replaced with $z^{\prime}$, but $\ell_{1}$ and
$\ell_{2}$ unchanged. So $P_{x,z}(y,\ell_{1},\ell_{2})$ and
$P_{x,z}(y^{\prime},\ell_{1},\ell_{2})$ are different patterns with some
overlap in the vertex and edge labels they receive.

####  5.2.1 Vertex-switchers

We first show how to $1$-absorb a set of $2$ vertices. We emphasise that when
we say a vertex of $\mathcal{H}_{k}$ in this section, we specifically mean a
vertex which corresponds to a vertex of $\vec{K}_{G}$, as opposed to a colour
of $\vec{K}_{G}$. This is crucial, as in fact it is impossible to build a
$1$-absorber for a set of $2$ vertices of $\mathcal{H}_{k}$ which correspond
to colours of $\vec{K}_{G}$. This follows from Observation 2.1.

######  Lemma 5.10.

Let $p\geq n^{-1/700}$. Let $3\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

For any distinct vertices $x,z\in\mathcal{H}_{k}$ and $U\subseteq G$ with
$|U|\leq p^{300}n/C_{\ref{Lemma_absorber_pair_main}}$,
$\mathcal{H}_{k}[(R_{1}\setminus U)\cup\\{x,z\\},(R_{2}\setminus U)]$ contains
a subgraph of size at most $10k$ that $1$-absorbs $\\{x,z\\}$.

###### Proof.

With high probability, Lemma 3.19 and Lemma 5.1 both hold.

Suppose first that $k=3$. Consider the pattern
$P=P_{x,z}(y,\ell_{1},\ell_{2})$ from Figure 1. A copy of $P$ can be found in
$\vec{K}_{G}[(R_{1}\setminus U)\cup\\{x,z\\},(R_{2}\setminus U)]$ by Lemma
3.19. Inspecting the two sets of matchings (the solid matching and the dashed
matching) in Figure 1 (top-left), we see that such a copy of $P$ corresponds
to a desired absorbing subgraph of $\mathcal{H}_{k}[(R_{1}\setminus
U)\cup\\{x,z\\},(R_{2}\setminus U)]$ of size $\leq 30$. Recall Observation
3.18 to justify this correspondence.

Suppose now that $4\leq k\leq\log^{10}n$. In this case consider a copy of the
pattern $P=P^{\prime}_{x,z}(y,\ell_{1},\ell_{2})$ from Figure 1 given by Lemma
3.19. To complete the absorber, we need to find rainbow paths of size $k-2\geq
2$ from $\ell_{1}$ to $y-\ell_{1}+x$ and from $\ell_{2}$ to $y-\ell_{2}+x$
(when we say $\ell_{1}$, we mean the copy of the vertex with the label
$\ell_{1}$ in $P^{\prime}_{x,z}(y,\ell_{1},\ell_{2})$, similarly for the other
variables. We use this convention in the rest of this section). Two
applications of Lemma 5.1(1) allows us to find these paths. As in the previous
case, the solid matching and the dashed matching demonstrates that the desired
absorption property holds. ∎

Chaining together gadgets which $1$-absorb pairs as in the previous lemma, we
can construct gadgets which $(s-1)$-absorb sets of size $s$.

######  Lemma 5.11.

Let $p\geq n^{-1/700}$. Let $3\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

Let $S$ be a vertex-subset of size at most $100$ and let $U\subseteq G$ with
$|U|\leq p^{310}n/C_{\ref{Lemma_absorber_99_main}}$. Then, there are sets
$V^{\prime}\subseteq R_{1}\setminus U$ and $C^{\prime}\subseteq R_{2}\setminus
U$ of size $\leq 10^{4}k$ such that $V^{\prime}\cup C^{\prime}$
$(|S|-1)$-absorbs $S$ in $\mathcal{H}_{k}$.

###### Proof.

With high probability, Lemma 5.10 holds.

Let $S=\\{a_{1},\ldots,a_{\ell}\\}$ be given for some $\ell$ with
$2\leq\ell\leq 100$. For every $i\in\\{1,\ldots,\ell-1\\}$, apply Lemma 5.10
with $(a,b)=(a_{i},a_{i+1})$, each time finding a subgraph $F_{i}$ which
$1$-absorbs $\\{a_{i},a_{i+1}\\}$ disjointly with $U$. By extending $U$ in
each application to include $F_{1},\ldots,F_{i-1}$, we can also ensure the
collection of $F_{i}$ are vertex and colour disjoint (except for elements of
$S$). The union of the subgraphs $F_{i}$ ($i\in[\ell]$) now has the desired
absorption property. For an illustration of the case when $k=\ell=3$, see
Figure 2 (left). ∎

Now we show how to $1$-absorb sets of size $s\leq 100$. For small $k$,
essentially all the necessary ideas are included in the previous two lemmas,
however for large $k$ we introduce some new ideas.

Figure 2: On the left: A $2$-absorber for the for the $3$ vertices contained
in boxes (from the proof of Lemma 5.10). Dashed versions of a coloured edge
are to be interpreted as having a distinct colour. The matching which absorbs
the outer two vertices is indicated. On the right: The pattern $P_{S}$ (from
the proof of Lemma 5.12 Case $1$) consisting of $3$ copies of the pattern
$P_{x}(c_{1},c_{2})$ ($\ell=3$), and the sets $S_{2}$ and $S_{3}$ shaded with
the diagonal lines. For the vertices covered with the diagonal lines we have a
$2$-absorber for the indicated vertices. The union of these two $2$-absorbers
and the illustrated directed graph $1$-absorbs the $3$-vertices on the top row
of the diagram.

######  Lemma 5.12.

Let $p\geq n^{-1/700}$ and let $3\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

Let $S$ be a vertex-subset of size at most $100$ and let $U\subseteq G$ with
$|U|\leq p^{340}n/C_{\ref{Lemma_vertex_absorber_2to100}}$, there are sets
$V^{\prime}\subseteq R_{1}\setminus U$ and $C^{\prime}\subseteq R_{2}\setminus
U$ of size $\leq 10^{8}k^{2}$ such that $V^{\prime}\sqcup C^{\prime}$
$1$-absorbs $S$ in $\mathcal{H}_{k}$.

###### Proof.

With high probability, Lemma 3.19, Lemma 5.1 and Lemma 5.11 all hold. Denote
$S=\\{a_{1},a_{2},\ldots,a_{\ell}\\}$ where $2\leq\ell\leq 100$.

Case 1: $k\in\\{3,4\\}$. We write the details of the argument for $k=3$, for
$k=4$ a proof can be obtained by replacing $P_{a_{i}}(c_{1},c_{2})$ with
$P_{a_{i}}^{(4)}(c_{1},c_{2},c_{3})$ in the below argument444The same argument
works for each $k=O(1)$, the reason why the second case exists is the range
when $k=\Omega(\log n)$..

Consider a pattern $P_{S}$ formed by the union of patterns
$P_{a_{i}}(c_{1},c_{2})$ for each $i\in[\ell]$ (recall Remark 5.9). This
pattern is well-defined as the vertices of $P_{a_{i}}(c_{1},c_{2})$ and
$P_{a_{j}}(c_{1},c_{2})$ get different labels when $i\neq j$ (as $a_{i}\neq
a_{j}$). To see that this pattern is well-distributed we only need to check
vertices and edges belonging to different copies, as each
$P_{a_{i}}(c_{1},c_{2})$ is well-distributed by Lemma 5.8 already. There is
nothing to check with edge labels as they are all identical. Vertices in the
same position in the triangle are separable by (b) (this is as $a_{i}\neq
a_{j}$ when $i\neq j$), and vertices in different positions are separable by
(a). By Lemma 3.19, $P_{S}$ admits a copy in $\vec{K}_{G}[(R_{1}\setminus
U)\cup S;R_{2}\setminus U]$, say $P_{S}^{\prime}$. For $j\in\\{2,3\\}$, denote
by $S_{2}$ the vertices of $F_{S}^{\prime}$ coming from copies of top vertices
of $P_{a_{i}}(c_{1},c_{2})$ and denote by $S_{3}$ the vertices coming from
bottom vertices of $P_{a_{i}}(c_{1},c_{2})$ for each $i\in[\ell]$. Apply Lemma
5.11 first with $S=S_{2}$, and then $S=S_{3}$, to find sets $A_{2}$ and
$A_{3}$ $(|S|-1)$-absorbing $S_{2}$ and $S_{3}$, respectively. We can also
ensure that $A_{2}$, $A_{3}$ and $F_{S}^{\prime}$ are vertex and colour
disjoint by extending $U$ in each successive application of Lemma 5.11. Now
$F_{S}^{\prime}\cup A_{2}\cup A_{3}$ is the desired absorber. See Figure 2 for
a demonstration of this when $\ell=3$, the boxes shaded with diagonal lines
represent the sets $S_{2}$ and $S_{3}$ which we can $2$-absorb.

Case 2: $k\geq 5$. We begin by the following observation which will help to
motivate the choice of parameters for the rest of the argument. We remind the
reader that when we say $d_{1}+d_{2}-2v-a$ below, what we mean is the copy of
the vertex of $P_{a}(v,d_{1},d_{2})$ with the label $d_{1}+d_{2}-2v-a$, and
similarly for the other expressions.

######  Observation 5.13.

Consider a copy $P$ of $P_{a}(v,d_{1},d_{2})$ from Figure 1. Let $Q$ be a
rainbow path from $d_{1}+d_{2}-2v-a$ to $v+a$, colour-disjoint with $P$, and
vertex-disjoint with $P$ except on the endpoints. Let $A$ be a set that
$2$-absorbs $Y:=\\{d_{1}-v,d_{1}-v+d_{2}-a,d_{2}-v\\}$ (the column shaded by
the diagonal lines), vertex and colour disjoint with $P\cup Q$, except on $Y$.
Then, $P\cup A\cup Q\setminus\\{a,d_{1},d_{2}\\}$ $1$-absorbs the vertex-
triple $\\{a,d_{1},d_{2}\\}$.

The previous observation essentially shows that we can find sets $1$-absorbing
triples, provided that $2$ elements of the triples are free variables (it is
important that $d_{1}$ and $d_{2}$ are free variables while ensuring that
$P_{a}(v,d_{1},d_{2})$ is well distributed, and that $d_{1}+d_{2}-2v-a$ is
linear in at least one variable). The remainder of the proof is focused on
using this property many times with carefully chosen sets of triples to find
subgraphs that $1$-absorb sets of size at most $100$ constants (not free
variables). The following observation motivates the choice of triples.

######  Observation 5.14.

Consider a collection of sets $\\{a_{1},d_{\ell},d_{1}\\}$,
$\\{a_{2},d_{1},d_{2}\\}$, $\\{a_{3},d_{2},d_{3}\\}$, $\ldots$,
$\\{a_{\ell-1},d_{\ell-2},d_{\ell-1}\\}$, $\\{a_{\ell},d_{\ell-1}\\}$. Suppose
for some $a_{i}$, the set containing $a_{i}$ is deleted from the collection.
Then, there exists a choice of an element from each of the remaining sets in
the collection so that overall the chosen elements are precisely
$\\{d_{1},\ldots,d_{\ell-1}\\}$.

###### Proof.

When $i=3$, the correct choices are displayed in the below table.

$a_{1}$ | $a_{2}$ | $\mathbf{a_{3}}$ | $a_{4}\,\,\,\cdots$ | $a_{\ell-1}$ | $a_{\ell}$
---|---|---|---|---|---
$d_{\ell}$ | $d_{1}$ | $d_{2}$ | $\mathbf{d_{3}}\,\,\,\cdots$ | $\mathbf{d_{\ell-2}}$ | $\mathbf{d_{\ell-1}}$
$\mathbf{d_{1}}$ | $\mathbf{d_{2}}$ | $d_{3}$ | $d_{4}\,\,\,\cdots$ | $d_{\ell-1}$ |

For other values of $i$, one can similarly choose the value on the bottom row
for the $j$th column where $j<i$, and choose the value on the middle row for
the $j$th column where $j>i$. ∎

Consider a pattern $P$ formed by the union of patterns
$P_{a_{1}}:=P_{a_{1}}(v_{1},d_{\ell},d_{1})$,
$P_{a_{2}}:=P_{a_{2}}(v_{2},d_{1},d_{2})$,
$P_{a_{3}}:=P_{a_{3}}(v_{3},d_{2},d_{3})$, $\ldots$,
$P_{a_{\ell-1}}:=P_{a_{\ell-1}}(v_{\ell-1},d_{\ell-2},d_{\ell-1})$ (recall
Remark 5.9). Formally, $P$ is obtained by taking the (disjoint) union of each
of the graphs $P_{a_{i}}$ and identifying together vertices which share the
same label (this identification step ensures that the second property in the
definition of pattern is satisfied, so $P$ is indeed a well-defined pattern).
We remark that the vertex/edge labels live in the set $(G\ast
F_{2\ell-1})^{\mathrm{ab}}$.

######  Claim 5.14.1.

$P$ is well-distributed.

###### Proof.

Each $P_{a_{i}}(\cdot,\cdot,\cdot)$ is well-distributed by Lemma 5.8, so we
only need to check separability for pairs of vertices and pairs of colours
coming from different $P_{a_{i}}(\cdot,\cdot,\cdot)$. For pairs of such
colours, the word corresponding to a label includes $v_{i}$ as a free variable
for some $i$, and the other label does not include $v_{i}$. This makes the
pair separable by (a). Similarly, for pairs of vertices, if one of the words
has a $v_{i}$ as a free variable for some $i$, we have separability by (a). If
this is not the case the pair of words could be of the form $(d_{i},d_{j})$
for some $i$ and $j$. If $i\neq j$, we have separability by (a), and
otherwise, the words are identical and in this case we do not need to check
separability, as in the definition of the union we identify such vertices
together. The pair of words could also be of the form
$(d_{i},d_{j}+d_{j+1}-2v_{j}-a_{j})$, in which case either $d_{j}$ or
$d_{j+1}$ is different with $d_{i}$, giving separability by (a). Finally, pair
of words could also be of the form
$(d_{i}+d_{i+1}-2v_{i}-a_{i},d_{j}+d_{j+1}-2v_{j}-a_{j})$ where $i$ and $j$
are distinct, so we again have separability by (a). ∎

By Lemma 3.19, we can find a copy of $P$, say $P^{\prime}$, in
$\vec{K}_{G}[R_{1}\setminus U;R_{2}\setminus U]$. In addition, by Lemma 5.10
applied with $\\{a,b\\}=\\{a_{\ell},d_{\ell-1}\\}$, we obtain a subgraph $A$
which $1$-absorbs $\\{a_{\ell},d_{\ell-1}\\}$. By extending $U$ in this
application, we can ensure $A$ is disjoint with $P^{\prime}$.

Recall that $k-3\geq 2$ by assumption. For each $i\in[\ell-1]$, apply Lemma
5.1 with $u$ set to be the copy of the rightmost vertex in $P_{a_{i}}$ and $v$
set to be the copy of the leftmost vertex in $P_{a_{i}}$ to find a rainbow
path of length $k-3$ directed from $u$ to $v$ that does not clash with any of
the forbidden colours or vertices (see the dashed line in Figure 1). We can
achieve this by iteratively invoking Lemma 5.1, extending $U$ at each step.
Note that $k\leq\log^{10}n$, so we never add more than $200\log^{10}n$
elements to $U$ during this process. Again, for each $i\in[\ell-1]$, apply
Lemma 5.11 with $S$ set the be the subset corresponding to the copies of the
$3$ vertices of $P_{a_{i}}$ which correspond to the column indicated with the
dots to obtain a subgraph $A_{a_{i}}$ which $2$-absorbs this subset. We can
ensure that the collection of $A_{a_{i}}$ are pairwise disjoint (except for
the vertices corresponding to highlighted vertices plugged into $S$), and also
disjoint with $U$, again by extending $U$ in each application of Lemma 5.11.
By the bound coming from Lemma 5.11, we never have to extend $U$ by more than
$10^{6}k^{2}\ell$ elements during this process.

For each $i\in[\ell-1]$, let $P^{\prime}_{a_{i}}$ be the copy of $P_{a_{i}}$
combined with the path found by applying Lemma 5.1 and $A_{a_{i}}$, and let
$Z_{a_{i}}$ be the set of vertices corresponding to the copies of the vertices
of $P_{a_{i}}$ (the column indicated by dots). The following is a rephrasing
of Observation 5.13.

######  Observation 5.15.

We have that $P^{\prime}_{a_{i}}\setminus Z_{a_{i}}$ $1$-absorbs $Z_{a_{i}}$.

Now, we claim that $(\bigcup P^{\prime}_{a_{i}}\setminus S)\cup A$ is the
desired absorber. To see this, let $a_{i}\in S$. We wish to show that the
vertices and colours of $(\bigcup P^{\prime}_{a_{i}}\setminus S)\cup
A\cup\\{a_{i}\\}$ induce a perfect matching in $\mathcal{H}$. To see this,
first take a perfect matching in $(P_{a_{i}}^{\prime}\setminus
Z_{a_{i}})\cup\\{a_{i}\\}$ (which exists by definition of $1$-absorbing and
Observation 5.15).

Now, from each set $Z_{a_{j}}$ (for $i\neq j$) and $\\{a_{\ell},d_{\ell-1}\\}$
(coming from the $1$-absorbing $A$), we can select exactly one
$d_{j^{\prime}}$ so that each $d_{j^{\prime}}$ (for each
$j^{\prime}\in[\ell-1]$) is selected precisely once, using Observation 5.14.
Using either Observation 5.15 or the $1$-absorbing property of $A$, we can
find a perfect matching of $(\bigcup P^{\prime}_{a_{i}}\setminus S)\cup
A\cup\\{a_{i}\\}$ as required. ∎

####  5.2.2 Colour-switchers

######  Lemma 5.16.

Let $p\geq n^{-1/700}$. Let $5\leq k\leq\log^{10}n$. Let $R_{1},R_{2}$ be
$p$-random subsets of $G$ sampled independently. With high probability, the
following holds.

Let $\alpha\in G$, and $s\in\mathbb{N}$ with $2\leq s\leq\min\\{k-2,100\\}$.
Let $S$ be a disjoint and near-dissociable family of rainbow $s$-tuples of
colours, each tuple sums to $\alpha$, and each tuple is a path-candidate, and
suppose $|S|\leq 100$. Let $U\subseteq G$ with $|U|\leq
p^{400}n/C_{\ref{Lemma_colour_absorber}}$. Then, there are sets
$V^{\prime}\subseteq R_{1}\setminus U$ and $C^{\prime}\subseteq R_{2}\setminus
U$ of size $\leq 10^{11}k^{2}$ such that $V^{\prime}\cup C^{\prime}$
$1$-absorbs $S$ in $\mathcal{H}_{k}$.

###### Proof.

With high probability, Lemma 3.19, Lemma 5.11 and Lemma 5.1 hold. Let $S$ and
$U$ be given as in the statement. Consider a pattern $P$ constructed as
follows. Take $|S|$ directed paths, each of length $s$, with the same start
and end vertices, but internally vertex-disjoint. Label the start vertex with
the free variable $v$. Label the edges of the $i$th directed path with the
$i$th $s$-tuple of $S$ (counting in order of proximity to $v$). Note this
induces a labelling on each of the remaining vertices of $P$. This labelling
is well-defined on the end-vertex, because each tuple in $S$ has the same sum,
namely, $\alpha$. In particular, the end-vertex receives the label $v-\alpha$.
For an illustration of the pattern when $s=3$ and
$S=\\{(e_{1},e_{2},e_{3}),(d_{1},d_{2},d_{3}),(c_{1},c_{2},c_{3})\\}$, inspect
the bottom-right pattern in Figure 1.

######  Observation 5.17.

$P$ is well-distributed.

###### Proof.

Each pair of colours is separable by (b) as distinct coordinates of elements
of $S$ are distinct, and the elements of $S$ are pairwise disjoint. We claim
each pair of vertices is separable by (b). For vertices belonging to the same
directed path, this follows as elements of $S$ are path-candidates. For
vertices belonging to different directed paths, this follows as $S$ is near-
dissociable. ∎

Thus, we may apply Lemma 3.19 to find a copy of $P$, say $P^{\prime}$, in
$\vec{K}_{G}[R_{1}\setminus U;(R_{2}\setminus U)\cup\bigcup S]$. For each
$i\in[s-1]$, let $P_{i}$ denote the vertices of distance $i$ from $v$, noting
$|P_{i}|=|S|\leq 100$. Apply Lemma 5.11 for each $P_{i}$ to find (disjointly)
sets $P_{i}^{\prime}$ which $|S|-1$ absorb $P_{i}$. Finally, noting that
$k-s\geq 2$, apply Lemma 5.1 with $u$ as the end-vertex of the path of length
$s$ from $v$, and $v=v$, and $k^{\prime}=k-s$, to find a rainbow path of
length $k-s$. It is easy so see that the resulting structure has the desired
absorption property. ∎

####  5.2.3 Putting the gadgets together

So far we have lemmas allowing us to find sets $1$-absorbing arbitrary sets of
size $\leq 100$. How can we go from to sets which can $h$ absorb sets of size
$(1+\beta)h$, where $h$ and $\beta h$ are potentially linear in $n$? The
bipartite graph given in the next lemma gives us a nice collection of subsets
of size at most $100$ to $1$-absorb, which together have the desired property.