Posets y retículos · Definición

Retículo

combinatoria enumerativaposets y retículos

Antes de empezar necesitas conocer

Los retículos generalizan la idea de unión y de intersección de conjuntos a cualquier relación de orden. Aparecen en combinatoria enumerativa al estudiar el orden de inclusión de particiones y de subespacios.

Definición

Un retículo es un conjunto parcialmente ordenado (L, ≤) en el que cada par de elementos x e y tiene un supremo (x ∨ y) y un ínfimo (x ∧ y).

\[x \vee y = \sup\{x,y\}, \quad x \wedge y = \inf\{x,y\}\]

Si \(L\) es un retículo, las operaciones \(\vee\) y \(\wedge\) son conmutativas, asociativas y satisfacen las leyes de absorción \(x \wedge (x \vee y) = x\) y \(x \vee (x \wedge y) = x\). Además, un poset finito con un elemento mínimo \(\hat{0}\) y un elemento máximo \(\hat{1}\) es retículo si y solo si cada par tiene supremo e ínfimo, lo que equivale a comprobar solo la existencia de estos objetos en pares.

Consideremos el poset de los divisores de 12 ordenado por divisibilidad. El supremo de 4 y 6 es 12 y el ínfimo es 2, porque 2 es el mayor divisor común de ambos. Así, este conjunto forma un retículo en el que \(x \vee y = \operatorname{mcm}(x,y)\) y \(x \wedge y = \operatorname{mcd}(x,y)\).

Un error típico es afirmar que todo poset con mínimo y máximo es un retículo. Por ejemplo, en el poset \(\hat{0} < a, b < c, d < \hat{1}\), los elementos \(a\) y \(b\) tienen dos cotas superiores minimales e incomparables, \(c\) y \(d\), así que no tienen supremo y el poset no es retículo.

Para pensar

¿Por qué tener mínimo y máximo no basta para que un poset sea retículo?

Porque dos elementos pueden tener varias cotas superiores (o inferiores) minimales incomparables, y entonces no existe un supremo (o ínfimo) único.

Ejercicios 10

  1. ¿Cuál es el supremo de 4 y 6 en el poset de divisores de 12 ordenado por divisibilidad?
  2. En el poset de divisores de 12 ordenado por divisibilidad, ¿cuánto vale \(4 \wedge (4 \vee 6)\)?
  3. En un retículo, ¿qué nombre recibe la operación x ∨ y?
  4. En el poset de los subconjuntos de \(\{1,2,3\}\) ordenado por inclusión, ¿cuál es \(\{1,2\} \vee \{2,3\}\)?
  5. ¿Cuál es el supremo de 2 y 3 en el poset de divisores de 6 ordenado por divisibilidad?
  6. En el poset de divisores de 30 ordenado por divisibilidad, calcula \(6 \wedge 10\).
  7. En el poset de divisores de 60 ordenado por divisibilidad, calcula \(10 \vee 15\).
  8. En el poset \(L=\{\hat{0},a,b,c,\hat{1}\}\) con \(\hat{0}<a,b<c<\hat{1}\), ¿cuál es \(a \wedge b\)?
  9. Sea \(L\) el poset formado por \(\hat{0}\), \(a\), \(b\), \(c\), \(\hat{1}\) con \(\hat{0} < a, b < c < \hat{1}\) (sin relación entre \(a\) y \(b\) salvo las indicadas). ¿Cuántas parejas de elementos de \(L\) carecen de supremo?
  10. ¿Cuántos divisores de 360 cumplen que su par con 12 tiene supremo y un ínfimo que es 4?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.