2013/11/12 by Xing Peng, Peng, Xing, Rafael Tesoro +3
Mathematics · #11B83 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:11B83
paper · pdf · doi:10.48550/arxiv.1311.2985
10 pages. arXiv admin note: text overlap with arXiv:1306.6044
arxiv created 2013/11/12 · arxiv updated 2013/11/14
Let Γ be an abelian group and g ≥ h ≥ 2 be integers. A set A ⊂ Γ is a Ch[g]-set if given any set X ⊂ Γ with |X| = k, and any set \ k1 , … , kg \ ⊂ Γ, at least one of the translates X+ ki is not contained in A. For any g ≥ h ≥ 2, we prove that if A ⊂ \1,2, … ,n \ is a Ch[g]-set in ℤ, then |A| ≤ (g-1)1/h n1 - 1/h + O(n1/2 - 1/2h). We show that for any integer n ≥ 1, there is a C3 [3]-set A ⊂ \1,2, … , n \ with |A| ≥ (4-2/3 + o(1)) n2/3. We also show that for any odd prime p, there is a C3[3]-set A ⊂ \mathbbFp3 with |A| ≥ p2 - p, which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer h ≥ 3, there is a Ch[h! +1]-set A ⊂ \1,2, … , n \ with |A| ≥ ( ch +o(1))n1-1/h. A set A is a weak Ch[g]-set if we add the condition that the translates X +k1, … , X + kg are all pairwise disjoint. We use the probabilistic method to construct weak Ch[g]-sets in \1,2, … , n \ for any g ≥ h ≥ 2. Lastly we obtain upper bounds on infinite Ch[g]-sequences. We prove that for any infinite Ch[g]-sequence A ⊂ ℕ, we have A(n) = O ( n1 - 1/h ( log n ) - 1/h ) for infinitely many n, where A(n) = | A ∩ \1,2, … , n \|.