En las matemáticas de matroides y celosías , una celosía geométrica es una celosía semimodular atomista finita , y una celosía matroide es una celosía semimodular atomística sin los supuestos de finitud. Las celosías geométricas y las celosías matroides, respectivamente, forman las celosías de los planos de matroides finitas e infinitas, y cada celosía geométrica o matroide proviene de una matroide de esta manera.
Definición
Una celosía es un conjunto en el que dos elementos cualesquiera y tienen ambos un supremo , denotado por, y un infimum , denotado por.
- Las siguientes definiciones se aplican a los posets en general, no solo a las celosías, excepto donde se indique lo contrario.
- Por un elemento mínimo , no hay elemento tal que .
- Un elemento cubre otro elemento (Escrito como o ) Si y no hay elemento distinto de ambos y así que eso .
- Una cubierta de un elemento mínimo se llama átomo .
- Una red es atomista si cada elemento es el supremo de algún conjunto de átomos.
- Un poset se califica cuando se le puede asignar una función de rango mapeando sus elementos a números enteros, de modo que cuando sea , y también cuando sea .
- Cuando un poset calificado tiene un elemento inferior, se puede asumir, sin perder generalidad, que su rango es cero. En este caso, los átomos son los elementos con rango uno.
- Una celosía graduada es semimodular si, para cada y , su función de rango obedece a la identidad [1]
- Una celosía matroide es una celosía que es tanto atomística como semimodular. [2] [3] A geométrico de celosía es un finito matroid celosía. [4]
- Algunos autores consideran sólo las celosías matroides finitas y usan los términos "celosía geométrica" y "celosía matroide" indistintamente para ambos. [5]
Criptomorfismo
Las celosías geométricas son criptomórficas a matroides (finitas, simples), y las celosías matroides son criptomórficas a matroides simples sin el supuesto de finitud.
Al igual que las celosías geométricas, las matroides están dotadas de funciones de rango , pero estas funciones asignan conjuntos de elementos a números en lugar de tomar elementos individuales como argumentos. La función de rango de una matroide debe ser monótona (agregar un elemento a un conjunto nunca puede disminuir su rango) y deben ser funciones submodulares , lo que significa que obedecen a una desigualdad similar a la de las celosías semimodulares:
Los conjuntos máximos de un rango determinado se denominan planos. La intersección de dos pisos es nuevamente un piso, definiendo una operación de límite inferior mayor en pares de pisos; también se puede definir un límite superior mínimo de un par de pisos 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 una matroide forman una celosía matroide, o (si la matroide es finita) una celosía geométrica. [4]
Por el contrario, si es una red matroide, se puede definir una función de rango en 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 una matroide. Este matroide es necesariamente simple, lo que significa que cada conjunto de dos elementos tiene rango dos. [4]
Estas dos construcciones, de una matroide simple a partir de una celosía y de una celosía a partir de una matroide, son inversas entre sí: partiendo de una celosía geométrica o una matroide simple, y realizando ambas construcciones una tras otra, se obtiene una celosía o matroide que es isomorfo al original. [4]
Dualidad
Hay dos nociones naturales diferentes de dualidad para una celosía geométrica. : el matroide dual, que tiene como base conjuntos los complementos de las bases del matroide correspondientes a, y la celosía dual , la celosía que tiene los mismos elementos queen 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 atomista no se conserva mediante la inversión de orden. Cheung (1974) define el adjunto de una celosía geométrica (o de la matroide definida a partir de ella) para ser una celosía geométrica mínima en la que la celosía dual de está incrustado en el orden . Algunas matroides no tienen adjuntos; un ejemplo es el matroide Vámos . [6]
Propiedades adicionales
Cada intervalo de una celosía geométrica (el subconjunto de la celosía entre elementos de límite superior e inferior dados) es en sí mismo geométrico; tomar un intervalo de una celosía geométrica corresponde a formar un menor de la matroide asociada. Las celosías geométricas se complementan y, debido a la propiedad de intervalo, también se complementan relativamente. [7]
Cada celosía finita es una sub-celosía de una celosía geométrica. [8]
Referencias
- ^ Birkhoff (1995) , Teorema 15, p. 40. Más precisamente, la definición de Birkhoff dice "Llamaremos P (superior) semimodular cuando satisfaga: si a ≠ b ambos cubren c , entonces existe un d ∈ P que cubre tanto a como b " (p.39). Teorema 15 estados: "A clasifican enrejado de longitud finita es semimodular si y sólo si r ( x ) + r ( y ) ≥ r ( x ∧ y ) + r ( x ∨ y )".
- ^ Maeda, F .; Maeda, S. (1970), Teoría de celosías simétricas , Die Grundlehren der Mathischen Wissenschaften, Band 173, Nueva York: Springer-Verlag, MR 0282889.
- ^ Galés, DJA (2010), Matroid Theory , Publicaciones de Courier Dover, p. 388, ISBN 9780486474397.
- ↑ a b c d Galés (2010) , p. 51.
- ^ Birkhoff, Garrett (1995), Lattice Theory , Colloquium Publications, 25 (3ª ed.), American Mathematical Society, p. 80, ISBN 9780821810255.
- ^ Cheung, Alan LC (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin , 17 (3): 363–365, corrección, ibid. 17 (1974), núm. 4, 623, doi : 10.4153 / CMB-1974-066-5 , Sr. 0373976.
- ^ Galés (2010) , págs. 55, 65–67.
- ^ Galés (2010) , p. 58; Welsh atribuye este resultado a Robert P. Dilworth , quien lo probó en 1941-1942, pero no da una cita específica para su prueba original.
enlaces externos
- "Celosía geométrica" . PlanetMath .
- Secuencia OEIS A281574 (Número de celosías geométricas sin etiquetar con n elementos)