Given a nonempty set L of linear orders, we say that the linear order L is L-convex embeddable into the linear order L′ if it is possible to partition L into convex sets indexed by some element of 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 [13]), which are the special cases L={1} and L=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.

Piecewise convex embeddability on linear orders

Motto Ros L.
;
2025-01-01

Abstract

Given a nonempty set L of linear orders, we say that the linear order L is L-convex embeddable into the linear order L′ if it is possible to partition L into convex sets indexed by some element of 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 [13]), which are the special cases L={1} and L=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.
2025
176
8
1
34
https://arxiv.org/abs/2312.01198
Borel reducibility; Convex embeddability; Linear orders; Piecewise convex embeddability
Iannella M.; Marcone A.; Motto Ros L.; Weinstein V.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/2068190
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact