Exact rainbow-extremal sets for restricted sum-free colorings

Let [n]={1,,n}[n]=\{1,\ldots,n\}. For a subset A[n]A\subseteq[n], let g(A,r)g(A,r) denote the number of rainbow sum-free rr-colorings of AA, and let g(n,r)=maxA[n]g(A,r)g(n,r)=\max_{A\subseteq[n]}g(A,r). A set attaining this maximum is called a rainbow rr-extremal set. For even nn, define

I1=[n21,n],I2=[n2,n],I_1=\left[\frac{n}{2}-1,n\right],\qquad I_2=\left[\frac{n}{2},n\right],

and for odd nn define

I3=[n12,n].I_3=\left[\frac{n-1}{2},n\right].

Exact-extremal-set conjecture. Let n,rn,r be positive integers with r4r\geq4. If nn is even and r7r\leq7, then

g(n,r)=rn/2(32r)2,g(n,r)=r^{n/2}\left(3-\frac{2}{r}\right)^2,

and I1I_1 is the unique rainbow rr-extremal set. If nn is even and r8r\geq8, then g(n,r)=rn/2+1g(n,r)=r^{n/2+1}, and I2I_2 is the unique rainbow rr-extremal set. If nn is odd and r=4r=4, then g(n,r)=g([n],r)g(n,r)=g([n],r), and [n][n] is the unique rainbow rr-extremal set. If nn is odd and r5r\geq5, then

g(n,r)=rn/2(32r),g(n,r)=r^{\lceil n/2\rceil}\left(3-\frac{2}{r}\right),

and I3I_3 is the unique rainbow rr-extremal set.

The paper proves the corresponding extremal results for r3r\leq3 and r8r\geq8; the exact structure remains unresolved for 4r74\leq r\leq7, making these cases the central open part of the conjecture.

Sources & referencesView supporting material

Primary source

Yangyang Cheng, Yifan Jing, Lina Li, Guanghui Wang and Wenling Zhou, “Integer colorings with forbidden rainbow sums”, arXiv:2005.14384 (2023).

Additional references

2 papers in this index state this conjecture (2017–2020). The statement above is taken from the most recent of them; the others are arXiv:1710.08025.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.