- Anticadena
-
Anticadena
En matemáticas, una anticadena en un conjunto parcialmente ordenado A es un subconjunto de S tal que cada par de miembros de A es incomparable, es decir, para cualquier x, y en A, ni x ≤ y ni y ≤ x.
El teorema de Dilworth establece que la no existencia de una anticadena de tamaño n+1 en S es una condición necesaria y suficiente para que S sea la unión de n órdenes totales o cadenas. Esto motiva preguntas sobre el tamaño de la anticadena máxima.
Por ejemplo, en el conjunto de partes de un conjunto finito X, ordenado por la inclusión, una anticadena máxima es descrita por el lema de Sperner, como los subconjuntos de tamaño 'mediano',|X|/2 en caso de que |X| sea par, y, o bien de (|X|+1)/2 o bien (|X|-1)/2 cuando |X| sea impar; la cardinalidad es el relevante coeficiente binomial.
Categorías: Teoría del orden | Combinatoria
Wikimedia foundation. 2010.