Exact rainbow-extremal sets for restricted sum-free colorings

About 9 years old · traced to

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)=max⁡A⊆[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=[n2−1,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=[n−12,n].I_3=\left[\frac{n-1}{2},n\right].

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

g(n,r)=rn/2(3−2r)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 r≥8r\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 r≥5r\geq5, then

g(n,r)=r⌈n/2⌉(3−2r),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 r≤3r\leq3 and r≥8r\geq8; the exact structure remains unresolved for 4≤r≤74\leq r\leq7, making these cases the central open part of the conjecture.

References

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.