Intentando lo imposible: enumerando funciones submodulares extremas para n = 6
Autores: Csirmaz, Elod P.; Csirmaz, Laszlo
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Intentando lo imposible: enumerando funciones submodulares extremas para n = 6
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Funciones submodulares
Conjunto base
Geometría poliédrica
Doble Descripción
Descomposición de Adyacencia
Análisis estadísticos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 48
Citaciones: Sin citaciones
Enumerar las funciones submodulares extremas definidas en subconjuntos de un conjunto base fijo solo se ha hecho para conjuntos base de hasta cinco elementos. Este artículo informa sobre los resultados de intentar generar todas esas funciones en un conjunto base de seis elementos. Utilizando herramientas mejoradas de geometría poliédrica, hemos calculado 360 mil millones de ellas y proporcionamos la primera estimación razonable de su número total, que se espera que esté entre 1000 y 10,000 veces este número. Los métodos de Doble Descripción y Descomposición de Adyacencia requieren un orden de inserción de las desigualdades definitorias. Introducimos dos órdenes novedosos, que aceleran significativamente los cálculos y proporcionan una mayor comprensión de la estructura altamente simétrica de las funciones submodulares. También presentamos una mejora en la prueba combinatoria utilizada como parte del método de Doble Descripción y utilizamos análisis estadísticos para estimar la degeneración del cono poliédrico utilizado para describir estas funciones. Los resultados estadísticos también resaltan las limitaciones de los métodos aplicados.
Descripción
Enumerar las funciones submodulares extremas definidas en subconjuntos de un conjunto base fijo solo se ha hecho para conjuntos base de hasta cinco elementos. Este artículo informa sobre los resultados de intentar generar todas esas funciones en un conjunto base de seis elementos. Utilizando herramientas mejoradas de geometría poliédrica, hemos calculado 360 mil millones de ellas y proporcionamos la primera estimación razonable de su número total, que se espera que esté entre 1000 y 10,000 veces este número. Los métodos de Doble Descripción y Descomposición de Adyacencia requieren un orden de inserción de las desigualdades definitorias. Introducimos dos órdenes novedosos, que aceleran significativamente los cálculos y proporcionan una mayor comprensión de la estructura altamente simétrica de las funciones submodulares. También presentamos una mejora en la prueba combinatoria utilizada como parte del método de Doble Descripción y utilizamos análisis estadísticos para estimar la degeneración del cono poliédrico utilizado para describir estas funciones. Los resultados estadísticos también resaltan las limitaciones de los métodos aplicados.