Etiquetados guay de grafos (para publicar y así no perecer)

Una de las alegrías de estar en el comité editorial de una revista de matemáticas de medio pelo es que a veces tengo que encargarme de algún artículo sobre un tema muy específico que me produce una típica reacción WTF: “¿Pero cómo puede ser que alguien trabaje en esto?”. Por suerte, enseguida recuerdo que sólo puede tirar la piedra quien está libre de pecado y lo miro sin prejuicios, y al final termino aprendiendo algo. Esta vez ha sido un artículo sobre una variante de grafos “cordiales”. No había oído hablar en mi vida de ellos y para mi gusto dan para algunos problemas interesantes de competición matemática y poco más. Y en cambio, una búsqueda de las palabras cordial graph en el Google Académico me ha dado 17.400 resultados. Soy un inculto.

El origen de los grafos cordiales está en un problema con un cierto pedigrí en teoría de grafos relacionado con los grafos llamados “gráciles” (graceful en inglés; en castellano los traducen como “graciosos”, por ejemplo en una Matiaventura, pero no creo que sea el sentido original del término). Un grafo no dirigido conexo G=(V,E) con m aristas es grácil cuando admite un etiquetado inyectivo de sus vértices f:V->{0,…,m} tal que si asignamos a cada arista e={u,v} la diferencia en valor absoluto de las etiquetas de sus extremos, |f(u)-f(v)|, obtenemos una biyección entre E y {1,…,m}. En este caso, se dice que el etiquetado f es grácil. Son grafos gráciles los caminos, las estrellas, las orugas, los grafos bipartitos completos, las ruedas y muchos más. Un problema abierto en teoría de grafos con mucho interés es la conjetura de que todos los árboles son gráciles.

El interés de esta conjetura proviene de la famosa Conjetura de G. Ringel de 1963: Dados un grafo completo K de 2n+1 nodos y un árbol T de n+1 nodos, siempre se puede recubrir K con 2n+1 copias de T. Esta conjetura tampoco está resuelta, pero es fácil demostrarla para árboles T gráciles. Si etiquetamos grácilmente los nodos de T con {0,…,n} y etiquetamos los nodos de K con {0,…,2n}, podemos recubrir K con los árboles Tk=(Vk,Ek), k=0,…,2n, donde cada Tk se obtiene sumando k módulo 2n+1 a los nodos de T. Por lo tanto, si todos los árboles son gráciles, la conjetura queda demostrada.

El problema de la existencia de etiquetados gráciles es interesante, e incluso parece ser que tiene aplicaciones en redes de comunicaciones. Y abrió el camino al estudio de otros tipos de etiquetados con propiedades definidas de manera similar. Por ejemplo, en 1980, R. Graham y N. Sloane definieron que un grafo  G=(V,E) con m aristas es armonioso cuando admite un etiquetado inyectivo V->Zm tal que si asignamos a cada arista la suma módulo m de las etiquetas de sus extremos obtenemos una biyección entre E y Zm. Su motivación, legítima, fue el estudio de bases aditivas modulares de Zm. Nada que objetar.

Y llegamos a los grafos cordiales, introducidos en 1987 por I. Cahit. Un grafo G es cordial cuando  admite un etiquetado f:V->{0,1} tal que

  • El número de nodos etiquetados 0 y el de los etiquetados 1 se diferencian en como máximo una unidad
  • Si etiquetamos cada arista e=(u,v) con 0 si f(u)= f(v)  y con 1 en caso contrario  (equivalentemente, con el valor |f(u)-f(v)|, que nos remite a los grafos gráciles, o también con el valor f(u)+f(v) módulo 2, que nos remite a los grafos armoniosos), resulta que el número de aristas etiquetadas 0 y el de las etiquetadas 1 también se diferencian en como máximo una unidad

¿Motivación de esta definición? En palabras de Cahit, “la imposibilidad hasta el momento de demostrar la existencia conjeturada de etiquetados [gráciles o armoniosos] de todos los árboles.” Y es que resulta que es fácil demostrar por inducción completa que todo árbol es cordial, aunque él mismo reconoce que esto no sirve para nada en el contexto de la conjetura de Ringel.

Y luego ya han llegado las generalizaciones por el puro placer de generalizar, del estilo de “un grafo es X-cordial cuando admite un cierto etiquetado f de los nodos tal que si asignamos a cada arista e={u,v} el valor 1 si existe cierta relación X entre  f(u) y f(v), y 0 en caso contrario, resulta que el número de aristas etiquetadas 0 y el de las etiquetadas 1 se diferencian en como máximo una unidad”. Poned la relación X que queráis, y ya tenéis una definición para la que demostrar si algunos grafos famosos la cumplen o no, y publicar un artículo en alguna revista con índice de impacto y aumentar el currículum.

En concreto, en los grafos primo-cordiales del artículo que ha motivado este comentario, el etiquetado de los nodos se toma biyectivo en {1,…,|V|} y un arco e={u,v} se etiqueta 1 si  mcd(f(u),f(v))=1 y 0 en caso contrario. ¿Interés? ¿Qué queréis que os diga? Como problema de competición matemática, puede tener su gracia pedir si tal grafo famoso es primo-cordial o no, pero no creo que tenga mucho más. Y en cambio, 41 resultados en la búsqueda de las palabras “prime cordial” graph en el Google Académico. Publica o perece en estado puro.

Este artículo participa en la Edición4.1231056256 del Carnaval de Matemáticas, organizado por Cuentos Cuánticos.

Advertisements

El truco de las 5 permutaciones

El miércoles que viene en el Club Diario de Mallorca organizamos con algunos amigos una sesión coral de magia matemática, para inaugurar la celebración del año del centenario de Martin Gardner. Para calentar motores, os voy a explicar uno de mis trucos favoritos, que no haré allí porque es demasiado matemático y hemos anunciado que el sarao será “para todos los públicos”. La verdad es que no sé de dónde lo he sacado, aunque estoy seguro de que no lo he inventado yo, lo recordaría. Mirando ficheros en mi Mac, veo que lo propuse por primera vez en el 2005 en una asignatura de “Laboratorio de Matemáticas” de primer curso de Matemáticas para que los alumnos descubrieran cómo se hacía y lo demostraran, pero no anoté su origen.

El truco es como sigue: le pido a un voluntario que piense un número de 3 cifras, abc. A continuación que sume (con la calculadora del móvil) los otros cinco números que se obtienen permutando estas cifras, acb+bca+bac+cab+cba. Finalmente, le pido que me diga el resultado de esta suma, y yo me concentro y adivino el número que ha pensado al principio.

Cómo funciona? Pensadlo un rato. Os dejo el truco en un comentario, para que no lo leáis automáticamente. De hecho, es un caso particular del resultado siguiente.

“Sean n un número natural y \mathbb{N}_n el conjunto de los números naturales de n cifras. Para cada m\in\mathbb{N}_n, sea S_m la suma de los n!-1 números que se obtienen permutando sus cifras. La aplicación de \mathbb{N}_n en \mathbb{N} que envía m a S_m es inyectiva.”

Hola. Me llamo Francis, y soy un adicto

galton

—Hola. Me llamo Francis y soy un adicto.

—¡Bienvenido, Francis!

—Mi adicción son las estadísticas. Cuando veo algo que se puede contar, lo tengo que contar.

—¡Te entendemos, Francis!
—Lo peor es cuando me preguntan algo que se pueda responder con una estadística. Por ejemplo, el otro día Lady Ashcroft me pidió si creía que las propiedades de la Iglesia Católica que fueron expropiadas en tiempos de Enrique VIII estaban malditas. Según me contó, suele pasar que cuando alguien compra una de estas propiedades, su primogénito muera antes de poder heredarla, lo que ya ha supuesto la desaparición de varios linajes familiares. Yo nunca había oído hablar de esa superstición, pero según parece, está muy extendida entre los católicos. Naturalmente, no pude resistir la tentación de recoger unos cuantos datos y analizarlos para poder responder a Lady Ashcroft. Así que, con la ayuda del Reverendo Harvey Bloom, un anticuario experto en transmisiones de propiedades, recogí información sobre los sucesivos dueños de 245 propiedades entre los años 1800 y 1900.
—¿Y qué encontraste, Francis?
Imatge

—En primer lugar, calculé el porcentaje de dueños de cada tipo de propiedad que han sido primogénitos, y son muy parecidos: en los dos casos un poco más de la mitad de las transmisiones de la propiedad han sido por herencia al primer hijo. Por lo tanto, no hay más defunciones prematuras entre los primogénitos de los dueños de propiedades expropiadas.

Imatge

» A continuación, calculé la duración media de la titularidad de los dueños de cada tipo de propiedad, y tampoco encontré diferencia. Por lo tanto, no hay evidencia de que los amos de propiedades expropiadas disfruten menos tiempo de sus propiedades.
»En resumen, estos números tendrían que convencer incluso al más crédulo que la maldición no existe.
—¡Qué descanso, Francis!
Imatge

—Para ser honestos, sí que detecté una anomalía curiosa. Las propiedades expropiadas se transmiten más a menudo por venta que las no expropiadas. Pero creo que hay una explicación plausible para este hecho queno tiene nada que ver con maldiciones. Las abadías y conventos no tienen una distribución de habitaciones conveniente para vivir, y suelen estar construidos en lugares poco salubres. Por otro lado, su romanticismo los hace muy atractivos. Así que cuando alguien hereda una de estas propiedades, si no se siente ligado emocionalmente a ella y sabe lo incómoda que es, es muy normal que esté dispuesto a venderla a alguien que esté dispuesto a pagar por un lugar pintoresco para vivir o pasar las vacaciones.

» Pero esto es pura especulación, lo tendría que investigar más. (Duda) Sí, sí que lo tendría que hacer. (Saca el móvil, marca y se lo pone a la oreja. Al público) Perdonadme. (Al móvil, mientras sale, va bajando el tono de voz) ¿Reverendo Bloom? Hola, soy Francis Galton.  Vuelvo a necesitar sus conocimientos. ¿Se acuerda del tema de las propiedades expropiadas? Pues he pensado que…

—¡Adiós, Francis! ¡Te queremos, Francis!

Un truco de magia olímpico

—Para mi próximo truco, necesito a tres voluntarios del público ¿Quién quiere salir? Tú, tú y tú, ¿queréis subir, por favor? Muchas gracias. Bienvenidas, ¿cómo os llamáis?

—Aina

—Bel

—Cati

—Encantado, Aina, Bel, Cati. Para empezar el truco necesito que tú,  Cati,  escojas un número par ni demasiado grande ni demasiado pequeño. Un número que esté bien.

—Mmmm… 18?

—Perfecto. Ahora escribe en la pizarra los números 1, 2, 3 y así sucesivamente hasta llegar al 18. Yo mientras escribiré un número en un papel y te lo daré cuando acabes. ¿Ya estás? Muy bien. Ten, guárdame este papel y no lo muestres hasta el final. ¡Y no lo mires, chismosa!

”Ahora, Aina, tú coge el rotulador azul y tú, Bel, el rojo Tenéis que marcar, por turnos, números de la lista que ha escrito Cati, los que queráis, desordenados, hasta que todos estén marcados. ¿Empiezas tú, Aina? Muy bien, ahora tú Bel. Perfecto, tú Aina otra vez. Bien, continuad.

”¿Ya estáis? ¿No queda ninguno sin marcar? Muy bien. Ahora Bel, por favor, escribe debajo de los números de Aina tus números, pero en el orden inverso. Es decir, debajo del primero de Aina escribe tu último número, debajo de su segundo número, tu penúltimo número. Y así sucesivamente.

”¿Ya está? Perfecto. Ahora, en cada una de estas parejas de números que has formado, escritos uno debajo del otro, resta el menor del mayor, de manera que el resultado sea siempre positivo. Vosotras, Aina y Cati, id vigilando que no se equivoque, ¿vale?

”¿Ya has terminado? Qué, ¿estás cansada de calcular? Pues Aina, ahora te toca a tí. Por favor, suma los resultados de estas nueve restas. Y vosotras, Bel y Cati, vigilad que no se equivoque.

”¿Ya está? ¿No se ha equivocado? ¿Te da 81? ¿Estáis seguras las tres? Bien, Cati, por favor, ¿muestras el número que he escrito en el papel que te he dado al comienzo? ¿Qué pone? ¡81! ¡Coinciden!

numeros

Os explico el truco. ¿Os habéis fijado que 81 es 9 al cuadrado, y que el número que ha elegido Cati al principio ha sido 9 por 2? No es casualidad. Si repetís este procedimiento con la lista de los números dels 1 al 2n, para cualquier número natural n, el resultado final siempre será el mismo, independientemente de los números que elijáis cada una: n al cuadrado. ¿Lo sabríais demostrar? Este problema fue propuesto en la fase final de la Olimpiada Matemática de la URSS de 1985.

¡Aviso de spoiler! Una indicación: Demostrad primero que en cada pareja de números que habéis restado, el menor siempre pertenece a 1,2,…,n y el mayor a n+1,n+2,…,2n. (Suponed que no y llegad a una contradicción,). A partir de aquí, terminar la demostración ya es coser y cantar.

Año nuevo, blog nuevo

A los 62 años, G. H. Hardy abría su “Autojustificación de un matemático” de esta manera: “Para un matemático profesional, escribir sobre matemáticas es una experiencia melancólica. La función de un matemático es hacer cosas, demostrar teoremas nuevos, aumentar el conocimiento matemático, en lugar de hablar sobre lo que él u otros matemáticos han hecho.” (La traducción es mía. No encuentro mi ejemplar de Ariel quincenal, demasiadas mudanzas desde que lo compré hace más de 30 años). Bueno, yo soy una persona tirando a melancólica, pero nunca me ha parecido melancólico escribir sobre matemáticas. También es verdad que no me parezco en lo más mínimo a Hardy, por suerte y por desgracia.

Para inaugurar el año del centenario de Martin Gardner, un problemilla. En la operación

FELIZ+AÑO-NUEVO=2014

cada letra representa una cifra, de manera que letras diferentes representan cifras diferentes y letras iguales, salvo acentos, representan cifras iguales (vaya, N=Ñ). Encontrad los posibles valores de las letras. ¿Cuántas soluciones hay, salvo el intercambio natural A<–>L?