Conjunto integralmente convexo

Un conjunto integralmente convexo es el análogo en geometría discreta del concepto de conjunto convexo en geometría.

Un subconjunto X de la cuadrícula de números enteros es integralmente convexo si cualquier punto y en la envoltura convexa de X puede expresarse como una combinación convexa de los puntos de X que están "cerca" de y , donde "cerca" significa que la distancia entre cada dos coordenadas es menor que 1. ^[1] ${\displaystyle \mathbb {Z} ^{n}}$

Definiciones

Sea X un subconjunto de . ${\displaystyle \mathbb {Z} ^{n}}$

Denotemos por ch( X ) la envoltura convexa de X . Nótese que ch( X ) es un subconjunto de , ya que contiene todos los puntos reales que son combinaciones convexas de los puntos enteros en X . ${\displaystyle \mathbb {R} ^{n}}$

Para cualquier punto y en , denotemos near( y ) := { z en | | z _i - y _i | < 1 para todo i en {1,..., n } }. Estos son los puntos enteros que se consideran "cercanos" al punto real y . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {Z} ^{n}}$

Un subconjunto X de se llama integralmente convexo si cada punto y en ch( X ) también está en ch( X ∩ near( y )). ^[2] ${\displaystyle \mathbb {Z} ^{n}}$

Ejemplo

Conjunto no integralmente convexo

Sea n = 2 y sea X = { (0,0), (1,0), (2,0), (2,1) }. Su envoltura convexa ch( X ) contiene, por ejemplo, el punto y = (1,2, 0,5).

Los puntos enteros cercanos a y son near( y ) = {(1,0), (2,0), (1,1), (2,1) }. Por lo tanto, X ∩ near( y ) = {(1,0), (2,0), (2,1)}. Pero y no está en ch( X ∩ near( y )). Ver imagen a la derecha.

Por lo tanto, X no es integralmente convexo. ^[1]

Por el contrario, el conjunto Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } es integralmente convexo.

Propiedades

Iimura, Murota y Tamura ^[3] han demostrado la siguiente propiedad del conjunto integralmente convexo.

Sea un conjunto finito integralmente convexo. Existe una triangulación de ch( X ) que es integral , es decir: ${\displaystyle X\subset \mathbb {Z} ^{n}}$

• Los vértices de la triangulación son los vértices de X ;
• Los vértices de cada símplex de la triangulación se encuentran en la misma "celda" (hipercubo de lado 1) de la cuadrícula de números enteros . ${\displaystyle \mathbb {Z} ^{n}}$

Conjunto integralmente convexo

El conjunto de ejemplo X no es integralmente convexo, y de hecho ch( X ) no admite una triangulación integral: cada triangulación de ch( X ), o bien tiene que agregar vértices que no están en X , o bien tiene que incluir símplices que no estén contenidos en una sola celda.

Por el contrario, el conjunto Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } es íntegramente convexo, y de hecho admite una triangulación íntegra, por ejemplo con los tres símplices {(0,0),(1,0),(1,1)} y {(1,0),(2,0),(2,1)} y {(1,0),(1,1),(2,1)}. Véase la imagen de la derecha.

Referencias

1. Yang, Zaifu (1 de diciembre de 2009). "Análisis discreto de punto fijo y sus aplicaciones". Revista de teoría y aplicaciones de punto fijo . 6 (2): 351–371. doi :10.1007/s11784-009-0130-9. ISSN  1661-7746. S2CID  122640338.
2. Chen, Xi; Deng, Xiaotie (2006). "Un enfoque simplista para teoremas de punto fijo discreto". En Chen, Danny Z.; Lee, DT (eds.). Computación y combinatoria . Apuntes de clase en informática. Vol. 4112. Berlín, Heidelberg: Springer. págs. 3–12. doi :10.1007/11809678_3. ISBN 978-3-540-36926-4.
3. Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (1 de diciembre de 2005). "Reconsideración del teorema del punto fijo discreto" (PDF) . Revista de Economía Matemática . 41 (8): 1030–1036. doi :10.1016/j.jmateco.2005.03.001. ISSN  0304-4068.