Piecewise convex embeddability on linear orders
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912359180664832 |
|---|---|
| author | Iannella, Martina Marcone, Alberto Ros, Luca Motto Weinstein, Vadim |
| author_facet | Iannella, Martina Marcone, Alberto Ros, Luca Motto Weinstein, Vadim |
| contents | Given a nonempty set $\mathcal{L}$ of linear orders, we say that the linear order $L$ is $\mathcal{L}$-convex embeddable into the linear order $L'$ if it is possible to partition $L$ into convex sets indexed by some element of $\mathcal{L}$ which are isomorphic to convex subsets of $L'$ ordered in the same way. This notion generalizes convex embeddability and (finite) piecewise convex embeddability (both studied in arXiv:2309.09910), which are the special cases $\mathcal{L} = \{\mathbf{1}\}$ and $\mathcal{L} = \mathsf{Fin}$. We focus mainly on the behavior of these relations on the set of countable linear orders, first characterizing when they are transitive, and hence a quasi-order. We then study these quasi-orders from a combinatorial point of view, and analyze their complexity with respect to Borel reducibility. Finally, we extend our analysis to uncountable linear orders. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01198 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Piecewise convex embeddability on linear orders Iannella, Martina Marcone, Alberto Ros, Luca Motto Weinstein, Vadim Logic Combinatorics 03E15, 06A05, 06A07 Given a nonempty set $\mathcal{L}$ of linear orders, we say that the linear order $L$ is $\mathcal{L}$-convex embeddable into the linear order $L'$ if it is possible to partition $L$ into convex sets indexed by some element of $\mathcal{L}$ which are isomorphic to convex subsets of $L'$ ordered in the same way. This notion generalizes convex embeddability and (finite) piecewise convex embeddability (both studied in arXiv:2309.09910), which are the special cases $\mathcal{L} = \{\mathbf{1}\}$ and $\mathcal{L} = \mathsf{Fin}$. We focus mainly on the behavior of these relations on the set of countable linear orders, first characterizing when they are transitive, and hence a quasi-order. We then study these quasi-orders from a combinatorial point of view, and analyze their complexity with respect to Borel reducibility. Finally, we extend our analysis to uncountable linear orders. |
| title | Piecewise convex embeddability on linear orders |
| topic | Logic Combinatorics 03E15, 06A05, 06A07 |
| url | https://arxiv.org/abs/2312.01198 |