Dense subsets of products of finite trees

Original · EN

We prove a "uniform" version of the finite density Halpern-Läuchli Theorem. Specifically, we say that a tree T is homogeneous if it is uniquely rooted and there is an integer b≥ 2, called the branching number of T, such that every t∈ T has exactly b immediate successors. We show the following. For every integer d≥ 1, every b₁,...,bd with bᵢ≥ 2 for all i∈{1,...,d}, every integer k 1 and every real 0<ε≤ 1 there exists an integer N with the following property. If (T₁,...,Td) are homogeneous trees such that the branching number of Tᵢ is bᵢ for all i∈{1,...,d}, L is a finite subset of N of cardinality at least N and D is a subset of the level product of (T₁,...,Td) satisfying |D∩ (T₁(n)×...× Td(n))| ≥ ε|T₁(n)×...× Td(n)| for every n∈ L, then there exist strong subtrees (S₁,...,Sd) of (T₁,...,Td) of height k and with common level set such that the level product of (S₁,...,Sd) is contained in D. The least integer N with this property will be denoted by UDHL(b₁,...,bd|k,ε). The main point is that the result is independent of the position of the finite set L. The proof is based on a density increment strategy and gives explicit upper bounds for the numbers UDHL(b₁,...,bd|k,ε).