El legado de Maryam Mirzakhani en la Matemática Discreta

Facultad de Matemáticas Departamento de Geometría y Topología TRABAJO FIN DE GRADO El legado de Maryam Mirzakhani en la Matemática Discreta Pedro José Muñoz Méndez Supervisado por María Trinidad Villar Liñán Sevilla, Junio 2024 2 Índice general Resumen ................................. 5 Abstract .................................. 7 Introducción ............................... 9 1. Preliminares 13 1.1. Definiciones............................. 13 1.2. Algunas propiedades básicas . . . . . . . . . . . . . . . . . . . . 16 2. Descomposición de Kn,m yKr,s,t en k−ciclos 19 2.1. Descomposición de Kn,m en k−ciclos............... 19 2.2. Descomposición de Kr,s,t en k−ciclos............... 20 2.2.1. Descomposición en 2k−ciclos............... 20 2.2.2. Descomposición en 3−ciclos................ 21 2.2.3. Descomposición en 5−ciclos................ 23 2.3. Ellegado .............................. 35 3. Un grafo planar pequeño no 4−elegible 37 3.1. Grafos coloreables por listas . . . . . . . . . . . . . . . . . . . . 37 3.2. Un grafo no 4−elegible....................... 39 3.3. Aplicaciones ............................ 44 4. Coloraciones de Sperner en hipergrafos 45 4.1. Complejos simpliciales . . . . . . . . . . . . . . . . . . . . . . . 45 4.2. Hipergrafos y etiquetado admisible Sperner . . . . . . . . . . . . 47 4.3. Una versión geométrica . . . . . . . . . . . . . . . . . . . . . . . 54 4.4. Aplicaciones del etiquetado de hipergrafos . . . . . . . . . . . . . 55 3 4ÍNDICE GENERAL Resumen Maryam Mirzakhani (1977 - 2017) fue una matemática iraní y la primera mujer en ganar la Medalla Fields (2014). Destacó en una amplia gama de áreas de las matemáticas, como geometría aritmética, geometría hiperbólica, sistemas dinámicos, geometría algebraica y geometría diferencial, entre otras. En este trabajo nos centraremos en algunas de sus aportaciones a la matemática discreta y cómo han trascendido a lo largo del tiempo. Precisamente, sus dos primeros trabajos publicados se enmarcan dentro de la teoría de grafos. En particular se tratará la descomposición en 5−ciclos de grafos tripartitos completos [18], veremos un ejemplo de un grafo planar no 4−elegible [20], y algunos resultados sobre coloración de Sperner ([22], [23]). Estos últimos, algo más recientes y publicados en los últimos años de su vida, proporcionan resultados aplicables a problemas de optimización combinatoria. 5 6 Abstract Maryam Mirzakhani (1977 - 2017) was an Iranian mathematician and the first woman to win the Fields Medal (2014). She excelled in a wide range of areas in mathematics, including arithmetic geometry, hyperbolic geometry, dynamical systems, algebraic geometry, and differential geometry, among others. In this work, we will focus on some of her contributions to discrete mathematics and how they have transcended over time. Specifically, her first two published papers fall within graph theory. In particular, we will discuss the decomposition into 5−cycles of complete tripartite graphs [18], we will see an example of a non- 4−choosable planar graph [20], and some results on Sperner coloring ([22], [23]). The latter, more recent and published in the last years of her life, provide results which are applicable to combinatorial optimization problems. 7 8 Introducción Maryam Mirzakhani, la primera mujer en recibir la Medalla Fields, nació el 12 de mayo de 1977 en Teherán, Irán ([3], [19]). Desde una edad temprana mostró pasión por la lectura y la escritura, pero no por las matemáticas. La pasión por estas despertó cuando su hermano le habló de la solución que dio Gauss al problema de sumar los primeros 100 números naturales. Cuando terminó la escuela primaria y se unió a la Escuela Farzanegan de Teherán, una escuela solo para chicas administrada por la Organización Nacional de Desarrollo de Talentos Excepcionales de Irán, la guerra Irán-Irak acababa de terminar, y el sistema educativo del país era más estable después de la Revolución Islámica en 1979. En la escuela secundaria, Mirzakhani tuvo inicialmente resultados poco satisfactorios en matemáticas, pero gracias a su entusiasmo, su profesor de matemáticas que la motivó y la directora del centro Ms. Haerizadeh, quien luchaba por las oportunidades de sus estudiantes, consiguió que las matemáticas se convirtieran en una de sus grandes fortalezas. Conoció a la que se convertiría en su íntima amiga Roya Beheshti en la escuela secundaria, quien recuerda a Mirzakha- ni como una persona interesada en el ámbito social y político que no toleraba ningún tipo de prejuicio contra las mujeres. Antes de terminar la escuela secundaria, Mirzakhani y Beheshti participaban en talleres de verano sobre matemáticas, donde conocieron a Ebad Mahmoodian, profesor en la Universidad de Sharif, con quien Mirzakhani publicó un artículo a la temprana edad de 18 años ([18]). Ambas participaron además en las Olimpiadas Internacionales de Matemáticas en 1994, convirtiéndose así en las primeras mujeres que representaban a Irán en dichas olimpiadas. Mirzakhani consiguió la medalla de oro en 1994 y 1995, obteniendo este segundo año una puntuación perfecta. Roya Beheshti, quien ahora es miembro del cuerpo docente de la Universidad de Washington, dijo en una entrevista: ”En realidad, nunca sentí que estuviera en desventaja por ser una estudiante femenina en el equipo”, a lo que añadió: "parte de ello se debía a que estaba con Maryam y me sentía empoderada al estar con otra estudiante femenina, especialmente alguien tan fuerte como ella". Uno de los entrenadores de las Olimpiadas de Matemáticas de Irán, Saieed Akbari, a menudo planteaba problemas de naturaleza combinatoria a Mirzakhani y 9 16 CAPÍTULO 1. PRELIMINARES 3. Aristas distintas vienen dadas por conjuntos de vértices distintos. 4. El interior de una arista cualquiera (del arco con el que la identificamos) no contiene vértices ni puntos de otras aristas. Un grafo se dirá planar si existe algún grafo isomorfo a él que sea plano. Ejemplo 2. Algunos ejemplos de grafos planares son K1, K2, K3, K4yK2,2. Sin embargo, grafos como K5yK3,3no son planares. Figura 1.5: K4es un grafo planar. Figura 1.6: K5no es un grafo planar. 1.2. Algunas propiedades básicas Pasamos a enunciar ahora algunas propiedades básicas sobre las definiciones anteriores. Lema 1.2.1. Sea n≥1.Entonces |Kn|=ny||Kn|| =n(n−1) 2. 1.2. ALGUNAS PROPIEDADES BÁSICAS 17 Lema 1.2.2. Dado r≥2, se cumple: |Kn1,n2,...,nr|= r X i=1 ni, ||Kn1,n2,...,nr|| =X 1≤i<j≤r ninj. En particular, |Kn,m| = n+m, ||Kn,m|| = nm |Kr,s,t| = r+s+t, ||Kr,s,t|| = rs +rt +st Demostración. El orden es inmediato por la partición del grafo. Para las aristas, lo vemos por inducción sobre r. Para el caso base r= 2, tenemos Kn1,n2. Si la partición es V1∪V2, como de cada uno de los n1vértices de V1salen n2aris- tas, tenemos n1n2aristas en total. Supuesto cierto para r, veamos que se cumple también para r+ 1. Si la partición es V1∪V2∪... ∪Vr+1, sabemos que sobre V1∪V2∪... ∪Vrtenemos X 1≤i<j≤r ninj aristas por hipótesis de inducción. Incluyendo Vr+1 en la partición, estamos añadiendo nr+1(n1+n2+... +nr) aristas. Sumadas a las de V1∪V2∪...∪Vr, tenemos lo que queríamos. Los grafos bipartitos se caracterizan según la siguiente propiedad. Proposición 1.2.3. Un grafo es bipartito si y solo si no contiene ciclos impares. Para el estudio de grafos tripartitos nos será de utilidad también el concepto de cuadrado latino. Definición 1.2.4. Una matriz A= (aij)1≤i,j≤ntal que aij ∈ {1, ..., n}se dice que es un cuadrado latino si cada elemento de {1, ..., n}aparece exactamente una vez en cada columna y en cada fila. Ejemplo 3. Algunos cuadrados latinos son, por ejemplo,   1 2 3 3 1 2 2 3 1  (1.1) 18 CAPÍTULO 1. PRELIMINARES     1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3     (1.2)       1 2 3 ... r r1 2 ... r −1 r−1r1... r −2 ... ... ... ... ... 2 3 4 ... 1       (1.3) Una caracterización importante sobre grafos planares es el Teorema de Kuratowski. Para enunciarlo, necesitamos el concepto de menores de un grafo. Definición 1.2.5. Sean G= (V, A)un grafo, x, y ∈Vyxy la arista que une xe y. Denotamos por G/a al grafo obtenido de G al contraer la arista aa un nuevo vértice va, que es adyacente a todos los vértices que eran adyacentes a xey. A cualquier grafo obtenido de G al contraer sucesivamente aristas se le llamará menor de G. Si Gcontiene un subgrafo Hque tiene como menor a un grafo G′, se dice que Gcontiene a G′como menor. Teorema 1.2.6 (Teorema de Kuratowski).Sea Gun grafo. Entonces Ges planar si y solo si Gno contiene a K5oK3,3como menores. Ejemplo 4. Utilizando el Teorema de Kuratowski, vamos a ver cómo contrayendo aristas llegamos a que un menor del grafo siguiente es K5, por lo que no es planar. Figura 1.7: Contracción de aristas para llegar a K5. Capítulo 2 Descomposición de Kn,m yKr,s,t en k−ciclos ”You don’t want to write down all the details. But the process of drawing something helps you somehow to stay connected” M. Mirzakhani Una partición de un grafo Gen subgrafos disjuntos por aristas G1, ..., Grtales que su unión es Gse llama descomposición de G. Cuando los subgrafos Gi son ciclos (para i= 1, .., r), se dice que es una descomposición en ciclos de G. Si además la longitud de todos los ciclos Gies k≥3, diremos que es una descomposición en k−ciclos. En este capítulo vamos a estudiar cuándo los grafos bipartitos y tripartitos completos admiten una descomposición en k−ciclos. Nos centraremos en la descomposición en 5−ciclos de grafos tripartitos completos, siguiendo el trabajo de Mahmoodian y Mirzakhani en Decomposition of Complete Tripartite Graphs Into 5−Cycles publicado en 1995 [18]. Gracias a la Nota 1, si Km,n admite descomposición en k−ciclos, dado que Km,n ∼ =Kn,m, tenemos que Kn,m también. Igual ocurre para Kr,s,t (y para cualquier grafo r−partito completo en general, r≥2). Aunque el artículo que vamos a seguir se centra en la descomposición en 5−ciclos de grafos tripartitos completos, comenzaremos viendo la descomposición de Kn,m en k−ciclos y la de Kr,s,t en 2k−ciclos y 3−ciclos. 2.1. Descomposición de Kn,m en k−ciclos Gracias a la caracterización de grafos bipartitos de la Proposición 1.2.3, basta estudiar el caso de ciclos pares. 19 20 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS Figura 2.1: Descomposición de K4,4en 4−ciclos. Teorema 2.1.1 (D. Sotteau [27]).El grafo Km,n admite una descomposición en 2k−ciclos si y solo si se verifican: 1. m≥k,n≥k. 2. mynson ambos pares. 3. 2k|mn. 2.2. Descomposición de Kr,s,t en k−ciclos Para el caso de los grafos tripartitos completos abordaremos algunos casos particulares. 2.2.1. Descomposición en 2k−ciclos Tenemos la siguiente condición necesaria para el caso de un grafo r−partito. Lema 2.2.1 (N.J. Cavenagh y E.J. Billington [8]).Sea G=Kn1,n2,...,nrcon n1≥n2≥... ≥nr. Si Gadmite una descomposición en 2k−ciclos, entonces se cumple: 1. 2kdivide a ||G||. 2. 2k≤ |G|. 3. k n−1 X i=1 ni≤ ||G||. 2.2. DESCOMPOSICIÓN DE Kr,s,t EN k−CICLOS 21 4. n X i=2 ni≥k. 5. El grado de todo vértice es par. 6. Los nison todos pares o todos impares. Si son todos impares, entonces res impar. Ejemplo 5. Podemos descomponer K4,4,2en 4−ciclos como sigue: Figura 2.2: Descomposición en 4−ciclos de K4,4,2. 2.2.2. Descomposición en 3−ciclos Vamos a estudiar algunos casos particulares de descomposición en ciclos de longitud 3, que servirán como herramienta para desarrollar la descomposición en 5−ciclos. Teorema 2.2.2 (N.J. Cavenagh [5]).El grafo Kr,r,r admite una descomposición en k−ciclos si y solo si: 1. |Kr,r,r| ≥ k. 2. ||Kr,r,r|| es múltiplo de k Proposición 2.2.3. El grafo Kr,s,t admite una descomposición en 3−ciclos si y solo si r=s=t. 22 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS Figura 2.3: Descomposición de K2,2,2en 3−ciclos. Demostración. Para la condición suficiente, basta considerar un cuadrado latino A= (aij)1≤i,j≤r. Tomando los ciclos {(i,j,aij) : 1≤i, j ≤r}, se tiene la descomposición. Veamos esto con más detalle. Vamos a considerar el siguiente cuadrado latino de tamaño r, al que añadimos además su fila y su columna. 1 2 3 ... r 1 1 2 3 ... r 2r1 2 ... r −1 3r−1r1... r −2 ... ... ... ... ... ... r2 3 4 ... 1 (2.1) Si ordenamos los vértices de V1, V2yV3, cada irepresenta los vértices de V1, cada jrepresenta los de V2y los aij los de V3. Con la notación {(i, j, aij) :1 ≤i, j ≤r}= ={(1,1,1),(2,1, r),(3,1, r −1), ..., (r, 1,2),(1,2,2),(2,2,1), ..., (r, r, 1)} indicamos que el ciclo lo componen el vértice ide V1, el vértice jde V2y el vértice aij de V3. Dado que es un cuadrado latino, nos aseguramos de que aparecen todos exactamente una vez. Por tanto vamos a tener todas las aristas exactamente una vez y tenemos la descomposición en 3−ciclos. 2.2. DESCOMPOSICIÓN DE Kr,s,t EN k−CICLOS 23 Para el recíproco, consideremos la partición de Kr,s,t = (V, A)como V= R∪S∪T, siendo r,sytel número de vértices de R,SyTrespectivamente. Por reducción al absurdo, supongamos sin pérdida de generalidad que t>s. Veamos dos casos. Si r=s, por el Teorema 2.2.2 sabemos que Kr,r,r admite una descomposición en 3−ciclos, pues |Kr,r,r|= 3ry||Kr,r,r|| = 3r2. Si tomamos Kr,r,r como subgrafo de Kr,r,t, la descomposición en 3−ciclos de Kr,r,t contiene a la de Kr,r,r. Para los demás t−rvértices de T, no vamos a poder encontrar ciclos, pues todas las aristas entre RySestán contenidas en algún 3−ciclo de la partición de Kr,r,r. Si s > r, utilizamos el mismo razonamiento: Kr,r,r admite una descomposición en 3−ciclos, y no vamos a encontrar más aristas de SaRpara los restantes s−rvértices de S. 2.2.3. Descomposición en 5−ciclos En esta sección vamos a estudiar con más detalle el caso de la descomposición en 5−ciclos de grafos tripartitos completos. Ejemplo 6. Veamos cómo podemos descomponer K4,2,2en 5−ciclos. Sean V1={a1, a2, a3, a4}, V2={b1, b1}, V3={c1, c1}, los subconjuntos de vértices de la partición. Una descomposición en 5−ciclos es (b1, a1, c2, a3, c1),(b2, a1, c1, a4, c2),(c2, a2, b2, a3, b1),(c1, a2, b1, a4, b2). Figura 2.4: Descomposición de K4,2,2en 5−ciclos. 24 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS Figura 2.5: Descomposición de K4,2,2en 5−ciclos viendo los ciclos por separado. Teorema 2.2.4 ([18]).Sea el grafo Kr,s,t con r≤s≤t. Si admite una descomposición en 5−ciclos entonces se cumple: 1. r, s y t son todos pares o todos impares. 2. 5|rs +rt +st. 3. t≤4rs/(r+s). Demostración. Si Kr,s,t = (V, A), sean R, S yTlos subconjuntos de Vde cardinal r, s ytrespectivamente. 1. Sea v1∈R. En cada ciclo, cada vértice es extremo de dos aristas, por lo que el grado de v1,s+t, debe ser par (pues la unión de las aristas de todos los ciclos son las aristas totales y no se repiten). Razonando igual para v2∈S yv3∈T, llegamos a que s+t, r +tyr+sson todos pares. Si ses par, entonces es de la forma s= 2k. Como s+tpar, 2k+tes par y por tanto ttambién es par. Igual para r+sy se llega a que todos son pares. 2.2. DESCOMPOSICIÓN DE Kr,s,t EN k−CICLOS 25 Si ses impar, entonces es de la forma s= 2k+ 1. Como s+tpar, 2k+1+tes par y por tanto necesariamente tes impar. Igual para r+s y se llega a que todos son impares. 2. Es inmediato ya que el número total de aristas es rs +rt +st y nos interesa hacer grupos de 5. 3. Sean A1, A2yA3las aristas que van de RaS, de RaTy de SaTrespectivamente y {c1, c2, c3, c4, c5}las aristas de un ciclo C5cualquiera de la descomposición. Entonces: Ningún Aj∩C5es vacío. Si suponemos que hay alguno vacío, por ejemplo A1∩C5, entonces tendríamos el ciclo C5de longitud impar entre los vértices de R∪SyT. Dado que el grafo KR∪S,T es subgrafo de KR,S,T y contiene al ciclo C5, tenemos contradicción con la Proposición 1.2.3 sobre la caracterización de grafos bipartitos. No hay más de 3 aristas en ningún Aj. Se deduce del hecho de que hay al menos una en cada uno. De estas dos afirmaciones y teniendo en cuenta que los conjuntos A1, A2 yA3tienen cardinal rs, rt yst respectivamente, se deducen las siguientes desigualdades: 2st/3(s+t)≤r≤4st/(s+t) 2rt/3(r+t)≤s≤4rt/(r+t) 2rs/3(r+s)≤t≤4rs/(r+s) Vemos con más detalle 2rs/3(r+s)≤t≤4rs/(r+s), ya que al ser r≤s≤t, se deducen las demás (y de hecho es la única que nos pide el teorema). La desigualdad 2rs/3(r+s)≤tse tiene si y solo si rs 3≤t(r+s) 2. Esto es, por cada grupo de 3aristas de A1, vamos a tener 2 aristas de A2y de A3. Por otra parte, la desigualdad t≤4rs/(r+s)se tiene si y solo si t(r+s) 4≤rs Esto es, por cada grupo de 4aristas de A2∪A3, vamos a necesitar al menos una arista de A1. 32 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS Demostración. De las condiciones necesarias del Teorema 2.2.4 deducimos que existen dos enteros positivos myntales que r= 3m+ 2nys=m+ 4n. Para ello, vemos primero que cualquier natural rlo podemos escribir como r= 3m+ 2n. Si res par, basta tomar n=r/2ym= 0. Si res impar, entonces es de la forma r= 2k+ 1 y tomamos en este caso n=k−1ym= 1. Para s, sabemos por las condiciones necesarias que 5|r2+ 2rs por lo que r2+ 2rs ≡0 (mod 5) Sustituyendo r= 3m+ 2n, llegamos a 4m2+ 4n2+ 2mn +ms + 4ns ≡0 (mod 5) Resolviendo en función de m, tenemos 3m≡3n+ 3s(mod 5) 2s≡3n+ 2m(mod 5) s≡4n+m(mod 5) De donde se deduce que existe un entero l≥0tal que s= 4n+m+ 5l De la condición s≤2r, tenemos 4n+m+ 5l≤6m+ 4n y por tanto l≤m. Dado que mpuede tomar el valor 0, necesariamente ldebe ser 0, y tenemos s= 4n+m. Se verifica además la condición de paridad: res par si y solo si mes par si y solo si ses par. Tomemos ahora la descomposición de los vértices de Kr,r,s como V=A∪ B∪Cdonde A={a1, ..., as}, B={b1, ..., br}, C={c1, ..., cr}. Los ciclos básicos que nos dan los autores en [18], en función de si rysson pares o impares, son: 2.2. DESCOMPOSICIÓN DE Kr,s,t EN k−CICLOS 33 Si rysson pares, los ciclos básicos son: (bi+2n−j, am+j, ci+1, am+2n+2j−i+2⌊i/2⌋, ci), (ci+3m+n+j, am+n+j, bi+1, am+2n+2j−i+2⌊i/2⌋, bi), (aj, bi, ci+3j, bi+2, ci+3j+1) donde i= 1, ..., r, j = 1, ..., m, tomando los índices de bycmódulo r. Si rysson impares, los ciclos básicos son: (bi+2n−j, am+j, ci+1, am+2n+2j−i+2⌊i/2⌋, ci), (br+2n−j, am+j, cr+1, am+n+j, cr) donde i= 1, ..., r −1, j = 1, ..., n; (ci+1, am+n+j, bi+n+2−j, am+2n+2j−i+2⌊i/2⌋, bi+n+1−j), (cr, am+2n+2j−1, br+n+1−j, am+2n+2j, br+n−j), (c1, am+2n+2j, br+n+2−j, am+j+n, br+n+1−j) donde i= 1, ..., r, j = 1, ..., m. De nuevo, tomando los índices de bycen módulo r. En el artículo podemos encontrar también algunos ejemplos de Kr,r,s en los que res múltiplo de 5,sno, y admiten descomposición en 5−ciclos. Ejemplo 8. Sea la descomposición de K5,5,3= (V, A)dada por V=R∪S∪T siendo R={a, b, c}, S ={0,1,2,3,4}, T ={5,6,7,8,9}. Una descomposición en 5−ciclos es, utilizando notación abreviada para facilitar la lectura: a0615 a1726 a2837 a3948 a4509 b5291 c5364 c6b70 b9c80 c3b47 b2c18. 34 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS Ejemplo 9. Sea la descomposición de K10,10,4= (V, A)dada por V=R∪S∪T siendo R={a, b, c, d}, S={0,1,2,3,4,5,6,7,8,9}, T={0,1,2,3,4,5,6,7,8,9}. Una descomposición en 5−ciclos es, utilizando una notación abreviada: a1122 a2314 a3143 a4215 a5261 a6336 a7760 a8608 b1624 b2537 b3405 b4653 b5566 b6478 b7291 b8102 c1709 c0186 c3993 c1579 c6954 c2788 c5832 d1948 d3094 d0596 d7047 d2083 d6758 d1730 d9289 d5482 0b9a0 9b0c8 7c7a9 4d5c4. Hasta ahora hemos visto ejemplos en los que el número de vértices de dos subconjuntos de la partición de los grafos tripartitos tenían el mismo cardinal. El último ejemplo de [18] nos da un caso distinto: K30,20,40 admite una descomposición en 5−ciclos. Veamos algunos resultados previos. Lema 2.2.12. Si Ka,b,b ,Ka,c,c yKb,c,c admiten una descomposición en 5−ciclos, entonces Ka+c,b+c,b+ctambién. Demostración. Sea la partición de Ka+c,b+c,b+c= (V, A)dada por V=R∪S∪T, y sean V1= {aprimeros vértices de R}, V2= {bprimeros vértices de S}, V3= {bprimeros vértices de T}, V4= {cúltimos vértices de R}, V5= {cúltimos vértices de S}, V6= {cúltimos vértices de T}. Basta considerar los ciclos de los subgrafos inducidos por V1∪V2∪V3, V1∪V5∪V6, 2.3. EL LEGADO 35 V4∪V2∪V6, V4∪V5∪V3. Estos subgrafos son, respectivamente, Ka,b,b ,Ka,c,c,Kc,b,c yKc,c,b. Todos ellos admiten descomposición en 5−ciclos por hipótesis, por lo que tenemos la descomposición de Ka+c,b+c,b+c. Corolario 2.2.13. Sean a, b ycenteros positivos. Entonces se tiene: 1. Si los grafos Ka,b,b yKc,b,b admiten una descomposición en 5−ciclos, entonces Ka+c,2b,2btambién. 2. Si los grafos Ka,b,b yKb,a,a admiten una descomposición en 5−ciclos, entonces Ka+b,2a,2btambién. Demostración. Son casos particulares del Lema 2.2.12 . Ejemplo 10. K30,20,40 admite una descomposición en 5−ciclos. Podemos escribir K30,20,40 como Ka+b,2a,2bsiendo a= 10,b= 20. Por el apartado 2 de la Proposición 2.2.13, basta ver que K10,20,20 yK20,10,10 admiten una descomposición en 5−ciclos. K10,20,20 admite descomposición en 5−ciclos ya que, por el primer apartado de la Proposición 2.2.13, basta ver que K6,10,10 yK4,10,10 la admite. •K6,10,10 se tiene por el Teorema 2.2.7 y el Ejemplo 8. •K4,10,10 se vio en el Ejemplo 9. K20,10,10 admite descomposición en 5−ciclos gracias al Corolario 2.2.9. 2.3. El legado Recordamos que el trabajo de Mirzakhani y Mahmoodian data de 1995. Posteriormente se han realizado diversos trabajos apoyados en él. En el año 2000, N.J. Cavenagh y E.J. Billington probaron algunos resultados sobre la descomposición en 2k−ciclos de grafos r−partitos, de los cuales destacamos los siguientes: Es fácil ver que las condiciones del Lema 2.2.1 son necesarias para la descomposición en 2k−ciclos de grafos r−partitos. ¿Son también suficientes? En [8] se da respuesta afirmativa a los casos k= 2,3y4. 36 CAPÍTULO 2. DESCOMPOSICIÓN DE Kn,m YKr,s,t EN k−CICLOS En [9], prueban el siguiente resultado como respuesta parcial a la Conjetura 2.2.5. Las condiciones del Teorema 2.2.4 son también suficientes si 2de los subconjuntos de vértices tienen el mismo cardinal o si rysson divisibles por 10. Dos años más tarde, Cavenagh prueba en [6] lo siguiente: Las condiciones del Teorema 2.2.4 son también suficientes si 2de los subconjuntos de vértices tienen el mismo cardinal o si los tres subconjuntos tienen cardinal par. El problema cuando los subconjuntos tenían cardinal impar seguía abierto. En 2011, de nuevo Cavenagh y Billington, prueban en [7] que si los tamaños de los subconjuntos de vértices son impares y parecidos, también son suficientes las condiciones. En concreto prueban: Sean r, s ytimpares los cardinales de los 3subconjuntos de vértices con r≤s≤t. Las condiciones del Teorema 2.2.4 son también suficientes si 100 ≤ r≤s≤t≤κr, con κ≈1,0806.Un año más tarde, en [17], Mahmoodian, Alipour y Mollaahmadi aumentan el valor de κa, aproximadamente, 5/3. En 2019, Abdolmaleki, Ilchi, Mahmoodian y Shabani prueban ([1]) que la Conjetura 2.2.5 es cierta si r, s ytverifican: r, s ytson múltiplos de 5 t+ 90 ≤4rs r+s t=s+ 10 Con respecto a otras nociones de descomposición en ciclos de grafos tripartitos, también han surgido más preguntas relacionadas. Por ejemplo, se dice que Kr,s,t tiene una {Ck, Pk}p,q−descomposición si admite una descomposición en p copias de Cky en qcopias de Pk, siendo CkyPkun ciclo y un camino de longitud krespectivamente. En octubre de 2023, Priyadarsini ([25]) estudió la descomposición de grafos tripartitos completos en ciclos y caminos de longitud kcuando k es primo. Es la referencia más reciente encontrada. Como hemos visto, la conjetura propuesta por Maryam Mirzakhani, así como las múltiples cuestiones derivadas de su trabajo, han dejado un legado monumental que continúa siendo objeto de estudio en la actualidad. El impacto de su obra resalta la importancia de su contribución al progreso científico y académico. Capítulo 3 Un grafo planar pequeño no 4−elegible ”The more I spent time on maths, the more excited I got” M. Mirzakhani En 1979, P. Erdös, A. L. Rubin y H. Taylor, conjeturaron en [14] que los grafos planares no eran necesariamente 4−elegibles. En 1993, Margit Voigt probó en [30] la conjetura con un grafo de 238 vértices. En este capítulo vamos a estudiar el artículo A small non-4−choosable planar graph [20], en el que Mirzakhani proporciona un ejemplo de un grafo planar que no es 4−elegible de tan solo 63 vértices. De hecho, el mismo ejemplo sirve para contestar a la pregunta planteada por Jensen y Stiebitz sobre si existe algún grafo 3-coloreable que no sea 4-elegible [15]. 3.1. Grafos coloreables por listas Vamos a comenzar definiendo los conceptos necesarios para el desarrollo del capítulo ([15]). Sean G= (V, A)un grafo y C={c1, c2,...cn}un conjunto de colores. Una coloración de Ges una aplicación P:V−→ Ctal que P(u)=P(v) para cada par de vértices adyacentes uyv. Si |P(V)|=k, se dice que Pes una k-coloración de G. Ges k-coloreable si existe una k-coloración de G. El número cromático de Ges el menor entero ktal que Ges k-coloreable, se denota χ(G). Una lista-coloración ocoloración por listas de Ges una coloración de Gen la que cada vértice vlleva un color tomado de una lista L(v)⊆C. El grafo G 37 38 CAPÍTULO 3. UN GRAFO PLANAR PEQUEÑO NO 4−ELEGIBLE es k-elegible ok-coloreable por listas si siempre existe una coloración por listas para cada lista L(v)con kcolores. El número lista-cromático de Ges el menor entero ktal que Ges k-elegible, se denota χl(G)y se dice que Ges k-lista-cromático ok-cromático por listas. Ejemplo 11. Veamos que el grafo bipartito completo K2,4no es 2-elegible. Consideremos la descomposición V=A∪Bcon A={a1, a2}yB={b1, b2, b3, b4}. Figura 3.1: K2,4y sus listas de colores. Para ver que no es 2-elegible, sean los colores {1,2,3,4}y L(a1) = {1,2}, L(a2) = {3,4}, L(b1) = {1,3}, L(b2) = {1,4}, L(b3) = {2,3}, L(b4) = {2,4}. Para a1tenemos dos opciones. Si elegimos el color 1, en b1debemos elegir el 3, ya que son adyacentes. En a2por tanto debemos elegir el 4y en b2nos quedamos sin opciones. Por otra parte, si elegimos en a1el 2, en b3debemos tomar el 3, en a2el 4, y en b4no tenemos opciones. Hemos encontrado listas L(v)de 2colores de forma que no existe una coloración por listas, por lo que K2,4no es 2- elegible. Sin embargo, sí es 3-elegible. Consideremos los pares siguientes, formados por los vértices de K2,4y sus listas de colores: (a1,{a11, a12, a13}),(a2,{a21, a22, a23}), (b1,{b11, b12, b13}),(b2,{b21, b22, b23}), (b3,{b31, b32, b33}),(b4,{b41, b42, b43}). Supongamos que en el vértice a1tomamos el color a11 y en el vértice a2el color a21. Si en la lista de b1están ambos colores, esto es, si b11 =a11 yb12 =a21 tomamos el color b13 para b1. Lo mismo hacemos para b2, b3yb4y tenemos la coloración por listas. 3.2. UN GRAFO NO 4−ELEGIBLE 39 Proposición 3.1.1. χl(G)≥χ(G) Demostración. Supongamos que χl(G) = k. Entonces existe una coloración por listas para cada lista L(v)con kcolores. En particular, si tomamos la misma lista L(v)para todos los vértices v∈V, tenemos una coloración de Gcon kcolores, por lo que χ(G)≤k. 3.2. Un grafo no 4−elegible Pasamos ahora a construir el grafo planar de 63 vértices que no es 4−elegible, según hace Mirzakhani en [20]. Para ello comenzamos viendo un lema. Figura 3.2: Grafo Hcon sus listas de colores. Figura 3.3: Subgrafos de Ha los que llamaremos cuadrados. 40 CAPÍTULO 3. UN GRAFO PLANAR PEQUEÑO NO 4−ELEGIBLE Lema 3.2.1 (Propiedad (P)).Sea Hel grafo de la Figura 3.2 con las listas de colores indicados en cada vértice. Llamemos T, R, B, L, C a los subgrafos de 5 vértices de arriba, derecha, abajo, izquierda y centro respectivamente, a los que llamaremos cuadrados. Se cumple, para cada cuadrado, que al menos dos vértices opuestos en él reciben el mismo color. Demostración. Tomemos un cuadrado cualquiera de los cinco, y sean V C,AI, AD,BD yBI los vértices del centro, arriba izquierda, arriba derecha, abajo derecha y abajo izquierda respectivamente. Como todos los cuadrados son de la forma de la Figura 3.3 para los valores de a, b, c, d en cada vértice según la tabla BTRLC a 1 2 1 4 3 b21324 c 3 4 4 1 2 d43231 basta probarlo para el cuadrado de la Figura 3.3. Vemos los distintos casos: 1. Si V C toma el valor ayAI el valor b, entonces AD debe tomar el valor d. Quedan dos posibilidades para BD:boc. Si toma el valor b, ya tenemos que AI yBD, que son vértices opuestos, toman el mismo valor. Si toma el valor c, entonces BI debe tomar el valor d, al igual que su opuesto AD. 2. Si V C toma el valor ayAI el valor c, entonces BI debe tomar el valor d. AD tiene dos opciones: bod. Si toma el valor dya lo tenemos. Si fuera b, entonces necesariamente BD debe tomar el valor cy lo tenemos también. Dado que los papeles de a, b, c ydson intercambiables, ya tenemos probada la propiedad (P). Proposición 3.2.2. Sea Hel grafo de la Figura 3.2 con las listas de colores indicados en cada vértice. Entonces Hno admite una coloración por listas con dichos colores. Demostración. Tenemos que |H|= 17 y que los vértices interiores tienen 4 colores y los exteriores 3. Vamos a continuar con la notación de la prueba del Lema 3.2.1. Consideramos a partir de ahora los vértices V Ci,AIi,ADi,BDiyBIicon i∈ {T, R, B, L, C}según el cuadrado al que pertenezcan. Podemos suponer además que en cualquier coloración por listas de H, en C,ADCes 1oAICes 2. Si por el contrario ni ADCes 1ni AICes 2, tenemos dos casos: Si ADCes 3, entonces usando (P)en T, o AITes 3, o ADTes 4, pero ninguno es posible. 3.2. UN GRAFO NO 4−ELEGIBLE 41 Si ADCes 4, entonces usando (P)en C, o BICes 4, o BDCes 3, pero ninguno es posible. Supongamos entonces que ADCes 1. Por (P)en R,BDCdebe ser 2(ya que BDRno puede ser 1). Usando ahora (P)en B,BICdebe ser 3. Por (P)en L, AICes 4. Tenemos por tanto contradicción utilizando (P)en C. Por último, si AICfuera 2, por (P)en Ltendríamos que BICes 1. Por (P)en Bentonces BDCes 4y, por (P)en R,ADCes 3, lo que vuelve a ser contradicción usando (P)en C. Para continuar con la construcción del grafo de 63 vértices, vamos a considerar ahora H1,H2,H3yH4cuatro copias disjuntas del grafo Hde la Proposición 3.2.2 tales que el color 4 + ise añade a la lista de cada vértice exterior de Hi, para i= 1,2,3,4. Añadimos también al grafo un vértice vcon la lista de colores {5,6,7,8}y lo unimos a todos los vértices exteriores de cada uno de los Hi. Figura 3.4: Grafo de 69 vértices con sus listas de colores, siendo {1,2,3,4} las listas de los vértices interiores de cada subgrafo Hi, i = 1,2,3,4. Además, faltan las aristas que unen a vcon cada uno de los vértices exteriores de los Hi. 48 CAPÍTULO 4. COLORACIONES DE SPERNER EN HIPERGRAFOS Llamaremos etiquetado a la aplicación lque a cada vértice de Vq,k le asocia un color, y diremos que el etiquetado es admisible Sperner si l(v)∈L(v)para cada vértice, es decir, si l(v) = jentonces vj>0. Diremos que una celda de dimensión kes arcoíris si sus vértices reciben los kcolores y que es monocromática si reciben todos el mismo color. Ejemplo 13. Veamos el caso particular en el que k= 3 yq= 5. Los vértices de H3,5son V3,5={b:b∈Z3, b ≥0 3 X i=1 bi= 5}= {(5,0,0),(4,1,0),(4,0,1),(3,2,0),(3,1,1),(3,0,2),(2,3,0), (2,2,1),(2,1,2),(2,0,3),(1,4,0),(1,3,1),(1,2,2),(1,1,3), (1,0,4),(0,5,0),(0,4,1),(0,3,2),(0,2,3),(0,1,4),(0,0,5)} y las hiperaristas A3,5={e(b) : b= (b1, b2, b3)∈Z3, b ≥0, 3 X i=1 bi= 4}= {{(5,0,0),(4,1,0),(4,0,1)},{(4,1,0),(3,2,0),(3,1,1)}, ... , {(1,0,4),(0,1,4),(0,0,5)}}. (a) ∆3,5. (b) V3,5. Figura 4.2: ∆3,5yV3,5vistos sobre R3. 4.2. HIPERGRAFOS Y ETIQUETADO ADMISIBLE SPERNER 49 Vamos a representar el hipergrafo H3,5sobre el plano x1+x2+x3= 5 junto con las listas de colores de sus vértices y las hiperaristas son los triángulos sombreados. Figura 4.3: H3,5junto con las listas de colores asociadas a sus vértices. Los vértices interiores llevan la lista {1,2,3}. Lema 4.2.2 (Lema de Sperner [28]).Para cualquier etiquetado admisible Sperner de los vértices de una subdivisión simplicial de ∆k, hay una celda arcoíris. Figura 4.4: Celdas arcoíris para dos etiquetados admisibles Sperner distintos. 50 CAPÍTULO 4. COLORACIONES DE SPERNER EN HIPERGRAFOS El resultado anterior nos sirve tan solo para subdivisiones simpliciales, pero Hk,q no lo es. Por ejemplo, en la Figura 4.4, podemos ver que para algunos etiquetados admisibles Sperner la celda arcoíris no se corresponde con ninguna arista. Pasamos a estudiar algunos resultados sobre Hk,q. Primero un lema. Lema 4.2.3. |Vk,q|=q+k−1 k−1 Demostración. Sabemos que Vk,q ={x= (x1, ...., xk)∈Zk:x≥0, k X i=1 xi=q}. Es decir, |Vk,q|es el número de posibles particiones de qcomo suma de kenteros positivos. Podemos escribir q=1+1+... + 1 ←→ (1,1, ..., 1) (4.1) y lo que buscamos es de cuántas formas podemos hacer kgrupos de unos. Consideramos el signo |como separación de estos grupos, al que llamaremos separador. Por ejemplo, si q= 10,k= 4, los puntos son (r1, r2, r3, r4)de forma que r1+r2+r3+r4= 10. Podemos ver los puntos de V4,10 como (3,2,0,5) ←→ (1,1,1,|,1,1,|,|,1,1,1,1,1) (1,1,1,7) ←→ (1,|,1,|,1,|,1,1,1,1,1,1,1) (10,0,0,0) ←→ (1,1,1,1,1,1,1,1,1,1,|,|,|) Dado que queremos hacer kgrupos, necesitamos k−1separadores. En total, tenemos q+k−1elementos: qunos y k−1separadores. Las posibles opciones de repartir los k−1separadores de la q+k−1−tupla son, efectivamente, q+k−1 k−1. Proposición 4.2.4. Sobre Hk,q, para cualquier etiquetado admisible Sperner l, hay al menos q+k−3 k−2hiperaristas que no son monocromáticas por l. Demostración. Dado que Vk,q ={x= (x1, ...., xk)∈Zk:x≥0, k X i=1 xi=q}, podemos escribir Ak,q ={e(b) : b= (b1, ..., bk)∈Zk, b ≥0, k X i=1 bi=q−1} ={e(b) : b∈Vk,q−1}. 4.2. HIPERGRAFOS Y ETIQUETADO ADMISIBLE SPERNER 51 Es decir, podemos identificar de forma biunívoca las hiperaristas de Ak,q con los vértices Vk,q−1. Como e(b) = {b+e1, b +e2, ..., b +ek}, dos hiperaristas e(b)ye(b′)comparten un vértice si y solo si b′+ej=b+eipara algún i, j ≤k, es decir, si byb′son vecinos como vértices de Vk,q−1(difieren en 1o−1en exactamente 2 coordenadas). Figura 4.5: V3,5(puntos negros) y V3,4(puntos azules). En la figura de la derecha aparece representado e(4,0,0) = {(5,0,0),(4,1,0),(4,0,1)}. Figura 4.6: Proyección de V3,5,V3,4ye(4,0,0) sobre el plano x1+x2+x3= 5. 52 CAPÍTULO 4. COLORACIONES DE SPERNER EN HIPERGRAFOS Vamos a considerar el etiquetado admisible Sperner l:Vk,q−1−→ {1,2, ..., k}. Para cada i∈ {1,2, ..., k}, vamos a denotar el conjunto de vértices de hiperaristas monocromáticas del color ipor Ci={b∈Vk,q−1:∀v∈e(b); l(v) = i} y definimos la aplicación ϕi:Ci−→ Vk,q−2 ϕi(b) = b−ei. Está bien definida pues si b∈Cientonces bi>0. Si no, e(b)contendría un vértice atal que ai= 0 y por tanto e(b)no sería monocromático de color i. Así, b−ei∈Zk +y(b−ei)·1=q−2siendo 1el vector cuyos elementos son todos 1. Por tanto, b−ei∈Vk,q−2. Además ϕies inyectiva para todo i= 1,2, ..., k. Si a, b ∈Ciyϕi(a) = ϕi(b) entonces a−ei=b−eiluego a=b. Figura 4.7: A la izquierda Hk,q con un etiquetado admisible Sperner. A la derecha, las aplicaciones ϕi. Las hiperaristas se representan con círculos vacíos. Las cruces representan Vk,q−2. Veamos que se tiene ϕi(Ci)∩ϕj(Cj) = ∅para todo i=j. Por reducción al absurdo, supongamos que existen b∈ϕi(Ci)yb′∈ϕj(Cj) tales que b−ei=b′−ej. Entonces a=b−ei=b′−ejes un elemento de las hiperaristas e(b)ye(b′), pero e(b)ye(b′)son monocromáticas de colores iyj respectivamente, por lo que hay contradicción ya que i=j. Tenemos entonces que |ϕi(Ci)|=|Ci|y por tanto el número de hiperaristas monocromáticas verifica 4.2. HIPERGRAFOS Y ETIQUETADO ADMISIBLE SPERNER 53 k X i=1 |Ci|= k X i=1 |ϕi(Ci)|≤|Vk,q−2|. Como habíamos identificado al principio de la prueba las hiperaristas de Ak,q con los vértices Vk,q−1, se tiene |Ak,q|=|Vk,q−1|. De aquí se deduce, gracias al Lema 4.2.3, que el número de hiperaristas no monocromáticas es |Ak,q| − k X i=1 |Ci| ≥ |Vk,q−1|−|Vk,q−2| =q+k−2 k−1−q+k−3 k−1=q+k−3 k−2. Nota 3. La cota dada por la Proposición 4.2.4 se alcanza, por ejemplo, con el etiquetado ”elección del primero”, esto es, se le asigna a cada vértice vel menor ital que vi>0. Así, todas las hiperaristas e(b)tales que bi>0son monocromáticas con el color 1. En el caso k= 3 yq= 5, tenemos 5+3−3 3−2=5 1= 5. Figura 4.8: En H3,5hay 5hiperaristas no monocromáticas. 54 CAPÍTULO 4. COLORACIONES DE SPERNER EN HIPERGRAFOS Como vimos en la Figura 4.4, podemos hacer un etiquetado de forma que cada triángulo de H3,5tenga a lo sumo 2colores, haciendo que la celda arcoíris no coincida con ninguna de las hiperaristas. De hecho, puede hacerse para cualquier H3,q. Siguiendo el mismo argumento, se puede asegurar que para Hk,q podemos encontrar un etiquetado de forma que cada celda contenga a lo sumo k−1colores. En [23] se plantea contestar a la siguiente pregunta: ¿cuál es el menor ctal que existe un etiquetado admisible Sperner con a lo sumo ccolores diferentes en cada hiperarista de Ak,q? Parte de la respuesta la da el siguiente resultado. Proposición 4.2.5 ([23]).Para cada k≥4y cada q≥k2, existe un etiquetado admisible Sperner de Hk,q = (Vk,q, Ak,q)tal que cada hiperarista de Ak,q contiene a lo sumo 4colores diferentes. 4.3. Una versión geométrica En esta sección veremos una variante geométrica de la Proposición 4.2.4. Para ello, vemos primero una versión geométrica del Lema 4.2.2 de Sperner. Lema 4.3.1 (Lema de Knaster-Kuratowski-Mazurkiewicz [16]).Sea un recubrimiento de cerrados A1, ..., Akdel símplice ∆kque cumple: Cada x∈∆kestá en un Aital que ti>0, siendo {t1, t2, ..., tk}las coordenadas baricéntricas de x. Entonces k T i=1 Ai=∅. La equivalencia del Lema 4.3.1 y del Lema 4.2.2 es un resultado bien conocido. Para la demostración, se puede ver por ejemplo [2] y [31]. De hecho, otro resultado equivalente a estos dos, del ámbito de la topología algebraica, es el siguiente. Teorema 4.3.2 (del punto fijo de Brouwer).Sea ∆un n−símplice en Rnde vértices x0, x1, ..., xny sea f: ∆ −→ ∆una aplicación continua. Entonces ftiene al menos un punto fijo, esto es, existe un x∈∆tal que f(x) = x. La prueba de la equivalencia de este teorema con el Lema 4.2.2 de Sperner puede consultarse en [29]. Para estudiar la versión geométrica de la Proposición 4.2.4, en lugar de la intersección de todos los conjuntos Aidel Lema 4.3.1, vamos a considerar la medida de las fronteras de pares de conjuntos Aique no tengan frontera vacía. Definición 4.3.3. Una partición admisible Sperner de ∆kes una k−tupla de conjuntos cerrados (A1, ..., Ak)tales que: 4.4. APLICACIONES DEL ETIQUETADO DE HIPERGRAFOS 55 k S i=1 Ai= ∆k. A1, ..., Akson disjuntos salvo en sus fronteras. ti>0para todo x∈Ai, siendo {t1, t2, ..., tk}las coordenadas baricéntricas de x. Llamaremos conjunto de separación a la unión de las fronteras S i=j (Ai∩Aj). Los autores prueban, en analogía con la Proposición 4.2.4, que la partición admisible Sperner de ∆kcuyo conjunto de separación tiene la menor medida es la partición de Voronoi. En esta, cada Aies el conjunto de puntos de ∆kque son más cercanos al vértice ei. Figura 4.9: Partición de Voronoi para ∆3. 4.4. Aplicaciones del etiquetado de hipergrafos Dedicamos la última sección a comentar brevemente algunas aplicaciones de los etiquetados de hipergrafos, que se pueden ver con más detalle en [22]. Diremos que un hipergrafo H(V, A)es ponderado si tiene asociada una función wdefinida sobre Allamada peso que a cada hiperarista le asocia un valor real. Los problemas que se plantean son los siguientes. 1. Etiquetado de Hipergrafos con Listas de Colores. Dado un hipergrafo H= (V, A)con pesos w(a),a∈Ay listas de colores L(v)⊆ {1,2, ..., k}, v∈V, encontrar un etiquetado l(v)∈L(v)para cada v∈Vque minimice el peso total de hiperaristas no monocromáticas. 56 CAPÍTULO 4. COLORACIONES DE SPERNER EN HIPERGRAFOS 2. Etiquetado de Hipergrafos. Dado un hipergrafo H= (V, A)con pesos en las aristas w(a)≥0y costos de asignación de vértices c(v, i)≥0, encontrar un etiquetado l:V→ {1,2, ..., k}que minimice el costo total de asignación más el peso total de las hiperaristas que reciben más de una etiqueta. min X v∈V c(v, l(v)) + X a∈A:|l[a]|>1 w(a). El segundo problema, propuesto por Chekuri y Ene [10], incluye al primero, considerando w(a)=1y costos de asignación en {0,∞}. De hecho, son problemas equivalentes bajo ciertas condiciones (resultado atribuido a Julia Chuzhoy por [11]). La Proposición 4.2.4 ayuda a aproximar la complejidad computacional de resolver estos problemas mediante algoritmos. Además, se considera en [22] la siguiente extensión del problema de etiquetado de hipergrafos con listas de colores. Dado un hipergrafo H= (V, A)con listas de colores L(v)⊆ {1,2, ..., k}, v∈V, y un parámetro j≥2, encontrar un etiquetado l(v)∈L(v)que minimice el número de hiperaristas que reciben al menos jetiquetas distintas. En particular, el problema de etiquetado de hipergrafos con listas de colores es el caso de j= 2. Si j=k, entonces el objetivo es minimizar el número de hiperaristas arcoíris. Bibliografía [1] M. Abdolmaleki, S. G. Ilchi, E. S. Mahmoodian y M . A. Shabani, On decomposing complete tripartite graphs into 5-cycles, arXiv preprint ar- Xiv:1907.06187, 2019. [2] P.S. Aleksandrov, Combinatorial topology (Vol. 1), Courier Corporation, 1998. [3] K.K. Anuradha y L. Parekh, Maryam Mizakhani: The Mathematical Genius, Éclat, A Mathematics Journal, Vol. 11, 2020, 95-102. [4] M. Borowiecki, Research problem 172, Discrete Math. 121, 1993, 235-237. [5] N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australasian J. Combinatorics 18, 1998, 193-200. [6] N.J. Cavenagh, Further decompositions of complete tripartite graphs into 5-cycles, Discrete mathematics, 256(1-2), 2002, 55-81. [7] N.J. Cavenagh y E.J. Billington, Decomposing complete tripartite graphs into 5-cycles when the partite sets have similar size, Aequationes mathematicae, 82, 2011, 277-289. [8] N.J. Cavenagh y E.J. Billington, Decompositions of complete multipartite graphs into cycles of even length, Graphs and Combinatorics 16, 2000, 49–65. [9] N.J. Cavenagh y E.J. Billington, On decomposing complete tripartite graphs into 5-cycles, Australasian Journal of Combinatorics, 22, 2000, 41-62. [10] C. Chekuri y A. Ene, Submodular cost allocation problem and applications Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, Proceedings, Part I 38. Springer Berlin Heidelberg, 2011, 354-366. 57