INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A29

DISJUNCTIVE RADO NUMBERS FOR x_{1} + x_{2} + c = x_{3}

Dusty Sabo

Department of Mathematics, Southern Oregon University, Ashland, OR 97520 USA

                               sabo@sou.edu

Daniel Schaal

Department of Mathematics and Statistics, South Dakota State University, Brookings, SD 57007 USA

                         daniel.schaal@sdstate.edu

Jacent Tokaz

Department of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332 USA

                            jtokaz@hotmail.com

Received: 10/19/05, Revised: 5/22/07, Accepted: 5/26/07, Published: 6/19/07

Abstract

Given two equations E_{1} and E_{2}, the disjunctive Rado number for E_{1} and E_{2} is the least integer n, provided that it exists, such that for every coloring of the set {1, 2, …, n} with two colors there exists a monochromatic solution to either E_{1} or E_{2}. If no such integer n exists, then the disjunctive Rado number for E_{1} and E_{2} is infinite. Let R(c, k) represent the disjunctive Rado number for the equations x_{1} + x_{2} + c = x_{3} and x_{1} + x_{2} + k = x_{3}. In this paper the values of R(c, k) are found for all natural numbers c and k where c ≤ k. It is shown that

R(c, k) = \{ \begin{matrix}4c + 5 & if & c ≤ k ≤ c + 1 \\ 3c + 4 & if & c + 2 ≤ k ≤ 3c + 2 \\ k + 2 & if & 3c + 3 ≤ k ≤ 4c + 2 \\ 4c + 5 & if & 4c + 3 ≤ k. \end{matrix}

1. Introduction

Let ℕ represent the set of natural numbers and let [a, b] denote the set {n ∈ ℕ, a ≤ n ≤ b}. A function Δ : [1, n] → [0, t − 1] is referred to as a t-coloring of the set [1, n]. Given a t-coloring Δ and a system L of linear equations or inequalities in m variables, a solution (x_{1}, x_{2}, …, x_{m}) to the system L is monochromatic if and only if

Δ(x_{1}) = Δ(x_{2}) = ⋯ = Δ(x_{m}).

In 1916, I. Schur [24] proved that for every t ≥ 2, there exists a least integer n = S(t) such that for every t-coloring of the set [1, n], there exists a monochromatic solution to x_{1} + x_{2} = x_{3}. The integers S(t) are called Schur numbers. It is known that S(2) = 5, S(3) = 14 and S(4) = 45, but no other Schur numbers are known [25]. In 1933, R. Rado generalized the concept of Schur numbers to arbitrary systems of linear equations. Rado found necessary and sufficient conditions to determine if an arbitrary system of linear equations admits a monochromatic solution under every t-coloring of the natural numbers [6, 17, 18, 19]. For a given system L of linear equations, the least integer n, provided that it exists, such that for every t-coloring of the set [1, n] there exists a monochromatic solution to L is called the t-color Rado number (or t-color generalized Schur number) for the system L. If such an integer n does not exist, then the t-color Rado number for the system L is infinite. In recent years the exact Rado numbers for several families of equations and inequalities have been found [4, 9, 10, 12, 13, 14, 23]. In [5] it was determined that the 2-color Rado number for the equation E(c) : x_{1} + x_{2} + c = x_{3} is 4c + 5 for every integer c ≥ 0.

Recently several other problems related to Schur numbers and Rado numbers have been considered [1, 2, 3, 7, 8, 16, 20, 21, 22]. Specifically, the concept of disjunctive Rado numbers (or disjunctive generalized Schur numbers) has recently been introduced [11, 15]. Given a set L of linear equations, the least integer n, provided that it exists, such that for every 2-coloring of the set [1, n] there exists a monochromatic solution to at least one equation in L is called the disjunctive Rado number for the set L. If such an integer n does not exist, then the disjunctive Rado number for the set L is infinite. Given a set of linear equations, it is clear that the disjunctive Rado number for this set is less than or equal to the 2-color Rado number for each equation in the set.

In this paper, the disjunctive Rado numbers are determined for the set consisting of the two equations

E(c) : x_{1} + x_{2} + c = x_{3} and E(k) : x_{1} + x_{2} + k = x_{3}

for all natural numbers c and k where c ≤ k. This disjunctive Rado number will be denoted by R(c, k).

2. Main Result

Theorem For all natural numbers c and k where c ≤ k,

R(c, k) = \{ \begin{matrix}4c + 5 & if & c ≤ k ≤ c + 1 \\ 3c + 4 & if & c + 2 ≤ k ≤ 3c + 2 \\ k + 2 & if & 3c + 3 ≤ k ≤ 4c + 2 \\ 4c + 5 & if & 4c + 3 ≤ k. \end{matrix}

Proof. It should be noted that the third interval in the expression of R(c, k) could be expanded to include the values of k = 3c+2 and k = 4c+3 without changing the expression.

The lower bounds can be established by exhibiting a coloring that avoids a monochromatic solution to both E(c) and E(k) for each of the intervals in the expression of R(c, k). Consider the coloring Δ′ : [1, 4c + 4] → [0, 1] defined by

Δ′(x) = \{ \begin{matrix}0 & 1 ≤ x ≤ c + 1 \\ 1 & c + 2 ≤ x ≤ 3c + 3 \\ 0 & 3c + 4 ≤ x ≤ 4c + 4. \end{matrix}

It is easy to check that the coloring Δ′ avoids a monochromatic solution to E(c), so every restriction of Δ′ to a smaller domain does as well. We leave it to the reader to show that Δ′ also avoids a monochromatic solution to E(k) when c ≤ k ≤ c + 1 or 4c + 3 ≤ k, that Δ′ |_{[1,3c+3]} avoids a monochromatic solution to E(k) when c + 2 ≤ k ≤ 3c + 2 and that Δ′ |_{[1,k+1]} avoids a monochromatic solution to E(k) when 3c + 3 ≤ k ≤ 4c + 2.

We shall now establish upper bounds for R(c, k). As was mentioned in the introduction, every 2-coloring of the set [1, 4c + 5] contains a monochromatic solution to E(c), so for the cases k ∈ [c, c + 1] and k ≥ 4c + 3, the upper bound of 4c + 5 is already established. Hence we must consider only two cases.

Case 1: Assume that k ∈ [c + 2, 3c + 2]. We will establish that

R(c, k) ≤ 3c + 4.

Assume by way of a contradiction that there exists a coloring Δ : [1, 3c + 4] → [0, 1] that does not admit a monochromatic solution to either E(c) or E(k). Without loss of generality we may assume that Δ(1) = 0, and so Δ(c + 2) = 1 to avoid a monochromatic solution to E(c). Let s ≤ c + 2 be the least integer such that Δ(s) = 1. Thus it must be the case that Δ(2s + c) = 0. We now establish that for every n ∈ [0, 2c + 4 − 2s] we have Δ(s + n) = 1 and Δ(2s + c + n) = 0. To prove this we will use induction on n, with the case n = 0 already established. We assume Δ(s + n_{0}) = 1 and Δ(2s + c + n_{0}) = 0 for some n_{0} ∈ [0, 2c + 3 − 2s]. Now, Δ(s − 1) = 0 and Δ(2s + c + n_{0}) = 0, so Δ(s + n_{0} + 1) = 1 or else (s − 1, s + n_{0} + 1, 2s + c + n_{0}) would be a monchromatic solution to E(c). Also, since Δ(s) = 1, we must have Δ(2s + c + n_{0} + 1) = 0 or else (s, s + n_{0} + 1, 2s + c + n_{0} + 1) would be a monchromatic solution to E(c).

Now, by the inductive result we have that [1, s − 1] ∪ [2s + c, 3c + 4] contains only elements of color 0. For any k ∈ [c + 2, 3c + 2] there exist integers x_{1} and x_{2} ∈ [1, s − 1] and x_{3} ∈ [2s + c, 3c + 4] such that x_{1} + x_{2} + k = x_{3}. This is a contradiction.

Case 2: Assume that k ∈ [3c + 3, 4c + 2]. We will show that

R(c, k) ≤ k + 2

by showing that every coloring Δ : [1, k + 2] → [0, 1] contains a monochromatic solution to either E(c) or E(k).

Let a coloring Δ : [1, k + 2] → [0, 1] be given. Without loss of generality we may assume that Δ(1) = 0. Then we may assume that Δ(c + 2) = 1 and Δ(k + 2) = 1 in order to avoid monochromatic solution to E(c) and E(k) respectively. Now, if Δ(3c + 4) = 1, then (c+2, c+2, 3c+4) is a monochromatic solution to E(c), so we may assume that Δ(3c+4) = 0. If Δ(2c + 3) = 0, then (1, 2c + 3, 3c + 4) is a monochromatic solution to E(c), so we may assume that Δ(2c + 3) = 1. If Δ(k − 3c − 1) = 1, then (k − 3c − 1, 2c + 3, k + 2) is a monochromatic solution to E(c), so we may assume that Δ(k − 3c − 1) = 0. Finally, if Δ(k − 2c) = 0, then (1, k − 3c − 1, k − 2c) is a monochromatic solution to E(c), and if Δ(k − 2c) = 1, then (c + 2, k − 2c, k + 2) is a monochromatic solution to E(c). Therefore, every coloring Δ : [1, k + 2] → [0, 1] contains a monochromatic solution to either E(c) or E(k). Hence,

R(c, k) ≤ k + 2

when k ∈ [3c + 3, 4c + 2] and the proof of the Theorem is complete.

Acknowledgements

This material is partially based upon work supported by the National Science Foundation Grant #DMS-9820520 and the University of Idaho REU. This work was also supported by a South Dakota Governor’s 2010 Individual Research Seed Grant.

References

[1] A. Bialostocki, G. Bialostocki, and D. Schaal, A zero-sum theorem, Journal of Combinatorial Theory Series. A vol 101 (2003), 147-152.

[2] A. Bialostocki, P. Erdös, H. Lefmann, Monochromatic and zero-sum sets of nondecreasing diameter, Discrete Math. 137 (1995), no. 1–3, 19–34.

[3] A. Bialostocki, H. Lefmann, T. Meerdink, On the degree of regularity of some equations, Selected papers in honour of Paul Erdös on the occasion of his 80th birthday, (Keszthely, 1993), Discrete Math. 150 (1996), no. 1–3, 49–60.

[4] A. Bialostocki, D. Schaal, On a Variation of Schur Numbers, Graphs and Combinatorics, vol 16 (2000), 139-147.

[5] S. Burr, S. Loo, On Rado Numbers I, preprint.

[6] W. Deuber, Developments Based on Rado’s Dissertation “Studien zur Kombinatorik“, Survey in Combinatorics (1989), 52-74, Cambridge University Press.

[7] H. Harborth, S. Maasberg, Rado numbers for Fibonacci sequences and a problem of S. Rabinowitz, in: G. E. Bergum at al., eds., Applications of Fibonacci Numbers, Vol. 6 (Cluwer Acad. Publ.) 143-153.

[8] H. Harborth, S. Maasberg, Rado numbers for homogeneous second order linear recurrences - degree of partition regularity, Congressus Numerantium, Vol 108 (1995), 109-118.

[9] H. Harborth, S. Maasberg, Rado numbers for a(x + y) = bz, Journal of Combinatorial Theory Series A, Vol. 80, num. 2 (1997), 356-363.

[10] H. Harborth, S. Maasberg, All two-color Rado numbers for a(x + y) = bz, Discrete Math., 197/198 (1999), 397-407.

[11] B. Johnson, D. Schaal, Disjunctive Rado Numbers, Journal of Combinatorial Theory Series A, Vol 112, num. 2 (2005), 263-276.

[12] S. Jones, D. Schaal, Some 2-color Rado numbers, Congressus Numerantium, 152 (2001), 197-199.

[13] S. Jones, D. Schaal, A class of two-color Rado numbers, Discrete Mathematics, 289 (2004), no. 1-3, 63-69.

[14] W. Kosek, D. Schaal, Rado Numbers for the equation ∑_{i=1}^{m−1} x_{i} + c = x_{m} for negative values of c, Advances in Applied Mathematics, vol 27 (2001), 805-815.

[15] W. Kosek, D. Schaal, A Note on Disjunctive Rado Numbers,Advances in Applied Mathematics, vol. 31 (2003), iss. 2, 433-439.

[16] B. Landman, A. Roberton, On Generalized Van der Waerden Triples, Discrete Mathematics, 256 (2002), 279-290.

[17] R. Rado, Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein Problem der Zahlentheorie, Sonderausg. Sitzungsber. Preuss. Akad. Wiss. Phys.- Math. Klasse, 17 (1933), 1-10.

[18] R. Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), 242-280.

[19] R. Rado, Note on Combinatorial Analysis, Proc. London Math. Soc. 48 (1936), 122-160.

[20] A. Robertson, D. Schaal, Off-Diagonal Generalized Schur Numbers, Advances in Applied Mathematics, vol. 26 (2001), 252-257.

[21] A. Robertson, Difference Ramsey Numbers and Issai Numbers, Advances in Applied Mathematics, 25 (2000), 153-162.

[22] A. Robertson, D. Zeilberger, A 2-Coloring of [1,N] Can Have N^{2}/22 + O(N) Monochromatic Schur Triples, But Not Less!, Electronic Journal of Combinatorics 5 (1998), R19.

[23] D. Schaal, On Generalized Schur Numbers, Congressus Numerantium, vol. 98 (1993), 178-187.

[24] I. Schur, Über die Kongruenz x^{m} + y^{m} ≡ z^{m}(mod p). Jahresber. Deutsch. Math. Verein. 25 (1916), 114-117.

[25] W. Wallis, A. Street, J. Wallis, Combinatorics: Room Squares, Sum-free Sets, Hadamard Matrices, Lecture Notes in Math., vol. 292, Springer- Verlag, Berlin and New York, 1972.