Ramsey Theory for Product Trees

Abstract

We develop a Ramsey theory for leaf-generated subsets of finite products of trees. Our starting point is a Theorem of Furstenberg and Weiss which states that for every $k\geq 1$ and $\alpha>0$, if $A$ is a subset of the leaves of $T_n$, where $T_n$ is the complete binary tree of height $n$, with size $|A|\geq 2^{\alpha n}$, then for $n$ sufficiently large the ancestor closed sub-tree $T_A\subset T_n$ generated by $A$ must contain a copy of $T_k$ such that (1) all vertices in the same level of $T_k$ are mapped into vertices at the same level of $T_A$, (2) if a non-leaf vertex $x\in T_k$ is mapped into a vertex $y \in T_A$, then the two children of $x$ are mapped into descendants of the two children of $y$, and (3) the levels of $T_A$ occupied by the copy of $T_k$ form an arithmetic progression. For the product $T_n \times T_n$ of two binary trees, we show that for every $k\geq 1$ and $\alpha>1$, for $n$ sufficiently large, every subset $A$ of the leaves of $T_n\times T_n$ of size at least $2^{\alpha n}$ has that its ancestor closure $\Gamma_A\subset T_n \times T_n$ contains similarly structured arithmetic copies of the height $k$ four-ary tree, where the four children of every non-leaf vertex in the source tree are required to map below the four distinct \textit{diagonal children} of the image vertex, where a diagonal child of a vertex $(x,y) \in T_n \times T_n$ is obtained by moving one level down each in each component. Our results generalise to product of $d$-many finite $b$-ary trees with a sharp critical exponent of \[ \alpha_{\text{crit}}(d,b) =d-1 + \log_b(b-1).\] Geometrically, our results imply that any set $E\subset [0,1)^d$ of upper Minkowski dimension greater than $\alpha_{\text{crit}}(d,b)$ contains arithmetic $b$-adic branching patterns of arbitrary finite order.