Monochromatic progressions in random colorings

DOI10.1016/J.JCTA.2012.01.010MaRDI QIDQ412191zbMATH OpenOpenAlexFDO

Authors S. Vijay

Publication date 4 May 2012

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

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

zbMATH Keywords

arithmetic progressionshypergraph coloringVan der Waerden's theorem

Mathematics Subject Classification ID

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

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

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 Z_p
• Monochromatic 4-term arithmetic progressions in 2-colorings of Z_n

Cites work

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

Cited in

(6)

• The minimum number of monochromatic 4-term progressions in Z_p
• Nonconventional averages along arithmetic progressions and lattice spin systems
• On the distribution of monochromatic complete subgraphs and arithmetic progressions
• 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)