Bounds on Arithmetic Rainbow Ramsey Multiplicities
Gabriel Elvin, Alexis Gonzales, Alejandro Rodriguez · 2026
Read Bounds on Arithmetic Rainbow Ramsey Multiplicities by Gabriel Elvin, Alexis Gonzales, Alejandro Rodriguez (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05442.txt.
Introduction
Gabriel Elvin and 3 co-authors study, in a 2026 combinatorics paper, how to maximize rainbow arithmetic progressions. A rainbow three-term progression has three numbers in equal spacing, each given a different color. The question is how to color the integers from one to n with three colors to create as many such progressions as possible.
The team proves a lower bound for that maximum on the ordinary integer range. They also give upper and lower bounds for the version played on integers modulo n, where counting wraps around. When n is a multiple of three, they find the exact maximum. The results add precision to Ramsey-type problems, which ask how structure must appear inside large colored sets.
Catalog record
| CREATOR | Gabriel Elvin, Alexis Gonzales, Alejandro Rodriguez |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05442
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bounds on Arithmetic Rainbow Ramsey Multiplicities Thanks: This work was supported by CSUSB’s Office of Student Research (OSR), the Proactive Approaches for Training in Hispanics in STEM grant (PATHS), and the Learning Aligned Employment Program (LAEP). Gabriel Elvin, Alexis Gonzales, Alejandro Rodriguez Abstract We study a quantitative Ramsey-type problem on 3 3 -term arithmetic progressions: how should the set of integers [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\dots,n\} be colored using 3 colors in order to maximize the number of rainbow 3-term arithmetic progressions? By rainbow , we mean progressions whose elements are each assigned a distinct color. We determine a lower bound for this question and upper and lower bounds when [ n ] [n] is replaced with the integers modulo n n , including an exact maximum when n n is a multiple of 3 3 . Keywords: Additive combinatorics; Ramsey theory; Ramsey multiplicities Mathematics Subject Classification (2020): 05D10 1 Introduction A classic starting point in Ramsey theory is the following. Consider coloring the edges of a complete graph K_{n} with 2 colors, either red or blue. What is the minimum n such that no matter the coloring, the K_{n} will contain a monochromatic triangle, i.e. a copy of K_{3} that has either all red edges or all blue edges? The answer is 6 , and importantly, if K_{3} is replaced by any fixed graph H , a monochromatic copy of H always exists, as long as n is made large enough, a famous result known as Ramsey’s Theorem [ 4 ] . Since such an n is guaranteed, we can ask a quantitative follow-up question: for very large n , what is the minimum number of monochromatic copies of H guaranteed in a 2-coloring of the edges of a K_{n} ? Or, to normalize, what is the minimum proportion , i.e. the number of monochromatic copies of H divided by the total number of copies H in the K_{n} ? A result of Goodman [ 3 ] in 1959 answers this question for H=K_{3} : as n\to\infty , the minimum proportion of monochromatic copies of K_{3} approaches 1/4 . Notably, if the edges of a K_{n} were colored uniformly randomly and independently, the expected proportion of monochromatic triangles also approaches 1/4 . Therefore, perhaps surprisingly, independently coloring the edges of K_{n} uniformly at random achieves the minimum proportion of monochromatic copies of K_{3} , at least asymptotically. This question can be generalized or altered in several ways. First, to reiterate, any fixed graph H can be investigated. Second, any fixed number of colors can be used. The asymptotic minimum for a graph is sometimes referred to as its Ramsey multiplicity , or the proportion after normalizing its Ramsey multiplicity constant , e.g. the Ramsey multiplicity constant of K_{3} is 1/4. These types of problems can be altered in another way: rather than attempt to minimize the number of monochromatic copies of H , one can attempt to maximize the number of rainbow copies of H . Here, H is rainbow if every edge is assigned a different color. Work in this area can be found in [ 1 , 7 , 8 ] . Further still, we need not be limited to graphs. Analogous to the question Goodman answered in 1959, the following was posed by Ron Graham (see [ 5 ] ) in 1996: If each element of the set [n]\coloneqq\{1,2,\dots,n\} is assigned a color, either red or blue, what is the minimum number of monochromatic solutions to the equation x+y=z ? By monochromatic solution , we mean a triple (x,y,x+y) such that either all elements are blue or all are red. Instinctively, one might guess that, analogous to Goodman’s result, the minimum proportion would again be 1/4 asymptotically. However, in 1998, Robertson and Zeilberger [ 5 ] showed that the minimum proportion, i.e. \frac{\text{\# of monochr. solns. to $x+y=z$}}{\text{\# of solutions to $x+y=z$}}, actually approaches 2/11 as n\to\infty 1 1 1 The authors did not directly compute this quantity, but it follows immediately from their result. . The correct analogy to Goodman’s result is to replace [n] with the integers modulo n , which we will denote by \mathbb{Z}_{n}=\{0,\dots,n-1\} (this analogy is in fact a correspondence; see [ 6 ] for more details). In this setting, as shown by Datskovsky [ 2 ] in 2003, the minimum proportion of monochromatic solutions to x+y=z is asymptotically 1/4 (in fact, it is exactly 1/4 when n is even and nearly so when n is odd). Just as with graphs, these questions can be expanded in many different directions by changing the equation, the number of colors, or the set of possible inputs, or by flipping the question from “minimizing monochromatic” to “maximizing rainbow”. In general, we are interested in showing that, for a given 3 -term equation, the maximum proportion of rainbow solutions (or minimum proportion of monochromatic solutions) is always asymptotically greater (or less) than what is expected from uniformly random colorings. We do this by providing explicit constructions which give lower bounds on the maximum (or upper bounds on the minimum). Next we introduce essential definitions and notation. By 3-term equation, we mean an equation of the form ax+by=cz , where a,b,c are positive integers. An r -coloring of a set X is a surjective function f:X\to[r] . A rainbow solution to an equation is a triple (x,y,z) that satisfies the equation and is such that each coordinate is assigned a different color, i.e. f(x)\neq f(y) , f(x)\neq f(z) , f(y)\neq f(z) . Let E be a shorthand for an equation ax+by=cz , X_{n}\in\{[n],\mathbb{Z}_{n}\} , and f be an r -coloring of X_{n} . Then • (solutions): T_{X_{n}}(E)\coloneqq\{(x,y,z)\in{X_{n}}^{3}\,:\,ax+by=cz\} , • (rainbow solutions): \text{Rb}_{f,X_{n}}(E)\coloneqq\{(x,y,z)\in T_{X_{n}}(E)\,:\,\text{$(x,y,z)$ is rainbow}\} , • (monochromatic solutions): \text{M}_{f,X_{n}}(E)\coloneqq\{(x,y,z)\in T_{X_{n}}(E)\,:\,f(x)=f(y)=f(z)\} • (rainbow proportion): \displaystyle\text{rb}_{f,X_{n}}(E)\coloneqq\frac{|\text{Rb}_{f,X_{n}}(E)|}{|T_{X_{n}}(E)|} , • (maximum rainbow proportion): \displaystyle\text{rb}_{X_{n}}(E)\coloneqq\max_{f:{X_{n}}\to[r]}\{\text{rb}_{f}(E)\} . We will omit “ X_{n} ” from subscripts when the choice of X_{n} is clear from context. Since our results are asymptotic, we will also cover the notation needed to precisely describe them. Let f and g be functions of n , the asymptotic variable. If there exists constants C and N such that |f(n)|\leq Cg(n) for all n\geq N , we say f=O(g) . By f=\Omega(g) , we mean g=O(f) . Lastly, If \lim_{n\to\infty}f/g=0 , then we say f=o(g) . In what follows, we restrict our analysis to 3 -term equations and 3 -colorings. Our main goal is to show that for certain equations, it is possible to find (sequences of) colorings that produce asymptotically more rainbow solutions than what is expected from uniformly random colorings. We capture this characteristic with the following definition: E is r -rainbow-uncommon over X_{n} if \liminf_{n\to\infty}\text{rb}_{X_{n}}(E)=\frac{2}{9}+\Omega(1). (1) Note that 2/9 is the (asymptotic) expected proportion of rainbow solutions to an equation when coloring uniformly at random: if a solution (x,y,z) , with x,y,z distinct 2 2 2 The solutions where x,y,z are not all distinct becomes a vanishing error term asymptotically. , is colored with 3 colors, there are 6 rainbow colorings out of 27 total colorings, and the asymptotic 2/9 proportion follows. The \Omega(1) term indicates we must be strictly above the 2/9 random threshold. A question