Combinatorial Designs, Ideals and Quasi-Steiner Triple Systems

El documento comienza presentando un método innovador para generar diseños combinatorios utilizando técnicas de geometría algebraica. La idea central es representar diseños combinatorios específicos como puntos en la variedad geométrica asociada a un ideal polinomial. Esta técnica se aplica con éxito en la construcción de ideales cuyas variedades geométricas son Sistemas Triples de Steiner (STS), incluso aquellos que cumplen restricciones adicionales, como ser anti-Pasch o Sistemas Triples de Kirkman. Sin embargo, la limitación reside en que el cálculo de la variedad geométrica solo es factible para sistemas de órdenes muy pequeños. Los autores exploraron la construcción de una base de Gröbner y la generación de puntos en las variedades utilizando algoritmos genéticos, pero estos métodos resultaron efectivos únicamente para órdenes pequeños.

El documento define los Sistemas Triples de Steiner (STS) como conjuntos de subconjuntos de 3 elementos, llamados triples o bloques, de un conjunto de v puntos, de manera que cada par de puntos aparece exactamente en un bloque. Se exploran las condiciones necesarias y suficientes para la existencia de un STS. Se introduce la noción de Sistemas Triples de Quasi-Steiner (QSTS) como una alternativa a los PSTS (Partial Steiner Triple Systems). Los QSTS contienen el mismo número de triples que un STS del mismo orden, pero permiten pares repetidos y faltantes. El número de pares faltantes en un QSTS se denomina nivel del QSTS.

Los autores exploran el uso de algoritmos genéticos (AGs) para encontrar puntos en la variedad geométrica asociada a los diseños combinatorios. Se codifica un conjunto de triples como un cromosoma representado por un vector característico, y la función de aptitud se define como el número de polinomios no satisfechos por el cromosoma. Se destaca una deficiencia en la operación de cruce de los AGs, ya que aumenta significativamente la aptitud del organismo resultante en comparación con los padres, especialmente cuando la aptitud está cerca de cero. Se propone la eliminación de la operación de cruce para utilizar un AG puramente mutativo. Se compara este enfoque con métodos de ascenso de colina, específicamente el método de Stinson, que se considera más eficiente para la construcción de STS.

El documento se centra en el estudio de las QSTS y en la introducción de operaciones básicas para transformar QSTS de un nivel a otro. Se destaca la transformación de nivel dos a nivel cero, que corresponde a la conversión de un QSTS en un STS. Se presentan cinco operaciones similares a la operación SWITCH, las cuales se utilizan en un método de reducción para convertir un QSTS de nivel superior a uno de nivel inferior. El documento analiza la complejidad temporal de este método de reducción y destaca la importancia de la descomposición de grafos en QSTS para la aplicación de estas operaciones. Se exploran patrones específicos en la descomposición de grafos que permiten reducir el nivel del QSTS.