Celosía geométrica

En las matemáticas de matroides y retículos , un retículo geométrico es un retículo semimodular atomístico finito , y un retículo matroide es un retículo semimodular atomístico sin el supuesto de finitud. Los retículos geométricos y los retículos matroidales, respectivamente, forman los retículos de planos de matroides finitos, o finitos e infinitos, y cada retículo geométrico o matroide proviene de un matroide de esta manera.

Definición

Una red es un conjunto de elementos en el que dos elementos cualesquiera y tienen un límite superior mínimo, llamado unión o supremo , denotado por , y un límite inferior máximo, llamado encuentro o ínfimo , denotado por . ${\estilo de visualización x}$ ${\estilo de visualización y}$ $x\vee y$ $x\cuña y$

Las siguientes definiciones se aplican a los posets en general, no solo a los reticulados, excepto que se indique lo contrario.
Para un elemento mínimo , no existe ningún elemento tal que . ${\estilo de visualización x}$ ${\estilo de visualización y}$ $y<x$
Un elemento cubre otro elemento (escrito como o ) si y no hay ningún elemento distinto de ambos y de modo que . ${\estilo de visualización x}$ ${\estilo de visualización y}$ $x:>y$ ${\estilo de visualización y<:x}$ $x>y$ ${\estilo de visualización z}$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ $x>z>y$
La cubierta de un elemento mínimo se llama átomo .
Una red es atomística si cada elemento es el supremo de algún conjunto de átomos.
Un conjunto posesivo se clasifica cuando se le puede dar una función de rango que asigne sus elementos a números enteros, de modo que siempre que , y también siempre que . ${\estilo de visualización r(x)}$ $r(x)>r(y)$ $x>y$ $r(x)=r(y)+1$ $x:>y$
Cuando un conjunto ordenado de elementos tiene un elemento inferior, se puede suponer, 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 y , su función de rango obedece a la identidad ^[1] ${\estilo de visualización x}$ ${\estilo de visualización y}$
$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 redes matroidales finitas y utilizan los términos "red geométrica" y "red matroide" indistintamente para ambos. ^[5]

Retículas vs. matroides

Las redes geométricas son equivalentes a matroides simples (finitos), y las redes de matroides son equivalentes a matroides simples sin el supuesto de finitud (según una definición apropiada de matroides infinitos; existen varias definiciones de este tipo). La correspondencia es 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. $a\leq x.$

Al igual que un retículo geométrico, un matroide está dotado de una función de rango , pero esa función asigna un conjunto de elementos del matroide a un número en lugar de tomar un elemento del retículo como argumento. La función de rango de un matroide debe ser monótona (agregar 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 los retículos clasificados semimodulares:

r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y)

para los conjuntos X e Y de elementos matroides. Los conjuntos máximos de un rango dado se denominan planos . La intersección de dos planos es nuevamente un plano, que define una operación de límite inferior máximo en pares de planos; también se puede definir un límite superior mínimo 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 manera, los planos de un matroide forman una red matroide o (si el matroide es finito) una red geométrica. ^[4]

Por el contrario, si es 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 red del límite inferior más grande 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 cada conjunto de dos elementos tiene rango dos. ^[4] ${\estilo de visualización L}$

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

Dualidad

Existen dos nociones naturales diferentes de dualidad para una red geométrica : la matroide dual, que tiene como conjuntos de base los complementos de las bases de la matroide correspondientes a , y la red dual , la red que tiene los mismos elementos que en el 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 atomística no se conserva por la inversión de orden. Cheung (1974) define el adjunto de una red geométrica (o de la matroide definida a partir de ella) como una red geométrica mínima en la que la red dual de está incrustada en orden . Algunas matroides no tienen adjuntos; un ejemplo es la matroide Vámos . ^[6] ${\estilo de visualización L}$ ${\estilo de visualización L}$ ${\estilo de visualización L}$ ${\estilo de visualización L}$ ${\estilo de visualización L}$

Propiedades adicionales

Cada intervalo de una red geométrica (el subconjunto de la red entre elementos dados de cota inferior y superior) 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 complementarias y, debido a la propiedad de intervalo, también son complementarias relativamente. ^[7]

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

Referencias

^ Birkhoff (1995), Teorema 15, p. 40. Más precisamente, la definición de Birkhoff dice: "Llamamos a P (superior) semimodular cuando satisface: Si a ≠ b ambos cubren c , entonces existe un d ∈ P que cubre tanto a como b " (p.39). El Teorema 15 establece: "Una red graduada de longitud finita es semimodular si y solo si r ( x ) + r ( y ) ≥ r ( x ∧ y ) + r ( x ∨ y )".
^ Maeda, F.; Maeda, S. (1970), Teoría de las celosías simétricas , Die Grundlehren der mathematischen Wissenschaften, Band 173, Nueva York: Springer-Verlag, MR 0282889.
^ Welsh, DJA (2010), Teoría matroide , Publicaciones Courier Dover, p. 388, ISBN 9780486474397.
^ abcd Welsh (2010), pág. 51.
^ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3.ª ed.), American Mathematical Society, pág. 80, ISBN 9780821810255.
^ Cheung, Alan LC (1974), "Adjuntos de una geometría", Canadian Mathematical Bulletin , 17 (3): 363–365, corrección, ibid. 17 (1974), núm. 4, 623, doi : 10.4153/CMB-1974-066-5 , MR 0373976.
^ Welsh (2010), págs. 55, 65–67.
^ Welsh (2010), pág. 58; Welsh atribuye este resultado a Robert P. Dilworth , quien lo demostró en 1941-1942, pero no da una cita específica para su prueba original.

Enlaces externos

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