Gráficas: teoría, aplicaciones e interacciones.

Resumen: Este curso es una introducción a la teoría de gráficas. Presentaremos nociones y resultados clásicos de la teoría y daremos diferentes aplicaciones.
Los resultados que discutiremos en este curso requieren un conocimiento modesto en matemáticas (si es necesario, para la comprensión del curso, recordaremos algunos conocimientos de base).

Complejidad de comunicación: algunas aplicaciones.

Resumen: La pregunta central de la teoría de la complejidad es la siguiente: ¿Cuánto recurso computacional se requiere para resolver un problema dado?
La naturaleza del recurso determina el tipo de complejidad que se está midiendo. Las medidas más comunes son el tiempo y el espacio. Sin embargo, el recurso que se considerará en este curso es el de comunicación.
Aquí, la pregunta específica es la siguiente: ¿Cuánta información deben intercambiar distintas partes de un sistema para poder juntos ejecutar cierta tarea?
Los resultados en complejidad comunicacional son traspasables, de modo más o menos directo, a problemas de comunicación. En efecto, las técnicas desarrolladas en este curso permitirán acotar, por ejemplo, el tiempo requerido por una red de procesadores para calcular cierta función cuyo input está distribuido.
Sin embargo, también son muy interesantes las aplicaciones de resultados en complejidad comunicacional a problemas en los cuales la comunicación no es explícita. En particular, en este curso se abordará el problema consistente en encontrar, para algunas funciones booleanas, la profundidad mínima de circuitos que las calculan.
El curso se hará en castellano. Lo único que se espera de los alumnos es un mínimo de madurez matemática. Sin embargo, no hay requisitos específicos.

Introducción a la programación, con un enfoque aplicado a la combinatoria.

Es necesario llevar su propia computadora portátil a este curso.
Resumen: En este curso daremos una introducción a la programación utilizando un paradigma de programación denominado "programación funcional". En este paradigma, la herramienta principal para expresar un programa es la recursividad.
De esta forma, un programa es una colección de funciones, definidas en términos de si mismas o de otras funciones, y ejecutar un programa corresponde a evaluar una función sobre un argumento concreto. Este paradigma permite que muchos problemas de combinatoria se expresen de manera muy natural y de forma muy concisa.
Algunos de los problemas que aprenderemos a resolver en este curso incluyen, entre otros:

  • Generación de todos los conjuntos de un conjunto dado.
  • Generación eficiente de todos los subconjuntos de tamaño k para un conjunto S, dados k y S.
  • Generación de permutaciones de una secuencia ordenada dada.
  • Generación de particiones en k partes de un conjunto S, para k y S dados.
  • Cálculo de invariantes de una gráfica, incluyendo el número cromático, número de independencia, número de clan, etc.
Cabe aclarar que existen excelentes paquetes de software que pueden hacer lo anterior. Pero en este curso nuestro objetivo es aprender a programar nuestras propias soluciones, no a utilizar las soluciones ya hechas por terceros.
El único prerrequisito para el curso es tener madurez matemática y habilidad para usar la inducción matemática. No hace falta tener experiencia en programación. Y puesto que el paradigma que utilizaremos no es el convencional, puede ser incluso recomendable no tener esa experiencia.

Coloraciones en digráficas

Resumen: Durante las cuatro sesiones que dura el curso el estudiante va a conocer algunas propiedades y resultados para dos coloraciones particulares en digráficas: el número dicromático y la inconexión acíclica, ambas fueron definidas por el matemático mexicano Víctor Neumann-Lara. Revisaremos la demostración de algunas propiedades, adem ́as de presentar y/o buscar ejemplos y contraejemplos que ayudara ́n a motivar y comprender los resultados conocidos así como los problemas abiertos que se presentarán en el curso.
En cada sesión habrá un tiempo para que el estudiante explore por su cuenta algún tema o resultado y en cada sesión se presentarán problemas abiertos.
La primera sesión: Antes de iniciar voy a establecer la punta de partida, según el grupo. Voy a motivar la definición de las dos coloraciones con la coloración del número cromático en gráficas. Entre todos revisaremos algunas propiedades en las digráficas que difieren de las propiedades en gráficas, para que comprendan la diferencia entre trabajar con digráficas y con digráficas. La segunda sesión: Trabajaremos únicamente con el número dicromático. Para empezar, calculamos el número dicromático para algunas digráficas de orden pequeño. Después revisaremos la relación entre el número dicromático y la estructura acíclica en digráficas y encontraremos cotas superiores para algunas familias particulares.
La tercera sesión: Trabajaremos únicamente con la inconexión acíclica, Para empezar vamos calcular inconexióon acíclica para algunas familias de digráficas. Después veremos algunas estructuras de dominaci ́ón que nos ayuda a acotar la inconexión acíclica y para terminar revisaremos su relación con otras invariantes en digráficas.
La cuarta sesión: Trabajaremos con las dos coloraciones y revisaremos la relación entre ellas. Al final, haremos una recopilaci ́on de los problemas abiertos propuestos en el curso y completaremos la lista en caso de faltar alguno.