Inicio - Novedades & actividades - Novedades - Departamento de Ingeniería Matemática gradúa a un nuevo doctor

Departamento de Ingeniería Matemática gradúa a un nuevo doctor

Flavio Guíñez realizó su tesis con el profesor Martín Matamala.

Tras defender con éxito su examen de tesis, el pasado 7 de diciembre, Flavio Guíñez se convirtió en el nuevo en Doctor en Ciencias, mención Modelación Matemática del DIM. Su investigación estuvo guiada por el profesor Martín Matamala.

Tras defender con éxito su examen de tesis, el pasado 7 de diciembre, Flavio Guíñez se convirtió en el nuevo en Doctor en Ciencias, mención Modelación Matemática del DIM. Su investigación estuvo guiada por el profesor Martín Matamala.

Con su tesis titulada: “Realizaciones disjuntas de secuencias de grado en grafos con algunas aplicaciones a tomografías discretas”, Flavio Guíñez obtuvo el máximo grado académico que otorga la Universidad de Chile.

Aunque califica como “largo y agotador” su paso por el programa doctoral del DIM, Flavio también reconoce que fue una experiencia muy positiva. “El proceso es larguísimo, con altibajos todo el tiempo, con momentos en que te no sale nada y otros en que te das cuenta que vas progresando. Pero pasar por este proceso es la única forma de aprender el oficio”.

“El departamento ha generado un ambiente que estimula el trabajo por sobre la genialidad. Esto es súper importante cuando se hace una tesis. Otro aspecto importante tiene que ver con las facilidades para hacer estadías y/o cotutelas en el extranjero; la experiencia de trabajar y vivir en otro país ayuda mucho en las futuras colaboraciones”, comentó.

Durante la realización de su doctorado, Flavio y su profesor guía, en conjunto con y el investigador Christoph Dürr del Ecole Polytechnique de Francia, recibieron el premio al Mejor Paper en la última versión de la principal conferencia Europea en algorítmica, efectuada en Copenhagen, Dinamarca, en septiembre de este año.

La decisión de realizar su postgrado en el DIM estuvo marcada por varios factores. “El DIM ofrece un ambiente de trabajo que está por sobre la media del país, además en el que en el último año de la licenciatura tomé un curso de grafos con Martín Matamala, y a partir de eso, decidí que ese era el tema que quería trabajar”, agregó.

Sobre el respaldo que brinda el Centro de Modelameinto Matemático al programa doctoral del DIM, Flavio cree que es muy trascendental. “Sobre todo en cuanto al contacto con investigadores extranjeros y al prestigio que tiene tanto en el país, como afuera. Además es un apoyo financiero importante para organizar y costear actividades”.

A pocos días de haber defendido con éxito su tesis, Flavio le da las gracias a quienes hicieron posible la realización de su doctorado. “Me gustaría agradecerle a Martin Matamala, por la confianza y optimismo, hasta en los momentos complicados de poca creación, por su capacidad de trabajo y por su constante apoyo. También me gustaría agradecer a toda la comunidad del DIM, profesores, compañeros de doctorado, los alumnos de la carrera, y especialmente a los funcionarios, que son impresionantemente eficientes a la hora de solucionar los problemas, lo que no es una constante, inclusive en las mejores universidades e institutos”, concluyó.

Resumen de la Tesis

Realización disjuntas de secuen cias de grado en grafos con algunas aplicaciones a tomografía discreta

Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para construirla cuando existe. Por otro lado, Chrobak y Dürr mostraron que para k mayor o igual a 4 el problema es NP-difícil.

La equivalencia natural entre una grilla y un grafo bipartito completo muestra que el caso k=3 corresponde a la restricción a esta clase de grafos del siguiente problema:

Dados un grafo G y funciones enteras b¹ y b² en V(G), ¿existen b¹ y b²-factores de G que sean disjuntos?

En esta tesis introducimos una nueva condición para este problema, la que resulta ser suficiente cuando G es un grafo bipartito completo y la diferencia entre el máximo y mínimo valor de b¹ + b² es a los más dos. La demostración de este resultado se basa en un algoritmo polinomial que encuentra dos factores disjuntos o bien un certificado de inexistencia.

Junto con esto, la contribución principal de esta tesis es la prueba de NP-dificultad del problema para grafos bipartitos completos cuando no se impone ninguna condición a b¹ y b². Esto resuelve el caso k = 3 del mencionado problema en Tomografía Discreta, lo que cierra el problema para todos los valores de k. Como corolario obtenemos además que el problema para grafos completos es también NP-difícil.

Para el problema de unicidad, caracterizamos las transformaciones que preservan las funciones b¹ y b² cuando G es un grafo bipartito. Este resultado es luego utilizado para probar la existencia de invariantes para algunas 3-coloraciones de la grilla.

Además, estudiamos la generalización del problema de k-coloración a la reconstrucción de embaldosados de la grilla usando como baldosas k rectángulos de diferentes tamaños. Para este problema, presentamos demostraciones que abarcan y extienden todos los resultados previos conocidos.

Para finalizar, se prueba la existencia de un núcleo cuadrático para una generalización del problema de Vertex Cover parametrizado por el tamaño requerido del conjunto solución.

fcfm
Departamento de Ingeniería Matemática, Universidad de Chile.
Facultad de Ciencias Físicas y Matemáticas.
Blanco Encalada 2120, piso 5. - Casilla 170-3. Correo 3. - Santiago, CHILE.
Fono: (562) 671 1530. Fax: (562) 688 3821 - Email: contacto [at] dim.uchile.cl