×

On the density of integral sets with missing differences from sets related to arithmetic progressions. (English) Zbl 1229.11044

Given a set \(M\) of positive integer, a set \(S\) of non-negative integers is said to be an \(M\)-set if \(a\in S\) and \(b\in S\) imply \(a-b\notin M\). In an unpublished problem collection T. S. Motzkin asks for determining the quantity \(\mu(M)=\bar{\delta}(S)\) where \(S\) varies over all \(M\)-sets and \(\bar{\delta}(S)\) stands for the upper asymptotic density. In the case \(|M|\leq2\) the problem was completely solved by D. G. Cantor and B. Gordon [J. Comb. Theory, Ser. A 14, 281–287 (1973; Zbl 0277.10043)], and there are known partial answers for several families of \(M\) with \(|M|\geq 3\). In the present paper some cases when \(M\) either contains an arithmetic progression or is contained in an arithmetic progression are settled.

MSC:

11B83 Special sequences and polynomials
11B05 Density, gaps, topology
11B25 Arithmetic progressions

Citations:

Zbl 0277.10043
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bienia, W.; Goddyn, L.; Gvozdjak, P.; Sebö, A.; Tarsi, M., Flows, view obstructions and the lonely runner, J. Combin. Theory Ser. B, 72, 1-9 (1998) · Zbl 0910.05064
[2] Barajas, J.; Serra, O., The lonely runner with seven runners, Electron. J. Combin., 15 (2008), Research paper 48, 18 pp · Zbl 1206.11030
[3] Cantor, D. G.; Gordon, B., Sequences of integers with missing differences, J. Combin. Theory Ser. A, 14, 281-287 (1973) · Zbl 0277.10043
[4] Chang, G. J.; Huang, L.; Zhu, X., The circular chromatic numbers and the fractional chromatic numbers of distance graphs, European J. Combin., 19, 423-431 (1998) · Zbl 0905.05032
[5] Chang, G.; Liu, D.; Zhu, X., Distance graphs and \(T\)-colorings, J. Combin. Theory Ser. B, 75, 159-169 (1999)
[6] Cusick, T. W., View-obstruction problems in \(n\)-dimensional geometry, J. Combin. Theory Ser. A, 16, 1-11 (1974) · Zbl 0273.10025
[7] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Coloring the real line, J. Combin. Theory Ser. B, 39, 86-100 (1985) · Zbl 0549.05029
[8] Griggs, J. R.; Liu, D.-D. F., The channel assignment problem for mutually adjacent sites, J. Combin. Theory Ser. A, 68, 169-183 (1994) · Zbl 0816.05027
[9] Gupta, S.; Tripathi, A., Density of \(M\)-sets in arithmetic progression, Acta Arith., 89, 3, 255-257 (1999) · Zbl 0932.11009
[10] Hale, W. K., Frequency assignment: theory and applications, Proc. IEEE, 68, 310-320 (1980)
[11] Haralambis, N. M., Sets of integers with missing differences, J. Combin. Theory Ser. A, 23, 22-33 (1977) · Zbl 0359.10047
[12] Kemnitz, A.; Kolberg, H., Coloring of integer distance graphs, Discrete Math., 191, 113-123 (1998) · Zbl 0956.05044
[13] Lam, P.; Lin, W., Coloring distance graphs with intervals as distance sets, European J. Combin., 26, 1216-1229 (2005) · Zbl 1082.05038
[14] Liu, D.-D. F.; Zhu, X., Fractional chromatic number for distance graphs with large clique size, J. Graph Theory, 47, 129-146 (2004) · Zbl 1055.05059
[15] Liu, D. D.-F.; Zhu, X., Fractional chromatic number of distance graphs generated by two-interval sets, European J. Combin., 29, 7, 1733-1742 (2008) · Zbl 1246.05058
[16] T.S. Motzkin, Unpublished problem collection.; T.S. Motzkin, Unpublished problem collection.
[17] R.K. Pandey, Some results on the density of integral sets with missing differences, PhD thesis, Department of Mathematics, Indian Institute of Technology, Delhi, 2008.; R.K. Pandey, Some results on the density of integral sets with missing differences, PhD thesis, Department of Mathematics, Indian Institute of Technology, Delhi, 2008.
[18] Rabinowitz, J. H.; Proulx, V. K., An asymptotic approach to the channel assignment problem, SIAM J. Alg. Disc. Methods, 6, 507-518 (1985) · Zbl 0579.05058
[19] Wills, J. M., Zwei Sätze uber inhomogene diophantische approximation von irrationalzahlen, Monatsh. Math., 71, 263-269 (1967) · Zbl 0148.27505
[20] Wu, J.; Lin, W., Circular chromatic numbers and fractional chromatic numbers of distance graphs with distance sets missing an interval, Ars Combin., 70, 161-168 (2004) · Zbl 1093.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.