antimatroide

Sistema matemático de ordenamiento o conjuntos.

Tres vistas de un antimatroide: un orden de inclusión en su familia de conjuntos factibles, un lenguaje formal y el correspondiente camino poset.

En matemáticas , un antimatroide es un sistema formal que describe procesos en los que un conjunto se construye incluyendo elementos uno a la vez, y en el que un elemento, una vez disponible para su inclusión, permanece disponible hasta que se incluye. ^[1] Los antimatroides comúnmente se axiomatizan de dos maneras equivalentes , ya sea como un sistema de conjuntos que modela los posibles estados de dicho proceso, o como un lenguaje formal que modela las diferentes secuencias en las que se pueden incluir elementos. Dilworth (1940) fue el primero en estudiar los antimatroides, utilizando otra axiomatización basada en la teoría de la red , y han sido redescubiertos con frecuencia en otros contextos. ^[2]

Los axiomas que definen a los antimatroides como sistemas de conjuntos son muy similares a los de las matroides , pero mientras que las matroides se definen mediante un axioma de intercambio , los antimatroides se definen en cambio mediante un axioma antiintercambio , del cual deriva su nombre. Los antimatroides pueden verse como un caso especial de greedoids y de redes semimodulares , y como una generalización de órdenes parciales y de redes distributivas . Los antimatroides son equivalentes, por complementación , a las geometrías convexas , una abstracción combinatoria de conjuntos convexos en geometría .

Los antimatroides se han aplicado para modelar restricciones de precedencia en problemas de programación , secuencias de eventos potenciales en simulaciones, planificación de tareas en inteligencia artificial y los estados de conocimiento de los alumnos humanos.

Definiciones

Un antimatroide se puede definir como una familia finita de conjuntos finitos, llamados conjuntos factibles , con las dos propiedades siguientes: ^[3] ${\displaystyle {\mathcal {F}}}$

• La unión de dos conjuntos factibles cualesquiera también es factible. Es decir, está cerrado bajo los sindicatos. ${\displaystyle {\mathcal {F}}}$
• Si es un conjunto factible no vacío, entonces contiene un elemento para el cual (el conjunto formado eliminando de ) también es factible. Es decir, es un sistema de conjunto accesible . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S\setminus \{x\}}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$

Los antimatroides también tienen una definición equivalente como lenguaje formal , es decir, como un conjunto de cadenas definidas a partir de un alfabeto finito de símbolos . Una cadena que pertenece a este conjunto se llama palabra del idioma. Un lenguaje que defina un antimatroide debe satisfacer las siguientes propiedades: ^[4] ${\displaystyle {\mathcal {L}}}$

• Cada símbolo del alfabeto aparece en al menos una palabra de . ${\displaystyle {\mathcal {L}}}$
• Cada palabra de contiene como máximo una copia de cada símbolo. Un lenguaje con esta propiedad se llama normal . ^[5] ${\displaystyle {\mathcal {L}}}$
• Cada prefijo de una palabra en también está en . Una lengua con esta propiedad se llama hereditaria . ^[5] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$
• Si y son palabras en , y contienen al menos un símbolo que no está en , entonces hay un símbolo en tal que la concatenación es otra palabra en . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle Tx}$ ${\displaystyle {\mathcal {L}}}$

La equivalencia de estas dos formas de definición se puede ver de la siguiente manera. Si un antimatroide se define como un lenguaje formal, entonces los conjuntos de símbolos en palabras forman un sistema de conjunto cerrado de unión accesible. Es accesible mediante la propiedad hereditaria de las cadenas, y se puede demostrar que tiene una unión cerrada mediante la aplicación repetida de la propiedad de concatenación de las cadenas. En la otra dirección, desde un sistema de conjunto cerrado de unión accesible , el lenguaje de cadenas normales cuyos prefijos tienen todos conjuntos de símbolos que pertenecen a cumple con los requisitos para que un lenguaje formal sea un antimatroide. Estas dos transformaciones son inversas entre sí: transformar una lengua formal en una familia fija y viceversa, o viceversa, produce el mismo sistema. Por tanto, estas dos definiciones conducen a clases de objetos matemáticamente equivalentes. ^[6] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Ejemplos

Una secuencia de bombardeo de un conjunto de puntos planos. Los segmentos de línea muestran los bordes de los cascos convexos después de que se hayan eliminado algunos de los puntos.

Los siguientes sistemas proporcionan ejemplos de antimatroides:

Antimatroides en cadena

Los prefijos de una sola cadena y los conjuntos de símbolos en estos prefijos forman un antimatroide. Por ejemplo, la cadena antimatroide definida por la cadena tiene como lenguaje formal el conjunto de cadenas ${\displaystyle abcd}$

$${\displaystyle \{\varepsilon ,a,ab,abc,abcd\}}$$

(donde denota la cadena vacía ) y como su familia de conjuntos factibles la familia ^[7] ${\displaystyle \varepsilon }$

$${\displaystyle {\bigl \{}\emptyset ,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}{\bigr \}}.}$$

Poset antimatroides

Los conjuntos inferiores de un conjunto finito parcialmente ordenado forman un antimatroide, y las palabras completas del antimatroide forman las extensiones lineales del orden parcial. ^[8] Según el teorema de representación de Birkhoff para redes distributivas, los conjuntos factibles en un poset antimatroide (ordenados por inclusión de conjuntos) forman una red distributiva, y todas las redes distributivas pueden formarse de esta manera. Por tanto, los antimatroides pueden verse como generalizaciones de redes distributivas. Un antimatroide en cadena es el caso especial de un antimatroide poset para un orden total . ^[7]

Bombardeo de antimatroides

Una secuencia de bombardeo de un conjunto finito de puntos en el plano euclidiano o un espacio euclidiano de dimensiones superiores se forma eliminando repetidamente los vértices del casco convexo . Los conjuntos factibles del antimatroide formados por estas secuencias son las intersecciones de con el complemento de un conjunto convexo. ^[7] ${\displaystyle U}$ ${\displaystyle U}$

Eliminación perfecta

Un orden de eliminación perfecta de un grafo cordal es un ordenamiento de sus vértices tal que, para cada vértice , los vecinos del que aparecen más tarde que en el ordenamiento forman una camarilla . Los prefijos de ordenamiento de eliminación perfecta de un gráfico cordal forman un antimatroide. ^[9] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Juegos de disparo de chips

Los juegos de disparo de fichas , como el modelo abeliano de pila de arena, se definen mediante un gráfico dirigido junto con un sistema de "fichas" colocadas en sus vértices. Siempre que el número de fichas en un vértice sea al menos tan grande como el número de aristas fuera de , es posible disparar , moviendo una ficha a cada vértice vecino. El evento que se dispara por enésima vez sólo puede ocurrir si ya ha disparado veces y acumulado el total de fichas. Estas condiciones no dependen del orden de los disparos anteriores y permanecen verdaderas hasta que se disparan, por lo que cualquier gráfico dado y ubicación inicial de los chips para los cuales termina el sistema define un antimatroide en los pares . Una consecuencia de la propiedad antimatroide de estos sistemas es que, para un estado inicial dado, el número de veces que se activa cada vértice y el eventual estado estable del sistema no dependen del orden de activación. ^[10] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i\cdot \deg(v)}$ ${\displaystyle v}$ ${\displaystyle (v,i)}$

Caminos y palabras básicas.

En la axiomatización teórica de conjuntos de un antimatroide hay ciertos conjuntos especiales llamados caminos que determinan el antimatroide completo, en el sentido de que los conjuntos del antimatroide son exactamente las uniones de caminos. ^[11] Si hay un conjunto factible del antimatroide, un elemento que se puede eliminar para formar otro conjunto factible se llama punto final de , y un conjunto factible que tiene un solo punto final se llama camino del antimatroide. ^[12] La familia de caminos se puede ordenar parcialmente mediante inclusión de conjuntos, formando el poset de caminos del antimatroide. ^[13] ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$

Para cada conjunto factible en el antimatroide, y cada elemento de , se puede encontrar un subconjunto de ruta para el cual es un punto final: para hacerlo, elimine uno a la vez los elementos hasta que dicha eliminación no deje un subconjunto factible. Por tanto, cada conjunto factible en un antimatroide es la unión de sus subconjuntos de caminos. ^[11] Si no es un camino, cada subconjunto en esta unión es un subconjunto propio de . Pero, si es en sí mismo una ruta con punto final , cada subconjunto adecuado pertenece al antimatroide excluye . Por lo tanto, las trayectorias de un antimatroide son exactamente los conjuntos factibles que no son iguales a las uniones de sus subconjuntos factibles adecuados. De manera equivalente, una familia dada de conjuntos forma la familia de caminos de un antimatroide si y sólo si, para cada in , la unión de subconjuntos de in tiene un elemento menos que ella misma. ^[14] Si es así, en sí misma es la familia de uniones de subconjuntos de . ^[11] ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {P}}}$

En la formalización del lenguaje formal de un antimatroide, las cadenas más largas se denominan palabras básicas . Cada palabra básica forma una permutación de todo el alfabeto. ^[15] Si es el conjunto de palabras básicas, se puede definir desde como el conjunto de prefijos de palabras en . ^[dieciséis] ${\displaystyle B}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle B}$ ${\displaystyle B}$

Geometrías convexas

Si el sistema de conjuntos define un antimatroide, igual a la unión de los conjuntos en , entonces la familia de conjuntos ${\displaystyle {\mathcal {F}}}$ ${\displaystyle U}$ ${\displaystyle {\mathcal {F}}}$

$${\displaystyle {\mathcal {G}}=\{U\setminus S\mid S\in {\mathcal {F}}\}}$$

complementariageometría convexaconjuntos convexos^[17] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {G}}}$

Una geometría convexa también se puede definir en términos de un operador de cierre que asigna cualquier subconjunto de a su superconjunto cerrado mínimo. Para ser un operador de cierre, debe tener las siguientes propiedades: ^[18] ${\displaystyle \tau }$ ${\displaystyle U}$ ${\displaystyle \tau }$

• ${\displaystyle \tau (\emptyset )=\emptyset }$: el cierre del conjunto vacío está vacío.
• Para cada subconjunto de , es un subconjunto de y . ${\displaystyle S}$ ${\displaystyle U}$ ${\displaystyle S}$ ${\displaystyle \tau (S)}$ ${\displaystyle \tau (S)=\tau {\bigl (}\tau (S){\bigr )}}$
• Siempre que , es un subconjunto de . ${\displaystyle S\subset T\subset U}$ ${\displaystyle \tau (S)}$ ${\displaystyle \tau (T)}$

La familia de conjuntos cerrados resultantes de una operación de cierre de este tipo está necesariamente cerrada bajo las intersecciones, pero puede no ser una geometría convexa. Los operadores de cierre que definen geometrías convexas también satisfacen un axioma antiintercambio adicional :

• Si es un subconjunto de , y y son elementos distintos de que no pertenecen a , pero sí pertenecen a , entonces no pertenece a . ^[18] ${\displaystyle S}$ ${\displaystyle U}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle U}$ ${\displaystyle \tau (S)}$ ${\displaystyle z}$ ${\displaystyle \tau (S\cup \{y\})}$ ${\displaystyle y}$ ${\displaystyle \tau (S\cup \{z\})}$

Una operación de cierre que satisface este axioma se denomina cierre antiintercambio . Si es un conjunto cerrado en un cierre antiintercambio, entonces el axioma antiintercambio determina un orden parcial en los elementos que no pertenecen a , donde en el orden parcial cuando pertenece a . Si es un elemento mínimo de este orden parcial, entonces está cerrado. Es decir, la familia de conjuntos cerrados de un cierre antiintercambio tiene la propiedad de que para cualquier conjunto distinto del conjunto universal hay un elemento que se le puede agregar para producir otro conjunto cerrado. Esta propiedad es complementaria a la propiedad de accesibilidad de los antimatroides, y el hecho de que las intersecciones de conjuntos cerrados sean cerradas es complementario a la propiedad de que las uniones de conjuntos factibles en un antimatroide sean factibles. Por tanto, los complementos de los conjuntos cerrados de cualquier cierre antiintercambio forman un antimatroide. ^[17] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle \tau (S\cup \{y\})}$ ${\displaystyle x}$ ${\displaystyle S\cup \{x\}}$ ${\displaystyle x}$

Los gráficos no dirigidos en los que los conjuntos convexos (subconjuntos de vértices que contienen todos los caminos más cortos entre los vértices del subconjunto) forman una geometría convexa son exactamente los gráficos ptolemaicos . ^[19]

Redes distributivas de unión

Cada dos conjuntos factibles de un antimatroide tienen un límite superior mínimo único (su unión) y un límite inferior máximo único (la unión de los conjuntos del antimatroide que están contenidos en ambos). Por tanto, los conjuntos factibles de un antimatroide, parcialmente ordenados por inclusión de conjuntos, forman una red . Varias características importantes de un antimatroide pueden interpretarse en términos de teoría reticular; por ejemplo, los caminos de un antimatroide son los elementos irreducibles de unión de la red correspondiente, y las palabras básicas del antimatroide corresponden a cadenas máximas en la red. Las redes que surgen de los antimatroides de esta manera generalizan las redes distributivas finitas y se pueden caracterizar de varias maneras diferentes.

• La descripción originalmente considerada por Dilworth (1940) se refiere a elementos irreducibles de la red. Para cada elemento de un antimatroide, existe un conjunto máximo factible único que no contiene : puede construirse como la unión de todos los conjuntos factibles que no contienen . Este conjunto es automáticamente irreducible por encuentro, lo que significa que no es el encuentro de dos elementos de red más grandes. Esto es cierto porque cada superconjunto factible de contiene y, por lo tanto, lo mismo ocurre con cada intersección de superconjuntos factibles. Cada elemento de una red arbitraria se puede descomponer como una reunión de conjuntos irreducibles, a menudo de múltiples maneras, pero en la red correspondiente a un antimatroide cada elemento tiene una familia mínima única de conjuntos irreducibles cuyo encuentro es ; esta familia está formada por los conjuntos de elementos que son factibles. Es decir, la red tiene descomposiciones irreducibles por encuentros únicas . ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle S_{x}}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle T\cup \{x\}}$
• Una segunda caracterización se refiere a los intervalos en la red, las subredes definidas por un par de elementos de la red que constan de todos los elementos de la red con . Un intervalo es atomístico si cada elemento que contiene es la unión de átomos (los elementos mínimos sobre el elemento inferior ), y es booleano si es isomorfo a la red de todos los subconjuntos de un conjunto finito. Para un antimatroide, todo intervalo atomístico también es booleano. ${\displaystyle x\leq y}$ ${\displaystyle z}$ ${\displaystyle x\leq z\leq y}$ ${\displaystyle x}$
• En tercer lugar, las redes que surgen de los antimatroides son redes semimodulares , redes que satisfacen la ley semimodular superior que por cada dos elementos y , si cubre entonces cubre . Al traducir esta condición a los conjuntos factibles de un antimatroide, si un conjunto factible tiene solo un elemento que no pertenece a otro conjunto factible, entonces se puede agregar ese elemento para formar otro conjunto en el antimatroide. Además, la red de un antimatroide tiene la propiedad semidistributiva de encuentro : para todos los elementos de la red , y , si y son iguales entre sí, entonces ambos también son iguales . Una red semimodular y semidistributiva se llama red distributiva de unión . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\wedge z}$ ${\displaystyle x\wedge (y\vee z)}$

Estas tres caracterizaciones son equivalentes: cualquier red con descomposiciones únicas irreducibles por encuentro tiene intervalos atomísticos booleanos y es distributiva por unión, cualquier red con intervalos atomísticos booleanos tiene descomposiciones irreducibles por encuentro únicas y es distributiva por unión, y cualquier red distributiva por unión tiene descomposiciones irreducibles por encuentro e intervalos atomísticos booleanos. ^[20] Por lo tanto, podemos referirnos a una red con cualquiera de estas tres propiedades como conjunta-distributiva. Cualquier antimatroide da lugar a una red finita de unión distributiva, y cualquier red finita de unión distributiva proviene de un antimatroide de esta manera. ^[21] Otra caracterización equivalente de las redes distributivas de unión finita es que están graduadas (dos cadenas máximas cualesquiera tienen la misma longitud) y la longitud de una cadena máxima es igual al número de elementos irreducibles de la red. ^[22] El antimatroide que representa una red distributiva de unión finita se puede recuperar de la red: los elementos del antimatroide pueden considerarse los elementos irreducibles por encuentro de la red, y el conjunto factible correspondiente a cualquier elemento de la red consiste del conjunto de elementos irreducibles tal que no es mayor o igual que en la red. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

Esta representación de cualquier red distributiva de unión finita como una familia accesible de conjuntos cerrados bajo uniones (es decir, como un antimatroide) puede verse como un análogo del teorema de representación de Birkhoff según el cual cualquier red distributiva finita tiene una representación como una familia de conjuntos. cerrado bajo uniones e intersecciones.

Antimatroides supersolubles

Motivado por el problema de definir órdenes parciales en los elementos de un grupo de Coxeter , Armstrong (2009) estudió antimatroides que también son redes supersolubles . Un antimatroide supersoluble se define por una colección de elementos totalmente ordenada y una familia de conjuntos de estos elementos. La familia debe incluir el conjunto vacío. Además, debe tener la propiedad de que si dos conjuntos y pertenecen a la familia, si la diferencia teórica de conjuntos no está vacía y si es el elemento más pequeño de , entonces también pertenece a la familia. Como observa Armstrong, cualquier familia de conjuntos de este tipo forma un antimatroide. Armstrong también proporciona una caracterización teórica de celosía de los antimatroides que puede formar esta construcción. ^[23] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B\setminus A}$ ${\displaystyle x}$ ${\displaystyle B\setminus A}$ ${\displaystyle A\cup \{x\}}$

Operación de unión y dimensión convexa.

Si y son dos antimatroides, ambos descritos como una familia de conjuntos sobre el mismo universo de elementos, entonces otro antimatroide, la unión de y , se puede formar de la siguiente manera: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

$${\displaystyle {\mathcal {A}}\vee {\mathcal {B}}=\{S\cup T\mid S\in {\mathcal {A}}\wedge T\in {\mathcal {B}}\}.}$$

semired^[24]

Las uniones están estrechamente relacionadas con una operación de cierre que asigna lenguajes formales a antimatroides, donde el cierre de un lenguaje es la intersección de todos los antimatroides que lo contienen como sublenguaje. Este cierre tiene como conjuntos factibles las uniones de prefijos de cadenas en . En términos de esta operación de cierre, la unión es el cierre de la unión de las lenguas de y . Cada antimatroide puede representarse como una unión de una familia de antimatroides en cadena o, de manera equivalente, como el cierre de un conjunto de palabras básicas; la dimensión convexa de un antimatroide es el número mínimo de antimatroides en cadena (o equivalentemente, el número mínimo de palabras básicas) en dicha representación. Si es una familia de antimatroides en cadena a cuyas palabras básicas pertenecen todas , entonces genera si y solo si los conjuntos factibles de incluyen todas las rutas de . Los caminos de pertenencia a un antimatroide de cadena única deben formar una cadena en el poset de camino de , por lo que la dimensión convexa de un antimatroide es igual al número mínimo de cadenas necesarias para cubrir el poset de camino, que según el teorema de Dilworth es igual al ancho del poset de camino . ^[25] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Si uno tiene una representación de un antimatroide como el cierre de un conjunto de palabras básicas, entonces esta representación se puede usar para mapear los conjuntos factibles del antimatroide a puntos en el espacio euclidiano de dimensiones: asigne una coordenada por palabra básica y haga la El valor de coordenadas de un conjunto factible es la longitud del prefijo más largo de que es un subconjunto de . Con esta incrustación, es un subconjunto de otro conjunto factible si y solo si las coordenadas de son todas menores o iguales a las coordenadas correspondientes de . Por lo tanto, la dimensión de orden del orden de inclusión de los conjuntos factibles es como máximo igual a la dimensión convexa del antimatroide. ^[26] Sin embargo, en general estas dos dimensiones pueden ser muy diferentes: existen antimatroides con dimensión de orden tres pero con una dimensión convexa arbitrariamente grande. ^[27] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle W}$ ${\displaystyle S}$ ${\displaystyle W}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

Enumeración

El número de posibles antimatroides en un conjunto de elementos crece rápidamente con el número de elementos del conjunto. Para conjuntos de uno, dos, tres, etc. elementos, el número de antimatroides distintos es ^[28]

$${\displaystyle 1,3,22,485,59386,133059751,\dots \,.}$$

Aplicaciones

Tanto las restricciones de precedencia como de tiempo de liberación en la notación estándar para problemas de programación teórica pueden modelarse mediante antimatroides. Boyd y Faigle (1990) utilizan antimatroides para generalizar un algoritmo codicioso de Eugene Lawler para resolver de manera óptima problemas de programación de un solo procesador con restricciones de precedencia en los que el objetivo es minimizar la penalización máxima incurrida por la programación tardía de una tarea.

Glasserman y Yao (1994) utilizan antimatroides para modelar el orden de eventos en sistemas de simulación de eventos discretos .

Parmar (2003) utiliza antimatroides para modelar el progreso hacia una meta en problemas de planificación de inteligencia artificial .

En la Teoría de la Optimidad , un modelo matemático para el desarrollo del lenguaje natural basado en la optimización bajo restricciones, las gramáticas son lógicamente equivalentes a los antimatroides. ^[29]

En psicología matemática , los antimatroides se han utilizado para describir estados factibles de conocimiento de un alumno humano. Cada elemento del antimatroide representa un concepto que el alumno debe comprender, o una clase de problemas que él o ella podría resolver correctamente, y los conjuntos de elementos que forman el antimatroide representan posibles conjuntos de conceptos que podrían ser entendido por una sola persona. Los axiomas que definen un antimatroide pueden expresarse informalmente como si afirmaran que aprender un concepto nunca puede impedir que el alumno aprenda otro concepto, y que cualquier estado factible de conocimiento se puede alcanzar aprendiendo un solo concepto a la vez. La tarea de un sistema de evaluación del conocimiento es inferir el conjunto de conceptos conocidos por un alumno determinado analizando sus respuestas a un conjunto pequeño y bien elegido de problemas. En este contexto, a los antimatroides también se les ha denominado "espacios de aprendizaje" y "espacios de conocimiento bien graduados". ^[30]

Notas

1. Véase Korte, Lovász y Schrader (1991) para un estudio completo de la teoría antimatroide con muchas referencias adicionales.
2. Dos referencias tempranas son Edelman (1980) y Jamison (1980); Jamison fue el primero en utilizar el término "antimatroide". Monjardet (1985) examina la historia del redescubrimiento de los antimatroides.
3. Véase, por ejemplo, Kempner y Levit (2003), Definición 2.1 y Proposición 2.3, p. 2.
4. Korte, Lovász y Schrader (1991), pág. 22.
5. Korte, Lovász y Schrader (1991), pág. 5.
6. Korte, Lovász y Schrader (1991), Teorema 1.4, p. 24.
7. Gordon (1997).
8. Korte, Lovász y Schrader (1991), págs. 24-25.
9. Gordon (1997) describe varios resultados relacionados con antimatroides de este tipo, pero estos antimatroides fueron mencionados anteriormente, por ejemplo, por Korte, Lovász y Schrader (1991). Chandran et al. (2003) utilizan la conexión con antimatroides como parte de un algoritmo para enumerar de manera eficiente todos los ordenamientos de eliminación perfectos de un gráfico cordal determinado.
10. Björner, Lovász y Shor (1991); Knauer (2009).
11. Korte, Lovász y Schrader (1991), Lema 3.12, p. 31.
12. Korte, Lovász y Schrader (1991), pág. 31.
13. Korte, Lovász y Schrader (1991), págs. 39–43.
14. Véase Korte, Lovász y Schrader (1991), Teorema 3.13, p. 32, que define caminos como conjuntos enraizados , conjuntos con un elemento distinguido, y establece una caracterización equivalente sobre las familias de conjuntos enraizados que forman los caminos de los antimatroides.
15. Korte, Lovász y Schrader (1991), págs.6, 22.
16. Véase Korte, Lovász y Schrader (1991), pág. 22: "cualquier palabra en un antimatroide se puede extender a una palabra básica".
17. Korte, Lovász y Schrader (1991), Teorema 1.1, p. 21.
18. Korte, Lovász y Schrader (1991), pág. 20.
19. Farber y Jamison (1986).
20. Adaricheva, Gorbunov y Tumanov (2003), Teoremas 1.7 y 1.9; Armstrong (2009), Teorema 2.7.
21. Edelman (1980), Teorema 3.3; Armstrong (2009), Teorema 2.8.
22. Monjardet (1985) atribuye una forma dual de esta caracterización a varios artículos de la década de 1960 de SP Avann.
23. Armstrong (2009).
24. Korte, Lovász y Schrader (1991), pág. 42; Eppstein (2008), sección 7.2; Falmagne et al. (2013), sección 14.4.
25. Edelman y Saks (1988); Korte, Lovász y Schrader (1991), Teorema 6.9.
26. Korte, Lovász y Schrader (1991), Corolario 6.10.
27. Eppstein (2008), Figura 15.
28. Sloane, N. J. A. (ed.), "Sequence A119770", La enciclopedia en línea de secuencias enteras , Fundación OEIS
29. Comerciante y Riggle (2016).
30. Doignon y Falmagne (1999).

Referencias

• Adaricheva, KV; Gorbunov, VA; Tumanov, VI (2003), "Unión de celosías semidistributivas y geometrías convexas", Avances en Matemáticas , 173 (1): 1–49, doi : 10.1016/S0001-8708(02)00011-7.
• Armstrong, Drew (2009), "El orden de clasificación en un grupo de Coxeter", Journal of Combinatorial Theory , Serie A, 116 (8): 1285–1305, arXiv : 0712.1047 , doi : 10.1016/j.jcta.2009.03.009 , Señor  2568800, S2CID  15474840.
• Birkhoff, Garrett ; Bennett, MK (1985), "La red de convexidad de un poset", Orden , 2 (3): 223–242, doi :10.1007/BF00333128, S2CID  118907732
• Björner, Anders ; Lovász, László ; Shor, Peter W. (1991), "Juegos de disparo de chips en gráficos", European Journal of Combinatorics , 12 (4): 283–291, doi :10.1016/S0195-6698(13)80111-4, MR  1120415
• Björner, Anders ; Ziegler, Günter M. (1992), "Introducción a los greedoids", en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, págs. 284–357, doi :10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, SEÑOR  1165537
• Boyd, E. Andrés; Faigle, Ulrich (1990), "Una caracterización algorítmica de antimatroides", Matemáticas Aplicadas Discretas , 28 (3): 197–205, doi :10.1016/0166-218X(90)90002-T, hdl : 1911/101636.
• Chandran, LS; Ibarra, L.; Ruskey, F .; Sawada, J. (2003), "Generación y caracterización de los ordenamientos de eliminación perfectos de un gráfico cordal" (PDF) , Ciencias de la Computación Teórica , 307 (2): 303–317, doi :10.1016/S0304-3975(03)00221- 4
• Dilworth, Robert P. (1940), "Celosías con descomposiciones irreducibles únicas", Annals of Mathematics , 41 (4): 771–777, doi :10.2307/1968857, JSTOR  1968857.
• Doignon, Jean-Paul; Falmagne, Jean-Claude (1999), Espacios de conocimiento , Springer-Verlag, ISBN 3-540-64501-2.
• Edelman, Paul H. (1980), "Rejillas distributivas de encuentros y cierre antiintercambio", Algebra Universalis , 10 (1): 290–299, doi :10.1007/BF02482912, S2CID  120403229.
• Edelman, Paul H.; Saks, Michael E. (1988), "Representación combinatoria y dimensión convexa de geometrías convexas", Orden , 5 (1): 23–32, doi :10.1007/BF00143895, S2CID  119826035.
• Eppstein, David (2008), Secuencias de aprendizaje , arXiv : 0803.4030. Adaptado parcialmente como capítulos 13 y 14 de Falmagne, Jean-Claude ; Alberto, Dietrich; Doble, Chris; Eppstein, David ; Hu, Xiangen, eds. (2013), Espacios de conocimiento: aplicaciones en educación , Springer-Verlag, doi :10.1007/978-3-642-35329-1, ISBN 978-3-642-35328-4.
• Farber, Martín; Jamison, Robert E. (1986), "Convexidad en gráficos e hipergráficos", Revista SIAM sobre métodos algebraicos y discretos , 7 (3): 433–444, doi :10.1137/0607049, hdl :10338.dmlcz/127659, MR  0844046.
• Glasserman, Paul; Yao, David D. (1994), Estructura monótona en sistemas de eventos discretos , Serie Wiley en probabilidad y estadística, Wiley Interscience, ISBN 978-0-471-58041-6.
• Gordon, Gary (1997), "A β invariant for greedoids and antimatroids", Electronic Journal of Combinatorics , 4 (1): Research Paper 13, doi : 10.37236/1298 , MR  1445628.
• Jamison, Robert (1980), "Copoints in antimatroids", Actas de la Undécima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Florida Atlantic Univ., Boca Raton, Florida, 1980), vol. II , Congreso Numerantium, vol. 29, págs. 535–544, SEÑOR  0608454.
• Kempner, Yulia; Levit, Vadim E. (2003), "Correspondencia entre dos caracterizaciones algorítmicas antimatroides", Electronic Journal of Combinatorics , 10 : Research Paper 44, arXiv : math/0307013 , Bibcode : 2003math......7013K, doi : 10.37236/ 1737, SEÑOR  2014531, S2CID  11015967
• Knauer, Kolja (2009), "Chip-disparo, antimatroides y poliedros", Conferencia europea sobre combinatoria, teoría de grafos y aplicaciones (EuroComb 2009) , Notas electrónicas en matemáticas discretas, vol. 34, págs. 9-13, doi :10.1016/j.endm.2009.07.002, SEÑOR  2591410
• Korté, Bernhard ; Lovász, László ; Schrader, Rainer (1991), Greedoids , Springer-Verlag, págs. 19–43, ISBN 3-540-18190-3.
• Comerciante, Nazarré; Riggle, Jason (2016), "Gramáticas OT, más allá de los órdenes parciales: conjuntos ERC y antimatroides", Lenguaje natural y teoría lingüística , 34 : 241–269, doi :10.1007/s11049-015-9297-5, S2CID  170567540.
• Monjardet, Bernard (1985), "Un uso para redescubrir con frecuencia un concepto", Orden , 1 (4): 415–417, doi :10.1007/BF00582748, S2CID  119378521.
• Parmar, Aarati (2003), "Algunas estructuras matemáticas subyacentes a la planificación eficiente", Simposio de primavera de la AAAI sobre formalización lógica del razonamiento de sentido común (PDF).