Abstract
Letm ≥ 3 andk ≥ 1 be two given integers. Asub-k-coloring of [n] = {1, 2,...,n} is an assignment of colors to the numbers of [n] in which each color is used at mostk times. Call an\(S \subseteq [n]\) arainbow set if no two of its elements have the same color. Thesub-k-Ramsey number sr(m, k) is defined as the minimumn such that every sub-k-coloring of [n] contains a rainbow arithmetic progression ofm terms. We prove thatΩ((k − 1)m 2/logmk) ≤ sr(m, k) ≤ O((k − 1)m 2 logmk) asm → ∞, and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Caro, Y.: Extremal problems concerning transformations of the set of edges of the complete graph. Europ. J. Comb.7, 93–104 (1986)
Alon, N., Caro, Y., Rödl, V., Tuza, Zs.: paper in preparation
Caro, Y.: Extremal problems concerning transformations of the edges of the complete hypergraphs. J. Graph Theory11, 25–37 (1987)
Davenport, H.: Multiplicative Number Theory. 2nd ed., revised by H.L. Montgomery. Berlin: Springer-Verlag 1980
Erdös, P.: My joint work with Richard Rado. In: Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Math. Soc. Lecture Notes Ser. Vol. 123, pp. 53–80. Cambridge University Press 1987
Erdös, P., Hajnal, A.: On the structure of set mappings. Acta Math. Acad. Sci. Hung.9, 111–131 (1958)
Szemerédi, E.: On sets of integers containing nok elements in arithmetic progression. Acta Arith.27, 199–245 (1975)
van der Waerden, B.L.: Beweis einer Baudetschen Vermutung. Nieuw. Arch. Wiskd.15, 212–216 (1927)
Author information
Authors and Affiliations
Additional information
Research supported in part by Allon Fellowship and by a Bat Sheva de-Rothschild grant.
Research supported in part by the “AKA” Research Fund of the Hungarian Academy of Sciences, grant No. 1-3-86-264.
Rights and permissions
About this article
Cite this article
Alon, N., Caro, Y. & Tuza, Z. Sub-Ramsey numbers for arithmetic progressions. Graphs and Combinatorics 5, 307–314 (1989). https://doi.org/10.1007/BF01788685
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01788685