Dense Subsets of Products of Finite Trees

作者：Dodos Pandelis^*; Kanellopoulos Vassilis; Tyros Konstantinos

来源：International Mathematics Research Notices, 2013, (4): 924-970.

DOI：10.1093/imrn/rns015

We prove a "uniform" version of the finite density Halpern-Lauchli 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 is an element of T has exactly b immediate successors. We show the following: for every integer d >= 1, every b(1), ..., b(d) is an element of N with b(i) >= 2 for all i is an element of {1, ..., d}, every integer k >= 1 and every real 0 < epsilon <= 1 there exists an integer N with the following property. If (T-1, ..., T-d) are homogeneous trees such that the branching number of T-i is b(i) for all i is an element of {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-1, ..., T-d) satisfying
vertical bar D boolean AND (T-1(n) x ... x T-d(n))vertical bar >= epsilon vertical bar T-1(n) x ... x T-d(n)vertical bar
for every n is an element of L, then there exist strong subtrees (S-1,...,S-d) of (T-1,...,T-d) of height k and with common level set such that the level product of (S-1,...,S-d) is contained in D. The least integer N with this property will be denoted by UDHL(b(1),...,b(d)vertical bar k,epsilon). 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(1),...,b(d)vertical bar k,epsilon).

• 出版日期2013