Ramsey degrees of boron tree structures (Q485537)

This paper concerns Ramseyian results on structures derived from binary trees, where the partition relation depends on the structure of the binary trees from which the structures were derived. A boron tree is an acyclic connected graph whose vertices are all of degree 3 or 1. (Note that a binary tree is the result of selecting a boron tree and designating a root.) Given a boron tree \(\mathbb B\), its boron tree structure is an elementary structure \(\mathbb B'\) whose domain is the set of leaves of \(\mathbb B\) and which has a 4-ary relation \(R\) such that for any distinct leaves \(a\), \(b\), \(c\), \(d\), \(R(a,b,c,d)\) iff the unique path from \(a\) to \(b\) in \(\mathbb B\) does not encounter the unique path from \(c\) to \(d\). Central to the machinery in this paper is the orientation of any set of leaves in a boron tree structure: given a set of leaves \(O\), the orientation \(\mathcal O\) can be regarded as a result of taking the original boron structure, removing all vertices not on paths connecting pairs of vertices of \(O\), and then applying a homeomorphism to remove all vertices of degree 2. Thus, given four leaves \(a\), \(b\), \(c\), \(d\), the orientation on those leaves determines whether \(R(a,b,c,d)\) is true. The primary result is presented as ``\dots in some sense -- an asymmetric version of \dots'' the \(n\)-parameter set theorem of \textit{R. L. Graham} and \textit{B. Rothschild} [Trans. Am. Math. Soc. 159, 257--292 (1971; Zbl 0233.05003)]. To describe this result, we need the following infrastructure. Given a boron tree structure \(\mathbb B\) with an orientation \(\mathcal O\) (inherited from the boron tree from whence it came), and given any boron tree structure \(\mathbb A\) and any orientation \(\mathcal O'\) (for the number of elements of \(\mathbb A\)'s domain), let \(\binom{\mathbb B}{\mathbb A}_{\mathcal O'}\) be the set of all substructures of \(\mathbb B\) isomorphic to \(\mathbb A\) and whose orientation, inherited from \(\mathcal O\), is isomorphic to \(\mathcal O'\). And for each \(n\), let \(\mathbb B(n)\) be the boron substructure of \(2^n\) elements induced from the binary tree of height \(n\), and let \(\mathcal O(n)\) be its orientation. Here is the primary result. Given positive integers \(n\), \(p\), \(r\), there exists \(N\) such that the following is true. If \(\mathbb A\) is a boron substructure with orientation \(\mathcal O\) of height \(p\), the following is true. For any coloring \(c : \binom{\mathbb B(N)}{\mathbb A}_{\mathcal O}\to\{1,2,\ldots,r\}\), there exists \(\mathbb B'\in \binom{\mathbb B(N)}{\mathbb B(n)}_{\mathcal O(n)}\) (i.e. a copy \(\mathbb B'\) of \(\mathbb B(n)\) of orientation \(\mathcal O(n)\)) such that \(c\) is monochromatic on \[ \left\{ \mathbb A \in \binom{\mathbb B(N)}{\mathbb A}_{\mathcal O} : \mathbb A \text{ is a substructure of } \mathbb B'\right\}. \] The partition relation is expressed as: \(\mathbb B(N) \to (\mathbb B(n))^{(\mathbb A, \mathcal O)}_r\). The rest of the paper consists of connecting dots. For example, one may expand a boron tree structure with a second relation defined from the underlying binary tree. The class \(\mathcal {OB}\) of expanded structures is a Ramsey class in the sense that for any \(\mathbb A, \mathbb B\in \mathcal{OB}\), and any integer \(r > 1\), there exists \(\mathcal C\in \mathcal{OB}\) such that for any \(r\)-coloring of the copies of \(\mathbb A\) in \(\mathcal C\), there exists a copy \(\mathbb B'\) of \(\mathbb B\) in \(\mathcal C\) such that all copies of \(\mathcal A\) in \(\mathcal B'\) are the same color. While the introduction discusses connections to topological dynamics and to logic, the paper consists of relatively elementary if intricate combinatorics. (The unmentioned elephant in the room is category theory.) Unfortunately, there are problems with the exposition, particularly in the notation, and typos and, in some places, a failure to adequately guide the reader through complexities. But other than the exposition, the paper is relatively self-contained, so despite its advertised dependence on \textit{B. Voigt} [J. Comb. Theory, Ser. A 28, 257--271 (1980; Zbl 0442.05003)], it is relatively accessible to readers familiar with partition relations.