Monochromatic Progressions in Random Colorings

2011/06/04 by Vijay, Sujith
#05D10 #11B25 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1106.0793

Abstract

Let N⁺(k)= 2^k/2 k^3/2 f(k) and N^-(k)= 2^k/2 k^1/2 g(k) where 1=o(f(k)) and g(k)=o(1). We show that the probability of a random 2-coloring of 1,2,...,N⁺(k) containing a monochromatic k-term arithmetic progression approaches 1, and the probability of a random 2-coloring of 1,2,...,N^-(k) containing a monochromatic k-term arithmetic progression approaches 0, for large k. This improves an upper bound due to Brown, who had established an analogous result for N⁺(k)= 2^k log k f(k).

Related

• A Probabilistic Threshold for Monochromatic Arithmetic Progressions
• Monochromatic 4-term arithmetic progressions in 2-colorings of \mathbb Z_n
• On the distribution of monochromatic complete subgraphs and arithmetic progressions
• Monochromatic products in random integer sets
• Linear configurations containing 4-term arithmetic progressions are uncommon