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

Iannella M.;Marcone A.;
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.
File in questo prodotto:
File Dimensione Formato  
20250226 Piecewise embeddability (first revision submitted).pdf

embargo fino al 04/04/2026

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 497.75 kB
Formato Adobe PDF
497.75 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11390/1305804
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact