tailieunhanh - Báo cáo toán học: " Triangle Free Sets and Arithmetic Progressions – Two Pisier Type Problems'

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Triangle Free Sets and Arithmetic Progressions – Two Pisier Type Problems. | Triangle Free Sets and Arithmetic Progressions - Two Pisier Type Problems Dennis Davenport Department of Mathematics Miami University Oxford OH 45056 USA davenpde@ Neil Hindman Department of Mathematics Howard University Washington DC 20059 USA nhindman@ http nhindman Dona Strauss Department of Pure Mathematics University of Hull Hull HU6 7RX UK Submitted May 31 2001 Accepted May 2 2002. MR Subject Classification 05D10 Abstract Let Pf N be the set of finite nonempty subsets offl and for F G 2 Pf N write F G when maxF minG. Let X F G F G 2 Pf N and F Gg. A triangle in X is a set of the form F u H G F G F H u G g where F H G. Motivated by a question of Erdos Nesetril and Rodl regarding three term arithmetic progressions we show that any finite subset Y of X contains a relatively large triangle free subset. Exact values are obtained for the largest triangle free sets which can be guaranteed to exist in any set Y c X with n elements for all n 14. This author acknowledges support received from the National Science Foundation USA via grant DMS-0070593. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R22 1 1. Introduction. Our motivation for this study comes from a question of Erdos Nesetril and Rodl 1 Problem 2 p. 221 . Question. Do there exist e 0 and a subset X ofN such that 1 for every r 2 N if X ur 1 Ci then there exist i 2 1 2 . r and a d 2 N with a a d a 2d c Ci but 2 for every finite subset Y of X there exists Z c Y such that ZI e YI and Z does not contain any three term arithmetic progressions It is easy to see that Szemeredi s Theorem 8 or in fact only Roth s Theorem 6 7 implies that X N does not satisfy 2 of Question . Modifying a suggestion of Vitaly Bergelson we came to consider triangles in the following set X. Here Pf N F c N F 0 and F is finite and F G means that maxF min G. Definition. a X F G F G 2 Pf N and F G . b A triangle in X is a set of the form FuH G F G F HuG where F H G 2 Pf N