A density version of the Carlson-Simpson theorem

DOI10.4171/JEMS/484MaRDI QIDQ479520zbMATH OpenOpenAlexFDO

Authors Pandelis Dodos, Vassilis Kanellopoulos, Konstantinos Tyros

Publication date 5 December 2014

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

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

zbMATH Keywords

densitywordsleft variable words

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15) Ramsey theory (05D10)

Abstract: We prove a density version of the Carlson--Simpson Theorem. Specifically we show the following. For every integer $kgeq2$ and every set $A$ of words over $k$ satisfying [limsup_{n oinfty} frac{|Acap [k]^n|}{k^n}>0] there exist a word $c$ over $k$ and a sequence $(w_n)$ of left variable words over $k$ such that the set [{c}cup �ig{c^{smallfrown}w_0(a_0)^{smallfrown}...^{smallfrown}w_n(a_n) : ninmathbb{N} ext{ and } a_0,...,a_nin [k]�ig}] is contained in $A$. While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

Recommendations

• A computable analysis of variable words theorems
• Partition theorems for left and right variable words
• A density version of the Hales-Jewett theorem
• Measurable events indexed by words
• scientific article; zbMATH DE number 66576

Cites work

• scientific article; zbMATH DE number 3473781 (Why is no real title available?)
• scientific article; zbMATH DE number 3316912 (Why is no real title available?)
• A Partition Theorem
• A Partition Theorem for the Infinite Subtrees of a Tree
• A Ramsey theorem for trees
• A density version of the Hales-Jewett theorem
• A density version of the Halpern-Läuchli theorem
• A dual form of Ramsey's theorem
• A simple proof of the density Hales-Jewett theorem
• An ergodic Szemerédi theorem for commuting transformations
• Combinatorial theorems in sparse random sets
• Dense Subsets of Products of Finite Trees
• Density theorems for finitistic trees
• Elemental methods in ergodic Ramsey theory
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Idempotents in compact semigroups and Ramsey theory
• Markov Processes and Ramsey Theory for Trees
• Measurable events indexed by products of trees
• Partition Theorems for Spaces of Variable Words
• Partition theorems for left and right variable words
• Polymath and the density Hales-Jewett theorem
• Ramsey's Theorem for n-Parameter Sets
• Regularity and Positional Games
• Remarks on a Ramsey theory for trees
• Set-polynomials and polynomial extension of the Hales-Jewett theorem
• Some unifying principles in Ramsey theory
• Two new extensions of the Hales-Jewett theorem

Cited in

(16)

• Measurable events indexed by words
• A Density Corrádi–Hajnal Theorem
• Measurable events indexed by products of trees
• Combinatorial Structures on van der Waerden sets
• scientific article; zbMATH DE number 6667279 (Why is no real title available?)
• A computable analysis of variable words theorems
• The refinement of a constant in the density theorem
• A density version of Cobham’s theorem
• Generic density and small span theorem
• A density version of the Halpern-Läuchli theorem
• A disjoint unions theorem for trees
• Density results for Graovac-Pisanski’s distance number
• A concentration inequality for product spaces
• Szemerédi's regularity lemma via martingales
• Density Versions of Plünnecke Inequality: Epsilon-Delta Approach
• Carlson-Simpson's lemma and applications in reverse mathematics

This page was built for publication: A density version of the Carlson-Simpson theorem

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