Rejilla geométrica

En las matemáticas de los matroides y las redes , una red geométrica es una red semimodular atomística finita , y una red de matroides es una red semimodular atomística sin la suposición de finitud. Las redes geométricas y las redes de matroides, respectivamente, forman las redes de planos de matroides finitos, o finitos e infinitos, y toda red geométrica o de matroides proviene de un matroide de esta manera.

Un retículo es un conjunto parcialmente ordenado en el que cualesquiera dos elementos${\displaystyle x}$y${\displaystyle y}$tienen ambos un límite superior mínimo, llamado unión o supremo , denotado por${\displaystyle x\vee y}$y un límite inferior máximo, llamado punto de encuentro o ínfimo , denotado por${\displaystyle x\wedge y}$.

Las siguientes definiciones se aplican a los conjuntos parcialmente ordenados en general, no solo a los retículos, salvo que se indique lo contrario.

• Para un elemento mínimo${\displaystyle x}$, no hay ningún elemento${\displaystyle y}$de tal manera que${\displaystyle y<x}$.
• Un elemento${\displaystyle x}$cubre otro elemento${\displaystyle y}$(escrito como${\displaystyle x:>y}$o${\displaystyle y<:x}$) si${\displaystyle x>y}$y no hay ningún elemento${\displaystyle z}$distinto de ambos${\displaystyle x}$y${\displaystyle y}$de modo que${\displaystyle x>z>y}$.
• Una cubierta de un elemento mínimo se llama átomo .
• Una red cristalina es atomística si cada elemento es el supremo de algún conjunto de átomos.
• Un conjunto parcialmente ordenado se considera graduado cuando se le puede asignar una función de rango.${\displaystyle r(x)}$mapeando sus elementos a números enteros, de tal manera que${\displaystyle r(x)>r(y)}$cuando sea${\displaystyle x>y}$y también${\displaystyle r(x)=r(y)+1}$cuando sea${\displaystyle x:>y}$.

Cuando un conjunto parcialmente ordenado graduado tiene un elemento mínimo, se puede asumir, sin pérdida de generalidad, que su rango es cero. En este caso, los átomos son los elementos con rango uno.

• Una red graduada es semimodular si, para cada${\displaystyle x}$y${\displaystyle y}$, su función de rango obedece la identidad ^{[ 1 ]}

${\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).\,}$

• Una red matroide es una red que es a la vez atomística y semimodular. ^{[ 2 ] [ 3 ]} Una red geométrica es una red matroide finita . ^{[ 4 ]}

Muchos autores consideran únicamente retículos matroidales finitos y utilizan los términos "retículo geométrico" y "retículo matroide" indistintamente para ambos. ^{[ 5 ]}

Las redes geométricas son equivalentes a matroides simples (finitos), y las redes de matroides son equivalentes a matroides simples sin la suposición de finitud (bajo una definición apropiada de matroides infinitos; existen varias definiciones de este tipo). La correspondencia radica en que los elementos del matroide son los átomos de la red, y un elemento x de la red corresponde al plano del matroide que consta de aquellos elementos del matroide que son átomos.${\displaystyle a\leq x.}$

Al igual que una red geométrica, un matroide está dotado de una función de rango , pero dicha función asigna un conjunto de elementos del matroide a un número en lugar de tomar un elemento de la red como argumento. La función de rango de un matroide debe ser monótona (añadir un elemento a un conjunto nunca puede disminuir su rango) y debe ser submodular , lo que significa que obedece una desigualdad similar a la de las redes semimodulares con rango:

${\displaystyle r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y)}$

para conjuntos X e Y de elementos de matroide. Los conjuntos máximos de un rango dado se denominan planos . La intersección de dos planos es también un plano, que define una operación de cota inferior máxima en pares de planos; también se puede definir una cota superior mínima de un par de planos como el superconjunto máximo (único) de su unión que tiene el mismo rango que su unión. De esta forma, los planos de un matroide forman una red de matroides o (si el matroide es finito) una red geométrica. ^{[ 4 ]}

Por el contrario, si${\displaystyle L}$Si se trata de una red matroide, se puede definir una función de rango sobre conjuntos de sus átomos, definiendo el rango de un conjunto de átomos como el rango de la red del límite superior más bajo del conjunto. Esta función de rango es necesariamente monótona y submodular, por lo que define un matroide. Este matroide es necesariamente simple, lo que significa que todo conjunto de dos elementos tiene rango dos. ^{[ 4 ]}

Estas dos construcciones, la de un matroide simple a partir de una red y la de una red a partir de un matroide, son inversas entre sí: partiendo de una red geométrica o un matroide simple, y realizando ambas construcciones una tras otra, se obtiene una red o un matroide isomorfo al original. ^{[ 4 ]}

Existen dos nociones naturales diferentes de dualidad para una red geométrica.${\displaystyle L}$: el matroide dual , que tiene como conjuntos base los complementos de las bases del matroide correspondientes a${\displaystyle L}$y la red dual , la red que tiene los mismos elementos que${\displaystyle L}$en orden inverso. No son lo mismo, y de hecho, la red dual generalmente no es en sí misma una red geométrica: la propiedad de ser semimodular (superior) no se conserva al invertir el orden. Un ejemplo simple de una red geométrica cuya red dual no es geométrica es la red de planos del matroide uniforme de rango 3 con 4 elementos. Cheung (1974) define el adjunto de una red geométrica${\displaystyle L}$(o del matroide definido a partir de él) para ser una red geométrica mínima en la que la red dual de${\displaystyle L}$es incrustado en el orden . Algunos matroides no tienen adjuntos; un ejemplo es el matroide Vámos . ^{[ 6 ]}

Cada intervalo de una red geométrica (el subconjunto de la red entre elementos límite inferior y superior dados) es en sí mismo geométrico; tomar un intervalo de una red geométrica corresponde a formar un menor del matroide asociado. Las redes geométricas son complementadas y, debido a la propiedad de intervalo, también son relativamente complementadas. ^{[ 7 ]}

Toda red finita es una subred de una red geométrica. ^{[ 8 ]}

• "Red geométrica" , PlanetMath
• Secuencia OEIS A281574 (Número de redes geométricas sin etiquetar con n elementos)