A combinatorial proof of the dense Hindman's theorem

DOI10.1016/J.DISC.2011.03.006MaRDI QIDQ2275370zbMATH OpenOpenAlexFDO

Authors Henry Towsner

Publication date 8 August 2011

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hindman's Theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of partitions of integers (05A17) Ramsey theory (05D10)

Abstract: The Dense Hindman's Theorem states that, in any finite coloring of the integers, one may find a single color and a "dense" set $B_1$, for each $b_{1}in{B}_1$ a "dense" set $B_2^{b_1}$ (depending on $b_1$), for each $b_{2}in{B}_2^{b_1}$ a "dense" set $B_3^{b_1,b_2}$ (depending on $b_1,b_2$), and so on, such that for any such sequence of $b_i$, all finite sums belong to the chosen color. (Here density is often taken to be "piecewise syndetic", but the proof is unchanged for any notion of density satisfying certain properties.) This theorem is an example of a combinatorial statement for which the only known proof requires the use of ultrafilters or a similar infinitary formalism. Here we give a direct combinatorial proof of the theorem.

Recommendations

• A combinatorial proof of a stronger dense Hindman theorem
• Hindman's theorem: an ultrafilter argument in second order arithmetic
• A simple proof and some difficult examples for Hindman's theorem
• Hindman's theorem, ultrafilters, and reverse mathematics
• Transfinite approximation of Hindman's theorem

Cites work

• A short proof of Hindman's theorem
• A simple proof and some difficult examples for Hindman's theorem
• Algebra in the Stone-Čech compactification. Theory and applications
• Divisible Properties and the Stone-Čech Compactification
• Finite sums from sequences within cells of a partition of N
• Hindman's theorem, ultrafilters, and reverse mathematics
• Hindman's theorem: an ultrafilter argument in second order arithmetic
• scientific article; zbMATH DE number 4063093 (Why is no real title available?)
• scientific article; zbMATH DE number 891064 (Why is no real title available?)
• scientific article; zbMATH DE number 1423048 (Why is no real title available?)
• Nonstandard methods for upper Banach density problems.
• The sumset phenomenon
• Ultrafilters: Some old and some new results

Cited in

(10)

• Transfinite approximation of Hindman's theorem
• Iterated combinatorial density theorems
• D sets and IP rich sets in \(\mathbb {Z}\)
• Ultrafilters in reverse mathematics
• ON THE STRENGTH OF TWO RECURRENCE THEOREMS
• Hindman's theorem: an ultrafilter argument in second order arithmetic
• A combinatorial proof of an infinite version of the Hales-Jewett theorem
• Conservativity of ultrafilters over subsystems of second order arithmetic
• A combinatorial proof of a stronger dense Hindman theorem
• On the descriptive power of probability logic

This page was built for publication: A combinatorial proof of the dense Hindman's theorem

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