Progressions and Paths in Colorings of \mathbb Z

arXiv1706.01579MaRDI QIDQ6287522FDOQ6287522

Publication date: 5 June 2017

Abstract: A

e x t i t l a d d e r

is a set

S s u b s e t e q m a t h b b Z^{+}

such that any finite coloring of

m a t h b b Z

contains arbitrarily long monochromatic progressions with common difference in

S

. Van der Waerden's theorem famously asserts that

m a t h b b Z^{+}

itself is a ladder. We also discuss variants of ladders, namely

e x t i t a c c e s s i b l e

and

e x t i t w a l k a b l e

sets, which are sets

S

such that any coloring of

m a t h b b Z

contains arbitrarily long (for accessible sets) or infinite (for walkable sets) monochromatic sequences with consecutive differences in

S

. We show that sets with upper density 1 are ladders and walkable. We also show that all directed graphs with infinite chromatic number are accessible, and reduce the bound on the walkability order of sparse sets from 3 to 2, making it tight.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Arithmetic progressions (11B25)

This page was built for publication: Progressions and Paths in Colorings of $\mathbb Z$

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