Estructuras aritméticas, núumeros de Catalan y triangulaciones del polígono.

Ponente(s): Carlos Enrique Valencia Oleta

En 1989, Dino Lorenzini introdujo las estructuras aritm\'eticas de una gr\'afica $G$ como un par $({\bf d},{\bf r})$ de vectores enteros positivos, tal que ${\bf r}$ es primitivo y \[ (\mathrm{diag}({\bf d})-A(G)){\bf r}^t={\bf 0}^t, \] donde $A(G)$ es la matriz de adyacencia de $G$. Un ejemplo muy simple est\'a dado por ${\bf d}$, el vector de grados de $G$ y ${\bf r}$, el vector con todas sus entradas igual a uno. En este caso, $\mathrm{diag}({\bf d})-A(G)$ es conocida como la matriz Laplaciana de $G$. Luego, siempre existe al menos un par de vectores que satisfacen estas condiciones. Lorenzini demostr\'o que el conjunto de estructuras aritm\'eticas de una gr\'afica simple es finito, por lo que es natural intentar enumerarlas. En esta pl\'atica haremos un repaso acerca de los \'ultimos avances realizados en el estudio de las estructuras aritm\'eticas. Primero presentaremos las estructuras aritm\'eticas en el marco de las $M$-matrices y demostraremos la finitud de las estructuras aritm\'eticas. El concepto de $M$-matriz ha resultado ser importante en diversas \'areas como probabilidad, an\'alisis num\'erico, econom\'ia e investigaci\'on de operaciones. Prueba de su importancia es el hecho de que existen m\'as de ochenta definiciones equivalentes de una $M$-matriz. Cabe resaltar que toda estructura aritm\'etica es soluci\'on de la ecuaci\'on Diofantina definida por el polinomio \[ f_G(X)=\mathrm{det}(\mathrm{diag}(X)-A(G)), \] donde $X=(x_1,\ldots,x_n)$ es un vector con variables en sus entradas. A pesar de que el D\'ecimo problema de Hilbert afirma que en general no existe un algoritmo para decidir si una ecuaci\'on Diofantina tiene o no soluci\'on, en este caso s\'i existe un algoritmo para encontrar todas las soluciones entero positivas. Presentaremos algunos resultados generales que muestran c\'omo se comporta el conjunto de estructuras aritm\'eticas de una gr\'afica bajo algunas operaciones como subdivisi\'on de aristas, duplicaci\'on de v\'ertices, $\Delta-Y$, etc. Posteriormente nos centraremos en las estructuras aritm\'eticas de una de las gr\'aficas m\'as simples, el camino. En este caso tan especial, las estructuras aritm\'eticas tienen una rica estructura combinatoria, la cual nos permite caracterizarlas y contarlas. Mostraremos que las estructuras del camino con $n$ v\'ertices se pueden obtener de manera inductiva de las estructuras aritm\'eticas de los caminos con menos v\'ertices a trav\'es de la operaci\'on de subdivisi\'on de aristas. Usando este hecho, adem\'as decaminos sobre una reticula y las sucesiones de votaci\'on obtenemos que las estructuras aritm\'eticas de $P_n$ obtenidas de $P_m$ ($m\leq n$) es el numero de votaci\'on \[ b(n-2,n-m)=\frac{m-1}{n-1}\binom{2n-2-m}{n-2} \] y por lo tanto el n\'umero de estructuras aritm\'eticas de $P_n$ es el n\'umero de Catalan $C_{n-1}$. Por otro lado se puede observar que las estructuras aritm\'eticas del camino presentan cierta simetr\'ia. Usando el concepto de estructura aritm\'etica extendida mostraremos que todas las estructuras aritm\'eticas del camino pueden ser obtenidas de una sola estructura aritm\'etica y estableceremos una biyecci\'on entre las estructuras aritm\'eticas de $P_n$ y las triangulaciones del poligono con $n+1$ lados. Como consecuencia obtenemos que las estructuras aritm\'eticas de $P_n$ con su $i$-esima entrada igual a $n-k-1$ es el n\'umero de votaci\'on $b(n-2,k)$.