Teorema de Doignon

El teorema de Doignon en geometría es un análogo del teorema de Helly para la red de enteros . Afirma que, si una familia de conjuntos convexos en un espacio euclidiano de dimensión -dimensional 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 de dimensión -dimensional forman un problema de tipo LP de dimensión combinatoria , 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 enteros. ^[2] ${\estilo de visualización d}$ ${\estilo de visualización 2^{d}}$ ${\estilo de visualización d}$ ${\estilo de visualización 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 . Recibe su nombre del matemático y psicólogo matemático belga Jean-Paul Doignon, quien lo publicó en 1973. Doignon atribuye a Francis Buekenhout el planteamiento de la pregunta respondida por este teorema. ^[2] También se le llama teorema de Doignon-Bell-Scarf , ^[3] atribuyéndolo a los economistas matemáticos David E. Bell y Herbert Scarf , 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 todos tienen un punto entero en su intersección, pero para los cuales el sistema completo no tiene intersección entera. Un sistema de este tipo puede obtenerse, por ejemplo, eligiendo semiespacios que contengan todos menos un vértice del cubo unitario . Otra forma de expresar el resultado es que el número de Helly de subconjuntos convexos de los 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 pueden elegirse para formar los vértices de un politopo convexo que no contenga 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] $Estilo de visualización 2^{d}-1$ ${\estilo de visualización 2^{d}}$ $\mathbb {Z} ^{d}\times \mathbb {R} ^{k}$ $Estilo de visualización 2^{d}(k+1)}$

Referencias

^ ab 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 la AMS sobre Métodos Algebraicos y Geométricos en Matemáticas Discretas Aplicadas celebrada en San Antonio, TX, el 11 de enero de 2015 , Contemporary Mathematics, vol. 685, Providence, Rhode Island: American Mathematical Society, pp. 55–95, arXiv : 1508.07606 , doi :10.1090/conm/685, ISBN 978-1-4704-2321-6, Sr. 3625571
^ ab Doignon, Jean-Paul (1973), "Convexidad en redes cristalográficas", Journal of Geometry , 3 : 71–85, doi :10.1007/BF01949705, MR 0387090
^ Chestnut, Stephen R.; Hildebrand, Robert; Zenklusen, Rico (2018), "Límites sublineales para un teorema cuantitativo de Doignon–Bell–Scarf", SIAM Journal on Discrete Mathematics , 32 (1): 352–371, arXiv : 1512.07126 , doi :10.1137/16M1100095, MR 3757097
^ 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
^ Scarf, 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, Bibcode :1977PNAS...74.3637S, doi : 10.1073/pnas.74.9.3637 , MR 0452678, PMC 431672 , PMID 16592435
^ 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
^ Averkov, G.; Weismantel, R. (2012), "Números transversales sobre subconjuntos de espacios lineales", Advances in Geometry , 12 (1): 19–28, arXiv : 1002.0948 , doi :10.1515/advgeom.2011.028, MR 2911157