COMBINATORIA ALGEBRAICA

Tarea 3

Federico Ardila

Fecha de entrega: 27 de Febrero de 2003

Instrucciones: Entregue 4 de los siguientes problemas. El problema 5 cuenta como 3 problemas diferentes. Cada problema vale entre 5 y 10 puntos, dependiendo de la solución y la dificultad del problema.

Problemas

1. (EC, Ejercicio Suplementario 3.1) Sea P un poset de n elementos. Para cada x ∈ P, sea c_{x} el número de elementos de P que son menores o iguales que x. Sea e(P) el número de extensiones lineales de P. Demostrar que

e(P) ≥ \frac{n!}{∏_{x∈P} c_{x}} .

2. Demuestre que el poset Π_{n} de particiones de [n] es un látice. ¿Para qué valores de n es distributivo?

3. Si λ = (λ_{1}, λ_{2}, …) y μ = (μ_{1}, μ_{2}, …) son dos particiones de n, se dice que λ domina a μ si λ_{1} + ⋯ + λ_{i} ≥ μ_{1} + ⋯ + μ_{i} para todo entero positivo i. Sea Par(n) el poset de particiones de n, donde λ ≥ μ si y sólo si λ domina a μ. Demuestre que Par(n) es un látice.

4. Sea G un grafo finito cuyo conjunto de vértices es V. Un subconjunto U ⊆ V es G-conexo si la restricción de G a U es conexa. Considere las particiones π del conjunto V tales que cada parte de π es G-conexa. Sea L_{G} el poset de tales particiones, ordenadas por refinamiento. Demuestre que L_{G} es un látice.

5. Sea A el conjunto de palabras finitas cuyos dígitos son 0’s y 1’s. Se define un orden parcial en A de la siguiente manera: las palabras que cubren a a son las palabras que se obtienen al cambiar un 1 de a por un 0, y la palabra que se obtiene al añadir un 1 al final de a.

(a) Demuestre que A es un poset graduado, y que el número de elementos en el nivel i es igual a F_{i}, el i-ésimo número de Fibonacci.

(b) Demuestre que A es un látice.

(c) Demuestre que cualquier intervalo de A es un látice distributivo.

6. (EC, Ejercicio 3.22b) Sea L un látice distributivo finito y f : ℕ → ℕ una función tales que, para cada x ∈ L, si x cubre a exactamente i elementos de L, entonces a x lo cubren exactamente f(i) elementos de L. Demuestre que L ≅ B_{k} para algún entero positivo k.