Examen Final de Combinatoria Algebraica

Instrucciones.

• El examen dura desde el Miércoles 23 de Abril a las 4pm hasta el Miércoles 30 de Abril a las 4pm. Durante esa semana, usted puede consultar cualquier fuente: apuntes, libros, bibliotecas, internet, etc. Sin embargo, no puede hablar sobre el examen ni mostrárselo a nadie distinto del profesor.

• La idea de este examen es aprender. Mucho. Para eso hay que trabajar. Mucho. El examen no es demasiado difícil, pero sí es demasiado largo. Reserve bastante tiempo para resolverlo y no lo deje para última hora!

• Por último, cuénteme aproximadamente cuánto tiempo le dedicó a este examen. Esto no es para generar competencia entre ustedes, ni tendrá ningún efecto sobre su nota; es sólo para mi información.

• Mucha suerte!

1. Cómo Contar los Racionales Una representación pseudobinaria de n es una partición de n en potencias de dos, de modo que cada sumando aparece máximo dos veces. Por ejemplo, las representaciones pseudobinarias de 10 son 8 + 2, 8 + 1 + 1, 4 + 4 + 2, 4 + 4 + 1 + 1 y 4 + 2 + 2 + 1 + 1. Sea a(n) el número de representaciones pseudobinarias de n.

(a) Encuentre una fórmula para la función generatriz A(x) = ∑ a(n)x^{n}.

(b) Demuestre que A(x) = (1 + x + x^{2})A(x^{2}). Comparando los coeficientes de x^{2n} y de x^{2n+1} en los dos lados de esta ecuación, concluya que a(2n) = a(n) + a(n − 1) y que a(2n + 1) = a(n).

(c) Dé una demostración combinatoria de las dos igualdades de la parte (b).

Considere el árbol infinito con raíz, tal que cada vértice tiene dos hijos. Empezando con la raíz, y bajando piso por piso de izquierda a derecha, escriba en los vértices del árbol las fracciones a(0)/a(1) , a(1)/a(2) , a(2)/a(3), … en ese orden. Observe que los hijos izquierdo y derecho del vértice con número a(n − 1)/a(n) tienen números a(2n − 1)/a(2n) y a(2n)/a(2n + 1) respectivamente. Por lo tanto, la raíz del árbol tiene el número 1/1, y los hijos izquierdo y derecho de un vértice numerado i/j se numeran i/(i + j) e (i + j)/j, respectivamente. Esto determina la numeración de todo el árbol.

(d) Demuestre que las fracciones escritas en los vértices del árbol son irreducibles. (Sugerencia: Use inducción sobre el piso en el que se encuentra el vértice.)

(e) Demuestre que toda fracción irreducible a/b aparece en algún vértice del árbol. (Sugerencia: Use inducción sobre a + b. Considere dos casos: que la fracción a/b sea mayor o menor que 1.)

(f) Demuestre que ninguna fracción aparece en más de un vértice del árbol. (Sugerencia: Use un argumento análogo al de la parte (e).)

(g) Concluya que a(0)/a(1) , a(1)/a(2) , a(2)/a(3), … es una lista completa y sin repeticiones de todos los números racionales positivos.

2. Ordenes de Intervalos Unitarios Considere n intervalos cerrados I_{1}, …, I_{n} de longitud 1 en la recta real. Sea I_{k} = [a_{k}, a_{k} +1]. Estos intervalos definen un poset P de la siguiente manera: I_{i} < I_{j} si el intervalo I_{i} está estrictamente a la izquierda del intervalo I_{j}; es decir, si a_{i} + 1 < a_{j}. Los posets que se pueden obtener de esta manera se conocen como órdenes de intervalos unitarios.

(a) Recuerde que el número de sucesiones de n 1’s y n −1’s cuyas sumas parciales son no negativas es igual al número de Catalan, C_{n} = \frac{1}{n+1} \binom{2n}{n}. Encuentre una biyección entre estas sucesiones y los órdenes de n intervalos unitarios.

(b) Demuestre que 2 + 2 y 3 + 1 no son órdenes de intervalos unitarios. Concluya que un orden de intervalos unitarios no puede contener a 2 + 2 o a 3 + 1 como subposet.

(c) Demuestre que todos los posets libres de 2+2 y 3+1 son órdenes de intervalos unitarios. (Sugerencia: Use inducción sobre el número de elementos de P. Considere un elemento maximal z de P. Sea A el conjunto de elementos de P menores que z, y B = P − A. Demuestre que B es una anticadena. Ahora considere un conjunto I de intervalos que representan el poset P − z, y añada un intervalo I_{z} que corresponda al elemento z. Desafortunadamente, para que I ∪ I_{z} represente a P, puede ser necesario cambiar un poco la posición de los intervalos de I.)

3. El Método de Campos Finitos Sea A un arreglo de hiperplanos en ℝ^{n}, tal que las ecuaciones que definen los hiperplanos tienen coeficientes enteros. El objetivo de este problema es encontrar un método para calcular el polinomio característico χ_{A}(q). La ecuación de cada hiperplano se puede considerar como una ecuación sobre el campo finito 𝔽_{q} de q elementos, donde q es un primo. Las n-tuplas que son soluciones de esta ecuación forman un hiperplano en el espacio 𝔽_{q}^{n}. De este modo obtenemos un arreglo de hiperplanos A_{q} en 𝔽_{q}^{n}.

(a) Explique brevemente por qué los posets de intersección L_{A} y L_{A_{q}} no siempre son isomorfos. Sin embargo, explique por qué, si q es suficientemente grande, L_{A} ≅ L_{A_{q}}.

(b) Sea q un primo suficientemente grande. Explique por qué la intersección x contiene exactamente q^{dim x} de los puntos de 𝔽_{q}^{n}. Sea

f(y) = ∑_{x≥y en L_{Aq}} μ(y, x)q^{dim x},

de modo que χ_{A}(q) = f(ˆ0). ¿Qué cuenta f(y)? (Sugerencia: Use la fórmula de inversión de Möbius.) Concluya que χ_{A}(q) es el número de puntos de 𝔽_{q}^{n} que no están sobre ningún hiperplano de A_{q}. Este es el método de campos finitos para calcular polinomios característicos.

(c) Use el método de campos finitos para calcular el polinomio característico del arreglo

H_{n} : x_{i} = 0 (1 ≤ i ≤ n).

(d) Use el método de campos finitos para calcular el polinomio característico del arreglo

trenza

B_{n} :  x_{i} = x_{j}  (1 ≤ i < j ≤ n).

4. El Arreglo de Catalan El arreglo de Catalan es el siguiente arreglo de 3\binom{n}{2} hiperplanos en ℝ^{n}:

C_{n} : x_{i} − x_{j} = −1, 0, 1 (1 ≤ i < j ≤ n).

(a) Dibuje el arreglo C_{3}. (Para simplificar el dibujo, dibuje la proyección sobre el plano x_{1} + x_{2} + x_{3} = 0, como hicimos en clase.) ¿Cuántas regiones tiene? ¿Cuántas regiones acotadas tiene? Usando estos dos cálculos y el teorema de Zaslavsky, calcule el polinomio característico χ_{C_{3}}(q).

(b) Se tiene una colección de m puntos dispuestos alrededor de un círculo. Demuestre que el número de formas de colorear k de ellos de rojo, de modo que no haya dos puntos rojos consecutivos, es f(m, k) = \frac{m}{m−k} \binom{m−k}{k}.

(Sugerencia: Es más fácil demostrar que (m − k)f(m, k) = m\binom{m−k}{k}.)

(c) Use el método de campos finitos para concluir que

χ_{C_{n}}(q) = q(q − n − 1)(q − n − 2)(q − n − 3) ⋯ (q − 2n + 2)(q − 2n + 1).

(d) Use el teorema de Zaslavsky para concluir que C_{n} tiene n! C_{n} regiones.

(e) Recuerde que el arreglo trenza B_{n} tiene n! regiones; cada una de ellas corresponde a un ordenamiento de las variables x_{1}, …, x_{n}. El arreglo de Catalan contiene a los hiperplanos del arreglo trenza; por simetría, los hiperplanos restantes parten cada una de estas regiones en C_{n} regiones más pequeñas. Observe esto en su dibujo del caso n = 3. Concentremos nuestra atención en la región x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{n} de B_{n}. El arreglo C_{n} divide a esta región en C_{n} regiones más pequeñas. Encuentre una biyección entre estas regiones y los órdenes de n intervalos unitarios.

Cada problema tiene un valor de 1.5 puntos, para un total posible de 6.0. La distribución de los puntos en cada problema es la siguiente.

• Problema 1: 0.2, 0.2, 0.4, 0.2, 0.2, 0.2, 0.1.

• Problema 2: 0.5, 0.3, 0.7.

• Problema 3: 0.5, 0.6, 0.2, 0.2.

• Problema 4: 0.2, 0.4, 0.3, 0.1, 0.5.