CERTAIN RESULTS ON THE MAXIMAL DENSITY OF SETS WITH MISSING DIFFERENCES FROM A GIVEN SET

Abstract

This thesis deals with a well-known problem posed by T. S. Motzkin asking \How dense can a set S of positive integers be, if no two elements of S are allowed to di er by an element of M?" For studying the structure of a set of positive integers, many types of densities on the sets are de ned. Among them the most common density is the asymptotic density, also known as natural density. Let S be any set of non-negative integers and let S(x) denote the number of elements n 2 S such that 1 n x; x 2 R: We de ne the upper and lower densities of S, denoted respectively by (S) and (S), as follows: (S) = lim sup x!1 S(x) x ; (S) = lim inf x!1 S(x) x : If (S)= (S)= (S); then we say that S has density (S): Let M be a given set of positive integers. A set S of non-negative integers is said to be an M-set if a; b 2 S implies a 􀀀 b =2 M. In this thesis, the main parameter of interest is the maximal density of an M-set, de ned by (M) := sup (S); where the supremum is taken over all M-sets S: In an unpublished problem collection [28], Motzkin asked to determine the maximal density (M) for a given set M: In 1973, Cantor and Gordon [5] proved that for a nite set M; (M) exists and is a rational number in the interval (0; 1 2 ]: This number theory problem becomes more interesting due to its connection with other problems of Mathematics. Motzkin's maximal density problem is closely related to several coloring parameters of the distance graph generated by M. The very rst work on maximal density is due to Cantor and Gordon [5] in 1973;in which they found a formula for (M) when jMj 2. In 1977; Haralambis [17] studied (M) for some sets of the families f1; x; yg and f1; 2; x; yg. For the general set M of three elements, Gupta [15] provided a lower bound. Furthermore, the author gave a lower bound for (M) for M = fx; y; x + yg: There is no general formula when jMj 3: Using some coloring problems in Graph Theory, Liu and Zhu [25] in 2004, gave values for all types of almost di erence closed sets (de ned at page 69 of the present thesis) except in a single case. In 2008; [26] they also found the value of (M) when M is the union of two intervals. Later on, Pandey [30; 34] in his thesis, investigated the value of (M) for several three-element families and some four-element families. In 2011; Pandey and Tripathi [35] also found bounds for (M) when M is either contained in an arithmetic progression or contains an arithmetic progression. This thesis is split into seven chapters. The rst chapter includes the literature survey and important de nitions. From Chapter 2 onwards, our main focus is to nd exact values or bounds for (M) for some families of nite sets M. More precisely, we study the three-element family M = fa; b; e(a+b)+rg; when 0 r a+b􀀀1; and calculate bounds on (M); which improve the lower bounds of (M) given by Gupta [15]. The four-element families considered are: M = fa; b; b 􀀀 a; e(a + b)g; M = fa; b; a+b; e(b􀀀a)g; M = fa; b; a+b; e(a+b)g and M = fa; b; b􀀀a; e(b􀀀a)g with a < b: These four-element families extend the family fa; b; a + bg discussed earlier by several authors. Also these results generalize the four-element family M = fa; b; a + b; b 􀀀 ag by Liu and Zhu [25] in some cases. Furthermore, we study (M) for the other families of the set of four-element M = fa; a + 1; 2a + 1; ng and ve-element M = fa; a + 1; 2a + 1; 3a + 1; ng; which generalize the results of Pandey and Srivastava [32] for the family M = fa; a + 1; xg: We also study some partial results about the bounds of (M) for the general family M = fa; a+1; 2a+ 1; : : : ; (s 􀀀 2)a + 1; ng, where s 5. We validate the lonely runner conjecture for this general family. Furthermore, for the four-elements families, we discuss related vertex coloring parameters of distance graphs generated by these families. Finally, we conclude the thesis in Chapter 7, with some remarks and future scope.