Ramsey degrees of boron tree structures (Q485537): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(8 intermediate revisions by 7 users not shown) | |||
Property / author | |||
Property / author: Jakub Jasinski / rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03C13 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 54H20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6385393 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complete binary tree | |||
Property / zbMATH Keywords: complete binary tree / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
boron tree structure | |||
Property / zbMATH Keywords: boron tree structure / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Fraisse class | |||
Property / zbMATH Keywords: Fraisse class / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(n\)-parameter set | |||
Property / zbMATH Keywords: \(n\)-parameter set / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ramsey class | |||
Property / zbMATH Keywords: Ramsey class / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ramsey degree | |||
Property / zbMATH Keywords: Ramsey degree / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ramsey partition relation | |||
Property / zbMATH Keywords: Ramsey partition relation / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Jakub Jasinski / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-013-2723-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2040142481 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3995219 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: SOME TREELIKE OBJECTS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A generalization of Ramsey's theorem for regular trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Symmetries and Ramsey properties of trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sur l'extension aux relations de quelques propriétés des ordres / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramsey's Theorem for n-Parameter Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Ramsey theorem for trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramsey Classes and Homogeneous Structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871773 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The partite construction and Ramsey set systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3415741 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The partition problem for finite Abelian groups / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:52, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey degrees of boron tree structures |
scientific article |
Statements
Ramsey degrees of boron tree structures (English)
0 references
9 January 2015
0 references
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.
0 references
complete binary tree
0 references
boron tree structure
0 references
Fraisse class
0 references
\(n\)-parameter set
0 references
Ramsey class
0 references
Ramsey degree
0 references
Ramsey partition relation
0 references
0 references