# Integer colorings with forbidden rainbow sums

Yangyang Cheng Yifan Jing Lina Li Guanghui Wang Wenling Zhou School of
Mathematics, Shandong University, Jinan, China, Email:
<EMAIL_ADDRESS>of Mathematics, University of Illinois at
Urbana-Champaign, Urbana, IL, USA. Email<EMAIL_ADDRESS>of
Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL, USA.
Email<EMAIL_ADDRESS>of Mathematics, Shandong University, Jinan,
China, Email<EMAIL_ADDRESS>of Mathematics, Shandong University,
Jinan, China, Email<EMAIL_ADDRESS>
###### Abstract

For a set of positive integers $A\subseteq[n]$, an $r$-coloring of $A$ is
rainbow sum-free if it contains no rainbow Schur triple. In this paper we
initiate the study of the rainbow Erdős-Rothchild problem in the context of
sum-free sets, which asks for the subsets of $[n]$ with the maximum number of
rainbow sum-free $r$-colorings. We show that for $r=3$, the interval $[n]$ is
optimal, while for $r\geq 8$, the set $[\lfloor n/2\rfloor,n]$ is optimal. We
also prove a stability theorem for $r\geq 4$. The proofs rely on the
hypergraph container method, and some ad-hoc stability analysis.

Keywords: rainbow sum-free; $r$-coloring; container method

##  1 Introduction

An interesting direction of combinatorics in recent years is the study of
multicolored version of classical extremal results, whose origin can be traced
back to a question of Erdős and Rothschild [11] in 1974. They asked which
$n$-vertex graph admits the maximum number of $2$-edge-colorings without
monochromatic triangles, and conjectured that the complete balanced bipartite
graph is the optimal graph. About twenty years later, Yuster [34] confirmed
this conjecture for sufficiently large $n$.

###  1.1 Erdős-Rothschild problems in various settings

There are many natural generalizations of the Erdős-Rothschild problem. The
most obvious one may be to ask it for graphs other than the triangles, and one
may also increase the number of colors used. A graph G on $n$ vertices is
called $(r,F)$-extremal if it admits the maximum number of $r$-edge-colorings
without any monochromatic copies of $F$ among all $n$-vertex graphs. Alon,
Balogh, Keevash and Sudakov [1] greatly extended Yuster’s result and showed
that the Turán graph $T_{k}(n)$ is the unique $(r,K_{k+1})$-extremal graph for
$k\geq 2$ and $r\in\\{2,3\\}$. Interestingly, they also showed that Turán
graphs $T_{k}(n)$ are no longer optimal for $r\geq 4$. Indeed, Pikhurko, and
Yilma [30] later proved that $T_{4}(n)$ is the unique $(4,K_{3})$-extremal
graph, while $T_{9}(n)$ is the unique $(4,K_{4})$-extremal graph. Determining
the extremal configurations in general for $k\geq 2$ and $r\geq 4$ turned out
to be a difficult problem. For further results along this line of research
(when $F$ is a non-complete graph or a hypergraph), we refer to [16, 18, 19,
26, 27, 28].

Another variant of this problem is to study edge-colorings of a graph avoiding
a copy of $F$ with a prescribed color pattern. For an $r$-colored graph
$\hat{F}$, a graph $G$ on $n$ vertices is called $(r,\hat{F})$-extremal if it
admits the maximum number of $r$-colorings which contain no subgraph whose
color pattern is isomorphic to $\hat{F}$. This line of work was initiated by
Balogh [2], who showed that the Turán graph $T_{k}(n)$ once again yields the
maximum number of 2-colorings avoiding $H_{k+1}$, where $H_{k+1}$ is any
2-coloring of $K_{k+1}$ that uses both colors. For $r\geq 3$, the behavior of
$(r,H_{k+1})$-extremal graphs was studied by Benevides, Hoppen, Sampaio,
Lefmann, and Odermann, see [6, 20, 21, 23, 24]. In particular, the case when
$\hat{F}=\hat{K}_{3}$ is a triangle with rainbow pattern has recently received
a lot of attention (for its relation to Gallai colorings). Hoppen, Lefmann and
Odermann [23] first proved that the Turán graph $T_{2}(n)$ is the unique
$(r,\hat{K}_{3})$-extremal graph for $r\geq 5$. Very recently, Balogh and Li
[3], confirming conjectures of [6] and [23], showed that the complete graph
$K_{n}$ is the unique $(3,\hat{K}_{3})$-extremal graph, while the Turán graph
$T_{2}(n)$ becomes optimal as $r\geq 4$.

The Erdős-Rothschild problem can also be extended to other discrete
structures. In the domain of extremal set theory, Hoppen, Kohayakawa and
Lefmann [17] solved the Erdős-Rothschild extension of the famous Erdős-Ko-Rado
Theorem. They, for instance, showed that the optimal $\ell$-intersecting
families (each set is of size $k$) yields the maximum number of $r$-colorings
in which every color class is $\ell$-intersecting for $r\in\\{2,3\\}$, and
also provided a fairly complete characterization of the corresponding extremal
family for $r\geq 4$. Hoppen, Lefmann and Odermann [22], and Clemens, Das and
Tran [7] later studied the Erdős-Rothschild extension of the Erdős-Ko-Rado
Theorem for vector spaces. Moving the problem to the context of power set
lattice, recently, Das, Glebov, Sudakov and Tran [9] investigated the the
Erdős-Rothschild extension of the Sperner’s Theorem, and proved that the
largest antichain yields the maximum number of $r$-colorings, in which each
color class is an antichain, for $r\in\\{2,3\\}$. As for many of the previous
results, they demonstrated that as $r$ grows, the largest antichain is no
longer optimal. They also determined that the extremal configurations for
2-colorings without monochromatic $k$-chains are the largest $k$-chain-free
family. The extremal configurations for $r\geq 3$ and $k\geq 2$ are widely
unknown.

###  1.2 Erdős-Rothschild problems for sum-free sets

Given integers $n\geq m\geq 1$, write $[m,n]:=\\{m,\ldots,n\\}$ and
$[n]:=\\{1,...,n\\}$.

######  Definition 1.1 (Schur triple & Sum-free set).

A Schur triple or a sum in an abelian group $G$ (or in $[n]$) is a triple
$\\{a,b,c\\}$ with $a+b=c$. A set $A\subseteq G$ (or $A\subseteq[n]$) is sum-
free if $A$ contains no such triple.

Given a set A of numbers, an r-coloring of $A$ is a mapping
$f:A\rightarrow[r]$, which assigns one color to each element of $A$. An
$r$-coloring of A is called a sum-free $r$-coloring if each of the color
classes is a sum-free set. Sum-free colorings are among the classical objects
studied in extremal combinatorics and can be traced back to Schur’s theorem,
one of the seminal results in Ramsey theory.

The Erdős-Rothschild extension for sum-free sets has been pursued by Liu,
Sharifzadeh and Staden [29] for subsets of the integers, and Hàn and Jiménez
[15] for finite abelian groups. More specifically, they investigated the
extremal configurations which maximize the number of sum-free $r$-colorings.
In the setting of integers, it is well known that the largest sum-free set in
$[n]$ has size $\lceil n/2\rceil$. Liu, Sharifzadeh and Staden [29] determined
the extremal configurations for $r=2$.

######  Theorem 1.2.

[29] There exists $n_{0}>0$ such that for all integers $n\geq n_{0}$ , the
number of sum-free $2$-colorings of a subset $A\subseteq[n]$ is at most
$2^{\lceil n/2\rceil}$. Moreover, the extremal subsets are
$\\{1,3,5,\cdots,2\lceil n/2\rceil-1\\}$, and $[\lfloor n/2\rfloor+1,n]$; and
if $n$ is even, we additionally have $[n/2,n-1]$, and $[n/2,n]$.

Unlike the graph case, in the sum-free setting, there are extremal
configurations which are not sum-free even for 2 colors. Therefore, one would
expect a more sophisticated extremal behavior as $r$ grows. Although some
asymptotic bounds were obtained in [29], the characterization of extremal sets
for $r\geq 3$ remains widely open.

Such problem was also studied for finite abelian groups. Let $G$ denote a
finite abelian group. Over fifty years ago, Diananda and Yap [10] determined
the maximum density $\mu(G)$ of a sum-free set in $G$ whenever $|G|$ has a
prime factor $q\not\equiv 1\mod 3$, but it was not until 2005 that Green and
Ruzsa [14] completely solved this extremal question for all finite abelian
group. Hàn and Jiménez [15] investigated the Erdős-Rothschild extension for
sum-free sets on some special abelian groups.

######  Theorem 1.3.

[15] Let $r\in\\{2,3\\}$, $q\in N$ and let $G$ be a abelian group of
sufficiently large order, which has a prime divisor $q$ such that $q\equiv
2\mod 3$. Then the number of sum-free $r$-coloring of a set $A\subseteq G$ is
at most $r^{\mu(G)}$. Moreover, the maximum is only achieved by the largest
sum-free set.

For more than three colors this phenomenon does not persist in general and the
problem becomes considerably more complicated. For more details, we refer the
readers to [15]. For other abelian groups, despite some asymptotic bounds
presented in [15], the exact extremal phenomena is unknown even for 2 colors.

###  1.3 Our results

In this paper, we consider a rainbow variant of the Erdős-Rothschild problem
for sum-free sets in $[n]$. A Schur triple or a sum $\\{x,y,z\\}$ is a rainbow
sum if $x,y,z$ are colored with different colors. Note that a rainbow sum must
have three distinct elements. For convenience, sometimes we would use the
following definitions, which are slightly different with the classical
notations on sum-free sets.

######  Definition 1.4 (Restricted Schur triple & Restricted sum-free set).

A restricted Schur triple or a restricted sum in $[n]$ is an ordered triple
$(a,b,c)$ with $a<b<c$ and $a+b=c$. A set $A\subseteq[n]$ is restricted sum-
free if $A$ contains no such triple.

For any integer $n\geq 7$, it is not hard to show that the largest restricted
sum-free sets in $[n]$ have size $\lfloor n/2\rfloor+1$. If $n$ is even, then
the only subset attaining this bound is $\left[\frac{n}{2},n\right]$; if $n$
is odd, then the maximum restricted sum-free sets are attained by the
following four sets:
$\left\\{\frac{n-1}{2},\frac{n-1}{2}+1,\ldots,n-1\right\\}$,
$\left\\{\frac{n-1}{2},\frac{n-1}{2}+2,\ldots,n\right\\}$,
$\left[\frac{n+1}{2},n\right]$, and $\\{1,3,5,\ldots,n\\}$.

Given a set of positive integers $A\subseteq[n]$, an $r$-coloring of $A$ is
rainbow sum-free if it contains no rainbow sum. For a positive integer $r$ and
a set $A\subseteq[n]$, we write $g(A,r)$ for the number of rainbow sum-free
$r$-colorings of $A$ and define

$g(n,r):=\max_{A\subseteq[n]}g(A,r).$

A set $A\subseteq[n]$ is rainbow $r$-extremal if $g(A,r)=g(n,r)$. When
$r\in\\{1,2\\}$, it is trivial to see that $g(n,r)=r^{n}$ for all positive
integers $n$, and the only extremal set is the interval $[n]$, since for every
subset $A\subseteq[n]$, all $r$-colorings of $A$ are rainbow sum-free. For
$r\geq 3$, the characterization of the extremal sets requires substantially
more work.

Our first main result is an upper bound on the number of rainbow sum-free
$r$-colorings of dense sets.

######  Theorem 1.5.

For every integer $r\geq 3$, there exists $n_{0}$ such that for all $n>n_{0}$
the following holds. For a set $A\subseteq[n]$ with $|A|\geq(1-{r}^{-3})n$,
the number of rainbow sum-free $r$-colorings $g(A,r)$ satisfies

$g(A,r)\leq\binom{r}{2}\cdot 2^{|A|}+2^{-\frac{n}{26\log n}}2^{n}.$

By choosing two of the $r$ colors and coloring the elements of $[n]$
arbitrarily with these two colors, one can easily obtain that

$g([n],r)\geq\binom{r}{2}(2^{n}-2)+r=\binom{r}{2}2^{n}-(r^{2}-2r).$ (1)

Therefore, Theorem 1.5 is asymptotically sharp for $A=[n]$ and then the
typical structure of rainbow sum-free $r$-colorings of $[n]$ immediately
follows from (1).

######  Corollary 1.6.

For every integer $r\geq 3$, almost all rainbow sum-free $r$-colorings of
$[n]$ are 2-colorings.

Now we turn to the extremal configurations of rainbow sum-free $r$-colorings.
Let us first consider the case $r=3$. Similarly as in the Gallai coloring
problem, two natural candidates of the extremal sets are the maximum
restricted sum-free sets and the interval $[n]$. Note that for every restrict
sum-free set $A$, we have $g(A,3)\leq 3^{\lfloor n/2\rfloor+1}\ll g([n],3)$.
Our second theorem shows that for three colors the interval $[n]$ is indeed
optimal.

######  Theorem 1.7.

There exists $n_{0}$ such that for all $n>n_{0}$, among all subsets of $[n]$,
the interval $[n]$ is the unique rainbow 3-extremal set.

Just as for the Erdős-Rothschild extension for Gallai colorings [3], we may
not expect that the same phenomena persists for $r\geq 4$. Define
$O:=\\{1,3,5,\cdots,2\lceil n/2\rceil-1\\}$, and $I_{0}:=[\lfloor
n/2\rfloor+1,n]$. We prove the following stability theorem.

######  Theorem 1.8.

For every positive integer $r\geq 4$, we have

$g(n,r)=r^{n/2+o(n)}.$

Moreover, for every $\varepsilon>0$, there exist $\delta,n_{0}>0$ such that
for all integers $n\geq n_{0}$ the following holds. Let $A$ be a subset of
$[n]$ with $g(A,r)\geq r^{n/2-\delta n}.$ Then

  1. (i)

for $r\geq 5$, we have that either $|A\bigtriangleup O|\leq\varepsilon n$, or
$|A\bigtriangleup I_{0}|\leq\varepsilon n$;

  2. (ii)

for $r=4$, we have that either $|A\bigtriangleup[n]|\leq\varepsilon n$, or
$|A\bigtriangleup O|\leq\varepsilon n$, or $|A\bigtriangleup
I_{0}|\leq\varepsilon n$.

The behavior of the exact extremal configurations not only depends on the
number of colors, but also depend on the parity of $n$. For even $n$, we
define

$I_{1}=\left[\frac{n}{2}-1,n\right],\qquad I_{2}=\left[\frac{n}{2},n\right].$

Observe that $I_{1}$ contains exactly two restricted Schur triples
$(n/2-1,n/2,n-1)$, $(n/2-1,n/2+1,n)$, and it is not hard to compute that
$g(I_{1},r)=r^{n/2}\left(3-2/r\right)^{2}$. On the other hand, the set $I_{2}$
is a restricted sum-free set and therefore $g(I_{2},r)=r^{|I_{1}|}=r^{n/2+1}$.
For odd $n$, we define

$I_{3}=\left[\frac{n-1}{2},n\right].$

Again, the set $I_{3}$ contains exactly one restricted Schur triple
$(\frac{n-1}{2},\frac{n-1}{2}+1,n)$, and one can show that
$g(I_{3},r)=r^{\lceil n/2\rceil}\left(3-2/r\right)$, which is already greater
than the number of colorings for any restricted sum-free set. When a set $A$
is of size at least the size of the maximum restricted sum-free sets and not
one of the above three sets, we believe that the restrictions from the triples
would more than counteract the extra possibilities offered by the additional
vertices. Therefore, we make the following conjecture.

######  Conjecture 1.9.

Let $n,r$ be positive integers and $r\geq 4$.

  1. (i)

If $n$ is even and $r\leq 7$, then $g(n,r)=r^{n/2}\left(3-2/r\right)^{2}$, and
$I_{1}$ is the unique rainbow $r$-extremal set.

  2. (ii)

If $n$ is even and $r\geq 8$, then $g(n,r)=r^{n/2+1}$, and $I_{2}$ is the
unique rainbow $r$-extremal set.

  3. (iii)

If $n$ is odd and $r=4$, then $g(n,r)=g([n],r)$, and $[n]$ is the unique
rainbow $r$-extremal set.

  4. (iv)

If $n$ is odd and $r\geq 5$, then $g(n,r)=r^{\lceil
n/2\rceil}\left(3-2/r\right)$, and $I_{3}$ is the unique rainbow $r$-extremal
set.

Our forth main result verifies Conjecture 1.9 for $r\geq 8$ and $n$
sufficiently large.

######  Theorem 1.10.

For an integer $r\geq 8$, there exists $n_{0}=n_{0}(r)$ such that for all
$n>n_{0}$ the following holds. Let $A$ be a subset of $[n]$ with
$|A|\geq\lceil n/2\rceil+1$.

  1. (i)

If $n$ is even, then $g(A,r)\leq r^{\lceil n/2\rceil+1}$, and the equality
holds if and only if $A=I_{2}$.

  2. (ii)

If $n$ is odd, then $g(A,r)\leq r^{\lceil n/2\rceil}\left(3-2/r\right)$, and
the equality holds if and only if $A=I_{3}$.

The paper is organized as follows. In the next section, we list some
structural results on sum-free sets, which are essential for the proof, and
introduce the multi-color container theorem. In Section 3, we prove Theorem
1.5. In Section 4, we prove the stability theorem, Theorem 1.8, and determine
$g(n,3)$ for $n$ sufficiently large. In Section 5, we determine $g(n,r)$ for
$r\geq 8$, and describe the corresponding extremal configurations. We close
the paper with some concluding remarks in Section 6. Throughout the paper, all
logarithms have base 2.

##  2 Notation and preliminaries

###  2.1 Basic properties of restricted sum-free sets

We use the following result of Staden [32] on the minimum number of additive
triples among all sets of a given size.

######  Theorem 2.1.

[32] Let $A$ be a subset of $[n]$ with $|A|>\lceil n/2\rceil$. Then the number
of Schur triples in $A$ is at least

$(|A|-\lceil n/2\rceil)(|A|-\lfloor n/2\rfloor),$

where the unique minimising set is $[n-|A|+1,n]$.

For a set $A\subseteq[n]$, we write $\mathcal{S}(A)$ for the set of all
restricted Schur triples in $A$, and let $s(A)=|\mathcal{S}(A)|$. For an
integer $t\in A$, denote by $\mathcal{S}(t,A)$ the set of all triples in
$\mathcal{S}(A)$ containing $t$, and let $s(t,A)=|\mathcal{S}(t,A)|$. Then
from Theorem 2.1, we immediately obtain the following proposition.

######  Proposition 2.2.

Let $A$ be a subset of $[n]$ with $|A|>\lceil n/2\rceil$. Then

$s(A)\geq(|A|-\lceil n/2\rceil)(|A|-\lfloor n/2\rfloor)-|A|/2.$

In particular, we have

$s([n])=\begin{cases}\frac{n^{2}-2n}{4}&\text{if }n\text{ is even};\\\
\frac{n^{2}-2n+1}{4}&\text{otherwise}.\end{cases}$

###  2.2 Structural properties of sum-free sets

We will use standard definitions and notation in additive combinatorics as
given in [33]. Given $A,B\subseteq\mathbb{Z}$, let

$A+B:=\\{a+b\mid a\in A,b\in B\\},\quad\text{ and }\quad A-B:=\\{a-b\mid a\in
A,b\in B\\}.$

When $B=\\{x\\}$, we simply write $A+x$ and $A-x$.

The following lemma is known as Green’s removal lemma, which was first proved
by Green [13], and was later generalized to non-abelian groups by Král and
Vena [8].

######  Lemma 2.3.

[8, 13] For all $\varepsilon>0$, there exists $\delta,n_{0}>0$ such that the
following holds for all integers $n\geq n_{0}$. Suppose that $A\subseteq[n]$
is a set containing at most $\delta n^{2}$ Schur triples. Then there exist
$B,C\subseteq[n]$ such that $A=B\cup C$ where $B$ is sum-free and
$|C|\leq\varepsilon n$.

We also require a very strong stability theorem for sum-free sets proved by
Deshouillers, Freiman, and Odermann [25].

######  Lemma 2.4.

[25] Every sum-free set $S$ in $[n]$ satisfies at least one of the following
conditions:

  1. (i)

$|S|\leq 2n/5$;

  2. (ii)

$S$ consists of odd numbers;

  3. (iii)

$|S|\leq\min(S)$.

###  2.3 Multi-color container theorem

An important tool in our proof is the hypergraph container theorem. We use the
following version from [4]. Let $\mathcal{H}$ be a $k$-uniform hypergraph with
average degree d. The co-degree of a set of vertices $X\subseteq
V(\mathcal{H})$ is the number of edges containing $X$; that is,

$d(X)=\\{e\in E(\mathcal{H})\ |\ X\subseteq e\\}.$

For every integer $2\leq j\leq k$, the $j$-th maximum co-degree of
$\mathcal{H}$ is

$\Delta_{j}(\mathcal{H})=\max\\{d(X)\ |\ X\subseteq V(\mathcal{H}),\
|X|=j\\}.$

When the underlying hypergraph is clear, we simply write it as $\Delta_{j}$.
For $0<\tau<1$, the co-degree function $\Delta(\mathcal{H},\tau)$ is defined
as

$\Delta(\mathcal{H},\tau)=2^{\binom{k}{2}-1}\sum_{j=2}^{k}2^{-\binom{j-1}{2}}\frac{\Delta_{j}}{d\tau^{j-1}}.$

In particular, when $k=3$,

$\Delta(\mathcal{H},\tau)=\frac{4\Delta_{2}}{d\tau}+\frac{2\Delta_{3}}{d\tau^{2}}.$

######  Theorem 2.5.

[4] Let $\mathcal{H}$ be a $k$-uniform hypergraph on vertex set $[N]$. Let
$0<\varepsilon,\tau<1/2$. Suppose that $\tau<1/(200k!^{2}k)$ and
$\Delta(\mathcal{H},\tau)\leq\varepsilon/(12k!)$. Then there exists
$c=c(k)\leq 1000k!^{3}k$ and a collection of vertex subsets $\mathcal{C}$ such
that

  1. (i)

every independent set in $\mathcal{H}$ is a subset of some of
$A\in\mathcal{C}$;

  2. (ii)

for every $A\in\mathcal{C}$, $e(\mathcal{H}[A])\leq\varepsilon\cdot
e(\mathcal{H})$;

  3. (iii)

$\log|\mathcal{C}|\leq cN\tau\log(1/\varepsilon)\log(1/\tau)$.

A key concept in applying container theory to such coloring problems is the
notion of template, which was first introduced in [12], although the concept
had already appeared in [31] under the name of ‘2-colored multigraphs’ and
later in [5], simply referred as ‘containers’.

######  Definition 2.6 (Template and palette).

An $r$-template of order $n$ is a function $P:[n]\to 2^{[r]}$, associating to
each element $x\in[n]$ a list of colors $P(x)\subseteq[r]$. We refer to this
set $P(x)$ as the palette available at $x$.

For a set $A\subseteq[n]$, any $r$-coloring of $A$ can be considered as an
$r$-template of order $n$, with only one color allowed at each element in $A$,
and no color allowed for elements not belonging to $A$.

######  Definition 2.7 (Subtemplate).

Let $P_{1}$, $P_{2}$ be two $r$-templates of order $n$. We say that $P_{1}$ is
a subtemplate of $P_{2}$ (written as $P_{1}\subseteq P_{2}$) if
$P_{1}(x)\subseteq P_{2}(x)$ for each element $x\in[n]$.

For an $r$-template $P$ of order $n$, write $RS(P)$ for the number of
subtemplate of $P$ that are rainbow restricted sums. We say that $P$ is a
rainbow restricted sum-free $r$-template if $RS(P)=0$. Using Theorem 2.5, we
obtain the following.

######  Theorem 2.8.

For every integer $r\geq 3$, there exists a constant $c=c(r)$ and a collection
$\mathcal{C}$ of $r$-templates of order $n$ such that

  1. (i)

every rainbow restricted sum-free $r$-template of order $n$ is a subtemplate
of some $P\in\mathcal{C}$;

  2. (ii)

for every $P\in\mathcal{C}$, $RS(P)\leq n^{-1/3}s([n])$;

  3. (iii)

$|\mathcal{C}|\leq 2^{cn^{2/3}\log^{2}n}$.

###### Proof.

Let $\mathcal{H}$ be a $3$-uniform hypergraph with vertex set
$[n]\times\\{1,2,...,r\\}$, whose edges are all triples
$\\{(x_{1},c_{1}),(x_{2},c_{2}),(x_{3},c_{3})\\}$ such that
$(x_{1},x_{2},x_{3})$ forms a restricted Schur triple in $[n]$ and
$c_{1},c_{2},c_{3}$ are all different. In other words, every hyperedge in
$\mathcal{H}$ corresponds to a rainbow restricted Schur triple. Note that
there are exactly $r(r-1)(r-2)$ ways to rainbow color a restricted Schur
triple with $r$ colors. Hence, the average degree $d$ of $\mathcal{H}$ is
equal to

$d=\frac{3e(\mathcal{H})}{v(\mathcal{H})}=\frac{3r(r-1)(r-2)s([n])}{nr}\geq\frac{3(r-1)(r-2)n}{8}.$

Now we apply Theorem 2.5 on $\mathcal{H}$. Let
$\varepsilon=n^{-1/3}/r(r-1)(r-2)$ ands $\tau=\sqrt{96\cdot 3!\cdot
r}n^{-\frac{1}{3}}$. Observe that
$\Delta_{2}(\mathcal{H})=2(r-2),\Delta_{3}(\mathcal{H})=1.$ For $n$
sufficiently large, we can get $\tau<1/(200\cdot 3!^{2}\cdot 3)$ and

$\Delta(\mathcal{H},\tau)=\frac{4\Delta_{2}}{d\tau}+\frac{2\Delta_{3}}{d\tau^{2}}=\frac{8(r-2)}{d\tau}+\frac{2}{d\tau^{2}}\leq\frac{3}{d\tau^{2}}\leq\frac{\varepsilon}{12\cdot
3!}.$

Hence, there is a collection of vertex subsets $\mathcal{C}$ satisfying
properties (i)-(iii) of Theorem 2.5. Observe that every vertex set of
$\mathcal{H}$ corresponds to an $r$-template of order $n$; every rainbow
restricted sum-free $r$-template of order $n$ corresponds to an independent
set in $\mathcal{H}$. Therefore, $\mathcal{C}$ is a desired collection of
$r$-templates. ∎

######  Definition 2.9 (Good $r$-template).

For $A\subseteq[n]$, an $r$-template $P$ of order $n$ is a good $r$-template
of $A$ if it satisfies the following properties:

  1. (i)

For each element $i\in A$, $|P(i)|\geq 1$;

  2. (ii)

$RS(P)\leq n^{-1/3}s([n])$.

For a set $A\subseteq[n]$ and a collection of templates $\mathcal{P}$, denote
by $G(\mathcal{P},A)$ the set of rainbow sum-free $r$-colorings of $A$, which
is a subtemplate of some $P\in\mathcal{P}$. Let
$g(\mathcal{P},A)=|G(\mathcal{P},A)|$. If $\mathcal{P}$ consists of a single
$r$-template $P$, then we simply write $G(P,A)$ and $g(P,A)$.

##  3 Proof of Theorem 1.5

Throughout this section, we fix an integer $r\geq 3$, a sufficiently large
integer $n$ and an arbitrary set $A\subseteq[n]$ with $|A|=(1-\xi)n$, where

$0\leq\xi\leq r^{-3}.$

Let $\mathcal{C}$ be the collection of containers given by Theorem 2.8, and
$\delta=1/(24\log n)$. We divide $\mathcal{C}$ into two classes

$\mathcal{C}_{1}=\\{P\in\mathcal{C}:g(P,A)\leq
2^{(1-\delta)n}\\},\quad\mathcal{C}_{2}=\\{P\in\mathcal{C}:g(P,A)>2^{(1-\delta)n}\\}.$
(2)

Note that every $P\in\mathcal{C}_{2}$ is a good $r$-template of $A$. The
crucial part of the proof is to estimate $g(\mathcal{C}_{2},A)$, which replies
on the following four lemmas.

######  Lemma 3.1.

Let $F$ be the collection of ordered pairs $(a,b)\in A^{2}$ with $a<b$ such
that $\\{a,b\\}\nsubseteq S$ for all $S\in\mathcal{S}(A)$. Then we have
$|F|\leq\xi n^{2}+n/6$.

###### Proof.

Let

$\displaystyle F_{1}=\\{(a,b)\in A^{2}\mid a+b\in[n]\backslash A,\
b=2a\\},\quad F_{2}=\\{(a,b)\in A^{2}\mid a+b>n,\ b=2a\\},$ $\displaystyle
F_{3}=\\{(a,b)\in A^{2}\mid a+b\in[n]\backslash A,\ b-a\in[n]\backslash
A\\},\quad F_{4}=\\{(a,b)\in A^{2}\mid a+b>n,\ b-a\in[n]\backslash A\\}.$

Clearly, $|F|=\sum_{i=1}^{4}|F_{i}|$ and $|F_{1}|\leq|[n]\backslash A|=\xi n$.
Since every $(a,b)\in F_{2}$ satisfies $b=2a\leq n$ and $a+b=3a>n$, we have
$|F_{2}|\leq n/6$. Moreover, we obtain that $|F_{3}|\leq\binom{\xi
n}{2}\leq{{\xi}^{2}n^{2}/2}$, as $a+b\in[n]\backslash A$ and
$b-a\in[n]\backslash A$. Similarly, we have $|F_{4}|\leq\xi n^{2}/2$, as
$b>n/2$ and $b-a\in[n]\backslash A$. Finally, we conclude that $|F|\leq\xi
n+n/6+{\xi}^{2}n^{2}/2+\xi n^{2}/2\leq\xi n^{2}+n/6$. ∎

For a template $P$ of $A$, let

$X_{1}=\\{x\in A\mid|P(x)|=1\\},\quad X_{2}=\\{x\in A\mid|P(x)|=2\\},\quad
X_{3}=\\{x\in A\mid|P(x)|\geq 3\\},$

and $x_{i}=|X_{i}|$ for $i\in[3]$.

######  Lemma 3.2.

Suppose that $P$ is a template of $A$ in $\mathcal{C}_{2}$. Then we have

$\max\left\\{\frac{(\xi-\delta)n+x_{1}}{\log{r}-1},\ 0\right\\}<x_{3}\leq
2n^{-1/3}n.$

In particular, if $\xi\geq 2(\log r-1)n^{-1/3}+\delta$, then $\mathcal{C}_{2}$
is empty.

###### Proof.

By the definitions of $G(P,A)$ and $\mathcal{C}_{2}$, we have

$2^{x_{2}}r^{x_{3}}\geq g(P,A)>2^{(1-\delta)n}.$ (3)

Since $x_{2}=|A|-x_{1}-x_{3}$ and $|A|=(1-\xi)n$, we obtain that

$x_{3}>\frac{(\xi-\delta)n+x_{1}}{\log{r}-1}.$ (4)

We first claim that $x_{2}\geq(1-\xi)n/3$. Otherwise, we immediately have
$x_{1}+x_{3}>2(1-\xi)n/3$. Together with (4), we obtain that
$x_{3}>\frac{(2+\xi-3\delta)n}{3\log r}>\frac{n}{2\log r}$. By Lemma 3.1 and
$0\leq\xi\leq r^{-3}$, there are at least

$\binom{x_{3}}{2}-({\xi}n^{2}+n/6)\geq\frac{n^{2}}{16\log^{2}r}$

pairs in $X_{3}$, which are contained in some restricted Schur triples in $A$.
This contradicts the definition of good $r$-templates, as $RS(P)\geq
n^{2}/(3\cdot 16\log^{2}r)>n^{-1/3}s([n])$.

For each $a\in X_{3}$, let $B_{a}:=\\{b\in X_{2}\mid\\{a,b\\}\subseteq
S,\text{ for some}\ S\in\mathcal{S}(A)\\}$. Note that every $b\in
X_{2}\setminus B_{a}$ satisfies either $|b-a|\in[n]\setminus A$ or
$|b-a|=\min\\{a,b\\}$. Then we have $|B_{a}|\geq(1-\xi)n/3-2\xi n-1>n/4$.
Since $P$ is a good $r$-template of $A$, we obtain that

$n^{-1/3}s([n])\geq RS(P)\geq\frac{1}{2}\sum_{a\in
X_{3}}|B_{a}|\geq\frac{x_{3}\cdot n}{8},$

which indicates $x_{3}\leq 2n^{-1/3}n.$ ∎

Next, we will prove a stability result on good templates with many rainbow
sum-free colorings.

######  Lemma 3.3.

Let $0\leq\xi<2(\log r-1)n^{-1/3}+\delta$. Then for every
$P\in\mathcal{C}_{2}$, there exist two colors $\\{i,j\\}\in[r]$ such that the
number of elements in $A$ with palette $\\{i,j\\}$ is at least $(1-2\delta)n$.

###### Proof.

By Lemma 3.2 and (3), we have

$x_{2}\geq(1-\delta-3\log r\cdot n^{-1/3})n.$

For $1\leq i<j\leq r$, define $Y_{i,j}:=\\{x\in X_{2}\mid P(x)=\\{i,j\\}\\}$.
Without loss of generality, we can assume that $|Y_{1,2}|\geq
x_{2}/\binom{r}{2}$. Let $Y^{\prime}=X_{2}\setminus Y_{1,2}$. For each $a\in
Y^{\prime}$, let $B_{a}=\\{b\in Y_{1,2}\mid\\{a,b\\}\subseteq S,\text{ for
some }S\in\mathcal{S}(A)\\}$. Similarly as in Lemma 3.2, we obtain that
$|B_{a}|\geq x_{2}/\binom{r}{2}-2\xi n-1$, and then

$n^{-1/3}s([n])\geq RS(P)\geq\frac{1}{2}\sum_{x\in
Y^{\prime}}|B_{a}|\geq\frac{|Y^{\prime}|\cdot n}{2r(r-1)}.$

Since $\delta\gg n^{-1/3}$, we have
$|Y_{1,2}|=x_{2}-|Y^{\prime}|\geq(1-2\delta)n$, which completes the proof. ∎

######  Lemma 3.4.

For two colors $i,j\in[r]$, denote by $\mathcal{P}=\mathcal{P}(i,j)$ the set
of good $r$-template of $A$, in which there are at least $(1-2\delta)n$
elements in $A$ with palette $\\{i,j\\}$. Then

$g(\mathcal{P},A)\leq 2^{|A|}(1+2^{-n/12}).$

###### Proof.

For an $r$-coloring $g\in G(\mathcal{P},A)$, let $S(g)$ the set of elements in
$A$, which are not colored by $i$ or $j$. By the definition of $\mathcal{P}$,
we have $|S(g)|\leq 2\delta n$. Define

$\mathcal{G}_{0}=\\{g\in G(\mathcal{P},A)\mid
S(g)=\varnothing\\},\quad\text{and}\quad\mathcal{G}_{1}=\\{g\in
G(\mathcal{P},A)\mid|S(g)|\geq 1\\}.$

Clearly, we have $g(\mathcal{P},A)=|\mathcal{G}_{0}|+|\mathcal{G}_{1}|$ and
$|\mathcal{G}_{0}|\leq 2^{|A|}$. It remains to show that
$|\mathcal{G}_{1}|\leq 2^{|A|-n/12}.$

Let us consider the ways to color $A$ so that the resulting colorings are in
$\mathcal{G}_{1}$. We first choose a set $A_{0}\subseteq A$ of size at most
$2\delta n$, which will be colored by the colors in $[r]\setminus\\{i,j\\}$.
The number of options is at most $\sum_{1\leq k\leq 2\delta n}\binom{n}{k}$,
and the number of colorings is at most $r^{2\delta n}$. Once we fix $A_{0}$
and its color, take an arbitrary vertex $t\in A_{0}$.

######  Claim 1.

Let $\mathcal{D}(t)$ be the collection of disjoint pairs $\\{a,b\\}$ in
$A\setminus A_{0}$ such that $\\{a,b,t\\}$ forms a restricted Schur triple.
Then $|\mathcal{D}(t)|\geq n/6$.

###### Proof.

Define

$\mathcal{S}_{1}=\\{(a,b)\in[n]^{2}\mid a+b=t,\ a<b\\},\ and\
\mathcal{S}_{2}=\\{(a,b)\in[n]^{2}\mid t+a=b,\ a<b\\}.$

We first observe that $|\mathcal{S}_{1}|=\lfloor(t-1)/2\rfloor$ for every
$t\in[n]$. Note that all pairs in $\mathcal{S}_{1}$ are disjoint. Therefore,
if $t>2n/5$, we have $|\mathcal{D}(t)|\geq|\mathcal{S}_{1}|-\xi
n-|A_{0}|\geq|\mathcal{S}_{1}|-(2\delta+\xi)n\geq n/6$. If $t\leq 2n/5$,
observe that $|\mathcal{S}_{2}|=n-2t$ and all pairs in $\mathcal{S}_{2}$ are
disjoint. Therefore, we obtain that $|\mathcal{D}(t)|\geq|\mathcal{S}_{2}|-\xi
n-|A_{0}|\geq|\mathcal{S}_{2}|-(2\delta+\xi)n\geq n/6$. ∎

For every pair $(a,b)\in\mathcal{D}(t)$, since $t$ is colored by some color in
$[r]\setminus\\{i,j\\}$, and $a,b$ can only be colored by $i$ or $j$, the
elements $a$ and $b$ must receive the same color in order to avoid the rainbow
Schur triple. Therefore, together with Claim 1, the number of ways to finish
the colorings is at most

$2^{|A|-|A_{0}|-|\mathcal{D}(t)|}\leq 2^{|A|-n/6}.$

Hence, we obtain that

$|\mathcal{G}_{2}|\leq\sum_{1\leq k\leq 2\delta n}\binom{n}{k}r^{2\delta
n}2^{|A|-n/6}\leq 2^{|A|+2\delta n(\log n+\log r)-n/6}\leq 2^{|A|-n/12},$

where the last inequality follows from $\delta=1/(24\log n)$. ∎

Now we have all ingredients to prove Theorem 1.5.

###### Proof of Theorem 1.5.

First, by property (i) of Theorem 2.8 , every rainbow sum-free $r$-coloring of
$A$ is a subtemplate of some $P\in\mathcal{C}$. By Property (iii) of Theorem
2.8 and the definition of $\mathcal{C}_{1}$ (see (2)), we have

$g(\mathcal{C}_{1},A)\leq|\mathcal{C}_{1}|\cdot
2^{(1-\delta)n}\leq|\mathcal{C}|\cdot 2^{(1-\delta)n}<2^{n}\cdot 2^{-n/(25\log
n)}.$

If $\xi\geq 2(\log r-1)n^{-1/3}+\delta$, using Lemma 3.2, we are done by
$g(\mathcal{C},A)=g(\mathcal{C}_{1},A)$. Otherwise, by Lemma 3.3 and Lemma
3.4, we obtain that

$g(\mathcal{C}_{2},A)=\sum_{1\leq i<j\leq
r}g(\mathcal{P}(i,j),A)\leq\binom{r}{2}2^{|A|}(1+2^{-n/12}).$

Hence, we have

$g(\mathcal{C},A)=g(\mathcal{C}_{1},A)+g(\mathcal{C}_{2},A)\leq 2^{n}\cdot
2^{-\frac{n}{25\log n}}+\binom{r}{2}2^{|A|}(1+2^{-n/12})\leq\binom{r}{2}\cdot
2^{|A|}+2^{-\frac{n}{26\log n}}2^{n},$

which gives the desired upper bound on the number of rainbow sum-free
$r$-colorings of $A$. ∎

##  4 Proof of Theorems 1.7 and 1.8

The following lemma gives us a structural description of large sum-free sets.

######  Lemma 4.1.

Let $\varepsilon,c>0$, $c>10\varepsilon$, and $\varepsilon<1/10$. Let
$A,B\subseteq[n]$ such that $A\cap B=\varnothing$, $B$ is sum-free, and
$|A|=cn$. If $|B|\geq(1/2-\varepsilon)n$, then $(A+B)\cap B\neq\varnothing.$

###### Proof.

Suppose, to the contrary, that $(A+B)\cap B=\varnothing$. Since $|B|>2n/5$, by
Lemma 2.4, either $B$ only contains odd numbers, or the minimum element of $B$
is at least $|B|\geq(1/2-\varepsilon)n$. If $B$ only contains odd numbers,
then there is $d\geq c-\varepsilon$, such that $|A\cap E|=dn$, where
$E\subseteq[n]$ is the collection of all even numbers. Thus, there exists an
$a\in A\cap E$ such that $dn\leq a\leq(1-d)n$. Let $P$ be the collection of
all pairs $(i,\ i+a)$, where $i$ is odd, and $1\leq i\leq dn$. Observe that
all pairs in $P$ are pairwise disjoint and there are at least $dn/2$ of them.
Since $(A+B)\cap B=\varnothing$, for each pair $(i,j)$ in $P$, at least one of
$\\{i,j\\}$ is not in $B$. This implies

$|B|\leq\frac{n}{2}-|P|\leq\frac{n}{2}-\frac{dn}{2}\leq\frac{n}{2}-\frac{(c-\varepsilon)n}{2}\leq\left(\frac{1}{2}-2\varepsilon\right)n,$

which contradicts the assumption of $B$.

If the minimum element of $B$ is at least $|B|\geq(1/2-\varepsilon)n$, let $b$
be the smallest element in $B$, then there is $d\geq c-2\varepsilon$ such that
$|A\cap[b-1]|=dn$. This implies that there exists $a\in A$ with $dn/2\leq
a\leq b-dn/2$. We define $P$ to be the collection of all pairs $(i,j)$, where
$b\leq i<(1/2+3\varepsilon)n$ and $j=i+a$. Then the number of pairs in $P$ is
at least $2\varepsilon n$, as $b\leq(1/2+\varepsilon)n$. Moreover, for every
$(i,j)$ in $P$, we have $j<n$ since $b-dn/2\leq(1/2-3\varepsilon)n$ and since
$b+a>(1/2+3\varepsilon)n$, $P$ is a set of disjoint pairs. Since $(A+B)\cap
B=\varnothing$, for every $(i,j)$ in $P$, at least one of $\\{i,j\\}$ is not
in $B$. Similarly we obtain that $|B|\leq(1/2-2\varepsilon)n$, a
contradiction. ∎

Our next lemma says that when the number of colorings $r=3$ and the size of
$A$ is significantly smaller than $n$, the number of rainbow sum-free
$r$-colorings will be much less than $2^{n}$. And when $r\geq 5$ and the size
of $A$ is significantly larger than $n/2$, much less than $r^{n/2}$ when $r$,
the number of rainbow sum-free $r$-colorings will be much less than $r^{n/2}$.

######  Lemma 4.2.

Let $\varepsilon>0$, $r$ be a positive integer, and let $A$ be a subset of
$[n]$. Then the followings hold.

  1. (i)

If $r=3$, and $|A|\leq(1-\varepsilon)n$, then here is a constant
$\delta_{1}=\delta_{1}(\varepsilon)>0$, such that

$g(A,3)\leq 2^{(1-\delta_{1})n}.$

  2. (ii)

If $r\geq 5$, and $|A|\geq\big{(}1/2+\varepsilon\big{)}n$,then there is a
constant $\delta_{1}=\delta_{1}(\varepsilon,r)>0$ such that

$g(A,r)\leq r^{(1/2-\delta_{1})n}.$

###### Proof.

Let $\mathcal{C}$ be the collection of containers given by Theorem 2.8, and
let

$g_{\max}(P,A)=\max_{P\in\mathcal{C}}g(P,A).$

For a template $P\in\mathcal{C}$, suppose $P$ is not a good template. Then
there must be an element $i\in A$ with $|P(i)|=0$, which immediately gives
$g(P,A)=0$. Therefore, $g_{\max}(P,A)$ is always achieved by a good template.

Let $P$ be a good template of $A$. Since $RS(P)=o(n^{2})$, by Green’s
arithmetic removal lemma, there is a set $E\subseteq[n]$ and a template
$P^{\prime}:[n]\setminus E\to 2^{[r]}$, such that $P\mid_{[n]\setminus
E}=P^{\prime}$, $|E|=o(n)$, and $P^{\prime}$ has no rainbow Schur triples.
Define

$X_{1}=\\{a\in[n]\setminus E:|P^{\prime}(a)|=1\\},\quad
X_{2}=\\{a\in[n]\setminus E:|P^{\prime}(a)|=2\\},$

and

$X_{3}=\\{a\in[n]\setminus E:|P^{\prime}(a)|\geq 3\\}.$

Let $T=X_{2}\cup X_{3}$ and let $x_{i}=|X_{i}|$ for $i=1,2,3$. Therefore, we
have

$(X_{3}+X_{3})\cap X_{3}=\varnothing,\quad(T+T)\cap
X_{3}=\varnothing,\quad(X_{3}+T)\cap T=\varnothing.$ (5)

As $X_{3}$ is sum-free, we have $x_{3}\leq\lfloor n/2\rfloor+1$.

Let $m$ be the largest element in $X_{3}$. By (5), for every $i<m$, at least
one of $\\{i,\ m-i\\}$ is not in $T$ which is also the same for $X_{3}$.
Hence, we have

$|T|\leq n-\Big{\lceil}\frac{m-1}{2}\Big{\rceil},\quad x_{3}\leq
m-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}.$ (6)

Case 1: $r=3$.

Observe that we may assume $\varepsilon<2/5$, as otherwise we will get
$g(A,3)\leq 3^{|A|}\leq 2^{0.955n}$, which completes the proof with
$\delta_{1}=0.045$. We first consider the case when
$x_{2}\leq(1-5\varepsilon/2)n$. Then we have

$\displaystyle\log g(\mathcal{C},A)$ $\displaystyle\leq\log(|\mathcal{C}|\cdot
g_{\max}(P,A))\leq cn^{2/3}\log^{2}n+|E|\log 3+x_{2}+x_{3}\log 3$
$\displaystyle=o(n)+x_{2}+x_{3}\log
3=\left(o(n)+\frac{1}{2}\left(|T|+x_{3}-\left(1-\frac{2}{\log
3}\right)x_{2}\right)\right)\log 3$ $\displaystyle\leq
n+o(n)-\frac{5\varepsilon}{2}\left(1-\frac{\log
3}{2}\right)n<(1-\delta_{1})n,$

where we take $\delta_{1}=\frac{5\varepsilon}{4}(1-\frac{\log 3}{2})$.

Now, we may assume that $x_{2}>(1-5\varepsilon/2)n$. Then
$x_{3}\leq|A|-x_{2}<3\varepsilon n/2$. Thus we obtain

$\displaystyle\log g(\mathcal{C},A)$ $\displaystyle\leq o(n)+x_{2}+x_{3}\log
3\leq o(n)+|A|+(\log 3-1)x_{3}$ $\displaystyle\leq
n+o(n)-\frac{\varepsilon}{2}\left(5-3\log 3\right)n<(1-\delta_{1})n,$

and we take $\delta_{1}=\frac{1}{4}\left(5-3\log 3\right)\varepsilon$.

Case 2: $r\geq 5$.

Since $|A|\geq(1/2+\varepsilon)n$, and $P$ is good, we have that
$x_{1}+x_{2}\geq|A|-x_{3}-|E|\geq\varepsilon n/2$ for large enough $n$. We
first assume that $x_{2}\geq\frac{\varepsilon n}{100}$. Similarly, we get

$\displaystyle\log g(\mathcal{C},A)$ $\displaystyle\leq\log(|\mathcal{C}|\cdot
g_{\max}(P,A))\leq cn^{2/3}\log^{2}n+|E|\log r+x_{2}+x_{3}\log r$
$\displaystyle=o(n)+x_{2}+x_{3}\log
r=\left(o(n)+\frac{1}{2}\left(|T|+x_{3}-\left(1-\frac{2}{\log
r}\right)x_{2}\right)\right)\log r$
$\displaystyle\leq\left(\frac{n}{2}+o(n)-\frac{1}{2}\left(1-\frac{2}{\log
r}\right)\frac{\varepsilon}{100}n\right)\log
r<\left(\frac{n}{2}-\delta_{1}n\right)\log r,$ (7)

where we take $\delta_{1}=\frac{1}{300}\left(1-\frac{2}{\log
r}\right)\varepsilon$. Note that $\delta_{1}>0$ as $r\geq 5$.

Finally, we may assume that $x_{2}\leq\frac{\varepsilon n}{100}$, and then
$x_{1}\geq\frac{\varepsilon n}{2}-x_{2}\geq\frac{\varepsilon n}{3}$. We claim
that $x_{3}\leq(1/2-\varepsilon/40)n$. Otherwise, by the way we construct
$P^{\prime}$, we also have $(X_{1}+X_{3})\cap X_{3}=\varnothing$ and this
contradicts Lemma 4.1. Similarly as before, we can conclude that

$\log g(\mathcal{C},A)\leq o(n)+x_{2}+x_{3}\log
r\leq\left(\frac{n}{2}+o(n)+\frac{\varepsilon}{100\log
r}n-\frac{\varepsilon}{80}n\right)\log
r\leq\left(\frac{n}{2}-\delta_{1}n\right)\log r,$

where we take $\delta_{1}=\frac{\varepsilon}{400}$. ∎

The case when $r=4$ is more involved, and we will discuss it later in this
section. But the result in Lemma 4.2 (i) is enough to imply Theorem 1.7.

###### Proof of Theorem 1.7.

Observe that $g([n],3)\geq 3\cdot 2^{n}-3$. Suppose $A\subseteq[n]$ and
$A\neq[n]$. When $|A|\leq(1-3^{-3})n$, by Lemma 4.2 (i), there is
$\delta_{1}>0$ such that $g(A,3)\leq 2^{(1-\delta_{1})n}<g([n],3).$ Now, we
have $(1-3^{-3})n<|A|\leq n-1$. By Theorem 1.5,
$g(A,3)\leq(1.5+o(1))2^{n}<g([n],3)$. ∎

The next lemma records an easy fact about intervals for convenience in the
proof of the analogue result of Lemma 4.2 when we have only 4 colors.

######  Lemma 4.3.

Let $\varepsilon>0$, and let $a,b$ be integers such that $0<a<b<n$,
$3\varepsilon n<a<n/2-2\varepsilon n$, and $a+2+3\varepsilon n<b\leq 2a$.
Suppose $A\subseteq[a+1,b]$, $B\subseteq[b+1,n]$, and $|A|>b-a-\varepsilon n$,
$|B|>n-b-\varepsilon n$. Then $(A+A)\cap B\neq\varnothing$.

###### Proof.

Let $\alpha$ be the smallest element in $A$, then $\alpha\leq a+\varepsilon
n+1$. Let $J=[\alpha+1,\alpha+1+\lceil 2\varepsilon n\rceil]\subseteq[a+1,b]$.
Observe that $\alpha+J\subseteq[b+1,n]$. Since $|J|=\lceil 2\varepsilon
n\rceil$, and $|[a+1,b]\setminus A|<\varepsilon n$, $|[b+1,n]\setminus
B|<\varepsilon n$, this implies there is $\beta\in A\cap J$ such that
$\alpha+\beta\in B$. ∎

The next lemma, Lemma 4.4, is similar to Lemma 4.2, but here we consider the
case when the number of colors is $4$. In order to obtain the same conclusion
in Lemma 4.2, we further require that the size of $A$ is significantly smaller
than $n$, since if $A$ is close to $[n]$, when we color all the elements in
$A$ by two colors, the number of colorings we obtained is also close to the
extremal case. Note that if we use the same proof as in Lemma 4.2 for $r=4$,
equation (7) does not give us the conclusion we want. Hence the proof of Lemma
4.4 requires a more careful and complicated analysis of the structures of the
containers.

######  Lemma 4.4.

Let $\varepsilon>0$ such that
$\big{(}1/2+\varepsilon\big{)}n\leq|A|\leq(1-\varepsilon)n$. Then there is
$\delta_{2}=\delta_{2}(\varepsilon)>0$ such that

$g(A,4)\leq 4^{n/2-\delta_{2}n}.$

###### Proof.

We apply Theorem 2.8 on $A$. Let $\mathcal{C}$ be the collection of
containers, and let $P\in\mathcal{C}$ be a good template of order $n$. As what
we did in the proof of Lemma 4.2, we similarly apply Green’s removal lemma on
$P$, and obtain a template $P^{\prime}:[n]\setminus E\to 2^{[r]}$, such that
$P\mid_{[n]\setminus E}=P^{\prime}$, $|E|=o(n)$, and $P^{\prime}$ is sum-free.
Let $X_{1},X_{2},X_{3}\subseteq A\setminus E$ such that $X_{1}=\\{a\in
A\mid|P^{\prime}(a)|=1\\}$, $X_{2}=\\{a\in A\mid|P^{\prime}(a)|=2\\}$, and
$X_{3}=\\{a\in A\mid|P^{\prime}(a)|\geq 3\\}$. Let $T=X_{2}\cup X_{3}$ and
$x_{i}=|X_{i}|$ for $i\in[3]$. Therefore, we have equations (5) still hold,
and in particular, $X_{3}$ is sum-free. Thus $x_{3}\leq(n+1)/2$. Since
$|A|\geq(1/2+\varepsilon)n$, and $P$ is good, we also obtain that
$x_{1}+x_{2}\geq\varepsilon n/2$. Let $m=n-\alpha$ be the maximum element in
$X_{3}$, by using the same argument, equations (6) still hold.

Suppose we have either

$|T|\leq n-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}-\frac{\varepsilon
n}{1000},\quad\text{ or }\quad x_{3}\leq
m-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}-\frac{\varepsilon n}{1000}.$

Thus

$\displaystyle g(\mathcal{C},A)\leq
2^{cn^{2/3}\log^{2}n}r^{|E|}2^{x_{2}}r^{x_{3}}=r^{o(n)+\frac{1}{2}(|T|+x_{3})}\leq
r^{\frac{n}{2}+o(n)-\frac{\varepsilon n}{2000}}<r^{\frac{n}{2}-\delta_{2}n},$

and we take $\delta_{2}=\frac{\varepsilon}{3000}.$ Therefore, we may assume
that

$n-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}-\frac{\varepsilon n}{1000}\leq|T|\leq
n-\Big{\lceil}\frac{m-1}{2}\Big{\rceil},\text{ and }\
m-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}-\frac{\varepsilon n}{1000}\leq
x_{3}\leq m-\Big{\lceil}\frac{m-1}{2}\Big{\rceil}.$ (8)

In the rest of the proof, we are going to show that this is impossible.

Suppose that $\alpha\leq\frac{\varepsilon n}{40}$. Note that
$\max\\{x_{1},x_{2}\\}\geq\frac{\varepsilon n}{4}$, and

$(X_{1}+X_{3})\cap X_{3}=\varnothing,\quad(X_{2}+X_{3})\cap
X_{3}=\varnothing,$

this contradicts Lemma 4.1. Thus we have $m\leq(1-\frac{\varepsilon}{40})n$.
Since $|A|\leq(1-\varepsilon)n$, thus by the lower bound on $|T|$ in (8),
$m\geq 3\varepsilon n/2$.

We now partition $[n]$ into three parts $J_{1},J_{2},J_{3}$, such that
$J_{1}=[n-\alpha+1,n]$, $J_{2}=[1,\alpha]$, and $J_{3}=[\alpha+1,n-\alpha]$.
By (8), we obtain that

$|J_{1}\cap X_{2}|\geq\alpha-\frac{\varepsilon n}{1000}.$ (9)

Take $d=\frac{\varepsilon}{400}$. Suppose $|J_{2}\cap X_{3}|\geq dn$, then we
can find $\beta\in X_{3}$ such that
$\frac{dn}{2}\leq\beta\leq\alpha-\frac{dn}{2}$. Let
$J_{1}^{\prime}=[n-\alpha+1,n-\alpha+\frac{dn}{2}]\subseteq J_{1}$. Note that
$(J_{1}^{\prime}+\beta)\cap J_{1}^{\prime}=\varnothing$, and
$J_{1}^{\prime}+\beta\subseteq J_{1}$, since $(X_{2}+X_{3})\cap
X_{2}=\varnothing$, and for every $i\in J_{1}^{\prime}$, there is at least one
element in the pair $\\{i,i+\beta\\}$ that is not contained in $X_{2}$, we
have that $|J_{1}\cap X_{2}|\leq\alpha-\frac{dn}{2}=\alpha-\frac{\varepsilon
n}{800}$, contradicts (9). Hence we may assume $|J_{2}\cap X_{3}|\leq dn$.
Therefore, by (8), $|J_{3}\cap X_{3}|\geq\frac{n-\alpha}{2}-\frac{\varepsilon
n}{1000}-dn$. This gives us an upper bound on $\alpha$ since
$|J_{3}|\geq|J_{3}\cap X_{3}|$, that $\alpha\leq\frac{n}{3}+\frac{\varepsilon
n}{1500}+\frac{2dn}{3}$. Next, we are going to show that actually we have
$\alpha\leq\frac{n}{3}$. Suppose $\alpha>\frac{n}{3}$. Note that $|J_{3}\cap
X_{3}|\geq\frac{n-\alpha}{2}-dn-\frac{\varepsilon n}{1000}$ implies

$|J_{3}\setminus X_{3}|\leq\frac{n-3\alpha}{2}+dn+\frac{\varepsilon
n}{1000}\leq dn+\frac{\varepsilon n}{1000}<\frac{\varepsilon n}{250}.$

By (9) and Lemma 4.3, we get $(X_{3}+X_{3})\cap X_{2}\neq\varnothing$, this
contradicts (5).

Let $J_{3}^{\prime}=[n-2\alpha,n-\alpha]$. We claim that

$|J_{3}^{\prime}\setminus X_{3}|\leq dn+\frac{\varepsilon
n}{800}=\frac{3\varepsilon n}{800}.$ (10)

Otherwise, observe that at least one of $\\{i,m-i\\}$ is not in $X_{3}$, then
$|X_{3}\cap(J_{3}\setminus J_{3}^{\prime})|\leq\frac{n-3\alpha}{2}$ since
$\alpha\leq n/3$. Hence

$x_{3}\leq\frac{m}{2}-\alpha+dn+\alpha-\Big{(}dn+\frac{\varepsilon
n}{800}\Big{)}\leq\frac{m}{2}-\frac{\varepsilon n}{800},$

contradicts (8).

Next, let $d^{\prime}=\frac{\varepsilon}{60}$, and suppose that
$|(J_{2}+\alpha)\cap X_{3}|\geq d^{\prime}n$. Thus there is $\gamma\in X_{3}$
such that $\alpha+\frac{d^{\prime}n}{2}\leq\gamma\leq
2\alpha-\frac{d^{\prime}n}{2}$. Let
$J_{1}^{\prime\prime}=[n-2\alpha,n-2\alpha+\frac{d^{\prime}n}{2}]$. Observe
that $(\gamma+J_{1}^{\prime\prime})\cap J_{1}^{\prime\prime}=\varnothing$, and
$\gamma+J_{1}^{\prime\prime}\subseteq J_{1}$. Since $(X_{2}+X_{3})\cap
X_{2}=\varnothing$, we have either $|X_{3}\cap
J_{3}^{\prime}|\leq\alpha-\frac{d^{\prime}n}{4}<\alpha-\frac{3\varepsilon
n}{800}$, or $|X_{2}\cap
J_{1}|\leq\alpha-\frac{d^{\prime}n}{4}<\alpha-\frac{\varepsilon n}{1000}$, and
in either case we get a contradiction with (9) or (10). Thus, we have
$|(J_{2}+\alpha)\cap X_{3}|\leq d^{\prime}n$. Note that
$J_{3}^{\prime}=\\{m\\}\cup(m-J_{2})$, clearly, $|X_{3}\cap(J_{2}\cup
J_{3}^{\prime})|\leq\alpha+1$. Then by (8),

$\frac{n-3\alpha}{2}-\frac{\varepsilon
n}{1000}\leq\big{|}X_{3}\cap[\alpha,n-2\alpha]\big{|}\leq
n-4\alpha+d^{\prime}n,$

hence $\alpha\leq\frac{n}{5}+\frac{2d^{\prime}n}{5}+\frac{\varepsilon
n}{2500}$. Suppose now $\alpha\geq\frac{n}{5}$. We have that
$|X_{3}\cap[2\alpha,n-\alpha]|\geq\frac{n-\alpha}{2}-dn-d^{\prime}n-\frac{\varepsilon
n}{1000}$, which implies $|[2\alpha,n-\alpha]\setminus
X_{3}|\leq\frac{\varepsilon n}{1000}+dn+d^{\prime}n$. By (9) and Lemma 4.3, we
obtain that $(X_{3}+X_{3})\cap X_{2}\neq\varnothing$, and this contradicts
(5).

Finally, we get $\frac{\varepsilon n}{40}\leq\alpha<\frac{n}{5}$. By (8), we
have that $x_{3}\leq\frac{2n}{5}$. By Lemma 2.4, either $X_{3}$ consists of
odd integers, or the minimum element in $X_{3}$ is at least
$\frac{n-\alpha}{2}-\frac{\varepsilon n}{1000}$. The first case is impossible.
Otherwise, since $|J_{2}|=\alpha>2dn+\frac{\varepsilon n}{1000}$, we have

$x_{3}=|X_{3}\cap J_{2}|+|X_{3}\cap J_{3}|\leq
dn+\frac{n-2\alpha}{2}\leq\frac{n-\alpha}{2}-\frac{9\varepsilon n}{800},$

and this contradicts the lower bound on $x_{3}$ in (8). Now, we assume $a\in
X_{3}$ is the minimum element, and $a\geq\frac{n-\alpha}{2}-\frac{\varepsilon
n}{1000}$. Observe that $|[\frac{n-\alpha}{2}+1,n-\alpha]\setminus
X_{3}|\leq\frac{\varepsilon n}{500}$,
$\frac{n-\alpha}{2}\leq\frac{n}{2}-\frac{\varepsilon n}{80}$, and by (9) and
Lemma 4.3, we have $(X_{3}+X_{3})\cap X_{2}\neq\varnothing$, this contradicts
(5). ∎

The final lemma consider the case when $A$ contains many Schur triples.

######  Lemma 4.5.

Let $r\geq 4$ be an integer. Suppose there is $\mu>0$, such that $s(A)\geq\mu
n^{2}$. Then

$g(A,r)\leq r^{|A|-\frac{3(2\log r-\log(3r-2))}{2\log r}\mu n}.$

###### Proof.

Since $s(A)\geq\mu n^{2}$, by Pigeonhole Principle, there is $t\in A$, such
that

$s(t,A)\geq\frac{3\mu n^{2}}{|A|}\geq 3\mu n.$

Let the link graph $L_{t}(A)$ to be the simple graph defined on the vertex set
$A\setminus\\{t\\}$, such that $xy\in E(L_{t}(A))$ if and only if
$\\{t,x,y\\}\in\mathcal{S}(t,A)$. Let $k$ be the size of the maximum matching
in $L_{t}(A)$. Observe that $\Delta(L_{t}(A))\leq 2$, and
$|E(L_{t}(A))|=s(t,A)\geq 3\mu n$. Then we have $k\geq 3\mu n/2$.

Now we consider the possible number of rainbow sum-free colorings of $A$. We
first fix a maximum matching $M$ of $L_{t}(A)$. For the elements in
$A\setminus V(M)$, we color them arbitrarily. For each edge $ab\in E(M)$, in
order to avoid a rainbow Schur triple, we either let $a,b$ share the same
color, or color one of $a,b$ by the color of $t$, and color another vertex by
a different color. In this way, $a,b$ have exactly $r+2(r-1)$ effective
colorings. Hence, we have

$\displaystyle g(A,r)$ $\displaystyle\leq r^{|A|-2k-1}r(3r-2)^{k}\leq
r^{|A|}\Big{(}\frac{3r-2}{r^{2}}\Big{)}^{\frac{3\mu
n}{2}}=r^{|A|-\frac{3(2\log r-\log(3r-2))}{2\log r}\mu n},$

as desired. ∎

Now we can prove the stability theorem.

###### Proof of Theorem 1.8.

The first part of the statement, that $g(n,r)\leq r^{n/2+o(n)}$, follows
easily from the fact $g(A,r)\leq r^{|A|}$ when $|A|\leq n/2+o(n)$. If $|A|\geq
n/2+\eta n$ for some constant $\eta$, the result follows from Lemma 4.2 (ii)
when $r\geq 5$. For the case $r=4$, after applying Lemma 4.4 we still have one
extra case that $|A|\geq(1-\eta)n$, and this follows from Theorem 1.5.

For the second part of the statement, we will prove it by contrapositive. Let
$c=\frac{3(2\log r-\log(3r-2))}{2\log r}$, clearly $c>0$ when $r\geq 4$. Let
$\mu$ be the value of $\delta(\frac{\varepsilon}{20})$ given in Lemma 2.3, and
let $\varepsilon^{\prime}=\min\\{\frac{c\mu}{2},\varepsilon\\}$. We first
consider $r\geq 5$, and suppose that we have both

$|A\triangle O|>\varepsilon n,\quad\text{ and }\quad|A\triangle
I_{0}|>\varepsilon n.$ (11)

In this case we take
$\delta=\min\\{\delta_{1}(\varepsilon^{\prime}),\varepsilon^{\prime},\frac{\varepsilon}{20}\\}$,
where $\delta_{1}(\varepsilon^{\prime})$ is given in Lemma 4.2 (ii). If
$|A|\geq\frac{n}{2}+\varepsilon^{\prime}n$, we apply Lemma 4.2 (ii) with
parameter $\varepsilon^{\prime}$, then we obtain that $g(A,r)\leq
r^{n/2-\delta n}$. Thus we may assume that
$|A|\leq(1/2+\varepsilon^{\prime})n$. If $s(A)\geq\mu n^{2}$, applying Lemma
4.5, then we have

$g(A,r)\leq r^{n/2+\varepsilon^{\prime}n-c\mu n}\leq
r^{n/2-\varepsilon^{\prime}n}\leq r^{n/2-\delta n}.$

Finally, we have $s(A)<\mu n^{2}$. By Lemma 2.3, we get the partition $A=B\cup
C$, where $B$ is sum-free and $|C|<\frac{\varepsilon}{20}n$. Note that we may
assume $|A|\geq\frac{n}{2}-\frac{\varepsilon}{20}n$, otherwise $g(A,r)\leq
r^{|A|}\leq r^{n/2-\delta n}$. Now we have

$|B|\geq|A|-|C|\geq\frac{n}{2}-\frac{\varepsilon n}{10}\geq\frac{2n}{5}$

since $\varepsilon\leq 1$. We apply Lemma 2.4 on $B$. Hence either $B$
contains only odd integers, or the minimum element of $B$ is at least $|B|$.
Suppose $B$ consists of odd integers. Thus

$|A\triangle O|\leq|C|+|O\setminus
B|\leq\frac{\varepsilon}{20}n+\frac{\varepsilon}{10}n<\varepsilon n,$

contradicts (11). Thus, let $a$ be the minimum element in $B$, then
$a\geq\frac{n}{2}-\frac{\varepsilon n}{10}$. Therefore,

$|A\triangle I_{0}|\leq|C|+|B\triangle
I_{0}|\leq\frac{\varepsilon}{20}n+\frac{\varepsilon}{10}n+\frac{\varepsilon}{5}n<\varepsilon
n,$

which also contradicts (11).

Next, let us consider the case when $r=4$. Besides (11), we further require

$|A\triangle[n]|>\varepsilon n.$ (12)

We now take
$\delta=\min\\{\delta_{2}(\varepsilon^{\prime}),\varepsilon^{\prime},\frac{\varepsilon}{20}\\}$,
where $\delta_{2}(\varepsilon^{\prime})$ is given in Lemma 4.4. The case when
$|A|\leq\frac{n}{2}+\varepsilon^{\prime}n$ is same as when $r\geq 5$. When
$\frac{n}{2}+\varepsilon^{\prime}n\leq|A|\leq n-\varepsilon^{\prime}n$, by
applying Lemma 4.4 we get $g(A,4)\leq 4^{n/2-\delta n}$. When $|A|\geq
n-\varepsilon^{\prime}n$, we get
$|A\triangle[n]|\leq\varepsilon^{\prime}n\leq\varepsilon n$, which contradicts
(12). ∎

##  5 Proof of Theorem 1.10

For a subset $A\subseteq[n]$ and an integer $t$, recall that $L_{t}(A)$ is the
simple graph defined on $A\setminus\\{t\\}$, in which $xy\in E(L_{t}(A))$ if
and only if $\\{t,x,y\\}\in\mathcal{S}(t,A)$. Let $k(t,A)$ be the size of the
maximum matching of $L_{t}(A)$. Note that $\Delta(L_{t}(A))\leq 2$. Therefore
we have

$k(t,A)\geq|E(L_{t}(A))|/2=s(t,A)/2.$ (13)

######  Proposition 5.1.

Let $n,r,c\in N$ with $r\geq 8$ and $c>1$. Suppose that $A$ is a subset of
$[n]$ of size $\lceil n/2\rceil+c$.

  1. (i)

If there exists an element $t\in A$ such that $k(t,A)\geq 2(c-1)$, then we
have $g(A,r)<r^{\lceil n/2\rceil+1}$.

  2. (ii)

If there exists an element $t\in A$ such that $k(t,A)\geq 2(c-1)+1$, then we
have $g(A,r)<r^{\lceil n/2\rceil}\left(3-2/r\right)$.

###### Proof.

First note that for $r\geq 8$ we have

$\frac{(3r-2)^{2}}{r^{3}}<1.$ (14)

Let $k=k(t,A)$. Similarly as in the proof of Lemma 4.5, we obtain that

$g(A,r)\leq r^{\lceil n/2\rceil+c-2k}(3r-2)^{k}=r^{\lceil
n/2\rceil+c}\left(\frac{3r-2}{r^{2}}\right)^{k}.$

For $k\geq 2(c-1)$, we have

$g(A,r)\leq r^{\lceil
n/2\rceil+c}\left(\frac{3r-2}{r^{2}}\right)^{2(c-1)}=r^{\lceil
n/2\rceil+1}\left(\frac{(3r-2)^{2}}{r^{3}}\right)^{c-1}<r^{\lceil
n/2\rceil+1},$

where the last inequality follows from (14) and $c>1$.

Similarly, for $k\geq 2(c-1)+1$, we have

$\begin{split}g(A,r)&\leq r^{\lceil
n/2\rceil}\left(3-\frac{2}{r}\right)r^{c-1}\left(\frac{3r-2}{r^{2}}\right)^{k-1}\leq
r^{\lceil
n/2\rceil}\left(3-\frac{2}{r}\right)r^{c-1}\left(\frac{3r-2}{r^{2}}\right)^{2(c-1)}\\\
&=r^{\lceil
n/2\rceil}\left(3-\frac{2}{r}\right)\left(\frac{(3r-2)^{2}}{r^{3}}\right)^{c-1}<r^{\lceil
n/2\rceil}\left(3-\frac{2}{r}\right).\end{split}$

Together with the previous inequality, this completes the proof. ∎

######  Lemma 5.2.

Let $r\geq 8$, $0<\varepsilon\leq 1/36$, and $A$ be a subset of $[n]$ of size
$\lceil n/2\rceil+c$, where $1<c\leq\varepsilon n$. Suppose that there exists
a partition $A=B\cup C$ such that $B$ consists of odd numbers and
$|C|\leq\varepsilon n$. Then we have $g(A,r)<r^{\lceil
n/2\rceil}\left(3-2/r\right)$.

###### Proof.

From the assumption of $A$, there must be an even number $t\in A$. By
Proposition 5.1(ii) and $\varepsilon\leq 1/36$, it is sufficient to show that
$k(t,A)\geq(1/12-\varepsilon)n-1$.

Recall that $O$ is the set of all odd numbers in $[n]$. Since $|A|\geq\lceil
n/2\rceil+1$ and $|C|\leq\varepsilon n$, we have $|O\setminus
B|\leq\varepsilon n$. Then,

$k(t,A)\geq k(t,B)\geq k(t,O)-\varepsilon n,$

and thus it is equivalent to show that $k(t,O)\geq n/12-1$.

If $t\geq n/3$, then we immediately have

$k(t,O)\geq\left|\left\\{(i,t-i,t),i\in
O\cap\left[t/2-1\right]\right\\}\right|\geq t/4-1\geq n/12-1.$

If $t<n/3$, then by (13) we obtain that

$k(t,O)\geq s(t,O)/2\geq\left|\left\\{(t,i,t+i),i\in O\cap\left[t+1,\
n-t\right]\right\\}\right|/2\geq(n-2t)/4\geq n/12.$

This completes the proof. ∎

######  Lemma 5.3.

Let $r\geq 8$, $0<\varepsilon\ll 1$, and $A$ be a subset of $[n]$ of size
$\lceil n/2\rceil+c$, where $1<c\leq\varepsilon n$. Suppose that there exists
a partition $A=B\cup C$ such that $B\subseteq I_{0}$ and $|C|\leq\varepsilon
n$. Then the following holds.

  1. (i)

If $n$ is even, then $g(A,r)<r^{\lceil n/2\rceil+1}$.

  2. (ii)

If $n$ is odd, then $g(A,r)<r^{\lceil n/2\rceil}\left(3-2/r\right)$.

###### Proof.

Let $m$ be the minimum element of $A$, and clearly $m\leq\lfloor
n/2\rfloor-(c-1)$. Recall that $I_{0}=[\lfloor n/2\rfloor+1,n]$. Let
$d=|I_{0}\setminus A|$. From the assumption of $A$, we have $d\leq\varepsilon
n$. We divide the proof into four cases.

Case 1: $m\leq d+3(c-1)$. In this case, we have $m\leq 4\varepsilon n$.
Similar to the proof of Lemma 5.2, we have

$k(m,A)\geq k(m,B)\geq k(m,I_{0})-d\geq s(m,I_{0})/2-\varepsilon
n\geq(n/2-m)/2-\varepsilon n\geq n/4-3\varepsilon n,$

which, together with Proposition 5.1(ii) and $\varepsilon\ll 1$, completes the
proof.

Case 2: $d+3(c-1)<m\leq\lceil n/2\rceil-d-3(c-1)$. Since $m\leq n/2$, each
nontrivial component of $L_{m}(I_{0})$ is a path, and there are
$\min\left\\{m,\lceil n/2\rceil-m\right\\}\geq d+3(c-1)$ of them. Therefore we
have

$k(m,A)\geq k(m,I_{0})-d\geq d+3(c-1)-d=3(c-1)$

which, together with Proposition 5.1(ii) and $c>1$, completes the proof.

Case 3: $\lceil n/2\rceil-d-3(c-1)<m\leq\lceil n/2\rceil-2(c-1)$. By the
choice of $m$, each nontrivial component of $L_{m}(A)$ is a path of length 1,
and the number of them is exactly

$s(m,[m+1,n])-|[m+1,n]\setminus A|=n-2m-(n-|A|-(m-1))=\lceil
n/2\rceil+(c-1)-m.$

Therefore, we obtain that

$k(m,A)=\lceil n/2\rceil+(c-1)-m\geq 3(c-1),$

which completes the proof together with Proposition 5.1(ii) and $c>1$.

Case 4: $\lceil n/2\rceil-2(c-1)<m\leq\lfloor n/2\rfloor-(c-1)$. Similarly as
in Case 3, we obtain that $k(m,A)=\lceil n/2\rceil+(c-1)-m$. By the choice of
$m$, for even $n$, we have $k(m,A)\geq 2(c-1)$, while for odd $n$, $k(m,A)\geq
2(c-1)+1$. By Proposition 5.1, this gives the desired upper bounds. ∎

###### Proof of Theorem 1.10..

Here we only prove (i) as the proof of (ii) is similar. If $|A|=\lceil
n/2\rceil+1$ and $A\neq I_{2}$, then $A$ must have at least one restricted
Schur triple, and therefore $g(A,r)<g(I_{2},r)=r^{\lceil n/2\rceil+1}$. When
$|A|>\lceil n/2\rceil+1$, choose a constant $\varepsilon\ll 1$, which
satisfies the assumptions of Lemmas 5.2 and 5.3. Then by Theorem 1.8, we can
further assume that $|A\bigtriangleup O|\leq\varepsilon n$, or
$|A\bigtriangleup I_{0}|\leq\varepsilon n$. Applying Lemmas 5.2 and 5.3(i) on
$A$, for both cases, we obtain $g(A,r)<r^{\lceil n/2\rceil+1}$. ∎

##  6 Concluding Remarks

Our investigation raises many open problems. In this paper, we determine the
rainbow $r$-extremal sets, that is, the subsets of $[n]$ which maximize the
number of rainbow sum-free $r$-colorings, for $r\leq 3$ and $r\geq 8$.
However, for $r\in\\{4,5,6,7\\}$, although Theorem 1.8 says the rainbow
$r$-extremal sets should be close to what we expect, our proofs cannot give
the exact structure of the extremal sets. Therefore, the most interesting
question is to determine the unsolved cases of Conjecture 1.9. Recall that
$I_{1}=[\frac{n}{2}-1,n]$ and $I_{3}=[\frac{n-1}{2},n]$.

######  Conjecture 6.1.

Let $n,r$ be positive integers and $4\leq r\leq 7$.

  1. (i)

If $n$ is even, then $g(n,r)=r^{n/2}\left(3-2/r\right)^{2}$, and $I_{1}$ is
the unique rainbow $r$-extremal set.

  2. (ii)

If $n$ is odd and $r=4$, then $g(n,r)=g([n],r)$, and $[n]$ is the unique
rainbow $r$-extremal set.

  3. (iii)

If $n$ is odd and $5\leq r\leq 7$, then $g(n,r)=r^{\lceil
n/2\rceil}\left(3-2/r\right)$, and $I_{3}$ is the unique rainbow $r$-extremal
set.

Another direction is that one can consider various generalization of this
problem. Recall that a sum-free set is a set forbidding the solutions of the
linear equation $x_{1}+x_{2}=y$. It is natural to extend the Erdős-Rothschild
problems on sets forbidding solutions of other linear equations, for example,
the $(k,\ell)$-free sets, that is, the sets without nontrivial tuples
$\\{x_{1},\ldots,x_{k},y_{1},\ldots,y_{\ell}\\}$ satisfying
$\sum_{i=1}^{k}x_{i}=\sum_{j=1}^{\ell}y_{j}$. It is possible that the method
used to prove Theorem 1.5 can prove the analogous results for some other
$(k,\ell)$-free sets. However, the stability analysis on other parts would be
very involved.

One could also broaden the study of rainbow Erdős-Rothschild problems to
various other extremal problems in this fashion. In the rainbow Erdős-
Rothchild problems studied to date, that is, the Gallai colorings and the
rainbow sum-free colorings, for $r=3$ the configurations maximizing the number
of such colorings are complete graphs or the whole intervals, while for
sufficiently large $r$ the optimal configurations are those solving the
original extremal problems. It would be very interesting to determine the
threshold of $r$ to ensure that the extremal configurations for the uncolored
problems are optimal for rainbow Erdős-Rothschild problems.

## Acknowledgements

This work was supported by the Natural Science Foundation of China (11871311,
11631014) and Shandong University multidisciplinary research and innovation
team of young scholars. Part of the work was done while the second and the
third authors were visiting the School of Mathematics at Shandong University.
They would like to thank the school for the hospitality they received.

## References

  * [1] N. Alon, J. Balogh, P. Keevash, and B. Sudakov.  The number of edge colorings with no monochromatic cliques.  Journal of the London Mathematical Society, 70(2):273–288, 2004\.
  * [2] J. Balogh.  A remark on the number of edge colorings of graphs.  European Journal of Combinatorics, 27(4):565–573, 2006.
  * [3] J. Balogh and L. Li.  The typical structure of gallai colorings and their extremal graphs.  SIAM Journal on Discrete Mathematics, 33(4):2416–2443, 2019.
  * [4] J. Balogh and J. Solymosi.  On the number of points in general position in the plane.  Discrete Analysis, page 4438, 2018.
  * [5] J. Balogh and A. Z. Wagner.  Further applications of the container method.  In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 191–213. Springer, 2016.
  * [6] F. S. Benevides, C. Hoppen, and R. M. Sampaio.  Edge-colorings of graphs avoiding complete graphs with a prescribed coloring.  Discrete Mathematics, 340(9):2143–2160, 2017.
  * [7] D. Clemens, S. Das, and T. Tran.  Colourings without monochromatic disjoint pairs.  European Journal of Combinatorics, 70:99–124, 2018.
  * [8] O. S. D. Král’ and L. Vena.  A combinatorial proof of the removal lemma for groups.  Journal of Combinatorial Theory, Series A, 116:971–978, 2009.
  * [9] S. Das, R. Glebov, B. Sudakov, and T. Tran.  Colouring set families without monochromatic k-chains.  Journal of Combinatorial Theory, Series A, 168:84–119, 2019.
  * [10] P. H. Diananda and H. P. Yap.  Maximal sum-free sets of elements of finite groups.  Proceedings of the Japan Academy, 45(1):1–5, 1969.
  * [11] P. Erdős.  Some new applications of probability methods to combinatorial analysis and graph theory.  University of Calgary, Department of Mathematics, Statistics and Computing Science, 1974.
  * [12] V. Falgas-Ravry, K. O’Connell, and A. Uzzell.  Multicolour containers, extremal entropy and counting.  Random Structures & Algorithms, 2018.
  * [13] B. Green.  A Szemerédi-type regularity lemma in abelian groups, with applications.  Geometric and Functional Analysis, 15:340–376, 2005.
  * [14] B. Green and I. Z. Ruzsa.  Sum-free sets in abelian groups.  Israel Journal of Mathematics, 147(1):157–188, 2005.
  * [15] H. Hàn and A. Jiménez.  Maximum number of sum-free colorings in finite abelian groups.  Israel Journal of Mathematics, 226(2):505–534, 2018.
  * [16] C. Hoppen, Y. Kohayakawa, and H. Lefmann.  Edge colourings of graphs avoiding monochromatic matchings of a given size.  Combinatorics, Probability and Computing, 21(1-2):203–218, 2012\.
  * [17] C. Hoppen, Y. Kohayakawa, and H. Lefmann.  Hypergraphs with many kneser colorings.  European Journal of Combinatorics, 33(5):816–843, 2012.
  * [18] C. Hoppen, Y. Kohayakawa, and H. Lefmann.  Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear turán number.  European Journal of Combinatorics, 35:354–373, 2014.
  * [19] C. Hoppen, Y. Kohayakawa, and H. Lefmann.  Edge-colorings of uniform hypergraphs avoiding monochromatic matchings.  Discrete Mathematics, 338(2):262–271, 2015.
  * [20] C. Hoppen and H. Lefmann.  Edge-colorings avoiding a fixed matching with a prescribed color pattern.  European Journal of Combinatorics, 47:75–94, 2015.
  * [21] C. Hoppen, H. Lefmann, and K. Odermann.  A rainbow Erdős-Rothschild problem.  Electronic Notes in Discrete Mathematics, 49:473–480, 2015.
  * [22] C. Hoppen, H. Lefmann, and K. Odermann.  A coloring problem for intersecting vector spaces.  Discrete Mathematics, 339(12):2941–2954, 2016.
  * [23] C. Hoppen, H. Lefmann, and K. Odermann.  On graphs with a large number of edge-colorings avoiding a rainbow triangle.  European Journal of Combinatorics, 66:168–190, 2017.
  * [24] C. Hoppen, H. Lefmann, and K. Odermann.  A rainbow Erdős-Rothschild problem.  SIAM Journal on Discrete Mathematics, 31(4):2647–2674, 2017.
  * [25] V. S. J. Deshouillers, G. Freiman and M. Temkin.  On the structure of sum-free sets ii.  Astérisque, 258:149–161, 1999.
  * [26] H. Lefmann and Y. Person.  Exact results on the number of restricted edge colorings for some families of linear hypergraphs.  Journal of Graph Theory, 73(1):1–31, 2013.
  * [27] H. Lefmann, Y. Person, V. Rödl, and M. Schacht.  On colourings of hypergraphs without monochromatic fano planes.  Combinatorics, Probability and Computing, 18(5):803–818, 2009.
  * [28] H. Lefmann, Y. Person, and M. Schacht.  A structural result for hypergraphs with many restricted edge colorings.  Journal of Combinatorics, 1(4):441–475, 2010.
  * [29] H. Liu, M. Sharifzadeh, and K. Staden.  On the maximum number of integer colourings with forbidden monochromatic sums.  arXiv preprint arXiv:1709.09589, 2017.
  * [30] O. Pikhurko and Z. B. Yilma.  The maximum number of $k_{3}$-free and $k_{4}$-free edge 4-colorings.  Journal of the London Mathematical Society, 85(3):593–615, 2012\.
  * [31] D. Saxton and A. Thomason.  Hypergraph containers.  Inventiones mathematicae, 201(3):925–992, 2015.
  * [32] K. Staden.  A note on the number of additive triples in subsets of integers.  2017\.
  * [33] T. Tao and V. Vu.  Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2010.
  * [34] R. Yuster.  The number of edge colorings with no monochromatic triangle.  Journal of Graph Theory, 21(4):441–452, 1996.