Artículo
Separability, Boxicity, and Partial Orders
Autor/es | Díaz Báñez, José Miguel
Horn, Paul López, Mario A. Marín, Nestaly Ramírez-Vigueras, Adriana Solé-Pi, Oriol Stevens, Alex Urrutia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Fecha de publicación | 2023 |
Fecha de depósito | 2023-08-07 |
Publicado en |
|
Resumen | A collection S = {Si,..., Sn} of disjoint closed convex sets in Rd is separable if there exists
a direction (a non-zero vector) −→v of Rd such that the elements of S can be removed, one
at a time, by translating them an ... A collection S = {Si,..., Sn} of disjoint closed convex sets in Rd is separable if there exists a direction (a non-zero vector) −→v of Rd such that the elements of S can be removed, one at a time, by translating them an arbitrarily large distance in the direction −→v without hitting another element of S. We say that Si ≺ Sj if Sj has to be removed before we can remove Si . The relation ≺ defines a partial order P(S, ≺) on S which we call the separability order of S and −→v . A partial order P(X, ≺ ) on X = {x1,..., xn} is called a separability order if there is a collection of convex sets S and a vector −→v in some Rd such that xi ≺ x j in P(X, ≺ ) if and only if Si ≺ Sj in P(S, ≺). We prove that every partial order is the separability order of a collection of convex sets in R4, and that any poset of dimension 2 is the separability order of a set of line segments in R3. We then study the case when the convex sets are restricted to be boxes in d-dimensional spaces. We prove that any partial order is the separability order of a family of disjoint boxes in Rd for some d ≤ n 2 + 1. We prove that every poset of dimension 3 has a subdivision that is the separability order of boxes in R3, that there are partial orders of dimension 2 that cannot be realized as box separability in R3 and that for any d there are posets with dimension d that are separability orders of boxes in R3. We also prove that for any d there are partial orders with box separability dimension d; that is, d is the smallest dimension for which they are separable orders of sets of boxes in Rd. |
Agencias financiadoras | Ministerio de Ciencia e Innovación (MICIN). España Unión Europea. Horizonte 2020 |
Identificador del proyecto | CIN/AEI/10.13039/501100011033
734922 |
Cita | Díaz Báñez, J.M., Horn, P., López, M.A., Marín, N., Ramírez-Vigueras, A., Solé-Pi, O.,...,Urrutia, J. (2023). Separability, Boxicity, and Partial Orders. Order. https://doi.org/10.1007/s11083-023-09628-8. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Order_2023_Diaz_Separability_OA.pdf | 891.2Kb | [PDF] | Ver/ | |