Ideales de aristas: un ejemplo de interacción entre el álgebra conmutativa y la combinatoria

FACULTAD DE CIENCIAS TRABAJO FIN DE MÁSTER Máster en Matemáticas IDEALES DE ARISTAS: UN EJEMPLO DE INTERACCIÓN ENTRE EL ÁLGEBRA CONMUTATIVA Y LA COMBINATORIA Autora: Sara Asensio Ferrero Tutor: Philippe Gimenez Año 2023 ii A Philippe, por tanta confianza depositada en m´ı y por hacer que todo sea m´as f´acil, con el deseo de poder seguir trabajando juntos muchos a˜nos A mi madre, mi padre y mi hermano, por la incondicionalidad de su amor y por demostrarme que nunca voy a estar sola mientras est´en ellos A mis abuelos, por la suerte que tengo de haber podido disfrutar de su compa˜n´ıa tanto tiempo y porque no ser´ıa la misma persona si no hubiese podido hacerlo A mis amigos, porque una de las mejores cosas que he hecho ha sido rodearme de ellos Al lugar en el mundo que he encontrado para m´ı iii ´ Indice general 1. Introducci´on 1 2. Ideales de aristas asociados a grafos 3 2.1. Preliminares.................................. 3 2.1.1. Teor´ıadegrafos............................ 5 2.1.2. Escisi´on de ideales . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Aristasdeescisi´on .............................. 7 2.3. V´ertices de escisi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3. Generalizaci´on 31 3.1. Complejos simpliciales e ideales de facetas . . . . . . . . . . . . . . . . . 31 3.2. Hipergrafos e ideales de aristas . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1. Preliminares.............................. 34 3.2.2. Aristas de escisi´on . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2.3. Hipergrafos triangulados . . . . . . . . . . . . . . . . . . . . . . . 49 4. L´ıneas de investigaci´on relacionadas 55 A. Implementaci´on en Macaulay2 57 Bibliograf´ıa 61 v vi ´ INDICE GENERAL Cap´ıtulo 1 Introducci´on El estudio de las resoluciones libres minimales graduadas de ideales monomiales es un ´area de trabajo cl´asica dentro del ´algebra conmutativa que permite el uso de m´etodos combinatorios y ofrece por lo tanto un puente entre las dos ´areas: el ´algebra conmutativa y la combinatoria. Adem´as, la t´ecnica conocida como polarizaci´on permite restringir este estudio al caso de los ideales monomiales libres de cuadrados sin p´erdida de generalidad. Los ideales monomiales cuadr´aticos libres de cuadrados, tambi´en llamados ideales de aristas, que fueron introducidos y estudiados por primera vez por Rafael H. Villarreal en un art´ıculo publicado en 1990 ([23]), ser´an nuestro objeto principal de estudio en el Cap´ıtulo 2 de este trabajo. Pocos a˜nos m´as tarde de haberlos introducido, el mismo autor publicaba un destacado art´ıculo junto con Aron Simis y Wolmer V. Vasconcelos ([24]) en el que continuaban estudiando en profundidad este tipo de ideales asociados a grafos. Es posible encontrar un repaso a la historia de este estudio en un art´ıculo de Rafael H. Villarreal y Mar´ıa Vaz Pinto dedicado a la memoria de Wolmer V. Vasconcelos que ha sido publicado en el mismo a˜no de la redacci´on de este trabajo ([21]). Tradicionalmente, la forma de abordar este estudio consist´ıa en recurrir a herramientas propias del ´algebra homol´ogica. No obstante, problemas como hallar la dimensi´on de un grupo de homolog´ıa pueden llegar a ser altamente complicados y en los ´ultimos a˜nos se ha desarrollado una nueva t´ecnica que permite evitarlos. Esta t´ecnica, que fue introducida por Shalom Eliahou y Michel Kervaire en 1990 en un art´ıculo que ha resultado ser de gran impacto ([5]), se conoce como escisi´on de ideales y permite recuperar muchos de los resultados conocidos como simples corolarios de otros resultados m´as generales. Mi principal objetivo va a ser presentarla detalladamente para ilustrar las ventajas que proporciona, permiti´endonos sustituir los problemas propios de la homolog´ıa por otros puramente combinatorios. Para ello, nos vamos a dedicar a estudiar principalmente los trabajos de Huy T`ai H`a y Adam Van Tuyl ([16], [17]). Aunque en este trabajo nos centraremos en mostrar la interacci´on entre el ´algebra conmutativa y la combinatoria v´ıa el estudio de las resoluciones de ideales monomiales libres de cuadrados, este no es m´as que un ejemplo concreto dentro de los muchos ´ambitos en los que la combinatoria est´a ganando fuerza en los ´ultimos a˜nos. Por ejemplo, en mi Trabajo de Fin de Grado ([1]), del que se puede encontrar un resumen extendido en una nota publicada en la Gaceta de la RSME ([2]), ya mostr´abamos c´omo la teor´ıa de 1 2CAP´ ITULO 1. INTRODUCCI ´ ON grafos resultaba de gran ayuda para resolver una conjetura que hab´ıa sido enunciada hace casi treinta a˜nos dentro de la teor´ıa de la complejidad computacional: la conjetura de la sensibilidad. La forma en la que se estructura este trabajo es la siguiente: en primer lugar, comenzaremos introduciendo las nociones b´asicas para comprender el problema al que queremos enfrentarnos y la forma en que queremos hacerlo, recurriendo a herramientas combinatorias como los grafos, los complejos simpliciales o los hipergrafos, as´ı como a la t´ecnica de escisi´on de ideales. A continuaci´on, lo que haremos ser´a seguir un orden creciente de generalidad; es decir, empezaremos estudiando los ideales de aristas asociados a grafos para continuar con los ideales de facetas asociados a complejos simpliciales y, por ´ultimo, estudiaremos el caso m´as general de los ideales de aristas asociados a hipergrafos. Otro de mis objetivos en este trabajo va a consistir en transmitir mi percepci´on acerca de la naturalidad con la que van surgiendo los distintos objetos de trabajo, en la mayor´ıa de los casos pensados para generalizar algunos tipos concretos de grafos. El Cap´ıtulo 2 va a estar dedicado a estudiar los ideales de aristas asociados a grafos, utilizando [16] como referencia principal. Consideraremos dos tipos de escisiones: la primera, que corresponde a las aristas de escisi´on, nos permitir´a proporcionar una f´ormula para el c´alculo de los n´umeros de Betti graduados de estos ideales en t´erminos de los n´umeros de Betti graduados de los ideales de aristas asociados a ciertos subgrafos. Adem´as, estudiaremos un caso en el que esta f´ormula es recursiva. El otro tipo de escisi´on que vamos a estudiar corresponde a los llamados v´ertices de escisi´on y nos va a permitir obtener un resultado que supone una mejora del conocido Teorema de Fr¨oberg y que muestra una fuerte conexi´on entre el ´algebra conmutativa y la teor´ıa de grafos. En el Cap´ıtulo 3 nos vamos a dedicar a estudiar ideales monomiales libres de cuadrados no necesariamente cuadr´aticos. Para ello utilizaremos [17] como principal referencia, y consideraremos los hipergrafos como objeto combinatorio que nos permitir´a generalizar varios de los resultados presentados en el cap´ıtulo previo. En particular, obtendremos una f´ormula para los n´umeros de Betti graduados de los ideales de aristas asociados a hipergrafos en t´erminos de los n´umeros de Betti graduados de los ideales de aristas asociados a ciertos subhipergrafos, y tambi´en trataremos de generalizar el Teorema de Fr¨oberg. En este ´ultimo caso, veremos que no es posible obtener una generalizaci´on t´ermino a t´ermino del mismo. El ´ultimo cap´ıtulo estar´a dedicado a ilustrar la contemporaneidad del tema tratado en este trabajo, comentando brevemente algunas de las l´ıneas de investigaci´on relacionadas con el tema que permanecen abiertas y con gran actividad en la actualidad. Adem´as del desarrollo te´orico principal del trabajo, dedicaremos un ap´endice a introducir de forma elemental ciertos aspectos b´asicos del paquete EdgeIdeals de Macaulay2. Este paquete, que fue escrito por Christopher A. Francisco, Andrew Hoefel y Adam Van Tuyl, resulta muy c´omodo para el manejo computacional de los ideales de aristas que estudiamos. Cap´ıtulo 2 Ideales de aristas asociados a grafos Comenzamos el desarrollo de este trabajo con un cap´ıtulo dedicado a los objetos menos generales de todos aquellos con los que vamos a trabajar: los grafos. En primer lugar, introduciremos las nociones b´asicas de teor´ıa de grafos que vamos a necesitar, y presentaremos la llamada escisi´on de ideales, t´ecnica que vamos a utilizar tambi´en en cap´ıtulos posteriores para estudiar las resoluciones libres minimales graduadas del tipo de ideales monomiales libres de cuadrados que corresponda a cada secci´on. Cuando hayamos introducido estos preliminares, as´ı como la forma de identificar un grafo con un ideal monomial libre de cuadrados (cuadr´atico en este caso), pasaremos a exponer dos tipos de escisiones que podemos llevar a cabo con el ideal de aristas de un grafo para obtener informaci´on acerca de su resoluci´on libre minimal graduada. 2.1. Preliminares Sea R=k[x1, . . . , xn] un anillo de polinomios sobre un cuerpo arbitrario k. Si I es un ideal homog´eneo de R(o, m´as generalmente, un R-m´odulo graduado finitamente generado), sabemos que le podemos asociar una resoluci´on libre minimal graduada 0→ ⊕jR(−j)βl,j (I)→ ⊕jR(−j)βl−1,j (I)→ · · · → ⊕jR(−j)β0,j (I)→I→0, donde la sucesi´on anterior de R-m´odulos y homomorfismos de R-m´odulos es exacta, l≤n yR(−j) es el resultado de desplazar los grados de los elementos de Ren junidades. Cada n´umero βi,j(I) es el i, j-´esimo n´umero de Betti graduado de I, y tiene la propiedad de que es un invariante de Iigual al n´umero de generadores minimales de grado jen el i-´esimo m´odulo de sizigias de I. En este cap´ıtulo nos vamos a centrar en el estudio de las resoluciones libres minimales graduadas de un tipo concreto de ideales monomiales: aquellos generados por monomios cuadr´aticos libres de cuadrados. El principal motivo que nos lleva a empezar estudiando este tipo de ideales es que es posible identificarlos con grafos simples de nv´ertices v´ıa una biyecci´on sencilla. Antes de detallar esta identificaci´on, definimos un grafo simple como un grafo no dirigido que no tiene aristas m´ultiples (es decir, entre cada par de v´ertices puede existir a lo sumo una arista) y tampoco tiene aristas que vayan de un v´ertice cualquiera en s´ı mismo. Ahora s´ı, es claro que un grafo simple Gcon v´ertices 3 10 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS Por la descripci´on de G(J∩K) que hemos dado en el Corolario 2.2.3 se tiene que uvx yuvy pertenecen a G(J∩K). La condici´on (a) de la Definici´on 2.1.2 implicar´ıa que uvx = mcm(ϕ(uvx), ψ(uvx)) = mcm(uv, ψ(uvx)). Entonces ψ(uvx) tendr´ıa que ser x,ux,vx ouvx. Pero como ψ(uvx)∈ G(K) = G(I(G\e)), queda descartado que ψ(uvx) pueda tomar los valores xouvx porque estos no tienen grado dos; y como vx /∈EG, el ´unico valor posible para ψ(uvx) es ux. Un argumento id´entico nos conduce a que ψ(uvy) = vy. Si consideramos ahora el subconjunto S={uvx, uvy}de G(J∩K), este subconjunto no cumple la propiedad (b) que exig´ıamos en la definici´on de ideal escindible. Esto se debe a que mcm(S) = uvxy = mcm(ψ(S)), de manera que mcm(ψ(S)) no divide estrictamente a mcm(S). Esto nos permite concluir que e=uv no es una arista de escisi´on, ya que I(G) = (uv) + I(G\e) no es una escisi´on del ideal I(G). Queda probada la doble implicaci´on, y por tanto el teorema. Antes de continuar con el desarrollo te´orico del trabajo, vamos a ilustrar la utilidad del Teorema 2.2.4 de caracterizaci´on de las aristas de escisi´on a trav´es de un ejemplo. Ejemplo 2.2.5. Consideramos el siguiente grafo: x1 x3 x2 x5 x4 x6 Gracias al Teorema 2.2.4, podemos concluir mediante una comprobaci´on muy sencilla que x1x2es una arista de escisi´on gracias a que N(x1) = {x2} ⊆ N(x2)∪ {x2}. Sin embargo, como N(x2) = {x1, x3, x4}yN(x4) = {x2, x5, x6}, se tiene que N(x2)⊆ N(x4)∪ {x4}yN(x4)⊆ N(x2)∪ {x2}. De aqu´ı se deduce, utilizando el Teorema de caracterizaci´on de las aristas de escisi´on que hemos enunciado y demostrado previamente, que x2x4no es una arista de escisi´on del grafo anterior. Vamos a introducir ahora un lema que necesitaremos de cara al c´alculo de los n´umeros de Betti graduados de los ideales que nos interesan. No vamos a demostrarlo por ser bien conocido dentro del estudio de resoluciones de ideales homog´eneos, aunque su prueba se puede encontrar en [19]. Lema 2.2.6. Sean R=k[x1, . . . , xn]yS=k[y1, . . . , ym], y sean I⊆RyJ⊆Sideales homog´eneos. Entonces βi,j R I⊗S J= i X l1=0 j X l2=0 βl1,l2R Iβi−l1,j−l2S J. 2.2. ARISTAS DE ESCISI ´ ON 11 Nota 2.2.7.Si I, J ⊆R=k[x1, . . . , xn] son ideales monomiales libres de cuadrados tales que ninguna de las variables que aparecen en los generadores minimales de Iaparecen en los generadores minimales de Jy viceversa, entonces se tiene un resultado propio del ´algebra conmutativa que asegura que R I⊗R J=R I+J. En este caso, el lema anterior implica que βi,j R I+J= i X l1=0 j X l2=0 βl1,l2R Iβi−l1,j−l2R J. Es esta observaci´on la que vamos a utilizar dentro de la prueba del siguiente lema, que nos permite dar un primer paso en nuestro camino hacia el estudio de las resoluciones libres minimales graduadas de los ideales de aristas asociados a grafos. Lema 2.2.8. Sea e=uv una arista de escisi´on de Gy supongamos, sin p´erdida de generalidad por el Teorema 2.2.4, que N(u)⊆(N(v)∪{v}).Si N(v)\{u}={v1, . . . , vd}, J= (uv)yK=I(G\e), entonces para todo i≥1y todo j≥0se tiene que βi−1,j(J∩K) = i X l=0 d lβi−l−1,j−l−2(I(H)) , donde I(H)es el ideal de aristas de H=G\ {u, v, v1, . . . , vd}. Demostraci´on. Como e=uv es una arista de escisi´on con N(u)⊆(N(v)∪{v}), al aplicar el Lema 2.2.2 con (N(u)\{v})⊂(N(v)\{u}) = {v1, . . . , vd}yH=G\(N(u)∪N(v)) = G\ {u, v, v1, . . . , vd}obtenemos J∩K=uv ((v1, . . . , vd) + I(H)) . Pongamos L= (v1, . . . , vd) + I(H). Como ning´un elemento del sistema minimal de generadores de Lformado por monomios es divisible por uy tampoco por v, se tiene que uv no es un divisor de cero en R/L. Esto implica que βi−1,j(J∩K) = βi−1,j(uvL) = βi−1,j−2(L). Adem´as, sabemos que βi−1,j−2(L) = βi,j−2(R/L), y como los conjuntos de variables que aparecen en G((v1, . . . , vd)) y G(I(H)) son disjuntos, podemos aplicar lo que hab´ıamos visto en la Nota 2.2.7 para obtener βi,j−2R L= i X l1=0 j−2 X l2=0 βl1,l2R (v1, . . . , vd)βi−l1,j−l2−2R I(H)= = i X l1=0 j−2 X l2=0 βl1,l2R (v1, . . . , vd)βi−l1−1,j−l2−2(I(H)) . Finalmente, usando el hecho de que v1, . . . , vdes una sucesi´on regular y por tanto los n´umeros de Betti graduados de R (v1,...,vd)se pueden obtener a partir del complejo de Koszul, que es en este caso una resoluci´on, y son βi,j R (v1, . . . , vd)=d isi i=j 0 si i=j , 12 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS ya podemos concluir: βi−1,j(J∩K) = i X l=0 d lβi−l−1,j−l−2(I(H)) , que es la f´ormula del enunciado. Pasamos ahora a enunciar y demostrar el resultado principal de esta secci´on: Teorema 2.2.9. Sea e=uv una arista de escisi´on de G, y sea H=G\(N(u)∪N(v)). Si d=|N(u)∪N(v)| − 2,entonces para todo i≥1y todo j≥0se tiene que βi,j(I(G)) = βi,j (I(G\e)) + i X l=0 d lβi−l−1,j−l−2(I(H)) . Demostraci´on. Como e=uv es una arista de escisi´on, gracias al Teorema 2.2.4 podemos suponer sin p´erdida de generalidad que N(u)⊆(N(v)∪{v}). Por lo tanto, N(u)∪N(v) = {u, v, v1, . . . , vd}con {v1, . . . , vd}=N(v)\ {u}yd=|N(u)∪N(v)| − 2. En virtud del Teorema 2.1.4 se tiene que para todos i, j ≥0 βi,j(I(G)) = βi,j ((uv)) + βi,j(I(G\e)) + βi−1,j (J∩K). Ahora bien, si i≥1 se verifica que βi,j((uv)) = 0 para cada j, ya que no existe ninguna relaci´on no trivial posible entre un ´unico elemento. Aplicando el Lema 2.2.8, ya podemos concluir que para todo i≥1 y todo j≥0 se verifica que βi,j(I(G)) = βi,j (I(G\e)) + i X l=0 d lβi−l−1,j−l−2(I(H)) , que es lo que quer´ıamos probar. La f´ormula que proporciona este teorema no es recursiva en general porque los subgrafos que van apareciendo no tienen por qu´e poseer aristas de escisi´on. Por ejemplo, consideremos el siguiente grafo G: x1x2x3 x4x5 Es claro que la arista e=x2x3es una arista de escisi´on en virtud del Teorema 2.2.4 porque N(x3) = {x2} ⊆ N(x2)∪ {x2}. Sin embargo, observemos ahora el subgrafo G\e: x1x2x3 x4x5 2.2. ARISTAS DE ESCISI ´ ON 13 Este subgrafo de Gno tiene aristas de escisi´on. Para probarlo, y dado que todas las aristas juegan el mismo papel, basta con demostrar que la arista x1x2no es una arista de escisi´on. Esto es muy sencillo utilizando el Teorema de caracterizaci´on de las aristas de escisi´on, ya que N(x1) = {x2, x4} ⊆ N(x2)∪ {x2}={x1, x2, x5}yN(x2) = {x1, x5} ⊆ N(x1)∪ {x1}={x1, x2, x4}. A pesar de esta falta de recursividad, la f´ormula que proporciona el Teorema 2.2.9 es suficientemente general para proporcionar nuevos resultados sobre la dimensi´on proyectiva y la regularidad de los ideales de aristas, como veremos en el siguiente corolario: Corolario 2.2.10. Con las hip´otesis y la notaci´on empleadas en el Teorema 2.2.9, tenemos que (i) reg(I(G)) = m´ax{2,reg(I(G\e)),reg(I(H)) + 1}. (ii) pd(I(G)) = m´ax{pd(I(G\e)),pd(I(H)) + d+ 1}. Demostraci´on. Gracias al Teorema 2.1.5 tenemos que reg(I(G)) = m´ax{reg((uv)),reg(I(G\e)),reg(J∩K)−1}. Adem´as, como se verifica que βi,j((uv)) = 1 si (i, j) = (0,2) 0 en caso contrario ,(2.1) tenemos que reg((uv)) = 2. Por lo tanto, solo nos falta comprobar que reg(J∩K)−1 = reg(I(H)) + 1 o, equivalentemente, que reg(J∩K) = reg(I(H)) + 2. Para ello, recurrimos al Lema 2.2.8, que nos permite deducir que reg(J∩K) = m´ax{j−i|βi,j(J∩K)= 0}= = m´ax{j−i+ 1 |βi−1,j(J∩K)= 0}= = m´ax{j−i+ 1 |βi−l−1,j−l−2(I(H)) = 0 con l∈ {0, . . . , i}} = = m´ax{j−i−1|βi−l−1,j−l−2(I(H)) = 0 con l∈ {0, . . . , i}} + 2 = = reg(I(H)) + 2 gracias a que (j−l−2) −(i−l−1) = j−i−1 para cada l∈ {0, . . . , i}. Con esto queda probado entonces el primer apartado del corolario. De forma similar, para probar el segundo apartado comenzamos notando que en virtud del Teorema 2.1.5 pd(I(G)) = m´ax{pd((uv)),pd(I(G\e)),pd(J∩K)+1}. En virtud de los n´umeros de Betti graduados de (uv) que hemos escrito en (2.1), es claro que pd((uv)) = 0. 14 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS Adem´as, en el Lema 2.2.8 hab´ıamos probado que βi−1,j(J∩K) = βi,j−2(R/((v1, . . . , vd)+ I(H))), lo que implica que pd(J∩K) = pd(R/((v1, . . . , vd) + I(H))) −1. En ese mismo lema hab´ıamos visto tambi´en que βi,j−2R (v1, . . . , vd) + I(H)= i X l=0 βl,l R (v1, . . . , vd)βi−l,j−2−lR I(H). Si tenemos en cuenta que pd(R/(v1, . . . , vd)) = dy llamamos pa la dimensi´on proyectiva de R/(I(H)), entonces considerando i=d+pyl=den la f´ormula anterior, es claro que podemos tomar jde manera que en el lado derecho de la igualdad haya sumandos no nulos. Esto implica que la dimensi´on proyectiva de R (v1,...,vd)+I(H)es al menos d+p. Por otra parte, en la misma f´ormula vemos que l=dei−l=pson de hecho los valores m´as grandes que podemos tomar sin que todos los sumandos del segundo miembro de la igualdad anterior se anulen, lo que implica que i=d+pes exactamente la dimensi´on proyectiva de R (v1,...,vd)+I(H); es decir, pd R (v1, . . . , vd) + I(H)=d+ pd R I(H). En estas condiciones, ya podemos concluir: pd(J∩K) + 1 = pd(R/((v1, . . . , vd) + I(H))) = =d+ pd(R/(I(H))) = d+ pd(I(H)) + 1 , y podemos aplicar el Teorema 2.1.5. El corolario anterior implica que al eliminar en un grafo una arista de escisi´on e, lo ´unico que les puede ocurrir tanto a la regularidad como a la dimensi´on proyectiva del ideal de aristas asociado es que permanezcan iguales o disminuyan; es decir, reg(I(G)) ≥ reg(I(G\e)) y pd(I(G)) ≥pd(I(G\e)). Sin embargo, si eno es una arista de escisi´on, entonces podr´ıa ocurrir que la regularidad y la dimensi´on proyectiva de I(G\e) fuesen estrictamente mayores que las del ideal de aristas asociado al grafo original G. Vamos a ilustrar esto con un ejemplo. Ejemplo 2.2.11. Consideramos el grafo que hab´ıamos presentado en el Ejemplo 2.2.5, que es el siguiente: x1 x3 x2 x5 x4 x6 Como hab´ıamos visto en el mencionado ejemplo utilizando el Teorema de caracterizaci´on de las aristas de escisi´on, la arista e=x2x4no es una arista de escisi´on. 2.2. ARISTAS DE ESCISI ´ ON 15 Si calculamos ahora los diagramas de Betti de I(G)=(x1x2, x2x3, x2x4, x4x5, x4x6) y de I(G\e) = (x1x2, x2x3, x4x5, x4x6), obtenemos I(G) 0 1 2 2 5 6 2 y I(G\e)0123 2 4 2 - - 3 - 4 4 1 . De aqu´ı se deduce que pd(I(G\e)) = 3 >2 = pd(I(G)) y reg(I(G\e)) = 3 > 2 = reg(I(G)). Aunque los diagramas de Betti anteriores se pueden hallar efectuando c´alculos a mano, por ejemplo utilizando el orden de Schreyer, este proceso resulta tedioso. Por este motivo, dedicamos el Ap´endice A de este trabajo a presentar c´omo el programa Macaulay2 nos permite trabajar con ideales de aristas asociados a grafos de una forma m´as c´omoda. Para terminar esta secci´on, vamos a proporcionar varios resultados sobre los n´umeros de Betti de los ideales de aristas asociados a bosques. Su inter´es principal se debe a que todo subgrafo inducido de un bosque es nuevamente un bosque, y en consecuencia las f´ormulas que se obtienen en este caso s´ı son recursivas. Aunque el primero en obtener los siguientes resultados que voy a exponer fue Sean Jacques en su tesis ([18]) y en un art´ıculo con Mordechai Katzman ([19]), la forma en la que los voy a abordar en este trabajo no se corresponde con el enfoque original de naturaleza homol´ogica que ellos les hab´ıan dado, sino que se encuadra dentro de este enfoque de naturaleza m´as combinatoria que Huy T`ai H`a y Adam Van Tuyl adoptan en [16], y que es el que he estudiado en profundidad para la elaboraci´on de este trabajo. Corolario 2.2.12. Sea e=uv una hoja cualquiera de un bosque G. Si deg v=dy N(v) = {u, v1, . . . , vd−1},entonces para i≥1yj≥0 βi,j(I(G)) = βi,j (I(T)) + i X l=0 d−1 lβi−l−1,j−l−2(I(H)) , donde T=G\eyH=G\ {u, v, v1, . . . , vd−1}. Nota 2.2.13.El grafo T=G\eque aparece en el enunciado de este corolario no es un subgrafo inducido de Gporque contiene al v´ertice uaislado, pero sigue siendo un bosque sin m´as que hacer la consideraci´on trivial de que el grafo formado por un ´unico v´ertice aislado es un ´arbol (conexo y ac´ıclico). Otra forma de ver la recursividad de la f´ormula anterior sin recurrir a esta consideraci´on consiste en observar que I(T) = I(G\e) = I(G\ {u}), donde G\ {u}s´ı que es un subgrafo inducido de Gy, por tanto, un bosque. Demostraci´on. Como uv es una hoja y deg v=d, tenemos que necesariamente deg u= 1. Por lo tanto, N(u) = {v} ⊆ (N(v)∪{v}) y resulta que uv es una arista de escisi´on. Basta aplicar entonces el Teorema 2.2.9, teniendo en cuenta que ahora |N(u)∪N(v)| − 2 = d−1. Corolario 2.2.14. Con las mismas notaciones que en el Corolario 2.2.12, pd(I(G)) = m´ax{pd(I(T)),pd(I(H)) + d}. 16 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS Demostraci´on. Basta aplicar el Corolario 2.2.10, teniendo en cuenta que ahora se tiene que |N(u)∪N(v)| − 2 = d−1. Se dice que dos aristas u1v1yu2v2de un grafo simple Gest´an desconectadas si (a){u1, v1}∩{u2, v2}=∅, y (b)u1u2, u1v2, v1u2, v1v2no son aristas de G. En el caso en que Ges un bosque, es posible relacionar reg(I(G)) con el n´umero de aristas desconectadas de G. Es esto a lo que vamos a dedicar el ´ultimo resultado de esta secci´on, presentando la demostraci´on alternativa que Huy T`ai H`a y Adam Van Tuyl proporcionaron para un resultado que originalmente hab´ıa sido enunciado y demostrado por Xinxian Zheng en [25] utilizando otras t´ecnicas. Corolario 2.2.15. Sea Gun bosque con ideal de aristas I(G). Entonces reg(I(G)) = j+ 1,donde jes el cardinal del mayor conjunto de aristas desconectadas dos a dos en G. Demostraci´on. Vamos a razonar por inducci´on sobre |EG|. Cuando |EG|= 1, el resultado es trivial. Por un lado, el n´umero de aristas desconectadas, como solo hay una, tiene que ser igual a uno. Adem´as, si llamamos a esta arista uv, sabemos que reg((uv)) = 2 = 1 + 1. Supongamos ahora que |EG|>1, y sea e=uv cualquier hoja de Gcon deg u= 1 (que existe por ser Gun bosque). En virtud del Corolario 2.2.10 tenemos que reg(I(G)) = m´ax{2,reg(I(T)),reg(I(H)) + 1},donde T=G\eyH=G\({v} ∪ N(v)).Aplicando la hip´otesis de inducci´on, reg(I(T)) = j1+ 1, donde j1es el cardinal del mayor conjunto de aristas desconectadas dos a dos en T, y reg(I(H)) = j2+1, donde j2es el cardinal del mayor conjunto de aristas desconectadas dos a dos en H. Como Ttiene al menos una arista porque estamos suponiendo que |EG|>1, resulta que j1+1 ≥2. En consecuencia, reg(I(G)) = m´ax{j1+ 1, j2+ 2}= m´ax{j1, j2+ 1}+ 1 . Si denotamos por jal cardinal del mayor conjunto de aristas desconectadas dos a dos en G, entonces para terminar la demostraci´on basta probar que j= m´ax{j1, j2+ 1}. Sea E1un conjunto de j1aristas desconectadas dos a dos de T. Las aristas de E1forman tambi´en un conjunto de aristas desconectadas dos a dos de G, luego |E1|=j1≤j. Si E2es un conjunto de j2aristas desconectadas dos a dos de H, entonces afirmamos que E2∪ {uv}es un conjunto de aristas desconectadas dos a dos en G. Efectivamente, uv no comparte ning´un v´ertice con ninguna arista de H. Las ´unicas aristas que comparten alg´un v´ertice con uv son las vvidonde vi∈N(v)\{u}. Sin embargo, ninguna de las aristas de E2puede compartir un v´ertice con esas aristas ya que ninguno de los v´ertices de N(v) pertenece a H. En consecuencia, |E2∪{uv}| =j2+1 ≤jy por tanto j≥m´ax{j1, j2+1}. Vamos a ver que, de hecho, se da la igualdad. Para ello, razonamos por reducci´on al absurdo, suponiendo que j > m´ax{j1, j2+ 1}. Sea Eun conjunto de jaristas desconectadas dos a dos de G. Si uv /∈ E, entonces Etambi´en es un conjunto de aristas desconectadas dos a dos en T, luego j=|E| ≤ j1, lo cual es absurdo. Si uv ∈ E, entonces 2.3. V ´ ERTICES DE ESCISI ´ ON 17 ninguna de las aristas que contienen a alg´un vi, con vi∈N(v)\ {u}, pertenecen a E por tratarse de un conjunto de aristas desconectadas dos a dos. As´ı pues, E \ {uv}es un conjunto de aristas desconectadas dos a dos de H=G\({v} ∪ N(v)). Pero esto implicar´ıa que j−1≤j2, lo cual de nuevo es absurdo. Ya podemos concluir entonces que se da la igualdad: j= m´ax{j1, j2+ 1}. Adem´as del caso de las aristas de escisi´on que acabamos de presentar, la t´ecnica de la escisi´on de ideales se puede utilizar de otras formas distintas. Por ejemplo, es posible hablar de v´ertices de escisi´on, a los que dedicamos la siguiente secci´on. 2.3. V´ertices de escisi´on El concepto de v´ertice de escisi´on con el que queremos trabajar en esta secci´on es an´alogo al concepto de arista de escisi´on con el que trabaj´abamos en la secci´on previa. En particular, las dos nociones surgen a partir de la misma idea. Si Ges un grafo simple y ves un v´ertice de Gcon conjunto de v´ertices adyacentes N(v) = {v1, . . . , vd}, entonces es claro que I(G) = J+K, donde J= (vv1, . . . , vvd) y K= I(G\ {v}). Sin embargo, al igual que ocurr´ıa en la secci´on anterior, esta suma no tiene por qu´e ser una escisi´on del ideal I(G), y lo que nos va a interesar es determinar cu´ando s´ı que lo es. No obstante, a diferencia de lo que hac´ıamos con las aristas de escisi´on, no va a ser esta la condici´on que exijamos en la definici´on de v´ertice de escisi´on. En este caso, una condici´on m´as natural implicar´a directamente la condici´on que deseamos. Si ves un v´ertice aislado de G(es decir, vno pertenece a ninguna arista del grafo G), entonces I(G) = I(G\ {v}) y, en consecuencia, todos los n´umeros de Betti graduados de estos dos ideales coinciden. Por otra parte, si el v´ertice vtiene grado d > 0 y G\ {v} es el grafo formado por dv´ertices aislados, entonces lo que tenemos es que el grafo Gde partida no es m´as que el grafo bipartito completo K1,d. En este caso, todos los n´umeros de Betti graduados del ideal de aristas asociado son conocidos y los recogemos en el siguiente resultado: Teorema 2.3.1. Si G=K1,d, entonces para todos i, j ≥0se tiene que βi,j(I(G)) = (d i+1si j=i+ 2 0en otro caso . Demostraci´on. Es claro que el ideal de aristas de G=K1,d es I(G) = (vv1, . . . , vvd), donde los dos conjuntos disjuntos en los que se divide el conjunto de v´ertices de Gson {v}, de cardinal 1, y {v1, . . . , vd}, de cardinal d. Entonces βi,j(I(G)) = βi,j((vv1, . . . , vvd)) = βi,j−1((v1, . . . , vd)). En la demostraci´on del Lema 2.2.8 hab´ıamos visto que βi,j R (v1, . . . , vd)=d isi i=j 0 si i=j , de donde se deduce que βi,j−1((v1, . . . , vd)) = βi+1,j−1R (v1, . . . , vd)=(d i+1si j=i+ 2 0 en caso contrario , 18 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS siendo esto lo que quer´ıamos probar. Dejando entonces a un lado estos dos casos, que hemos visto que son conocidos, vamos a llamar v´ertice de escisi´on a todo aquel que no est´e en ninguna de las dos situaciones que acabamos de describir. Para mayor precisi´on, recogemos la definici´on de este nuevo concepto a continuaci´on: Definici´on 2.3.2. Se dice que un v´ertice v∈VGes un v´ertice de escisi´on si deg(v) = d > 0 y G\ {v}no es el grafo formado por dv´ertices aislados. A continuaci´on, vamos a presentar un resultado que prueba lo que avanz´abamos al comienzo de esta secci´on: basta definir los v´ertices de escisi´on como lo hemos hecho en la definici´on anterior para que estos nos proporcionen una escisi´on del ideal de aristas de G. Teorema 2.3.3. Sea vun v´ertice de escisi´on de Gcon N(v) = {v1, . . . , vd}, y sean J= (vv1, . . . , vvd)yK=I(G\ {v}). Entonces I(G) = J+Kes una escisi´on de I(G). Demostraci´on. Es claro que I(G) = J+Ky que G(I(G)) es la uni´on disjunta de G(J) yG(K). Por lo tanto, para probar que I(G) = J+Kes una escisi´on, basta construir una funci´on de escisi´on. Para ello, necesitamos conocer primero el conjunto G(J∩K). Como tanto Jcomo Kson ideales monomiales, tenemos que J∩K= ({mcm(m1, m2)|m1∈ {vv1, . . . , vvd}, m2∈ G(I(H))}), donde H=G\ {v}. En consecuencia, G(J∩K) = {vvivj|vivj∈EG} ⊔ {vviyj|viyj∈EG} ⊔ ⊔ {vviyjyk|yjyk∈EGpero viyj, viyk/∈EG}, donde los yjson v´ertices de Gque no pertenecen al conjunto {v, v1, . . . , vd}, y los tres conjuntos que aparecen en la uni´on anterior son disjuntos. Vamos a definir ahora una aplicaci´on G(J∩K)→ G(J)× G(K), y probaremos que es una funci´on de escisi´on. Si w∈ G(J∩K), entonces definimos ϕ:G(J∩K)→ G(J) y ψ:G(J∩K)→ G(K) por ϕ(w) =    vvisi w=vvivjei < j , vvisi w=vviyj, vvisi w=vviyjyk yψ(w) =    vivjsi w=vvivj, viyjsi w=vviyj, yjyksi w=vviyjyk. Queremos probar que la aplicaci´on dada por w7−→ (ϕ(w), ψ(w)) es una funci´on de escisi´on. Es claro a partir de la propia definici´on que w= mcm(ϕ(w), ψ(w)) para todo w∈ G(J∩K), de manera que lo ´unico que nos falta probar es que para cada subconjunto S⊆ G(J∩K), tanto mcm(ϕ(S)) como mcm(ψ(S)) dividen estrictamente a mcm(S). Sea entonces S⊆ G(J∩K). Si Scontiene a alg´un monomio divisible por alguna variable y /∈ {v, v1, . . . , vd}, entonces mcm(ϕ(S)) divide estrictamente a mcm(S), ya que 2.3. V ´ ERTICES DE ESCISI ´ ON 19 ydivide a mcm(S) pero no divide a ning´un elemento de ϕ(S), y por tanto tampoco a mcm(ϕ(S)). En caso contrario, necesariamente tendr´ıamos que S⊆ {vvivj|vivj∈EG}. Si denotamos por mal mayor ´ındice tal que vmpertenece a alg´un monomio de S, entonces, en virtud de la definici´on de ϕ, se tiene que vmno divide a ning´un elemento de ϕ(S) y por tanto mcm(ϕ(S)) divide estrictamente a mcm(S). Por otra parte, como vdivide a todos los elementos de Spero no divide a ning´un elemento de ψ(S), se tiene que mcm(ψ(S)) divide estrictamente a mcm(S). Esto nos permite concluir que la aplicaci´on que hemos definido es una funci´on de escisi´on, lo que prueba el teorema. Una consecuencia inmediata de la descripci´on de G(J∩K) que hemos dado en la demostraci´on del teorema anterior es la siguiente: Corolario 2.3.4. Con las mismas notaciones que en el Teorema 2.3.3, definimos Gi:= G\(N(v)∪N(vi)) para i= 1, . . . , d, y G(v):= G{v1,...,vd}∪ {e∈EG|econtiene a alg´un v1, . . . , vdpero no a v}, donde recordamos que G{v1,...,vd}no es m´as que el subgrafo inducido de Gsobre el conjunto de v´ertices {v1, . . . , vd}. Entonces J∩K=vI(G(v)) + vv1I(G1) + vv2I(G2) + . . . +vvdI(Gd). Como los grafos que hemos definido en el corolario anterior van a aparecer en resultados posteriores, conviene aclarar sus definiciones a trav´es de un ejemplo: Ejemplo 2.3.5. Consideramos el mismo grafo que en el Ejemplo 2.2.5 y tomamos v=x2, de manera que los v´ertices adyacentes a vson N(v) = {x1=v1, x3=v2, x4=v3}y aparecen coloreados de rojo en la siguiente figura: x1=v1x5 x6 x4=v3 x3=v2 x2=v En este caso, los grafos G1yG2coinciden con el grafo cuyos dos ´unicos v´ertices son x5yx6, ambos aislados; G3es el grafo vac´ıo, dado que N(v)∪N(v3) es el conjunto total de v´ertices de G; y G(v)es el grafo siguiente: 26 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS Ga alg´un elemento de dicho conjunto (a trav´es de alguna no-cuerda de C), y por tanto es un v´ertice de G(v). Para i∈ {2, . . . , l −2}se tiene que xixi+1 ∈EGc (v), ya que xixi+1 no es una arista de Gy tanto xicomo xi+1 son elementos de N(v). En consecuencia, (x1x2. . . xl−1xlx1) es un ciclo de Gc (v)de longitud l≥4. Lo ´unico que nos falta probar es que no tiene cuerdas, y esto es muy sencillo. Por un lado, x1no puede ser adyacente en Gc (v)a ning´un v´ertice del ciclo (x1x2. . . xl−1xlx1) distinto de x2y de xl. Esto se debe a que x1xi∈EGpara cada i∈ {3, . . . , l −1}, con xi∈N(v), y esto implica que x1xi∈EG(v). Un razonamiento id´entico conduce a que xlno puede ser adyacente en Gc (v)a ninguno de los xicon idistinto de 1 y de l−1. Por otra parte, si tenemos i < j, ambos en {2, . . . , l −1}y tales que j=i+ 1, entonces xixj∈EGy xi, xj∈N(v), lo que implica que xixj∈EG(v)y por tanto xixj/∈EGc (v). Dentro del caso l≥4 vamos a distinguir dos nuevas posibilidades: 1. Si p= 2, entonces C= (vx1. . . xlv) tiene longitud l+1 ≥4+1 = 5 = p+3 y se verifica lo que quer´ıamos probar. 2. Supongamos ahora que p > 2. Como G(v)no contiene a vy estamos suponiendo que I(G(v)) satisface la propiedad N2,p−1, aplicando la hip´otesis de inducci´on se tiene que todo ciclo minimal en Gc (v)tiene longitud mayor o igual que (p−1)+3 = p+2. Pero antes hemos probado que (x1. . . xlx1) es un ciclo minimal de Gc (v), luego tiene longitud l≥p+ 2 y esto nos permite concluir que Ctiene longitud l+ 1 ≥p+ 3, que es lo que quer´ıamos probar. •Para concluir la demostraci´on de la implicaci´on con la que estamos trabajando, vamos a estudiar el caso en que l= 3. Como C= (vx1x2x3v) es un ciclo minimal en Gc, se tiene que x1x3no es una cuerda y, por tanto, es una arista de G. Adem´as, hab´ıamos visto que x1yx3 no pertenecen a N(v). Se tiene que el monomio vx2x1x3∈J= (vv1, . . . , vvd) porque x2∈N(v) = {v1, . . . , vd}. Adem´as, vx2x1x3tambi´en pertenece a K=I(G\ {v}) porque x1x3es una arista de Gcon x1yx3distintos de v. En consecuencia, vx2x1x3∈J∩K=L, donde estamos suponiendo que L=vI(G(v)), pero esto es absurdo porque vx2x1x3/∈vI(G(v)). Esto se debe a que un razonamiento id´entico al que hac´ıamos cuando lera mayor o igual que 4 nos permite probar que (x1x2x3x1) es un ciclo de Gc (v)y, en consecuencia, ninguna de las aristas xixjcon i, j ∈ {1,2,3}pertenece a EG(v). Concluimos entonces que el caso l= 3 no es posible y queda probada la primera implicaci´on. ⇐Rec´ıprocamente, supongamos que todo ciclo minimal en Gcque contiene a vtiene longitud mayor o igual que p+ 3. Tenemos que probar que se verifica lo siguiente: (a)L=vI(G(v)). 2.3. V ´ ERTICES DE ESCISI ´ ON 27 (b)I(G(v)) satisface la propiedad N2,p−1. Empecemos probando (a). Para ello vamos a razonar por reducci´on al absurdo, suponiendo que vI(G(v)) est´a contenido estrictamente en L=vI(G(v)) + Pd i=1 vviI(Gi). Esto implica que existe i∈ {1, . . . , d}tal que el ideal I(Gi) es no nulo; es decir, el grafo Gi=G\(N(v)∪N(vi)) tiene al menos una arista, a la que vamos a denotar por uw. En consecuencia, (vuviw) es un ciclo minimal de longitud 4 en Gc. Efectivamente, por una parte es claro que vw,vu,uviyviwno son aristas de Gya que u, w /∈ (N(v)∪N(vi)). Por otra parte, el ciclo anterior no tiene cuerdas debido a que vvi yuw s´ı que son aristas de G, y por tanto no lo son de Gc. Llegamos de este modo a una contradicci´on, ya que estamos suponiendo que todo ciclo minimal en Gcque contiene a vtiene longitud mayor o igual que p+3 para un cierto pestrictamente mayor que 1, y por tanto la longitud de todo ciclo minimal con esas caracter´ısticas tiene que ser estrictamente mayor que 4. Queremos probar ahora (b); es decir, que I(G(v)) satisface N2,p−1. Si p= 2, (b) es claramente cierto. En efecto, lo que tendr´ıamos que probar es que βi,j(I(G(v))) = 0 para todo icon 0 ≤i < p −1 = 1 y todo j > i + 2. Pero esto es evidente ya que el ´unico valor posible de ien estas condiciones ser´ıa 0 y, como I(G(v)) est´a generado por elementos de grado 2, se verifica que su ´unico n´umero de Betti graduado no nulo 0, j-´esimo es β0,2(I(G(v))). Supongamos entonces a partir de ahora que p > 2. El conjunto de v´ertices del grafo G(v)no contiene a v, luego |VG(v)|<|VG|.Si probamos que todo ciclo minimal en Gc (v)tiene longitud mayor o igual que p+ 2 = (p−1) + 3, entonces por hip´otesis de inducci´on tendremos que I(G(v)) satisface N2,p−1, que es lo que queremos probar. Sea entonces D= (x1x2. . . xlx1) un ciclo minimal en Gc (v), de manera que en particular l≥4 y xi=vpara todo i∈ {1, . . . , l}. Sea tambi´en W={w1, . . . , ws} el conjunto de v´ertices de G\ {v, v1, . . . , vd}que son adyacentes en Ga al menos uno de los v´ertices de N(v). Vamos a distinguir ahora varios casos, en funci´on del n´umero de elementos de W que forman parte del ciclo Dque estamos considerando. Antes de ello notemos que, para que Dpueda ser un ciclo minimal, este n´umero tendr´a que ser a lo sumo 2. Esto se debe a que wiwj, con i=j, no es una arista de G(v)ya que todas las aristas de este grafo contienen al menos a un elemento de N(v). Por lo tanto, todos los elementos de Wson adyacentes dos a dos en Gc (v)y no puede haber m´as de dos en un ciclo minimal de dicho grafo (dar´ıan lugar a cuerdas). Analizamos entonces los distintos casos posibles: (∗) Supongamos que existen iyjcon 1 ≤i, j ≤sei=jtales que wi, wj∈ {x1, . . . , xl}. Entonces, como wiwjes una arista de Gc (v), tendr´a que ser una 28 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS arista de D(en caso contrario ser´ıa una cuerda, lo cual es absurdo). Sin p´erdida de generalidad, podemos suponer que wi=x1ywj=xl. En este caso, si probamos que (x1x2. . . xlvx1) es un ciclo minimal de Gc, habremos terminado. Efectivamente, como estamos suponiendo en esta implicaci´on que todo ciclo minimal de Gcque contiene a vtiene longitud mayor o igual que p+ 3, tendr´ıamos que l+ 1 ≥p+ 3 y, en consecuencia, Dtendr´ıa longitud l≥p+ 2, tal y como quer´ıamos probar. Veamos entonces que (x1x2. . . xlvx1) es un ciclo minimal de Gc. Para ello, como toda arista de G(v)es una arista de G(por la propia definici´on de G(v)), la informaci´on que proporciona el ciclo minimal Dnos permite limitarnos a probar los seis puntos siguientes: 1. x1v∈EGc, lo cual es cierto porque x1=wi/∈N(v). 2. xlv∈EGc, lo cual es cierto porque xl=wj/∈N(v). 3. xiv /∈EGcpara i∈ {2, . . . , l −1}. Esto equivale a probar que xiv∈EGpara cada i∈ {2, . . . , l −1}, que es lo que vamos a demostrar a continuaci´on. Como xi/∈W, tenemos dos opciones: o bien xino pertenece al conjunto de v´ertices de G\{v, v1, . . . , vd}, de manera que xi∈N(v) y por tanto xiv∈ EG; o bien xis´ı pertenece al conjunto de v´ertices de G\ {v, v1, . . . , vd} pero no es adyacente a ning´un elemento de N(v). Esto ´ultimo es absurdo, porque en ese caso xino formar´ıa parte de ninguna arista de G(v)y sabemos que s´ı lo hace (pertenece a las aristas correspondientes a las no-cuerdas de D). 4. x1x2∈EGc. Sabemos que x1x2=wix2es una arista de Dy, por tanto, de Gc (v). Como x2/∈W, tenemos dos opciones. Por una parte, podr´ıa ocurrir que x2no perteneciese al conjunto de v´ertices de G\ {v, v1, . . . , vd}.En este caso, x2∈N(v) y si x1x2perteneciese aEGtendr´ıamos que x1x2es una arista de G(v), lo cual sabemos que no es cierto. Por tanto, x1x2no es una arista de G. En caso contrario, tendr´ıamos que x2pertenece al conjunto de v´ertices de G\ {v, v1, . . . , vd}y no es adyacente a ning´un elemento de N(v).Esto es absurdo, ya que implicar´ıa que x2no pertenece a ninguna arista de G(v), pero sabemos que s´ı que lo hace (pertenece a las aristas correspondientes a las no-cuerdas de D). 5. De forma an´aloga al punto 4 se prueba que xl−1xl∈EGc. 6. xixi+1 ∈EGcpara cada i∈ {2, . . . , l −2}. Como xiyxi+1 no pertenecen a Wpara ning´un i, tenemos cuatro posibilidades. En primer lugar, podr´ıa ocurrir que xiyxi+1 no fueran elementos del conjunto de v´ertices de G\ {v, v1, . . . , vd}. Como ambos son distintos de v, tendr´ıamos que xi, xi+1 ∈N(v). As´ı, si xixi+1 fuese una arista de G, lo 2.3. V ´ ERTICES DE ESCISI ´ ON 29 ser´ıa en particular de G{v1,...,vd}y, por tanto, de G(v). Pero esto es absurdo, porque de la forma de Dse deduce que xixi+1 es una arista de Gc (v). Otra posibilidad ser´ıa que uno de los v´ertices perteneciese a N(v) y el otro fuese un elemento del conjunto de v´ertices de G\ {v, v1, . . . , vd}, pero no adyacente en Ga ning´un elemento de N(v). As´ı pues, xiyxi+1 no podr´ıan ser adyacentes en G, de manera que xixi+1 ser´ıa una arista de Gc. Por ´ultimo, podr´ıa ocurrir que xiyxi+1 pertenecieran al conjunto de v´ertices de G\ {v, v1, . . . , vd}y no fueran adyacentes a ning´un elemento de N(v). Llegamos en este caso a una contradicci´on, porque entonces xi yxi+1 no pertenecer´ıan a ninguna arista de G(v)y s´ı que lo hacen (a las aristas correspondientes a las no-cuerdas de D). (∗) Supongamos que existe a lo sumo un elemento de Wque pertenece al conjunto {x1, . . . , xl}, y veamos que entonces Des un ciclo minimal de Gc, lo cual implicar´ıa (gracias a que Dno contiene a vy por tanto ser´ıa un ciclo de Gc\ {v}) que tiene longitud l≥p+ 3 > p + 2. Distinguimos nuevamente dos casos: (∗∗) Supongamos que existe un ´unico i0∈ {1, . . . , s}tal que wi0∈ {x1, . . . , xl}. Sin p´erdida de generalidad podemos suponer que wi0=x1, de manera que D= (wi0x2. . . xlwi0). Como hac´ıamos en el caso anterior, basta probar los tres puntos siguientes: 1. wi0x2es una arista de Gc: Sabemos que x1x2=wi0x2es una arista de Dy, por tanto, de Gc (v). Como x2/∈W, podemos razonar igual que en el punto 4 anterior. 2. wi0xles una arista de Gc: se hace un razonamiento an´alogo al que hicimos en el punto 4 anterior. 3. xixi+1 ∈EGcpara cada i∈ {2, . . . , l −1}. Como xiyxi+1 no pertenecen a Wpara ning´un i, podemos razonar igual que en el punto 6 anterior. (∗∗) Supongamos por ´ultimo que ning´un elemento de Wpertenece al conjunto {x1, . . . , xl}, y veamos que D= (x1x2. . . xlx1), que es un ciclo minimal en Gc (v), es tambi´en un ciclo minimal en Gc. Basta probar los dos puntos siguientes: 1. xixi+1 es una arista de Gcpara cada i∈ {1, . . . , l}, con xl+1 =x1. Como xiyxi+1 no pertenecen a Wpara ning´un i, podemos razonar igual que en el punto 6 del primer caso analizado. 2. Si jno es congruente con i+ 1 m´odulo l, entonces xixjno es una arista de Gc. Efectivamente, por la forma en la que hemos escrito D, tenemos que xixjes una arista de G(v)y por tanto de G, que es lo que quer´ıamos probar. La prueba de la doble implicaci´on nos permite concluir la demostraci´on. 30 CAP´ ITULO 2. IDEALES DE ARISTAS ASOCIADOS A GRAFOS El corolario anterior no solo es interesante en s´ı mismo porque permite caracterizar una propiedad de los ideales de aristas en t´erminos muy sencillos dentro del grafo asociado, sino que adem´as permite recuperar el principal teorema de Ralf Fr¨oberg como una consecuencia directa. Este teorema, que enunciamos y demostramos a continuaci´on, aparece originalmente en [13] y caracteriza a los ideales de aristas que tienen una resoluci´on lineal. Estos ideales tienen especial inter´es por la particular sencillez de sus diagramas de Betti, que est´an formados por una ´unica fila. Antes de enunciar el llamado Teorema de Fr¨oberg, necesitamos introducir una nueva definici´on: Definici´on 2.3.13. Se dice que un grafo Ges cordal si todo ciclo de longitud estrictamente mayor que 3 tiene alguna cuerda; es decir, si Gno tiene ciclos minimales. Corolario 2.3.14. Sea Gun grafo con ideal de aristas I(G). Entonces I(G)tiene una resoluci´on lineal si y solo si Gces un grafo cordal. Demostraci´on. Para demostrar este resultado, vamos a probar la doble implicaci´on. ⇒Supongamos que I(G) tiene una resoluci´on lineal, de manera que verifica la propiedad N2,p para todo p > 1. Queremos probar que Gcno tiene ciclos minimales, y lo haremos razonando por reducci´on al absurdo. Para ello, supongamos que Gctiene un ciclo minimal de longitud k≥4. Como I(G) satisface la propiedad N2,k, del Corolario 2.3.11 se sigue que todo ciclo minimal en Gcdeber´ıa tener longitud mayor o igual que k+3, que es estrictamente mayor que k, y por tanto hemos alcanzado una contradicci´on. ⇐Supongamos ahora que Gces un grafo cordal, de manera que no tiene ciclos minimales. Esto implica, en virtud del Corolario 2.3.11, que I(G) satisface N2,p para todo p > 1.Pero, como hab´ıamos comentado en la Nota 2.3.10, lo que esto quiere decir es que I(G) tiene una resoluci´on lineal hasta el paso p-´esimo para todo p > 1. Es decir, I(G) tiene una resoluci´on lineal. La prueba de la doble implicaci´on nos permite concluir. Despu´es de haber estudiado con detalle los ideales de aristas asociados a grafos, surge de manera natural el inter´es en estudiar, a trav´es de la misma idea, ideales monomiales libres de cuadrados no necesariamente cuadr´aticos. Esto nos conduce a considerar objetos combinatorios que constituyan, de alguna manera, una generalizaci´on de los grafos. En el siguiente cap´ıtulo vamos a presentar c´omo los complejos simpliciales surgen como una primera generalizaci´on, si bien es cierto que la riqueza de su estructura no va a ser necesaria para nuestro objetivo. Esto ´ultimo ser´a lo que nos lleve a considerar los hipergrafos, que estudiaremos tambi´en detalladamente en el siguiente cap´ıtulo. Cap´ıtulo 3 Generalizaci´on Hemos dedicado el cap´ıtulo anterior al estudio de los ideales monomiales cuadr´aticos libres de cuadrados a trav´es de la identificaci´on existente entre ellos y los grafos simples. Es natural que a partir de ah´ı surja inter´es por el estudio de ideales monomiales libres de cuadrados que no sean necesariamente cuadr´aticos. Esto es lo que nos conduce a buscar objetos combinatorios que generalicen los grafos con los que hemos trabajado hasta ahora, y los complejos simpliciales aparecen como primeros candidatos para nuestro estudio. Ve´amoslo en la primera secci´on de este cap´ıtulo. 3.1. Complejos simpliciales e ideales de facetas En primer lugar, daremos la definici´on de complejo simplicial. A continuaci´on, introduciremos algunos de los conceptos m´as b´asicos relacionados con los complejos simpliciales, y veremos c´omo estos generalizan los grafos que ya conocemos y tambi´en c´omo se pueden identificar con los ideales monomiales libres de cuadrados generados por monomios de grados arbitrarios. Definici´on 3.1.1. Un complejo simplicial ∆ sobre un conjunto de v´ertices V∆={x1, ...,xn}es un subconjunto de P(V∆), la colecci´on de todos los subconjuntos de V∆, que cumple las dos propiedades siguientes: (a){xi} ∈ ∆ para cada i∈ {1, . . . , n}. (b) Si F∈∆, entonces todos los subconjuntos de Ftambi´en pertenecen a ∆. Los elementos de ∆ reciben el nombre de caras del complejo simplicial, y aquellas caras que son maximales para la inclusi´on se denominan facetas. El conjunto de facetas del complejo simplicial ∆ se denota por F(∆). A partir de la definici´on anterior, ya tenemos todas las herramientas necesarias para identificar los complejos simpliciales con los ideales monomiales libres de cuadrados no necesariamente cuadr´aticos. Efectivamente, si ∆ es un complejo simplicial sobre un conjunto de v´ertices V∆={x1, . . . , xn}ykes un cuerpo a priori arbitrario, entonces 31 32 CAP´ ITULO 3. GENERALIZACI ´ ON les podemos asociar un ideal I(∆) en el anillo de polinomios R=k[x1, . . . , xn] definido como I(∆) = ({F|F∈ F(∆)})⊆R , donde estamos cometiendo un abuso de notaci´on para denotar por Ftanto a una faceta del complejo simplicial como al monomio Qx∈Fx. Este ideal I(∆) que acabamos de definir es el que recibe el nombre de ideal de facetas asociado al complejo simplicial ∆. Adem´as, es claro que se trata de un ideal monomial libre de cuadrados y que sus generadores tendr´an grados arbitrarios, correspondientes al n´umero de elementos que compongan las distintas facetas de ∆. A la inversa, y gracias a que un complejo simplicial queda determinado por sus facetas, es posible asociar a todo ideal monomial libre de cuadrados un complejo simplicial cuyas facetas sean los conjuntos correspondientes a los monomios que forman parte del sistema minimal de generadores formado por monomios del ideal de partida. Evidentemente, si todas las facetas de un complejo simplicial ∆ tienen cardinal 2, podemos ver al complejo simplicial en cuesti´on como un grafo cuyas aristas coinciden con las facetas de ∆ y cuyo ideal de aristas coincide, en consecuencia, con el ideal de facetas de ∆. El punto de vista de los ideales de facetas es novedoso, ya que tradicionalmente se sol´ıa asociar a un complejo simplicial ∆ un ideal que recib´ıa el nombre de ideal de Stanley-Reisner y que estaba generado por los monomios correspondientes a las no-caras minimales de ∆. Estos ideales han sido estudiados en la asignatura “´ Algebra Combinatoria” del M´aster en Matem´aticas, en la que se ha introducido la f´ormula de Hochster como una de las herramientas principales para calcular los n´umeros de Betti de los ideales de Stanley-Reisner. La nueva perspectiva de los ideales de facetas permite llevar a cabo un estudio satisfactorio de los ideales monomiales libres de cuadrados arbitrarios. Partiendo de esta peque˜na introducci´on que acabamos de realizar, es posible efectuar con los ideales de facetas asociados a complejos simpliciales un estudio an´alogo al que hac´ıamos en el cap´ıtulo anterior, definiendo en este caso las llamadas facetas de escisi´on y utilizando t´ecnicas semejantes. Una peque˜na muestra de este estudio se puede encontrar en la ´ultima secci´on de [16]. No obstante, los autores del mencionado art´ıculo observaron que la riqueza de la estructura simplicial que se presenta en la Definici´on 3.1.1 no es necesaria para el estudio que nos interesa. As´ı lo comentan en un art´ıculo posterior ([17]), en el que generalizan el concepto de complejo simplicial a la noci´on de hipergrafo. En la siguiente secci´on de este cap´ıtulo presentaremos este nuevo concepto, veremos c´omo generaliza la noci´on de complejo simplicial, y lo utilizaremos para estudiar detalladamente las resoluciones libres minimales graduadas de los ideales monomiales libres de cuadrados generados por elementos de grados arbitrarios. 3.2. Hipergrafos e ideales de aristas Comenzamos esta secci´on introduciendo el concepto de hipergrafo y viendo c´omo es posible identificar estos objetos combinatorios, que generalizan los grafos que ya conocemos, con los ideales monomiales libres de cuadrados. 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 33 Definici´on 3.2.1. Sea X={x1, . . . , xn}y sea E={E1, . . . , Es}una colecci´on de subconjuntos de X. El par H= (X,E) recibe el nombre de hipergrafo si Ei=∅para cada i∈ {1, . . . , s}. Los elementos de Xse denominan v´ertices, mientras que los elementos de Ese llaman aristas del hipergrafo H. Un hipergrafo Hes simple si verifica las dos condiciones siguientes: 1. Hno tiene lazos; es decir, |E| ≥ 2 para todo E∈ E. 2. Hno tiene aristas m´ultiples; es decir, si Ei, Ej∈ E yEi⊆Ej, entonces i=j. Cuando no haya riesgo de confusi´on, ser´a habitual referirnos a un hipergrafo haciendo alusi´on ´unicamente a su conjunto de aristas. As´ı, en numerosas ocasiones escribiremos E∈ H en lugar de E∈ E. A partir de esta definici´on, es claro que el concepto de hipergrafo generaliza la noci´on de grafo que ya conocemos: un grafo es un hipergrafo en el que todas las aristas tienen cardinal dos. Si tenemos ahora un cuerpo k, es posible asociar a un hipergrafo simple H= (X,E), con X={x1, . . . , xn}, el ideal monomial libre de cuadrados I(H) = (xE=Y x∈E x|E∈ E)!⊆R=k[x1, . . . , xn], donde identificamos los v´ertices con las variables en el anillo de polinomios asociado. El ideal anterior recibe el nombre de ideal de aristas de H, y a partir de su definici´on es claro que existe una biyecci´on entre el conjunto de hipergrafos simples con conjunto de v´ertices {x1, . . . , xn}y el conjunto de ideales monomiales libres de cuadrados generados por elementos de grado mayor que 1 en el anillo R=k[x1, . . . , xn]. Gracias a esta biyecci´on, para estudiar las resoluciones libres minimales graduadas de los ideales monomiales libres de cuadrados podremos limitarnos a estudiar los ideales de aristas asociados a hipergrafos. Antes de proceder a este estudio, vamos a comentar la relaci´on existente entre los hipergrafos y los complejos simpliciales que anunci´abamos en la secci´on anterior. Si ∆ es un complejo simplicial sobre el conjunto de v´ertices Xy tiene F(∆) como conjunto de facetas, entonces es claro que H(∆) = (X,F(∆)) es un hipergrafo ya que todas las facetas son no vac´ıas por tratarse de conjuntos maximales para la inclusi´on. Es evidente a partir de las definiciones que I(∆) = I(H(∆)). Rec´ıprocamente, dado un hipergrafo H= (X,E), podemos asociarle el conjunto ∆(H) = {F⊆ X | F⊆Eipara alg´un Ei∈ E}, que es un complejo simplicial sobre el conjunto de v´ertices que aparecen en los distintos elementos de E. Veamos que efectivamente cumple las condiciones de la Definici´on 3.1.1: Si xi∈Ejpara alg´un Ej∈ E, entonces {xi} ⊆ Ejy por tanto {xi} ∈ ∆(H). Supongamos que F∈∆(H) y veamos que si A⊆F, entonces tambi´en Apertenece a ∆(H). 34 CAP´ ITULO 3. GENERALIZACI ´ ON Como F∈∆(H), tenemos que F⊆ X yF⊆Eipara alg´un Ei∈ E. En consecuencia, A⊆F⊆ X yA⊆F⊆Ei, con Ei∈ E. Esto nos permite concluir que A∈∆(H). Queda probado entonces que ∆(H) es efectivamente un complejo simplicial, y adem´as se verifica que I(H) = I(∆(H)). En efecto, por un lado tenemos que el ideal de aristas del hipergrafo Hest´a generado por los monomios correspondientes a las aristas de H. Por otra parte, el ideal de facetas asociado al complejo simplicial ∆(H) est´a generado por los monomios correspondientes a las facetas de ∆(H), que no son m´as que los elementos maximales para la inclusi´on del conjunto de aristas del hipergrafo H. A partir de estos comentarios podemos concluir que ambos ideales son iguales, sin m´as que observar que los generadores de I(H) correspondientes a aristas que no son maximales son superfluos. La relaci´on existente entre los complejos simpliciales y los hipergrafos que acabamos de presentar nos permite adoptar dos puntos de vista diferentes, interpretando los generadores de un ideal monomial libre de cuadrados como las facetas de un complejo simplicial o como las aristas de un hipergrafo. Como he comentado en la secci´on anterior, la riqueza en la estructura del complejo simplicial no es necesaria para nuestro estudio. Esto es lo que nos lleva a trabajar con hipergrafos, que constituyen de hecho una generalizaci´on m´as natural de los grafos con los que trabaj´abamos en el cap´ıtulo anterior, si bien es cierto que los resultados que vamos a presentar en esta secci´on podr´ıan reinterpretarse en t´erminos de ideales de facetas asociados a ciertos complejos simpliciales. A continuaci´on, introduciremos algunas nociones b´asicas relacionadas con los hipergrafos y presentaremos c´omo la t´ecnica de escisi´on de ideales que utiliz´abamos en el cap´ıtulo anterior es ´util tambi´en en este caso para estudiar las resoluciones libres minimales graduadas de los ideales monomiales libres de cuadrados arbitrarios, que se identifican con los ideales de aristas asociados a hipergrafos. 3.2.1. Preliminares Al igual que hac´ıamos en el cap´ıtulo previo, a partir de ahora supondremos que todo hipergrafo con el que vamos a trabajar es simple. Cuando todas las aristas de un hipergrafo tienen el mismo cardinal d, se dice que el hipergrafo en cuesti´on es d-uniforme. Por tanto, utilizando esta terminolog´ıa, un grafo simple no es m´as que un hipergrafo simple 2-uniforme y la mayor´ıa de los resultados que presentaremos consistir´an en generalizaciones de los resultados que hab´ıamos estudiado en el cap´ıtulo anterior. Si Ees una arista del hipergrafo H= (X,E), denotaremos por H \ Eal hipergrafo obtenido eliminando la arista Een H. An´alogamente, si xes un v´ertice de H, denotaremos por H \ {x}al hipergrafo obtenido eliminando xdel conjunto de v´ertices de H, as´ı como todas las aristas del hipergrafo a las que xpertenece. Si Y ⊆ X , entonces el hipergrafo inducido sobre Yse denotar´a por HYy ser´a el subhipergrafo de Hcon conjunto de v´ertices Yy conjunto de aristas {E∈ E | E⊆ Y}; es decir, estar´a formado por aquellas aristas de Hcuyos elementos pertenecen al conjunto Y.Algunas definiciones que resultar´an importantes a lo largo de esta secci´on son las siguientes: 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 35 Definici´on 3.2.2. Sea Hun hipergrafo. Una cadena de longitud den Hes una sucesi´on (E0, y1, E1, . . . , yd, Ed) (tambi´en denotada a veces simplemente por (E0, . . . , Ed) cuando los v´ertices no son relevantes) que verifica las siguientes condiciones: 1. y1, . . . , ydson dv´ertices distintos de H. 2. E0, . . . , Edson d+ 1 aristas distintas de H. 3. y1∈E0,yd∈Ede{yk, yk+1} ⊆ Ekpara cada k∈ {1, . . . , d −1}. En particular, la tercera condici´on implica que la intersecci´on de cada arista de la sucesi´on con la siguiente es no vac´ıa; es decir, Ei∩Ei+1 =∅para cada i∈ {0, . . . , d −1}. Si EyE′son dos aristas de H, se dice que est´an conectadas si existe una cadena (E0, . . . , Ed) en el sentido que acabamos de definir, con E0=EyEd=E′. Si |E| ≥ |E′|, entonces una cadena (E=E0, . . . , Ed=E′) que conecta EyE′es propia si |Ei∩Ei+1|=|Ei+1| − 1 para todo ientre 0 y d−1. Una cadena (propia) que conecta dos aristas EyE′es una cadena (propia) irredundante si ninguna subsucesi´on estricta es una cadena (propia) entre EyE′. Si EyE′son dos aristas de Hcon |E|≥|E′|, se define la distancia entre EyE′, y se denota por distH(E, E′), como distH(E, E′) = m´ın{l|(E=E0, . . . , El=E′) es una cadena propia irredundante}. Si no existe ninguna cadena propia irredundante entre dos aristas EyE′de H, entonces decimos que la distancia entre ellas es infinita: distH(E, E′) = ∞. Tras haber presentado estas definiciones, vamos a dedicarnos ahora a utilizar la t´ecnica de escisi´on de ideales para estudiar los ideales monomiales libres de cuadrados a trav´es del estudio de los ideales de aristas asociados a hipergrafos. Para ello, vamos a centrarnos en una posible escisi´on de estos ideales que resulta de generalizar la noci´on de arista de escisi´on que hab´ıamos dado para grafos simples. 3.2.2. Aristas de escisi´on Al igual que razon´abamos en el cap´ıtulo que ten´ıa a los grafos como objeto combinatorio principal de estudio, si tenemos ahora una arista Ede un hipergrafo Hy utilizamos las notaciones que hemos introducido previamente, es claro que I(H) = (xE)+I(H\E). No obstante, esta suma no tiene por qu´e ser una escisi´on de I(H) y nos interesar´an los casos en los que s´ı lo sea. Surge de esta manera la siguiente definici´on: Definici´on 3.2.3. Dado un hipergrafo H, se dice que una arista Ees una arista de escisi´on de Hsi la suma I(H) = (xE) + I(H \ E) es una escisi´on del ideal I(H). 42 CAP´ ITULO 3. GENERALIZACI ´ ON cionado teorema del cap´ıtulo anterior: E=uv es una arista de escisi´on en el sentido de los hipergrafos ⇔Existe z∈E|(E\ {z})∪ {zi} ∈ EG∀zi∈(N(u)∪N(v)) \ {u, v} ⇔(E\ {u})∪ {zi}=vzi∈EG∀zi∈(N(u)∪N(v)) \ {u, v},o (E\ {v})∪ {zi}=uzi∈EG∀zi∈(N(u)∪N(v)) \ {u, v} ⇔(N(u)∪N(v)) \ {u, v} ⊆ N(v) o (N(u)∪N(v)) \ {u, v} ⊆ N(u) ⇔N(u)⊆N(v)∪ {v}oN(v)⊆N(u)∪ {u} ⇔E=uv es una arista de escisi´on en el sentido de los grafos . Ahora s´ı, veamos los dos lemas que necesitamos para demostrar el Teorema 3.2.16: Lema 3.2.18. Sea Hun hipergrafo d-uniforme propiamente conexo. Supongamos que E=E0={x1, . . . , xd}yE′son aristas de Hcon distH(E, E′) = t≤d. Entonces, tras renombrar los v´ertices convenientemente, existen aristas E1, . . . , Ettales que Ei= {y1, . . . , yi, xi+1, . . . , xd},Et=E′, e yi/∈Ejpara todo j < i. Demostraci´on. Como distH(E, E′) = t≤d, tiene que existir una cadena propia irredundante de aristas (E0=E, E1, . . . , Et=E′). |Ei∩Ei+1|=|Ei+1| − 1 = d−1, de manera que EiyEi+1 difieren exactamente en un v´ertice para todo i. En consecuencia, en el i-´esimo eslab´on de la cadena vamos a tener un conjunto Eique difiere de Een a lo sumo iv´ertices; dicho de otra forma, |E∩Ei| ≥ d−i. Como (E0, . . . , Et) es una cadena propia irredundante y Hes d-uniforme y propiamente conexo, para todo i<dtenemos que i= distH(E, Ei) = d−|E∩Ei|. En consecuencia, |E∩Ei|=d−i > 0 para todo i<d. Adem´as, si i=d=t, entonces distH(E0, Ei) = dy en consecuencia E0∩Ei=∅, ya que hemos tenido que cambiar los dv´ertices que formaban la arista E0. Por lo tanto, tambi´en en este caso se verifica que |E0∩Ei|=0=d−i. Vamos a probar ahora que los conjuntos Eicon los que estamos trabajando verifican, tras renombrar convenientemente los v´ertices, las condiciones del enunciado del lema. Lo vamos a hacer razonando por inducci´on sobre i. Si i= 1, queremos ver que el conjunto E1verifica las afirmaciones del enunciado. Tenemos que E=E0={x1, . . . , xd}, donde renombramos los v´ertices de manera que x1no pertenezca a E1. |E0∩E1|=d−1, luego E1={y1, x2, . . . , xd}, con y1/∈E0=E. Esto prueba el caso i= 1. Supongamos ahora que E0, . . . , Eisatisfacen el enunciado del lema para un cierto i > 1; es decir, Ei={y1, . . . , yi, xi+1, . . . , xd}, con yi/∈Ejpara todo j < i. |Ei∩Ei+1|=d−1, luego Ei+1 se puede construir a partir de Eisustituyendo un v´ertice de Eipor otro v´ertice al que vamos a llamar yi+1 que no pertenece a Ei. Esto implica en particular que yi+1 es distinto de y1, . . . , yi, xi+1, . . . , xd. En primer lugar, veamos que el v´ertice que eliminamos de Eino es ninguno de los yj, de manera que y1, . . . , yipertenecen a Ei+1. Efectivamente, si reemplaz´aramos 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 43 alguno de los yj(con j≤i) por yi+1 tendr´ıamos que |E0∩Ei|=|{xi+1, . . . , xd}| = d−i≤ |E0∩Ei+1|, pero esto es absurdo porque |E0∩Ei+1|=d−(i+1) = d−i−1. En consecuencia, yi+1 va a reemplazar a alg´un elemento del conjunto {xi+1, . . . , xd} y, renombrando convenientemente los v´ertices, podemos suponer que yi+1 va a reemplazar a xi+1; es decir, Ei+1 ={y1, . . . , yi, yi+1, xi+2, . . . , xd}. Lo ´ultimo que nos falta demostrar es que yi+1 no pertenece a Ejpara ning´un j≤i. Para ello vamos a razonar por reducci´on al absurdo, suponiendo que existe jmenor o igual que ital que yi+1 =xj. Entonces d−i=|E0∩Ei|=|{xi+1, . . . , xd}| = |{xj, xi+2, . . . , xd}| =|E0∩Ei+1|=d−i−1, lo cual es absurdo. Deducimos por tanto que yi+1 =xjpara todo j≤i. Como tambi´en ten´ıamos que yi+1 es distinto de y1, . . . , yi, xi+1, . . . , xd, ya podemos concluir que yi+1 /∈Ejpara ning´un j≤i. El razonamiento por inducci´on nos permite concluir la demostraci´on del lema. Lema 3.2.19. Sea Euna arista cualquiera de un hipergrafo d-uniforme propiamente conexo H. Entonces (xE)∩ I(H \ E) = ({mcm(xE, xH)|H∈ H ydistH(E, H) = 1}) + + ({mcm(xE, xH)|H∈ H ydistH(E, H)≥d+ 1}). Demostraci´on. Sean A= ({mcm(xE, xH)|H∈ H \ Ey distH(E, H)≤d}) y B= ({mcm(xE, xH)|H∈ H \ Ey distH(E, H)≥d+ 1}) = = ({mcm(xE, xH)|H∈ H y distH(E, H)≥d+ 1}), donde la ´ultima igualdad se debe a que distH(E, H)= 0 implica que E=H. Por definici´on, (xE)∩ I(H \ E) = A+B. En consecuencia, si denotamos por Cal ideal ({mcm(xE, xH)|H∈ H y distH(E, H) = 1}), para demostrar el lema basta probar que A=C. Como d≥2, tenemos que una arista Hque est´a a distancia 1 de Ees distinta de E y est´a a una distancia menor o igual que dde ella; por tanto, C⊆A. Veamos ahora que tambi´en se verifica la otra contenci´on. Sea xE∪H= mcm(xE, xH) un elemento del conjunto de generadores de Aque hemos descrito antes; es decir, suponemos que H∈ H\Eyt= distH(E, H)≤d. Si tfuese igual a 1, entonces ya tendr´ıamos que xE∪H∈C. Por tanto, podemos suponer que 2 ≤t≤d. En consecuencia, como Hes propiamente conexo, existe una cadena propia irredundante (E=H0, H1, H2, . . . , Ht=H) como en el Lema 3.2.18 y cuya longitud es minimal entre todas las cadenas propias irredundantes que van desde Ehasta H. En virtud del Lema 3.2.18, si E={x1, . . . , xd}y renombramos los v´ertices convenientemente, entonces H1={y1, x2, . . . , xd}, donde y1no es un elemento de Epero y1∈Hi para todo i∈ {2, . . . , t}. A partir de esto, mcm(xE, xH1) = xE∪H1=xE∪{y1}=xEy1. Como distH(E, H1) = 1, tenemos entonces que xEy1es un generador de C. Adem´as, como y1∈Hipara todo i∈ {2, . . . , t}, tenemos que mcm(xE, xHi) = xE∪Hies divisible por xEy1para todo 44 CAP´ ITULO 3. GENERALIZACI ´ ON i∈ {2, . . . , t}y, por tanto, pertenece a C. En particular, xE∪Ht=xE∪H∈C, tal y como quer´ıamos probar. Estamos ya en condiciones de demostrar el Teorema 3.2.16, para lo cual recordamos primero su enunciado: Teorema. Sea Euna arista de un hipergrafo d-uniforme propiamente conexo H, y supongamos que N(E) = {z1, . . . , zt}. Entonces Ees una arista de escisi´on si y solo si existe un v´ertice z∈Etal que (E\ {z})∪ {zi} ∈ H para cada zi∈N(E). Demostraci´on. Para probar la equivalencia del enunciado, vamos a demostrar por separado las dos implicaciones. ⇒Supongamos que Ees una arista de escisi´on. En virtud del Teorema 3.2.4, existe un v´ertice z∈Etal que (xE)∩I(H\E)⊆(xE)∩I(H\{z}). Si zi∈N(E), vamos a probar que (E\ {z})∪ {zi}es una arista de H \ {z}, lo que implicar´a que es una arista de H. Como zi∈N(E), existe una arista Hde Hcon distH(E, H) = 1 tal que H\E= {zi}. En virtud del Lema 3.2.19, xE∪Hes un generador de (xE)∩ I(H \ E)⊆ (xE)∩ I(H \ {z}). Tenemos entonces que xE∪H∈(xE)∩ I(H \ {z}), y por tanto existe una arista H′∈ H \ {z}tal que E∪H=E∪H′. En consecuencia, |E|+|H|−|E∩H|=|E∪H|=|E∪H′|=|E|+|H′|− |E∩H′|, y como |H|=|H′|=ddeducimos que |E∩H′|=|E∩H|=d−1, de manera que EyH′(que tienen el mismo cardinal) difieren en un ´unico v´ertice. M´as all´a de esto, tenemos que zpertenece a Epero no a H′, y zipertenece a H\E. Como E∪H=E∪H′,zitendr´a que pertenecer tambi´en a H′. En consecuencia, H′= (E\ {z})∪ {zi}, y como H′es una arista de H \ {z}podemos concluir que (E\ {z})∪ {zi}tambi´en lo es. ⇐Supongamos ahora que existe un v´ertice z∈Etal que (E\ {z})∪ {zi} ∈ H para cada zi∈N(E), y veamos que entonces Ees una arista de escisi´on. Sea xLuno de los generadores minimales de (xE)∩ I(H \ E). En virtud del Lema 3.2.19, se tiene que o bien L=E∪Hcon distH(E, H) = 1, o bien L=E∪Hcon distH(E, H)≥d+ 1. Si distH(E, H)≥d+1, entonces z /∈Hporque todas las aristas tienen cardinal dy por tanto E∩H=∅. En este caso, H∈ H\{z}y por tanto xL∈(xE)∩I(H\{z}). Si L=E∪Hcon distH(E, H) = 1, entonces existe zi∈N(E) tal que H\E={zi}. Por tanto, E∪H=E∪ {zi}. Por hip´otesis, E′= (E\ {z})∪ {zi}es una arista de H. En particular, lo es de H \ {z}. Adem´as, L=E∪H=E∪ {zi}=E∪((E\ {z})∪ {zi}) = E∪E′y por tanto xL=xE∪E′∈(xE)∩ I(H \ {z}). En definitiva, hemos probado que (xE)∩I(H\E)⊆(xE)∩I(H\{z}), y el Teorema 3.2.4 nos permite concluir que entonces Ees una arista de escisi´on. 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 45 Queda probada la doble implicaci´on y, por tanto, el teorema. Si Ees una arista de un hipergrafo d-uniforme propiamente conexo H, a partir de ahora denotaremos por H′al subhipergrafo {H∈ H | distH(E, H)≥d+ 1}de H, con el objetivo de simplificar la notaci´on. Presentamos a continuaci´on un lema en virtud del cual H′hereda de Hla propiedad de ser propiamente conexo. Lema 3.2.20. Si Ees una arista de un hipergrafo Hd-uniforme y propiamente conexo, entonces el subhipergrafo H′definido a partir de Etambi´en es un hipergrafo d-uniforme propiamente conexo. Demostraci´on. Es evidente que H′es un hipergrafo d-uniforme, de manera que solo tenemos que probar que es propiamente conexo. Para ello, tomamos dos aristas HyH′de H′con la propiedad de que H∩H′=∅. Como HyH′tambi´en son aristas de HyHes propiamente conexo, tenemos que existe una cadena (H=H0, H1, . . . , Ht=H′) en Hcomo en el Lema 3.2.18 tal que t= distH(H, H′) = d− |H∩H′|. Si tuvi´eramos que todas las aristas Hianteriores, con i∈ {1, . . . , t −1}, tambi´en pertenecen a H′, entonces ya tendr´ıamos que distH′(H, H′) = t=d− |H∩H′|. Supongamos entonces que existe i∈ {1, . . . , t −1}tal que Hino es una arista de H′={H∈ H | distH(E, H)≥d+ 1}. En consecuencia, distH(E, Hi) (valor al que voy a denotar por s) es menor o igual que d. Sea (E=E0, E1, . . . , Es=Hi) una cadena propia irredundante en Hentre EyHi. Tenemos entonces que distH(E1, Hi) = s−1< d, y como |E1|=|Hi|=d, lo anterior implica que E1∩Hi=∅. Podemos tomar entonces un elemento xde E1∩Hi. Como x∈Hiy hemos elegido una cadena propia irredundante como en el Lema 3.2.18, tenemos que o bien xpertenece aHo bien pertenece a H′. Sin p´erdida de generalidad, podemos suponer que x∈H. Gracias a que Hes propiamente conexo, se tiene que distH(E1, H) = d− |E1∩H| ≤ d−1, donde la ´ultima desigualdad se debe a que, por ser H∩E1=∅(ya que x∈H∩E1), su cardinal ha de ser mayor o igual que uno. Se tiene que distH(E1, H)≤d−1 y distH(E, E1) = 1, luego existe una cadena propia en Hde longitud a lo sumo dentre EyH, lo que contradice la suposici´on de que H∈ H′ y en consecuencia distH(E, H)≥d+ 1. Hemos alcanzado una contradicci´on, de donde deducimos que Hi∈ H′para todo i∈ {1, . . . , t−1}. Por lo tanto, distH′(H, H′) = d−|H∩H′|para cualquier par de aristas H, H′de H′con H∩H′=∅. Concluimos as´ı que efectivamente H′es propiamente conexo. El siguiente resultado que vamos a presentar es una consecuencia del Lema 3.2.19 y nos permite obtener una descripci´on de (xE)∩ I(H \ E) que resultar´a ´util m´as adelante. Corolario 3.2.21. Sea Euna arista de un hipergrafo d-uniforme propiamente conexo H, y supongamos que N(E) = {z1, . . . , zt}. Entonces (xE)∩ I(H \ E) = xE((z1, . . . , zt) + I(H′)) . 46 CAP´ ITULO 3. GENERALIZACI ´ ON Demostraci´on. En virtud del Lema 3.2.19, (xE)∩ I(H \ E) = ({mcm(xE, xH)|H∈ H y distH(E, H) = 1}) + + ({mcm(xE, xH)|H∈ H y distH(E, H)≥d+ 1}). Si H∈ H y distH(E, H) = 1, entonces existe i∈ {1, . . . , t}tal que H\E={zi}. Por lo tanto, mcm(xE, xH) = xE∪H=xE∪{zi}=xEziy esto nos permite deducir que ({mcm(xE, xH)|H∈ H y distH(E, H) = 1}) = xE(z1, . . . , zt). Si H∈ H y distH(E, H)≥d+ 1, entonces E∩H=∅porque en caso contrario, como Hes propiamente conexo, tendr´ıamos que distH(E, H) = d− |E∩H| ≤ d−1, lo cual es absurdo. Por lo tanto, en este caso mcm(xE, xH) = xE∪H=xExH, con H∈ H′ yE∩H=∅. Esto nos permite deducir que ({mcm(xE, xH)|H∈ H y distH(E, H)≥d+ 1}) = xEI(H′). Aplicando ahora el Lema 3.2.19 tal y como se˜nal´abamos al principio de la demostraci´on, se concluye la prueba de este corolario. El corolario que acabamos de demostrar es una generalizaci´on del Lema 2.2.2 que ve´ıamos en el cap´ıtulo anterior. Efectivamente, como ya hemos comentado en la Nota 3.2.17, cuando el hipergrafo Hcon el que estamos trabajando es un grafo simple y consideramos la arista E=uv, se verifica que N(E) = (N(u)∪N(v)) \ {u, v}. Adem´as, en el caso de grafos simples, H′, que est´a formado por las aristas cuya distancia a Ees al menos 3, est´a formado entonces por las aristas que no contienen a ninguno de los v´ertices del conjunto N(u)∪N(v); es decir, H′=G\(N(u)∪N(v)). Recuperamos entonces el Lema 2.2.2 sin m´as que restringirnos a grafos simples en el lema anterior. Siguiendo la l´ınea de generalizar los resultados estudiados en el cap´ıtulo anterior, el lema que presentamos a continuaci´on constituye una generalizaci´on del Lema 2.2.8 sin m´as que prestar atenci´on a los comentarios efectuados en el p´arrafo anterior, con la diferencia de que la arista que consideramos ahora en el enunciado es arbitraria y no necesariamente de escisi´on. Lema 3.2.22. Sea Euna arista de un hipergrafo Hd-uniforme y propiamente conexo. Si t=|N(E)|, entonces βi−1,j((xE)∩ I(H \ E)) = i X l=0 t lβi−1−l,j−d−l(I(H′)) , donde seguimos considerando que β−1,j(I(H′)) = 1 si j= 0 yβ−1,j(I(H′)) = 0 si j= 0. Demostraci´on. Si N(E) = {z1, . . . , zt}, entonces en virtud del Corolario 3.2.21 se tiene que βi−1,j((xE)∩ I(H \ E)) = βi−1,j(xE((z1, . . . , zt) + I(H′))) = =βi−1,j−d((z1, . . . , zt) + I(H′)) = =βi,j−d(R/((z1, . . . , zt) + I(H′))) . 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 47 Ninguno de los generadores de I(H′) es divisible por zipara ning´un i∈ {1, . . . , t}. Para probarlo, supongamos que el generador xH∈ I(H′) es divisible por alg´un zi, de manera que zies un v´ertice de la arista Hde H′. Como zi∈N(E), existe una arista Hi de Htal que zi∈Hiy distH(E, Hi) = 1. Tenemos entonces que H∩Hi=∅porque zi∈H∩Hi. En consecuencia, como Hes propiamente conexo, se tiene que p= distH(H, Hi) = d− |H∩Hi|< d, de manera que existe una cadena propia irredundante (Hi=H′ 0, . . . , H′ p=H) desde Hihasta H. As´ı pues, (E, Hi=H′ 0, . . . , H′ p=H) es una cadena propia de longitud p+ 1 ≤d desde Ehasta H. Pero esto implicar´ıa que distH(E, H)≤d, lo que contradice que distH(E, H)≥d+ 1 por ser Huna arista de H′. En definitiva, se tiene que ning´un generador de I(H′) es divisible por ning´un elemento de N(E). Modificamos ahora nuestra notaci´on y escribimos R=k[z1, . . . , zt, y1, . . . , ys], donde {y1, . . . , ys}=X \N(E). Haciendo uso del Lema 2.2.6 y la Nota 2.2.7 que hab´ıamos introducido en el cap´ıtulo anterior, tenemos entonces que R (z1, . . . , zt) + I(H′)∼ =R1 (z1, . . . , zt)⊗k R2 I(H′), donde R1=k[z1, . . . , zt] y R2=k[y1, . . . , ys]; y βi,j−dR L= i X l1=0 j−d X l2=0 βl1,l2R1 (z1, . . . , zt)βi−l1,j−d−l2R2 I(H′), donde L= (z1, . . . , zt) + I(H′). Sabemos adem´as que βl1,l2R1 (z1, . . . , zt)=t lsi l=l1=l2 0 si l1=l2, de manera que juntando todo lo anterior obtenemos que βi,j−dR L= i X l=0 t lβi−l,j−d−lR2 I(H′). Ahora ya podemos concluir, sin m´as que observar que βi−l,j−d−l(R2/I(H′)) = βi−l,j−d−l(R/I(H′)) = βi−1−l,j−d−l(I(H′)) para todo l(donde adoptamos el convenio de que β−1,j(I(H′)) = 1 si j= 0 y toma el valor 0 si j= 0). Si utilizamos ahora el Lema 3.2.22, es posible obtener una generalizaci´on del Teorema 2.2.9 que nos va a proporcionar una f´ormula para los n´umeros de Betti graduados del ideal de aristas de un hipergrafo en t´erminos de los n´umeros de Betti graduados de los ideales de aristas de ciertos subhipergrafos. 48 CAP´ ITULO 3. GENERALIZACI ´ ON Teorema 3.2.23. Sea Hun hipergrafo d-uniforme propiamente conexo y sea Euna arista de escisi´on de H. Sean tambi´en H′={H∈ H | distH(E, H)≥d+1}yt=|N(E)|. Entonces para todo i≥1y todo j≥0se tiene que βi,j(I(H)) = βi,j (I(H \ E)) + i X l=0 t lβi−1−l,j−d−l(I(H′)) , donde seguimos considerando que β−1,j(I(H′)) = 1 si j= 0 yβ−1,j(I(H′)) = 0 si j= 0. Demostraci´on. Como Ees una arista de escisi´on, en virtud del Teorema 2.1.4 tenemos que βi,j(I(H)) = βi,j ((xE)) + βi,j(I(H \ E)) + βi−1,j((xE)∩ I(H \ E)) . En consecuencia, basta se˜nalar que βi,j((xE)) = 0 siempre que i≥1 y aplicar el Lema 3.2.22 para obtener la f´ormula del enunciado del teorema. Si Hes un hipergrafo propiamente conexo y Ees una arista de escisi´on, los subhipergrafos H \ EyH′no tienen por qu´e tener aristas de escisi´on; de hecho, es posible que H \ Eni siquiera sea propiamente conexo. Vamos a ilustrar esta ´ultima afirmaci´on a trav´es de un ejemplo: Ejemplo 3.2.24. Consideramos el hipergrafo 3-uniforme y propiamente conexo H1que hab´ıamos definido en el ejemplo 3.2.13, el cual tiene como conjunto de aristas E= {x1x2x3, x1x2x4, x1x3x5, x2x3x4, x2x3x5, x3x4x5}. Consideramos ahora la arista E=x1x2x3. Utilizando el Teorema 3.2.16, vamos a probar que Ees una arista de escisi´on: por una parte, como las aristas que est´an a distancia 1 de Eson las que pertenecen al conjunto {x1x2x4, x1x3x5, x2x3x4, x2x3x5}, es claro que N(E) = {x4, x5}. Ahora bien, el hecho de que (E\ {x1})∪ {x4}=x2x3x4y (E\{x1})∪ {x5}=x2x3x5son aristas de H1ya nos permite deducir que Ees una arista de escisi´on. Sin embargo, H1\Eno es propiamente conexo porque las aristas E1=x1x2x4y E2=x1x3x5comparten el v´ertice x1y, sin embargo, no existe ninguna cadena propia en H1\Edesde E1hasta E2que tenga longitud 2 = 3 − |E1∩E2|. Lo anterior implica que, al igual que ocurr´ıa en el Teorema 2.2.9, la f´ormula que proporciona el Teorema 3.2.23 no es recursiva en general. En el cap´ıtulo previo hab´ıamos visto que si el grafo Gcon el que trabaj´abamos era un bosque, entonces la f´ormula que obten´ıamos en el Teorema 2.2.9 gracias a la t´ecnica de escisi´on de ideales trabajando con aristas de escisi´on s´ı que era recursiva. En el caso de hipergrafos, aquellos para los cuales la f´ormula obtenida en el Teorema 3.2.23 es recursiva son los llamados hipergrafos triangulados, que vamos a estudiar a continuaci´on y que son una generalizaci´on de los grafos cordales. Para evitar que la extensi´on del trabajo sea excesiva, no nos centraremos en el estudio de la recursividad de la f´ormula anterior, sino que estudiaremos los hipergrafos triangulados en relaci´on con una posible generalizaci´on del Teorema de Fr¨oberg 2.3.14 que estudi´abamos en el cap´ıtulo previo y que se enunciaba en t´erminos de grafos cordales. 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 49 3.2.3. Hipergrafos triangulados Como acabamos de comentar, con los hipergrafos triangulados buscamos generalizar la noci´on de grafo cordal que hab´ıamos estudiado en el cap´ıtulo anterior. Un grafo cordal se define como aquel que no tiene ciclos minimales. Sin embargo, para generalizar este concepto haremos uso de una caracterizaci´on de los grafos cordales que no demostramos aqu´ı porque no se encuentra dentro de los objetivos del trabajo, pero que se puede encontrar (aunque utilizando una nomenclatura diferente) en [3]. Esta caracterizaci´on es la siguiente: Teorema 3.2.25. Un grafo Ges cordal si y solo si todo subgrafo inducido de Gcontiene un v´ertice vtal que el conjunto N(v)es un clique de G(es decir, es un subgrafo de G que es un grafo completo). Nota 3.2.26.En cuanto al enunciado del teorema anterior, notemos que, como ves adyacente a todo v´ertice de N(v), tendr´ıamos tambi´en que el subgrafo inducido de G sobre N(v)∪ {v}es un clique de G. A partir de la caracterizaci´on anterior de los grafos cordales, resulta natural que en nuestro camino hacia la generalizaci´on de este concepto introduzcamos primero una generalizaci´on de los grafos completos y de los v´ertices adyacentes a uno dado. A esto dedicamos las siguientes definiciones, que nos van a permitir introducir el concepto de hipergrafo triangulado. Definici´on 3.2.27. El hipergrafo d-completo de orden n se denota por Kd ny se define como el hipergrafo cuyas aristas son todos los subconjuntos de delementos del conjunto de v´ertices X, con |X| =n. Cuando d= 2, K2 nes el grafo completo de nv´ertices, al que denot´abamos en el cap´ıtulo anterior por Kn. Si n < d, adoptamos el convenio de que Kd n es el hipergrafo formado por nv´ertices aislados. Por ´ultimo, si n= 0, entonces Kd 0es el grafo vac´ıo, al que podemos ver como un hipergrafo d-completo de orden 0. Definici´on 3.2.28. Dos v´ertices distintos x, y ∈ X son adyacentes si existe una arista E∈ H tal que x, y ∈E. Dado un v´ertice x∈ X, vamos a denotar por N(x) al conjunto de v´ertices adyacentes ax; es decir, N(x) = {y∈ X | yes adyacente a x}. A partir de la definici´on anterior, es claro que si Ees una arista de Hyx∈E, entonces E⊆N(x)∪ {x}. Definici´on 3.2.29. Se dice que un hipergrafo d-uniforme propiamente conexo Hes triangulado si para todo subconjunto no vac´ıo Yde Xse verifica que el subhipergrafo inducido de Hsobre Y,HY, contiene un v´ertice x∈ Y ⊆ X tal que el subhipergrafo inducido de HYsobre N(x)∪ {x}es un hipergrafo d-completo de orden |N(x)|+ 1. Gracias al Teorema 3.2.25 que hab´ıamos enunciado antes, es claro que los hipergrafos triangulados constituyen una generalizaci´on de los grafos cordales. Antes de intentar generalizar el teorema de Fr¨oberg, vamos a introducir una definici´on y un par de resultados que necesitaremos. 50 CAP´ ITULO 3. GENERALIZACI ´ ON Definici´on 3.2.30. Sea Hun hipergrafo d-uniforme propiamente conexo. Dos aristas E yHde Hson t-disjuntas si distH(E, H)≥t. Se dice que un conjunto de aristas E′⊆ E son t-disjuntas dos a dos si cada par de aristas de E′son t-disjuntas. Cuando Hes un hipergrafo d-uniforme propiamente conexo, claramente se tiene que dos aristas EyHson d-disjuntas si y solo si E∩H=∅; es decir, si EyHson disjuntas en el sentido usual. Adem´as, cuando el hipergrafo con el que trabajamos es un grafo simple G, la definici´on que d´abamos en el cap´ıtulo anterior para aristas desconectadas es equivalente a decir que las aristas en cuesti´on son 3-disjuntas en G. Presentamos ahora un teorema que utilizaremos m´as adelante, si bien no vamos a exponer su demostraci´on porque utiliza ciertos conceptos de ´algebra homol´ogica que no forman parte del desarrollo principal del trabajo y su introducci´on en este punto supondr´ıa una alargamiento excesivo del mismo. En cualquier caso, esta demostraci´on se puede encontrar en [17]. Teorema 3.2.31. Sea Hun hipergrafo d-uniforme propiamente conexo. Entonces el n´umero de Betti graduado βi−1,di(I(H)) es igual al n´umero de conjuntos formados por i aristas (d+ 1)-disjuntas dos a dos de H. En particular, si ces el cardinal del mayor conjunto de aristas (d+ 1)-disjuntas dos a dos de H, entonces reg(I(H)) ≥(d−1)c+ 1. Hab´ıamos comentado antes que los hipergrafos triangulados permit´ıan recuperar el car´acter recursivo de la f´ormula para los n´umeros de Betti graduados que nos proporciona la t´ecnica de escisi´on de ideales en el Teorema 3.2.23, algo que en el caso de grafos simples hab´ıamos obtenido para bosques. De una forma similar, los hipergrafos triangulados nos permiten generalizar un resultado que en el cap´ıtulo anterior hab´ıamos enunciado y demostrado para grafos simples que eran bosques. Se trata del Corolario 2.2.15, que proporciona el valor de la regularidad del ideal de aristas de un bosque en t´erminos del n´umero de aristas desconectadas dos a dos en ´el y nos da la licencia de omitir la demostraci´on del siguiente resultado por ser esta muy similar. Corolario 3.2.32. Sea Hun hipergrafo d-uniforme propiamente conexo y triangulado. Si ces el cardinal del mayor conjunto de aristas (d+1)-disjuntas dos a dos de H, entonces reg(I(H)) = (d−1)c+ 1. Ahora s´ı, nos encontramos en condiciones de intentar generalizar el Teorema de Fr¨oberg, en virtud del cual todo grafo Gverifica que su ideal de aristas tiene una resoluci´on lineal si y solo si Gces un grafo cordal. Ya hab´ıamos visto que el concepto de hipergrafo triangulado es una generalizaci´on de la noci´on de grafo cordal, pero antes de seguir tenemos que generalizar el concepto de grafo complementario al caso de hipergrafos. Es esto a lo que dedicamos la siguiente definici´on: Definici´on 3.2.33. Si Hes un hipergrafo d-uniforme propiamente conexo, definimos el complementario de H, y lo denotamos por Hc, como el hipergrafo cuyo conjunto de aristas es {E⊆ X | |E|=dyE /∈ H}. 3.2. HIPERGRAFOS E IDEALES DE ARISTAS 51 Generalizando t´ermino a t´ermino el Teorema de Fr¨oberg, cabr´ıa esperar que en el caso de un hipergrafo Hpropiamente conexo se verificara que I(H) tiene una resoluci´on lineal si y solo si Hces un hipergrafo triangulado. Sin embargo, vamos a mostrar a continuaci´on un ejemplo que ilustra que el resultado anterior no es cierto porque Hc puede incluso no ser propiamente conexo. Ejemplo 3.2.34. Consideramos el conjunto de v´ertices X={x1, x2, x3, x4, x5}y el hipergrafo H=K3 5\ {x1x2x3, x3x4x5}; es decir, Hes el hipergrafo 3-completo de orden 5 al que le hemos quitado dos aristas. En este caso se tiene que el hipergrafo Hc, cuyo conjunto de aristas es precisamente {x1x2x3, x3x4x5}, no es propiamente conexo porque sus dos aristas comparten el v´ertice x3y sin embargo no existe ninguna cadena propia irredundante entre ellas de longitud 2 = 3 −1. El hecho de que Hcno sea propiamente conexo hace que ni siquiera podamos plantearnos si es triangulado, concepto que se defin´ıa ´unicamente para hipergrafos propiamente conexos. Sin embargo, utilizando por ejemplo Macaulay2 de la forma en que se expone en el Ap´endice A, es posible comprobar que la resoluci´on de I(H) es lineal. Queda claro de esta manera que no es posible llevar a cabo una generalizaci´on t´ermino a t´ermino del Teorema de Fr¨oberg, de manera que en lugar de caracterizar cu´ando el ideal de aristas de un hipergrafo propiamente conexo tiene una resoluci´on lineal vamos a intentar caracterizar cu´ando dicho ideal tiene primeras sizigias lineales. Para ello, comenzamos introduciendo el siguiente concepto: Definici´on 3.2.35. El di´ametro de un hipergrafo d-uniforme propiamente conexo Hse define como diam(H) = m´ax{distH(E, H)|E, H ∈ H}, donde el di´ametro es infinito si existen dos aristas que no est´en conectadas por ninguna cadena propia. El siguiente teorema nos va a proporcionar una caracterizaci´on de los ideales de aristas que tienen primeras sizigias lineales, y lo har´a en t´erminos del di´ametro del hipergrafo asociado. Teorema 3.2.36. Sea Hun hipergrafo d-uniforme propiamente conexo. Se verifica que I(H)tiene primeras sizigias lineales si y solo si diam(H)≤d. Demostraci´on. Para probar la equivalencia del enunciado, demostraremos por separado cada implicaci´on. ⇐Supongamos en primer lugar que diam(H)≤d. Gracias a la resoluci´on de Taylor, es conocido que el primer m´odulo de sizigias de I(H) est´a generado por las sizigias S(xE, xH), con EyHaristas de H, que se obtienen a partir de los S-polinomios correspondientes. Para probar esta implicaci´on, bastar´a entonces con demostrar que S(xE, xH) est´a generada por sizigias lineales. Sea t= distH(E, H). Como diam(H)≤d, tenemos tambi´en que t≤d. Gracias al Lema 3.2.18, podemos considerar una cadena propia irredundante (E= 58 AP ´ ENDICE A. IMPLEMENTACI ´ ON EN MACAULAY2 R=QQ[ x_1 .. x_6 ] E ={{ x_1 , x_2 } ,{ x_2 , x_3 } ,{ x_2 , x_4 } ,{ x_4 , x_5 } ,{ x_4 , x_6 }} G= graph (R,E) A partir de esto, Macaulay2 almacena el grafo que acabamos de definir, mostrando por pantalla lo siguiente: Graph { edges => {{ x_1 , x_2 } ,{ x_2 , x_3 } ,{ x_2 , x_4 } ,{ x_4 , x_5 },{ x_4 , x_6 }} , ring => R, vertices => {x_1 ,x_2 ,x_3 ,x_4 ,x_5 , x_6 }} Otra forma de definir el mismo grafo consiste en representar sus aristas como generadores de un ideal monomial cuadr´atico libre de cuadrados y utilizar este ideal para definir el grafo, que tendr´a como v´ertices las distintas variables que aparezcan entre los generadores del ideal. Lo vemos en el siguiente recuadro: e= monomialIdeal (x_1 *x_2 , x_2 *x_3 ,x_2*x_4 ,x_4*x_5 ,x_4*x_6) H= graph e Para Macaulay2, los dos grafos GyHque acabamos de definir son el mismo: basta escribir G==H en la l´ınea de comandos y ver c´omo el programa devuelve el valor true. Ahora que ya sabemos definir grafos, podemos pedir a Macaulay2 que nos devuelva el ideal de aristas asociado a un grafo. Esto se hace de la siguiente manera: i= edgeIdeal G El ideal que Macaulay2 nos devuelve al ejecutar este comando es efectivamente el ideal de aristas de nuestro grafo G. Lo que nos muestra por pantalla es lo siguiente: monomialIdeal (x_1*x_2 , x_2 *x_3 , x_2*x_4 , x_4*x_5 , x_4*x_6) Veamos ahora c´omo calcular los diagramas de Betti que aparec´ıan en el Ejemplo 2.2.11. Si empezamos con el ideal de aristas asociado al grafo de partida, el siguiente comando nos proporciona directamente su diagrama de Betti: minimalBetti i No obstante, el diagrama que Macaulay2 nos proporciona no se ajusta exactamente a la forma en la que solemos representarlo, sino que en la i-´esima columna y en la j-´esima fila contiene al elemento βi−1,i+j(I(G)). Este diagrama es el siguiente: I(G)0123 0 1 - - - 1 - 5 6 2 59 A partir de este diagrama es posible calcular la dimensi´on proyectiva y la regularidad del ideal de aristas de nuestro grafo, aunque tambi´en existen comandos espec´ıficos para ello y son los siguientes: si isigue siendo nuestro ideal de aristas, regularity i nos devuelve la regularidad de iypdim (module i) nos devuelve su dimensi´on proyectiva, viendo icomo un R-m´odulo. En el Ejemplo 2.2.11, calcul´abamos tambi´en el diagrama de Betti del grafo G\e, donde eera la arista x2x4. El procedimiento para ello es el mismo que acabamos de presentar para G, pero en lugar de construir el grafo nuevamente desde el principio, ahora podemos utilizar una funci´on que permite eliminar aristas de un grafo dado. Esta funci´on, que se llama deleteEdges, toma como valores de entrada un grafo Gy una lista Eque consiste en el conjunto de aristas que deseamos eliminar, y devuelve el grafo que resulta de eliminar en Glas aristas del conjunto E. Basta introducir lo siguiente en la l´ınea de comandos para eliminar la arista ede nuestro grafo Goriginal: E ={{ x_2 , x_4 }} deleteEdges (G ,E) Aunque el paquete EdgeIdeals tiene un gran n´umero de funciones interesantes, muchas de ellas corresponden a conceptos que no han aparecido en este trabajo. Por este motivo, voy a terminar este ap´endice comentando solamente dos funciones m´as. La siguiente funci´on que me gustar´ıa presentar es inducedGraph, que toma como argumentos un grafo Gy un subconjunto Pdel conjunto de v´ertices de G, y devuelve el subgrafo inducido de Gsobre los v´ertices de P. Para conseguir esto, basta introducir inducedGraph(G,P) en la l´ınea de comandos. Por ´ultimo, vamos a hablar de una funci´on que es muy ´util en la investigaci´on porque permite formular conjeturas gracias a la posibilidad de comprobar un gran n´umero de ejemplos de forma r´apida. Se trata de la funci´on randomGraph, que permite generar un grafo aleatorio con un n´umero previamente fijado de v´ertices y de aristas. Esta funci´on recibe como argumentos un anillo de polinomios y un n´umero entero. Las variables del anillo de polinomios ser´an los v´ertices del grafo generado, mientras que el n´umero entero indica el n´umero de aristas que deseamos que tenga el grafo que se va a generar aleatoriamente. 60 AP ´ ENDICE A. IMPLEMENTACI ´ ON EN MACAULAY2 Bibliograf´ıa [1] S. Asensio,Sobre la conjetura de la sensibilidad y su resoluci´on v´ıa teor´ıa de grafos, Trabajo de fin de grado, Facultad de Ciencias, Universidad de Valladolid, https://uvadoc.uva.es/handle/10324/57957, 2022. [2] S. Asensio,La conjetura de la sensibilidad y su resoluci´on v´ıa teor´ıa de grafos, La Gaceta de la RSME 26 (1), pp. 131-148, 2023. [3] G. A. Dirac,On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Universit¨at Hamburg 25, pp. 71-76, 1961. [4] D. Eisenbud, M. Green, K. Hulek y S. Popescu,Restricting linear syzygies: algebra and geometry, Compositio Mathematica 141 (6), pp. 1460-1478, 2004. [5] S. Eliahou y M. Kervaire,Minimal resolutions of some monomial ideals, Journal of Algebra 129, pp. 1-25, 1990. [6] S. Faridi,The facet ideal of a simplicial complex, Manuscripta Mathematica 109, pp. 159-174, 2002. [7] G. Favacchio, J. Hofscheier, G. Keiper y A. Van Tuyl,Splittings of toric ideals, Journal of Algebra 574, pp. 409-433, 2021. [8] ´ O. Fern´ andez-Ramos,Graded Betti numbers of edge ideals, PhD thesis, Universidad de Valladolid, https://uvadoc.uva.es/handle/10324/1769, 2012. [9] ´ O. Fern´ andez-Ramos y P. Gimenez,First nonlinear syzygies of ideals associated to graphs, Communications in Algebra 37 (6), pp. 1921-1933, 2009. [10] ´ O. Fern´ andez-Ramos y P. Gimenez,Regularity 3 in edge ideals associated to bipartite graphs, Journal of Algebraic Combinatorics 39 (4), pp. 919-937, 2014. [11] C. A. Francisco, H. T. H` a y A. Van Tuyl,Splittings of monomial ideals, Proceedings of the American Mathematical Society 137 (10), pp. 3271-3282, 2009. [12] C. A. Francisco, A. Hoefel y A. Van Tuyl,EdgeIdeals: A package for (hyper)graphs, The Journal of Software for Algebra and Geometry 1, pp. 1-4, 2009. [13] R. Fr¨ oberg,On Stanley-Reisner rings, Topics in Algebra, Banach Center Publications 26 (2), pp. 57-50, 1990. 61 62 BIBLIOGRAF´ IA [14] D. R. Grayson y M. E. Stillman, Macaulay2, un sistema de software para la investigaci´on en geometr´ıa algebraica. Disponible en https://faculty. math.illinois.edu/Macaulay2/. [15] H. T. H` a y A. Van Tuyl,Resolutions of square-free monomial ideals via facet ideals: a survey, Algebra, geometry and their interactions, Contemporary Mathematics 448, pp.91-117, American Mathematical Society, Providence, RI, USA, 2007. [16] H. T. H` a y A. Van Tuyl,Splittable ideals and the resolutions of monomial ideals, Journal of Algebra 309, pp. 405-425, 2007. [17] H. T. H` a y A. Van Tuyl,Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, Journal of Algebraic Combinatorics 27, pp. 215-245, 2008. [18] S. Jacques,Betti numbers of graph ideals, PhD thesis, University of Sheffield, https://arxiv.org/abs/math/0410107, 2004. [19] S. Jacques y M. Katzman,The Betti numbers of forests,https://arxiv. org/abs/math/0501226, 2005. [20] E. Miller y B. Sturmfels,Combinatorial commutative algebra, Graduate texts in Mathematics 227, Springer-Verlag, New York, 2005. [21] M. V. Pinto y R. H. Villarreal,Graph rings and ideals: Wolmer Vasconcelos contributions,https://arxiv.org/abs/2305.06270, 2023. [22] A. Van Tuyl,Edge Ideals Using Macaulay2. En: Monomial ideals, computations and applications (A. Bigatti, P. Gimenez, E. S´aenz-de-Cabez´on Eds.), Lecture Notes in Mathematics 2083, pp. 95-105, Springer, Berlin, Heidelberg, 2013. [23] R. H. Villarreal,Cohen-Macaulay graphs, Manuscripta Mathematica 66 (3), pp. 277-293, 1990. [24] A. Simis, W. V. Vasconcelos y R. H. Villarreal,On the ideal theory of graphs, Journal of Algebra 167 (2), pp. 389-416, 1994. [25] X. Zheng,Resolutions of facet ideals, Communications in Algebra 32 (6), pp. 2301-2324, 2004.