With his thesis tittled: “Divided implementation of sequences of degree in graphs with some applications to discreet tomography “, Flavio Guíñez obtained the maximum academic degree the Universidad de Chile grants.
Though it was considers as” long and exhausting” his time through the doctoral program of the DIM, Flavio also admits it was a very positive experience. “The process is the longest, with ups and downs all the time, with moments where inspiration gone but then comes again and I realize you are progressing. But the only way to learn about the trade is passing for this process.”
“DIM has generated an environment that stimulates the work than brilliant ideas. This is too much important when a thesis is done. Another important aspect show the facilities to do stays and / or cotutels abroad; the experience of working and living in another country helps very much in the future collaborations,” he commented.
During the execution of his doctorate, Flavio and his guide teacher, and the investigator Christoph Dürr del Ecole Polytechnique of France, received the prize to the Best Paper in the last version of the principal European conference in algorithmic, carried out in Copenhagen, Denmark, in September of this year.
The decision to start his post degree in the DIM was marked by several factors. “DIM offers an environment of work which is on the average of the country, in addition in the last year of the degree I took a course of graphs with Martin Matamala, and since then, I decided that would be the topic that wanted to work,” he added.
About the support offers by the Center for the Mathematical Modeling to the doctoral program of the DIM, Flavio believes that it is transcendental. “Especially as much the contact with foreign researchers and the prestige that has in the country, as out. In addition it is a financial important support to organize and to finance activities.”
Few days of have defended successfully his thesis, Flavio gives thanks to whom made possible the execution of his doctorate. “I would like to thank to Martin Matamala, for the confidence and optimism, even in the complicated moments of few creation, for his capacity of work and for his constant support. Also I would like to be grateful to the whole community of the DIM, teachers, workmates of doctorate, the students of the career, and specially the staff members, who are impressively efficient at the moment of solve a problem, which is not a constant feature, inclusive in the best universities and institutes, ” concluded.
| Summary of the Thesis Divided implementation of sequences of degree in graphs with some applications to discreet tomography This thesis is about a problem of reconstruction in Discreet Tomographyin which is been interested by coloring using k colors, in such a waythat for every line and column, the number of cells of every color hada certain predeterminated given value. For k = 2, a classic result ofthe Combinatorial analysis delivers a necessary and pass condition forthe existence of such a coloration together with an algorithmpolinomial to be construct when it exists. On the other hand, Chrobakand Dürr showed that for k major or equal to 4 the problem isNP-difficult. The natural equivalence between a grid and a bipartite complete graphshows in the case k=3 fit the restriction to this class of graphs ofthe following problem: Giving a grafo G and entire functions b ¹ and b ² in V (G), Do they exist b ¹ and b ²-factors of G that are divided? In this thesis we introduce a new condition for this problem, whichturns out to be pass when G is a bipartite complete graph and thedifference between the maximum and minimal value of b ¹ + b ² is tomore two. The proof of this result bases on an algorithm polinomialthat finds two factors divided or a certificate of nonexistence. Besides, the principal contribution of this thesis is the proof ofNP-difficulty of the problem for bipartite complete graphs when nocondition is imposed to b ¹ and b ². This solves the case k = 3 of thementioned problem in Discreet Tomography, which closes the problem forall the values of k. As a consequence we obtain besides the fact thatthe problem for complete graphs is also NP-difficult. For the problem of oneness, we characterize the transformations thatpreserve functions b ¹ and b ² when G is a bipartite graph. This resultis used then to prove the existence of unvariants for some 3 -colouration of the grid. In addition, we study the generalization of the problem ofk-colouration to the reconstruction of tiled of the grid using astiles k rectangles of different sizes. For this problem, we presentproofs that include and extend all the previous known results. To finish, it is proves the existence of a quadratic nucleus for ageneralization of Vertex Cover's problem parametrized by the sizeneeded of the set solution. |
