teorema de doignon

El teorema de Doignon en geometría es un análogo del teorema de Helly para la red de números enteros . Afirma que, si una familia de conjuntos convexos en un espacio euclidiano de dimensiones tiene la propiedad de que la intersección de cada uno contiene un punto entero, entonces la intersección de todos los conjuntos contiene un punto entero. Por lo tanto, los programas lineales enteros -dimensionales forman un problema de dimensión combinatoria tipo LP , y pueden resolverse mediante ciertas generalizaciones de algoritmos de programación lineal en una cantidad de tiempo que es lineal en el número de restricciones del problema y manejable con parámetros fijos en su dimensión. ^[1] El mismo teorema se aplica de manera más general a cualquier red , no solo a la red de números enteros. ^[2] ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$ ${\displaystyle 2^{d}}$

El teorema se puede clasificar como perteneciente a la geometría convexa , la geometría discreta y la geometría de los números . Lleva el nombre del matemático y psicólogo matemático belga Jean-Paul Doignon, quien lo publicó en 1973. Doignon le da crédito a Francis Buekenhout por plantear la pregunta respondida por este teorema. ^[2] También se le llama teorema de Doignon-Bell-Scarf , ^[3] dándole crédito a los economistas matemáticos David E. Bell y Herbert Bufanda , quienes lo redescubrieron en 1977 ^{[4] [5]} y señalaron sus aplicaciones a la programación entera. ^[1]

El resultado es ajustado: existen sistemas de semiespacios para los cuales cada uno tiene un punto entero en su intersección, pero para los cuales el sistema completo no tiene una intersección entera. Un sistema de este tipo se puede obtener, por ejemplo, eligiendo semiespacios que contengan todos los vértices del cubo unitario menos uno . Otra forma de expresar el resultado es que el número de Helly de subconjuntos convexos de los números enteros es exactamente . De manera más general, el número de Helly de cualquier conjunto discreto de puntos euclidianos es igual al número máximo de puntos que se pueden elegir para formar los vértices de un politopo convexo que no contiene ningún otro punto del conjunto. ^[6] Generalizando tanto el teorema de Helly como el teorema de Doignon, el número de Helly del producto cartesiano es . ^[7] ${\displaystyle 2^{d}-1}$ ${\displaystyle 2^{d}}$ ${\displaystyle \mathbb {Z} ^{d}\times \mathbb {R} ^{k}}$ ${\displaystyle 2^{d}(k+1)}$

Referencias

1. Amenta, Nina ; De Loera, Jesús A .; Soberón, Pablo (2017), “Teorema de Helly: nuevas variaciones y aplicaciones”, en Harrington, Heather A. ; Omar, Mohamed; Wright, Matthew (eds.), Actas de la sesión especial de AMS sobre métodos algebraicos y geométricos en matemáticas discretas aplicadas celebrada en San Antonio, TX, el 11 de enero de 2015 , Matemáticas contemporáneas, vol. 685, Providence, Rhode Island: Sociedad Matemática Estadounidense, págs. 55–95, arXiv : 1508.07606 , doi : 10.1090/conm/685, MR  3625571
2. Doignon, Jean-Paul (1973), "Convexidad en redes cristalográficas", Journal of Geometry , 3 : 71–85, doi :10.1007/BF01949705, MR  0387090
3. Castaño, Stephen R.; Hildebrand, Robert; Zenklusen, Rico (2018), "Límites sublineales para un teorema cuantitativo de Doignon-Bell-Scarf", Revista SIAM de Matemáticas Discretas , 32 (1): 352–371, arXiv : 1512.07126 , doi :10.1137/16M1100095, MR  3757097
4. Bell, David E. (1977), "Un teorema sobre la red de números enteros", Estudios en Matemáticas Aplicadas , 56 (2): 187–188, doi :10.1002/sapm1977562187, MR  0462617
5. Bufanda, Herbert E. (1977), "Una observación sobre la estructura de los conjuntos de producción con indivisibilidades", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 74 (9): 3637–3641, doi :10.1073/ pnas.74.9.3637, SEÑOR  0452678, PMC 431672 
6. Ambrus, Gergely; Balko, Martín; Frankl, Nora; Jung, Atila; Naszódi, Márton (2023), "Sobre los números de Helly de redes exponenciales", en Chambers, Erin W.; Gudmundsson, Joachim (eds.), 39.º Simposio internacional sobre geometría computacional, SoCG 2023, 12 al 15 de junio de 2023, Dallas, Texas, EE. UU. , LIPIcs, vol. 258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 8:1–8:16, doi :10.4230/LIPIcs.SoCG.2023.8
7. Averkov, G.; Weismantel, R. (2012), "Números transversales sobre subconjuntos de espacios lineales", Avances en geometría , 12 (1): 19–28, arXiv : 1002.0948 , doi :10.1515/advgeom.2011.028, MR  2911157