\documentclass[12pt]{article}% \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \usepackage{graphicx}% \setcounter{MaxMatrixCols}{30} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \begin{document} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A29} \vskip 40pt \begin{center} {\bf DISJUNCTIVE RADO NUMBERS FOR $x_1+x_2+c=x_3$} \vskip 20pt {\bf Dusty Sabo}\\ {\smallit Department of Mathematics, Southern Oregon University, Ashland, OR 97520 USA}\\ {\tt sabo@sou.edu}\\ \vskip 10pt {\bf Daniel Schaal}\\ {\smallit Department of Mathematics and Statistics, South Dakota State University, Brookings, SD 57007 USA}\\ {\tt daniel.schaal@sdstate.edu}\\ \vskip 10pt {\bf Jacent Tokaz}\\ {\smallit Department of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332 USA}\\ {\tt jtokaz@hotmail.com}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 10/19/05, Revised: 5/22/07, Accepted: 5/26/07, Published: 6/19/07} \vskip 30pt \centerline{\bf Abstract} \noindent 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,\ldots,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\leq k$. \ It is shown that \[ R(c,k)= \left\{ \begin{array} [c]{ccl}% 4c+5& \text{if }&c\leq k\leq c+1\text{ }\\ 3c+4& \text{if }&c+2\leq k \leq 3c+2\text{ }\\ k+2& \text{if }&3c+3\leq k \leq 4c+2\text{ }\\ 4c+5& \text{if }&4c+3\leq k. \text{ } \end{array} \right. % \] \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A29\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} \indent \indent Let $\mathbb{N}$ represent the set of natural numbers and let $[a,b]$ denote the set $\{n\in\mathbb{N},a\leq n\leq b\}$. A function $\Delta:[1,n]\rightarrow[0,t-1]$ is referred to as a $t$-$coloring$ of the set $[1,n]$. \ Given a $t$-coloring $\Delta$ and a system $L$ of linear equations or inequalities in $m$ variables, a solution $(x_1,x_2,\,\ldots\,,x_m)$ to the system $L$ is monochromatic if and only if \[ \Delta(x_1)=\Delta(x_2)=\,\cdots\,=\Delta(x_m).\] In 1916, I. Schur \lbrack 24\rbrack\ proved that for every $t\geq 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 \lbrack 25\rbrack. \ 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 \lbrack 6,$\,17$,$\,18$,$\,19$\rbrack. \ 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 \lbrack 4,$\,9$,$\,10$,$\,12$,$\,13$,$\,14$,$\,23$\rbrack. \ In \lbrack 5\rbrack\ 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\geq 0$. Recently several other problems related to Schur numbers and Rado numbers have been considered \lbrack 1,$\,2$,$\,3$,$\,7$,$\,8$,$\,16$,$\,20$,$\,21$,$\,22$\rbrack. \ Specifically, the concept of disjunctive Rado numbers (or disjunctive generalized Schur numbers) has recently been introduced \lbrack 11,$\,15$\rbrack. \ 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 \vspace*{0pt} \[ E(c):\,x_1+x_2+c=x_3 \text{ and } E(k):\,x_1+x_2+k=x_3\] \noindent for all natural numbers $c$ and $k$ where $c\leq k$. \ This disjunctive Rado number will be denoted by $R(c,k)$. \vskip 30pt \section*{\normalsize 2. Main Result} {\bf Theorem} For all natural numbers $c$ and $k$ where $c\leq k$, \[ R(c,k)= \left\{ \begin{array} [c]{ccl}% 4c+5& \text{if }&c\leq k\leq c+1\text{ }\\ 3c+4& \text{if }&c+2\leq k \leq 3c+2\text{ }\\ k+2& \text{if }&3c+3\leq k \leq 4c+2\text{ }\\ 4c+5& \text{if }&4c+3\leq k. \text{ } \end{array} \right. % \] \newpage \noindent {\it 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 $\Delta':[1,4c+4]\rightarrow[0,1]$ defined by \[ \Delta'(x)= \left\{ \begin{array} [c]{ccl}% 0 &\text{ } &1\leq x\leq c+1\\ 1 &\text{ } &c+2\leq x \leq 3c+3\\ 0 &\text{ } &3c+4\leq x \leq 4c+4.\\ \end{array} \right. % \] \noindent It is easy to check that the coloring $\Delta'$ avoids a monochromatic solution to $E(c)$, so every restriction of $\Delta'$ to a smaller domain does as well. \ We leave it to the reader to show that $\Delta'$ also avoids a monochromatic solution to $E(k)$ when $c\leq k\leq c+1$ or $4c+3\leq k$, that $\Delta'\!\mid_{[1,3c+3]}$ avoids a monochromatic solution to $E(k)$ when $c+2\leq k \leq 3c+2$ and that $\Delta'\!\mid_{[1,k+1]}$ avoids a monochromatic solution to $E(k)$ when $3c+3\leq k \leq 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\in[c,c+1]$ and $k\geq 4c+3$, the upper bound of $4c+5$ is already established. \ Hence we must consider only two cases.\\ \noindent \textbf{Case 1:} \ Assume that $k\in[c+2,3c+2]$. \ We will establish that %CASE 1 \[ R(c,k)\leq 3c+4.\] \noindent Assume by way of a contradiction that there exists a coloring $\Delta:[1,3c+4]\rightarrow[0,1]$ that does not admit a monochromatic solution to either $E(c)$ or $E(k)$. \ Without loss of generality we may assume that $\Delta(1)=0$, and so $\Delta(c+2)=1$ to avoid a monochromatic solution to $E(c)$. Let $s \leq c+2$ be the least integer such that $\Delta(s)= 1$. Thus it must be the case that $\Delta(2s+c)=0$. We now establish that for every $n\in[0,2c+4-2s]$ we have $\Delta(s+n)=1$ and $\Delta(2s+c+n)=0$. \indent To prove this we will use induction on $n$, with the case $n=0$ already established. We assume $\Delta(s+n_0)=1$ and $\Delta(2s+c+n_0)=0$ for some $n_0\in[0,2c+3-2s]$. Now, $\Delta(s-1)=0$ and $\Delta(2s+c+n_0)=0$, so $\Delta(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 $\Delta(s)=1$, we must have $\Delta(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] \cup [2s+c,3c+4]$ contains only elements of color $0$. For any $k\in[c+2,3c+2]$ there exist integers $x_1$ and $x_2 \in [1,s-1]$ and $x_3 \in [2s+c,3c+4]$ such that $x_1+x_2+k=x_3$. This is a contradiction. \\ \noindent \textbf{Case 2:} \ Assume that $k\in[3c+3,4c+2].\,\,$We will show that \vspace*{0pt} \[R(c,k)\leq k+2\] \noindent by showing that every coloring $\Delta:[1,k+2]\rightarrow[0,1]$ contains a monochromatic solution to either $E(c)$ or $E(k)$. Let a coloring $\Delta:[1,k+2]\rightarrow[0,1]$ be given. \ Without loss of generality we may assume that $\Delta(1)=0$. Then we may assume that $\Delta(c+2)=1$ and $\Delta(k+2)=1$ in order to avoid monochromatic solution to $E(c)$ and $E(k)$ respectively. \ Now, if $\Delta(3c+4)=1$, then $(c+2,c+2,3c+4)$ is a monochromatic solution to $E(c)$, so we may assume that $\Delta(3c+4)=0$. \ If $\Delta(2c+3)=0$, then $(1,2c+3,3c+4)$ is a monochromatic solution to $E(c)$, so we may assume that $\Delta(2c+3)=1$. \ If $\Delta(k-3c-1)=1$, then $(k-3c-1,2c+3,k+2)$ is a monochromatic solution to $E(c)$, so we may assume that $\Delta(k-3c-1)=0$. \ Finally, if $\Delta(k-2c)=0$, then $(1,k-3c-1,k-2c)$ is a monochromatic solution to $E(c)$, and if $\Delta(k-2c)=1$, then $(c+2,k-2c,k+2)$ is a monochromatic solution to $E(c)$. \ Therefore, every coloring $\Delta:[1,k+2]\rightarrow[0,1]$ contains a monochromatic solution to either $E(c)$ or $E(k)$. Hence, \vspace*{0pt} \[R(c,k)\leq k+2\] \noindent when $k\in[3c+3,4c+2]$ and the proof of the Theorem is complete. \vskip 20pt \noindent \normalsize \textbf{Acknowledgements} \normalsize \ 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. \noindent \section*{\normalsize References} %%%%%%%%%% references \footnotesize [1] {A. Bialostocki, G. Bialostocki, and D. Schaal, A zero-sum theorem, \textit\textit{Journal of Combinatorial Theory} Series. A vol 101 (2003), 147-152.} \noindent[2] {A. Bialostocki, P. Erd\"os, H. Lefmann, Monochromatic and zero-sum sets} {of nondecreasing diameter, \textit{Discrete Math.} 137 (1995), no. 1--3, 19--34.} \noindent[3] {A. Bialostocki, H. Lefmann, T. Meerdink, On the degree of regularity of} {some equations, Selected papers in honour of Paul Erd\"os on the occasion} {of his 80th birthday, (Keszthely, 1993), \textit{Discrete Math.} 150 (1996), no.} {1--3, 49--60.} \noindent[4] {A. Bialostocki, D. Schaal, On a Variation of Schur Numbers, \textit{Graphs and Combinatorics}, vol 16 (2000), 139-147.} \noindent[5] {S. Burr, S. Loo, On Rado Numbers I, preprint.} \noindent[6] {W. Deuber, Developments Based on Rado's Dissertation ``Studien zur Kombinatorik``, \textit{Survey in Combinatorics} (1989), 52-74, Cambridge University Press.} \noindent[7] {H. Harborth, S. Maasberg, Rado numbers for Fibonacci sequences and a} {problem of S. Rabinowitz, in: G. E. Bergum at al., eds., \textit{Applications of Fibonacci Numbers}, Vol. 6 (Cluwer Acad. Publ.) 143-153.} \noindent[8] {H. Harborth, S. Maasberg, Rado numbers for homogeneous second order} {linear recurrences - degree of partition regularity, \textit{Congressus Numerantium}, Vol 108 (1995), 109-118.} \noindent[9] {H. Harborth, S. Maasberg, Rado numbers for $a(x+y)=bz$, \textit{Journal of Combinatorial Theory} Series A, Vol. 80, num. 2 (1997), 356-363.} \noindent[10] {H. Harborth, S. Maasberg, All two-color Rado numbers for} {$a(x+y)=bz$, \textit{Discrete Math.}, 197/198 (1999), 397-407.} \noindent[11] {B. Johnson, D. Schaal, Disjunctive Rado Numbers, \textit{Journal of Combinatorial Theory} Series A, Vol 112, num. 2 (2005), 263-276.} \noindent[12] {S. Jones, D. Schaal, Some 2-color Rado numbers, \textit{Congressus Numerantium}, 152 (2001), 197-199.} \noindent[13] {S. Jones, D. Schaal, A class of two-color Rado numbers, \textit{Discrete Mathematics}, 289 (2004), no. 1-3, 63-69.} \noindent[14] {W. Kosek, D. Schaal, Rado Numbers for the equation $\sum_{i=1}^{m-1}x_i+c=x_m$ for negative values of $c$, \textit{Advances in Applied Mathematics}, vol 27 (2001), 805-815.} \noindent[15] {W. Kosek, D. Schaal, A Note on Disjunctive Rado Numbers,\textit{Advances in Applied Mathematics}, vol. 31 (2003), iss. 2, 433-439. } \noindent[16] {B. Landman, A. Roberton, On Generalized Van der Waerden Triples, \textit{Discrete Mathematics}, 256 (2002), 279-290.} \noindent[17] {R. Rado, Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein Problem der Zahlentheorie, \textit{Sonderausg. Sitzungsber. Preuss. Akad. Wiss. Phys.- Math. Klasse}, 17 (1933), 1-10.} \noindent[18] {R. Rado, Studien zur Kombinatorik, \textit{Math. Z.} 36 (1933), 242-280.} \noindent[19] {R. Rado, Note on Combinatorial Analysis, \textit{Proc. London Math. Soc.} 48 (1936), 122-160.} \noindent[20] {A. Robertson, D. Schaal, Off-Diagonal Generalized Schur Numbers, \textit{Advances in Applied Mathematics}, vol. 26 (2001), 252-257.} \noindent[21] {A. Robertson, Difference Ramsey Numbers and Issai Numbers, \textit{Advances in Applied Mathematics}, 25 (2000), 153-162.} \noindent[22] {A. Robertson, D. Zeilberger, A 2-Coloring of \lbrack 1,N\rbrack\ Can Have N$^2$/22 + O(N) Monochromatic Schur Triples, But Not Less!, \textit{Electronic Journal of Combinatorics} 5 (1998), R19.} \noindent[23] D. Schaal, On Generalized Schur Numbers, \textit{Congressus Numerantium}, {vol. 98 (1993), 178-187.} \noindent[24] {I. Schur, \"Uber die Kongruenz $x^m+y^m\equiv z^m($mod $p)$. \textit{Jahresber. Deutsch. Math. Verein.} 25 (1916), 114-117.} \noindent[25] {W. Wallis, A. Street, J. Wallis, Combinatorics: Room Squares, Sum-free} {Sets, Hadamard Matrices, \textit{Lecture Notes in Math.}, vol. 292, Springer-} {Verlag, Berlin and New York, 1972.} \end{document}