Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.

Ingeniera Civil Matemática / En la presente memoria se considera la relación entre coloreamiento de vértices y la noción de inmersión. Específicamente, se estudia una conjetura propuesta por Abu-Khzam y Langston, la cual dice que el grafo completo de tamaño t está inmerso en todo grafo t-cromático. En primer lugar, se ven algunos resultados generales de inmersiones y se prueba que la conjetura se cumple para los grafos cuyo complemento no contiene ciclos inducidos de largo cuatro y también para los grafos tales que todo conjunto de cinco vértices induce un subgrafo con al menos seis aristas. Luego, se da una breve mirada a una nueva relación definida, en un intento de generalizar la relación de inmersión. Finalmente, se estudia en detalle una clase especial de grafos, aquella de los grafos sin conjunto independiente de tamaño tres. Se presentan condiciones suficientes para que se cumpla la conjetura de Abu-Khzam y Langston. Luego, se introduce una nueva conjetura, implicada por la conjetura de Abu-Khzam y Langston y se demuestra una versión un tanto más débil que ésta. Se prueba además, que ambas conjeturas son equivalentes. Por último, se exhiben una serie de propiedades que debería cumplir un contraejemplo mínimo, en caso de existir alguno.

RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2005. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-08T19:45:39Z No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-08T19:45:58Z (GMT) No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-06-08T19:45:58Z (GMT). No. of bitstreams: 1 2008_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported. / Neste trabalho abordamos o problema de coloração de vértices via programação inteira. Uma versão expandida da formulação por conjuntos independentes é utilizada para abrigar outras sub-estruturas do grafos além dos vértices. Cada uma dessas sub-estruturas define uma restrição que determina quantos conjuntos independentes são necessarios para cobrir aquele subgrafo. Experimentos com um método de geração de cortes e colunas para o problema são feitos para determinar um limite inferior para um conjunto de instâncias classicas para esse problema a biblioteca DIMACS.

RODRIGUES, Carlos Diego. Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas. 2008. 79 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T11:50:40Z No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:28:23Z (GMT) No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) / Made available in DSpace on 2016-07-14T15:28:23Z (GMT). No. of bitstreams: 1 2005_dis_cdrodrigues.pdf: 545679 bytes, checksum: 7cceeca6a76bce10cbde4bfb4ef0ee02 (MD5) Previous issue date: 2008 / In this work the vertex coloring problem is approached via integer programming. A tighter version of the independent set formulation is used, where the vertex-related constraints are substituted by subgraph-related constraints. Each constraint establishes a lower bound on the number of independent sets intersecting a subgraph H. It is shown a sufficient condition for this inequality to define a facet of the associated polytope. Basically, H is required to be color critical, not included in another color critical subgraph, and to have a connected complement. Also, the column generation algorithm proposed by Mehotra and Trick (INFORMS Journal in Computing, 1996) is adapted to allow the addition of cutting planes and to provide lower bounds along the process, which may abbreviate its end. Some computational experiments are reported. / Neste trabalho abordamos o problema de coloração de vértices via programação inteira. Uma versão expandida da formulação por conjuntos independentes é utilizada para abrigar outras sub-estruturas do grafos além dos vértices. Cada uma dessas sub-estruturas define uma restrição que determina quantos conjuntos independentes são necessarios para cobrir aquele subgrafo. Experimentos com um método de geração de cortes e colunas para o problema são feitos para determinar um limite inferior para um conjunto de instâncias classicas para esse problema a biblioteca DIMACS.

QUINTINO, Arthur Lima. Vértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticos. 2016. 59 f. Dissertação (Mestrado em Matemática)- Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:21:47Z No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:22:11Z (GMT) No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Made available in DSpace on 2016-08-01T13:22:11Z (GMT). No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) Previous issue date: 2016 / In 1989, Gyárfás conjectured that, for every natural r, r monochromatic paths are suficient to vertex-partition any r-edge-coloured complete graph. Later, Erdos, Gyárfás and Pyber proposed a stronger version of this conjecture, in which r monochromatic cycles are wanted instead of r monochromatic paths. In this dissertation, we present many problems and results related to such conjectures, including problems where the graph to be coloured is not a complete graph, but a complete multipartite graph. We also highlight how the Szemeredi's regularity lemma may be applied in this context. Furthermore, we prove two original results. In the first one, we extend some arguments introduced by Gyárfás and Lehel in order to obtain an alternative, simpler, proof for a result due to Pokrovskiy. Whereas in the second, we show that 4 monochromatic cycles are suficient to vertex-partition any 2-edge-coloured balanced complete bipartite graph, thereby reducing the number of 12 monochromatic cycles that had been previously obtained by Schaudt and Stein. Lastly, we discuss some strategies that may be followed in future works in order to reduce the quantity of monochromatic cycles needed in this case from 4 to 3, which is the minimum possible for such case. / Em 1989, Gyárfás conjecturou que, para todo r natural, r caminhos monocromáticos são suficientes para vértice-particionar qualquer grafo completo r-aresta-colorido. Mais tarde, Erdos, Gyárfás e Pyber propuseram uma versão mais forte dessa conjectura, na qual r ciclos monocromáticos são procurados em vez de r caminhos monocromáticos. Nesta dissertação, apresentamos vários problemas e resultados relacionados com tais conjecturas, incluindo problemas onde o grafo a ser colorido não é um grafo completo, mas sim um grafo multipartido completo. Destacamos ainda como o Lema da regularidade de Szemerédi pode ser aplicado nesse contexto. Al em disso, provamos dois resultados originais. No primeiro deles, estendemos alguns argumentos introduzidos por Gyárfás e Lehel afim de obtermos uma prova alternativa, mais simples, para um resultado devido a Pokrovskiy. Enquanto que no segundo, mostramos que 4 ciclos monocromáticos são suficientes para vértice-particionar qualquer grafo bipartido completo balanceado 2-aresta-colorido, reduzindo assim o número de 12 ciclos monocromáticos que havia sido obtido anteriormente por Schaudt e Stein. Por fim, discutimos algumas estratégias que podem ser seguidas em trabalhos futuros a fim de reduzir a quantidade de ciclos monocromáticos necessários nesse caso de 4 para 3, o que e o mínimo possível para tal caso.

Orientador: Cristiano Torezzan / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T15:05:42Z (GMT). No. of bitstreams: 1 Monticeli_AndreRodrigues_M.pdf: 7043231 bytes, checksum: 683696a5c1b284a08a9d19c54647edaa (MD5) Previous issue date: 2010 / Resumo: Neste trabalho abordamos o problema de descrever o conjunto solução de um sistema de inequações lineares. Este problema está fortemente relacionado com o problema clássico da enumeração de vértices de um poliedro. Descrevemos o método de Fourier-Motzkin que pode ser utilizado para eliminar variáveis de um sistema de inequações lineares e projetar a região de solução num espaço de dimensão menor. Mostramos como o problema da enumeração de vértices pode ser convertido em um problema de encontrar o fecho convexo do conjunto de pontos dual ao sistema de inequações lineares, uma vez encontrado um ponto interior factível. Alguns algoritmos para o fecho convexo de um conjunto finito de pontos e também para encontrar um ponto interior factível são estudados. Nosso interesse, além de listar os vértices e as faces é também visualizar a região de solução utilizando um programa computacional. Para tanto propomos um método que constrói a lista dos vértices e faces do poliedro definido por um dado sistema de inequações lineares e grava o resultado num arquivo de texto puro com extensão obj, que é compatível com os principais softwares de visualização gráfica 3D. O método foi implementado no Octave e diversos testes foram feitos, analisando o custo computacional e possíveis dificuldades que podem surgir devido a erros numéricos ou falta de memória / Abstract: In this work we approach the problem of describing the solution of a system of linear inequalities. This problem is closely related to the classical problem known as vertex enumeration. We describe the method of Fourier-Motzkin, that can be used to eliminate variables in a system of linear inequalities, projecting its solution in a lower dimensional space. We show how the vertex enumeration problem can be converted into an equivalent problem of finding the convex hull of a set of dual points, once found a feasible interior point. Some algorithms for convex hull and also for finding a feasible interior point are studied. Our interest is not only to store the vertices and faces but also visualize the correspondent polyhedron using a computer graphics software. In this way we propose a method that stores the polyhedron's vertices and faces and output the results into a plain text _le with extension obj, which is a geometric definition file format that can be opened with all major 3D graphics software. The method was implemented in Octave and several tests were made, analyzing the computational cost and possible difficulties that may arise due to numerical errors or memory requirements / Mestrado / Matematica / Mestre em Matemática

Neste trabalho, estendemos o método desenvolvido em (SALARINOGHABI, 2016),(SALARINOGHABI; TARI, 2017) para curvas no plano Minkowski. Tal método propõe um modo de estudar deformações de curvas planas levando em consideração a geometria das mesmas juntamente com suas singularidades. Abordamos detalhadamente todos os fenômenos locais que ocorrem genericamente em famílias de curvas a 2-parâmetros. Em cada caso, obtemos a geometria da curva deformada, ou seja, informações a respeito de inflexões, vértices e pontos lightlike. Obtemos também o comportamento da evoluta/cáustica de uma curva em pontos especiais e as bifurcações que podem aparecer ao deformá-la. Além disso, a fim de obter as deformações genéricas em uma inflexão lightlike de ordem 2, também classificamos submersões de R3 em R por meio de difeomorfismos na fonte que preservam a swallowtail e, utilizando tal classificação, estudamos a geometria plana da swallowtail, a qual provém de seu contato com planos, o qual por sua vez é medido pelas singularidades da função altura sobre a swallowtail. / In this work, we extend the method developed in (SALARINOGHABI, 2016),(SALARINOGHABI; TARI, 2017) to curves in the Minkowski plane. The method proposes a way to study deformations of plane curves taking into consideration their geometry as well as their singularities. We deal in detail with all local phenomena that occur generically in 2-parameters families of curves. In each case, we obtain the geometry of the deformed curve, that is, information about inflections, vertices and lightlike points. We also obtain the behavior of the evolute/caustic of a curve at special points and the bifurcations that can occur when the curve is deformed. Moreover, in order to obtain the generic deformations at a lightlike inflection point of order 2, we also classify submersions from R3 to R by diffeomorphisms in the source that preserve the swallowtail and, using such classification, we study the flat geometry of the swallowtail, which comes from its contact with planes, which in turn is measured by the singularities of the height function on the swallowtail.

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

O objetivo deste trabalho é analisar o comportamento dos expoentes críticos do modelo de Oito Vértices através de cotas superior e inferior para sua função de partição na vizinhança de modelos solúveis. O método é ilustrado pelo modelo de Heisenberg quântico unidimensional também denominado modelo XYZh. Aplica-se igualmente ao modelo de Ising bidimensional (com interação quártica e segundos vizinhos). Assim, propomos um modo alternativo de abordar universalidade nos modelos de Heisenberg unidimensional quântico e Ising bidimensional clássico por desigualdades satisfeitas por suas funções de partição. Dentre os métodos que utilizamos para a obtenção das cotas destacam-se: a interação Gaussiana nas variáveis reais e nas variáveis de Grassmann; o mapeamento de um modelo unidimensional em um bidimensional através do auxílio da fórmula Trotter; a representação da função de partição pelo Pfaffiano de uma matriz; e, para a obtenção da cota superior, a técnica de positividade por reflexão, estendida ao acaso de variáveis que anti-comutam. / The aim of this work is to analyze the behavior of critical exponents in the eight-vertex model starting from the upper and lower bound obtained for its partition function. We studied the quantum onedimensional Heisenberg model also denominated XYZh model. We propose na alternative way of approaching universality in Heisenberg and Ising models using inequalities satisfied for their partition functions.Among the methods that we used in the solutions of the models atand out the integration on the Grassmann variables, the mapping of a onedimensional model in a two-dimensional one through the aid of the Trotter formula and, finally, the representation of the partition function as Pfaffian of a matrix. To obtain na upper bound, the positivity reflection technique was used, extended to the case of variables that, anticomute, and the method of thechess board estimate.

We propose in this thesis a way to study deformations of plane curves that take into consideration the geometry of the curves as well as their singularities. We deal in details with local phenomena that occur generically in two-parameter families of curves. We obtain information on the inflections and vertices appearing on the deformed curves. We also obtain the configurations of the evolutes of the curves and of their deformations, and apply our results to orthogonal projections of space curves. Finally, we consider the profile (outline, apparent contour) of a smooth surface in the Euclidian 3-space. This is the image of the singular set of an orthogonal projection of the surface. The profile is a plane curve and may have singularities. We study the changes in the geometry of the profile as the direction of projection changes locally in the unit sphere. / Propomos nesta tese um método para estudar deformações de curvas planas que leva em consideração a geometria delas, bem como as suas singularidades. Consideramos em detalhes os fenômenos locais que ocorrem genericamente em famílias de curvas com dois parâmetros. Obtemos informações sobre as inflexões e vértices que aparecem nas curvas deformadas. Obtemos também as configurações das evolutas das curvas e das suas deformações e aplicamos os nossos resultados nas projeções ortogonais de curvas espaciais. Finalmente, consideramos o perfil de uma superfície regular no espaço Euclidiano R3. O perfil é a imagem do conjunto singular de uma projeção ortogonal da superfície, esta é uma curva plana e pode ter singularidades. Estudamos as alterações na geometria do perfil quando a direção de projeção muda localmente na esfera unitária.