Conseguir un enrejado distributivo de Poset o, equivalente, un Greedoid de un Poset

Question

Teórico de fondo

Permite establecer algunos antecedentes para estar seguro de lo que estoy hablando

Posets

Un Poset se define como un par $(S,\leq)$ donde $S$ y sus elementos $s \in S$ están conectados entre sí por una relación binaria $\leq$ la satisfacción de las siguientes propiedades de $s,t,u \in S$:

• $s \leq s$
• $s \leq t \wedge t \leq s \implies s=t$
• $s \leq t \wedge t \leq u \implies s \leq u$

Celosías

Una celosía es un poset , donde siempre es posible, para cada elemento del conjunto $S$: $\forall s \in S$, para encontrar un conocer y unirse. O, equivalentemente, un Mayor límite Inferior y un Mínimo de límite Superior. Conocer y Unirse DEBE ser ÚNICO para todos los elementos del conjunto sin ambigüedad.

El problema

Mi problema es conseguir un Entramado de un Poset. Esto siempre es posible por medio del concepto de Ideal.

Ideal

Un debate sobre la definición de ideal está todavía en curso aquí (en esta comunidad). A continuación me estoy informando de las dos definiciones, una en la Wikipedia artículo de la Wikipedia sobre los Ideales (poset) y el otro en algunos libros autoritativos (ver más abajo).

Definición de Ideal de acuerdo a Wikipedia

Dado poset $(S,\leq)$ consideramos un $I \subseteq S$. Es un Ideal de a $S$ si se tiene la siguiente propiedad:

$$I \subseteq S,\forall x,y\in I\exists z\in I\ x\leq z\ \text{and}\ y\leq z \wedge x \leq y \in I \implies x \in I$$

Definición de Ideal de acuerdo a A. Bjorner, G. M. Ziegler (Matroid Aplicaciones editado por N. L. Blanco - Cambridge University Press - publicado por Primera vez en 1992)

Citando el libro:

"Vamos a $(E,\leq)$ ser finito, parcialmente conjunto ordenado y $F$ el conjunto de los ideales de $E$ (un subconjunto $A \subseteq E$ es un ideal si $x \leq y \in A$ implica $x \in A$)...".

Definición de Ideal de acuerdo a Alexander Schrijver (3 volumen de la enciclopedia "Optimización Combinatoria - Volumen" - Springer - 2002)

Citando el libro:

"Cada parcialmente conjunto ordenado $(S,\leq)$ da una celosía distributivo de la siguiente manera. Llamar a un subconjunto $I \subseteq S$ menor ideal, o simplemente un ideal, si $t \in I$ $s \leq t$ implica que el $s \in I$...".

La construcción de la Celosía

Para obtener un Entramado de un Poset $(S,\leq)$, uno debe considerar el conjunto de los Ideales de $S$. Mi problema es saber si puedo realizar este proceso correctamente. Así que por favor, se puede construir el entramado de la poset caracteriza por los siguientes elementos donde $\leq$ es el conjunto clásico de contención de la relación?

$$S = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{3,4\}, \{1,2,3\}, \{2,3,4\}, \{1,2,3,4\} \}$$

De manera más compacta:

$$S = \{ A, B, C, D, E, F, G, H, I, L \}$$

Gracias

Lo que yo pensaba

Pensé acerca de algunas de las posibles respuestas, pero no sé si mi interpretación es correcta.

Que uno me estoy refiriendo?

Teniendo en cuenta la presencia de algunas de las definiciones de Ideal aquí, me deja claro que a mí me hizo la siguiente hipótesis basándose en las definiciones que he encontrado en los libros que he leído.

Es el juego de poder?

Buscando en la definición de ideal parece que tengo que tomar todos los subconjuntos de a $S$ y, para cada subconjunto, con el fin de hacer de él un ideal, tengo que tomar todos los subconjuntos de a $I$. Así que voy a obtener el conjunto de todos los Ideales. Pero esto sería un juego de poder de $S$ y no creo que este es el conjunto de todos los ideales de a $S$.

Es correcto lo que estoy diciendo?

En el Ideal de la definición de "$I \subseteq S$ Ideal si $t \in I$ $s \leq t$ implica que $s \in I$", $s$ se consideran elementos en $S$?

Si considero que un subconjunto de a $S$, considero que por ejemplo $t \in S$, $t = H = \{ 1,2,3 \}$. La condición de me dice que me deben considerar a todos los subconjuntos de a $H$? Yo creo que no. Dice que debo buscar $s \leq t$. Pero, utilizando el $\leq$ operador de algo implica que $s$ es un elemento en el $S$ derecho? Así que, en mi caso, considerando $t$, tengo que pensar en mi ideal también $\{1,2\}, \{1\}, \{2\}, \emptyset$.

Es correcto esto?

Además

Esta pregunta fue editado cambiar el ideal de la definición con la reportada en la Wikipedia. Últimamente he cambiado a esta pregunta de nuevo de informes de todas las definiciones y sus correspondientes fuentes.

El punto es que un concepto diferente del Ideal está siendo formulado por el artículo de la Wikipedia, mientras que en algunos libros autoritativos otras definiciones (más sencillo). Los cambios en esta pregunta se hizo con el fin de discutir también sobre esta otra de las muchas propósito de la pregunta (el problema que se me preguntó acerca de).

Una nueva pregunta

La definición en Wikipedia añade una condición que no puedo ver en la mayoría de los textos auténticos acerca de la optimización combinatoria. Por favor, me explique la equivalencia con las relaciones que he proporcionado, que no puedo entender.

Answer 1

Puesto que el poset es pequeña, puede ayudarle a dibujar su diagrama de Hasse:

                           L  
                          / \
                         /   \  
                        /     \  
                       H       I  
                       |       |  
                       F       G  
                      / \     / \  
                     B   C   D   E  
                      \  |   |  /  
                       \ |   | /  
                        \ \ / /  
                         \| |/
                           A

Un más bajo establecido (o en los términos de un ideal) es un conjunto con la propiedad de que si uno de estos elementos está en, cada elemento por debajo de eso es también en ella. Así, inmediatamente obtendrá una ideal para cada uno de los nueve elementos:

$$\begin{array}{}A&\mapsto&\{A\}\\B&\mapsto&\{B,A\}\\C&\mapsto&\{C,A\}\\D&\mapsto&\{D,A\}\\E&\mapsto&\{E,A\}\\F&\mapsto&\{F,B,C,A\}\\G&\mapsto&\{G,D,E,A\}\\H&\mapsto&\{H,F,B,C,A\}\\I&\mapsto&\{I,G,D,E,A\}\\ L&\mapsto&\{L,H,I,F,G,B,C,D,E,A\} \end{array}\tag{1}$$

However, these aren't the only lower sets of the poset. For example, $\{B,C,A\}$ is a lower set: it contains everthing that is below any of its members. Two more lower sets not in the list $1$ are $ \ {A, B, C, D\} $and$ \ {A, B, C, D, E, G\} $. Usted debe ser capaz de encontrar bastantes más.

Answer 2

No todos los subconjuntos de $S$ son ideales. Por ejemplo $\{\{1\},\{2\}\}$ no es un ideal puesto que no está cerrado hacia abajo. Por otra parte, hay ideales diferentes del conjunto potencia de $S$ $\{\emptyset, \{1\}\}$.

Nos lista todos los ideales por el % de cardinalidad $n$de su elemento más grande. (1) si $n=0$ luego el ideal es $\{\emptyset\}$ (2) si $n=1$ entonces tiene $\{\emptyset, \{a\}\},\ \{\emptyset, \{a\}, \{b\}\},\ \{\emptyset, \{a\},\{b\},\{c\}\}$ y $\{\emptyset, \{a\},\{b\},\{c\},\{d\}\}$, donde $a,b,c,d\in\{1,2,3,4\}$ (3) si $n=2$ entonces haz $\{\emptyset, \{a,b\},\{a\},\{b\}\}$ donde $a\in\{1,3\},\ b\in\{2,4\}$ y $\{\emptyset, \{1,2\}, \{2,3\}, \{1\}, \{2\},\{3\},\{4\}\}$. Debe quedar claro cómo proceder desde allí.

Answer 3

Con respecto a la parte sin resolverse la cuestión relativa a los Ideales, creo que tengo una respuesta.

Las referencias más importantes

En el fin de explicar mejor, me voy a referir a los siguientes libros autoritativos:

• (R1) "Celosía Teoría" por Garrett Birkhoff - Sociedad Matemática Americana - 1984

• (R2) "Matroid Aplicaciones" de la Enciclopedia de las Matemáticas y sus Aplicaciones N. L. Blanco - G. Rota - 1992 (publicado por primera vez)

• (R3) "optimización Combinatoria, Poliedros y Eficiencia, control de Volumen en los Caminos, los Flujos y las elecciones" por Alexander Schrijver - Springer - 2002

Las diferencias

Resultados de R2 y R3 son los reportados en la pregunta.

Birkhoff formulación

Birkhoff en R1 página 25 (Capítulo II, Párrafo 3: "Morfismos y los ideales"), en realidad se centra en la definición de los ideales de la siguiente manera (cita):

Un Ideal es un nonvoid subconjunto $J$ de un entramado (o unir-semilattice) $L$ con las propiedades

(2) $a \in J, x \in L, x \leq a$ implican $x \in J$

(3) $a \in J, b \in J$ implican $a \vee b \in J$

Birkhoff es una de las figuras más importantes de esta teoría.

Dónde está la diferencia?

Wikipedia en realidad es proporcionar una formulación equivalente a la proporcionada por Birkhoff con un posible error, Birkoff define los Ideales de Celosías con el fin de obtener otra red. Birkhoff comienza a partir de un Entramado mientras que los otros autores se refieren a Posets. De esta manera, el artículo en Wikipedia es incorrecta porque es hypothizing un Poset y condiciones de uso evaluados por Birkhoff para Celosías.

Tenemos, así, sin preocuparse mucho acerca de los nombres (lo que importa es el concepto), dos tipos de ideales en la literatura:

• Poset Ideales capaces de dejar un pase de un Poset a la rejilla.

• Celosías Ideales capaz de dejar pasar de una red a otra red

Espero que esto ayude.