4 votos

Anchura y la altura de conjuntos ordenados parciales

La anchura $w$ parcial del conjunto ordenado(poset) se define como la cardinalidad de la máxima antichain. Por el Teorema de Dilworth, sabemos que es equivalente al número mínimo de cadenas en cualquier partición.

Si se denota un antichain como $A$ y una partición en cadenas como $P$, entonces sabemos $|A| \leq |P|$. Y Dilworth Teorema nos dice que $\exists A_0, P_0$ s.t. $w = |A_0| = |P_0|$.

Del mismo modo, si se denota una cadena como $C$ y una partición en antichains como $Q$, $\exists C_0, P_0$ s.t. la altura de la $h = |C_0| = |Q_0|$.

Desde $|A| \leq |P|$ siempre tiene, para cumplir con la igualdad, se intenta disminuir $|P|$, lo que significa que la partición de la puesta en menos de cadenas. Sin embargo, dado que la cardinalidad del conjunto es fijo, esto hará que (algunos de) las cadenas más largas. Esto significa que podemos aumentar el $|C|$. Y la pregunta es, ¿siempre existe $P = \{C_1, C_2, \dots, C_k\}$ s.t. $|P| = |P_0|$ $|C_i| = |C_0|$ algunos $i$?

(Es decir, no siempre existe una partición en cadenas con un mínimo de $|P|$ y un máximo de $|C|$?)

1voto

bof Puntos 19273

Contraejemplo: Considerar el $6$-elemento poset $\{2,3,4,8,12,36\}$ ordenado por la divisibilidad.

El $4$-elemento de la cadena de $C_0=\{2,4,12,36\}$ y la partición de $Q_0=\{\{2\},\{3,4\},\{8,12\},\{36\}\}$ a $4$ antichains muestran que la altura es de $h=|C_0|=|Q_0|=4$.

El $2$-elemento antichain $A_0=\{3,4\}$ y la partición de $P_0=\{\{2,4,8\},\{3,12,36\}\}$ a $2$ cadenas muestran que el ancho es $w=|A_0|=|P_0|=2$.

Es fácil ver que $P_0$ es la única posible partición de este poset en $2$ cadenas; por lo tanto no hay partición en $2$ cadenas contiene un $4$-elemento de la cadena.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X