Sub-Ramsey numbers for arithmetic progressions |
| |
Authors: | Noga Alon Yair Caro Zsolt Tuza |
| |
Affiliation: | (1) Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, 69978 Ramat-Aviv, Tel Aviv, Israel;(2) Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary |
| |
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 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)m2/logmk) sr(m, k) O((k – 1)m2 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.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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|