Anticadena

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 xy ni yx.

El número de anticadenas no vacías definidas sobre un conjunto A dado se conoce como número de Dedekind.

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.