6.4: Extensiones Lineales de Conjuntos Parcialmente Ordenados

Última actualización
Guardar como PDF

Page ID: 118429

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Dejar\(P=(X,P)\) ser un conjunto parcialmente ordenado. Un orden lineal\(L\) on\(X\) se llama una extensión lineal (también, una especie topológica) de\(P\), si\(x<y\) en\(L\) siempre que\(x<y\) en\(P\). Por ejemplo, la tabla mostrada en la Figura 6.23 muestra que nuestro ejemplo familiar\(P_3\) tiene 11 extensiones lineales.

Screen Shot 2022-03-04 a las 9.49.07 AM.png — Figura **6.23.** Un poset y sus extensiones lineales

Discusión 6.24

Bob dice que no está convencido de que cada poset finito tenga una extensión lineal. Alice dice que es fácil demostrar que lo hacen. ¿Ella tiene razón?

Carlos dice que hay sutilezas a esta pregunta cuando el conjunto de suelo\(X \) es infinito. Es posible que desee hacer una búsqueda en la web sobre el nombre Szpilrajn y leer sobre su contribución a este número.

El problema de clasificación clásica estudiado en todos los cursos elementales de informática es determinar un orden lineal desconocido\(L\) de un conjunto\(X\) haciendo una serie de preguntas de la forma: ¿Está\(x<y\) en\(L\)? Todos los algoritmos de clasificación conocidos (bubble sort, merge sort, quick sort, etc.) proceden de esta manera.

Discusión 6.25

Dado el poset\(P=(X,P)\) mostrado en la Figura 6.5 y el problema de determinar una extensión lineal desconocida de\(P\), ¿cómo debería Alice decidir qué pregunta (de la forma: ¿Está\(x<y\) en\(L\)?) preguntar?

¿Cómo te gustaría que te asignaran para contar el número de extensiones lineales de este poset? En general, ¿qué tan difícil es determinar el número de extensiones lineales de un poset? ¿Podrías (y tu computadora) hacer esto contar para un poset en 100,000 puntos?