Proof of Theorem 2.3

Pick a value of $\varepsilon _{2.3}$ such that $0<\varepsilon _{2.3}\ll \varepsilon _{2.4},\varepsilon _{2.5}, 1/K_{2.4}$ . 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/1000)\varepsilon _{2.5}p^4/k^{100}$ (and $p_2=p-p_1$ ). We have that $p_1\geq n^{-\varepsilon _{2.4}}$ and $p_2\geq n^{\varepsilon _{2.5}}$ if $\varepsilon _{2.3}$ 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_{2.4}} n$ (there exist such values of m as $\varepsilon _{2.4}K_{2.4}\leq 10^{-10}$ ). With high probability, Lemma 2.4 holds with $(R_1^{(1)},R_2^{(1)},p_1,m)$ in place of $(R_1,R_2,p,m)$ and Lemma 2.5 holds with $(R_1^{(2)},R_2^{(2)},p_2)$ in place of $(R_1,R_2,p)$ . 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 3p_1n$ (as this bounds from above even the sizes of $R_1^{(1)}$ and $R_2^{(1)}$ ) and also note that $3p_1n\leq \varepsilon _{2.5}p_2^4n/k^{100}$ (using the definition of $p_1$ and that $p_2\geq p/2$ ). Note also that $||V_D|-|C_D||\leq 10n^{3/4}$ so $V_D$ and $C_D$ are nearly equal sizedFootnote ¹ . By an application of Lemma 2.5, we may deduce that $\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 $2n^{1-1/10^8}$ verticesFootnote ² . Unmatch some edges of $M_1$ so that the number of leftover vertices $V':=V\setminus V(M_1)$ and colours $C':=C\setminus V(M_1)$ are both equal to m (this is possible as k divides $|V|,|C|$ , m and $|V_A|=|C_A|$ , and m is at least twice as large at the number of leftover vertices). Note that the matching $M_1$ guarantees that all colours in $C\setminus C'$ 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'=0$ also. As $\sum C=0$ by assumption, this implies that $\sum C'=0$ , so we can invoke the property coming from Lemma 2.4. This means that $V'$ and $C'$ combine with $V_A$ and $C_A$ to produce a matching, $M_2$ . $M_1\cup M_2$ is then the desired perfect matching.

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'\circ p$ where $p\colon (G\ast F_k)\to (G\ast F_k)^{\mathrm {ab}}$ is the quotient map, and $h'\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.

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 '$ that agrees with $\pi $ and additionally has $\pi '(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 '(w)=g$ is equivalent to $\pi '(w)=\pi '(g)$ (as $\pi '$ is a projection) which is equivalent to $\pi '(v_k)=\pi '(h)$ (as $\pi $ is a homomorphism). As $\pi '$ agrees with $\pi $ and $h\in (G\ast F_{k-1})^{\mathrm {ab}}$ , we have that $\pi '(v_k)=\pi (h)\in G$ . Therefore, $\pi '$ has that $\pi '(v_k)=\pi (h)$ , and $\pi '(v_i)=\pi (v_i)$ for $1\leq i<k$ . By Lemma 3.7, there is a unique projection with this property.

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

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

2. (b) We can rearrange $\pi (w)=\pi (w')$ 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')$ in this case.

3. (c) Similarly to the previous cases, we can rearrange $\pi (w)=\pi (w')$ 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/2}$ images, and suppose $\pi $ also satisfies $\pi (v_j)=g'$ for some $g'\in G$ , so we have $3\pi (v_i)=g"\in G$ (where $g"=g+2g'$ ). As $x\to 3x$ is a homomorphism (G is abelian) and has at least $n^{1/2}$ images, the preimage of $g"$ under the map $x\to 3x$ has size at most $n^{1/2}$ (each nonempty preimage must have the same size in a group homomorphism). This means $\pi (v_i)$ must live in a set $T_{g'}$ of size at most $n^{1/2}$ assuming that $\pi (w)=\pi (w')$ and $\pi (v_j)=g'$ . Thus, if $\pi (w)=\pi (w')$ , $\pi $ must agree with one of $n^{k-1}n^{1/2}$ functions $f\colon \{v_1,\ldots , v_k\}\to G$ , meaning that there are at most $n^{k-1/2}$ such projections, using Lemma 3.7. A symmetric argument works when $x\to 2x$ has at least $n^{1/2}$ images.

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

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 $|S|(|S|t)n^{k-1}=10^4tn^{k-1}$ good projections. On the other hand, there are at most $|S|^2n^{k-1/2}\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 10^4tn^{k-1}$ , meaning $t\geq n/(2\cdot 10^4)$ , as desired.

Proof. Note that there are at most $20\cdot 40^{20}\cdot n$ words of length at most $20$ in $(G*F_k)^{\mathrm {ab}}$ for some $k\leq 20$ , and thus at most $40^{2100}n^{100}$ distinct choices for S. Fix some choice of S. We will show that the statement holds for S with probability $\geq 1-e^{\Omega (\sqrt {n})}$ , so the desired statement holds for all S simultaneously by a union bound.

Let $\pi _1,\ldots , \pi _{n/10^5}$ be the projections separating S with disjoint images as guaranteed by Lemma 3.13. For any of these projections, that $\pi (S_1)\subseteq R_1$ and $\pi (S_2)\subseteq R_2$ is an event with probability at least $p^{100}$ , so the expected number $\pi $ satisfying this property is $p^{100}n/10^5$ , and further these events are mutually independent over the various $\pi $ as they are determined by whether disjoint sets of vertices are sampled into $R_1$ (or $R_2$ ). Hence, that at least $p^{100}n/10^6$ of the $\pi $ satisfy this property happens with probability at least $\geq 1-e^{\Omega (\sqrt {n})}$ by Chernoff’s bound (using that $p\geq n^{-1/700}$ ).

Once this property is satisfied, any $U\subseteq G$ can meet at most $|U|$ distinct images of $\pi $ (as the $\pi $ are disjoint), so for any $|U|$ of size at most $p^{100}n/10^{7}$ , we may find a $\pi $ of the desired form, disjointly with U.

Observation 3.18. Let S be a copy of P. Then, there is an 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.

Proof. With high probability, $R_1$ and $R_2$ satisfy the conclusion of Lemma 3.14. Fix such $R_1$ and $R_2$ .

Let P be a well-distributed pattern with $|V(P)|+|E(P)|\leq 100$ so we have that $\phi [V(P)]\sqcup \phi [C(P)]:=S$ ( $\sqcup $ indicates a disjoint union) has size at most $100$ . We may safely ignore the words that are constants in $\phi [V(P)]$ or $\phi [C(P)]$ as then their presence in the target vertex/colour of $\vec {K}_G[(R_1\setminus U)\cup V';(R_2\setminus U)\cup C']$ is guaranteed. Hence, we may assume all words are linear in at least one free variable by the definition of well-distributed. We then apply the property from Lemma 3.14 (its hypotheses are satisfied by linearity in at least one variable and item 3. of well-distributed) with $S_1=\phi [V(P)]$ and $S_2=\phi [C(P)]$ and $S=\phi [V(P)]\sqcup \phi [C(P)]$ . This allows us to deduce that there exists a projection $\pi $ of S mapping vertices to $R_1\setminus U$ and $R_2\setminus U$ separating $S_1$ and $S_2$ . The image of this projection naturally corresponds to a copy by picking a subgraph keeping exactly the directed edges that were present in the pattern P (in order to ensure item 3. of a copy).

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'$ with $\sum S' = 0$ , $|S'|=|X|/4$ , and such that $S'$ has small symmetric difference with S. This implies that $\sum (-S'-\alpha )= -(|X|/4)\cdot \alpha $ , and also we have that $-S'-\alpha $ has small symmetric difference with $-S-\alpha $ . Thus we have that $\sum X_1 +\sum X_2 + \sum S'=0$ and $\sum X_3 +\sum X_4 + \sum (-S'-\alpha )=0$ . Also, we remark that $S'$ can be chosen so that both $S'$ and $-S'-\alpha $ do not contain $0$ . So we can apply Theorem 3.20 twice to deduce that both $H_G[X_1,X_2,S']$ and $H_G[X_3,X_4,-S'-\alpha ]$ has a perfect matching. For each $s'\in S'$ , consider the edges $(x_1,x_2,s')$ and $(x_4,x_4,-s'-\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.

Proof. Choose some $\varepsilon _{3.25}\leq 10^{-1000}$ . With high probability, Lemma 3.21 and Corollary 3.23 both hold for R. Let $R'$ be given. For part (1), we apply Lemma 3.21 to partition $R'$ 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.

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^2nn^{k-3}\leq k^2n^{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.

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}$ .

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$ .

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']} F(i)=\pm (q+m\cdot f)$ when $j'=2$ (by the property from Claim 3.27.3). When $j'=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']}\mathcal {F}_{new}(i)$ where $j,j'\in [3]$ . It is impossible that $j'=1$ due to Claim 3.27.5 and it is impossible that $j'=2$ because of 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.

Proof. Fix a large constant $C\geq 10^7$ and fix $C_{5.1}\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^3n/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^3n/10$ such paths for any choice of u and v with high probability. Call this property $(\ast )$ . Also, Lemma 3.19 holds with high probability.