Monochromatic progressions in random colorings

DOI10.1016/J.JCTA.2012.01.010zbMATH Open1239.05075arXiv1106.0793OpenAlexW1963997033MaRDI QIDQ412191FDOQ412191

Authors: S. Vijay 

Publication date: 4 May 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/1106.0793

Recommendations

• A probabilistic threshold for monochromatic arithmetic progressions
• A pseudo upper bound for the van der Waerden function
• On sequences covering all rainbow \(k\)-progressions
• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• Monochromatic 4-term arithmetic progressions in 2-colorings of \(\mathbb Z_n\)

zbMATH Keywords

arithmetic progressionshypergraph coloringVan der Waerden's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• A new proof of Szemerédi's theorem
• A pseudo upper bound for the van der Waerden function
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• Almost disjoint families of 3-term arithmetic progressions

Cited In (4)

• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• A probabilistic threshold for monochromatic arithmetic progressions
• Two-colorings of normed spaces with no long monochromatic unit arithmetic progressions
• Ramsey Functions for Generalized Progressions

This page was built for publication: Monochromatic progressions in random colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412191)