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: Felipe Fernandes Fanchini / Resumo: Na presente Tese realizou-se um estudo acerca das relações monogâmicas entre emaranhamento de formação (EF) e discórdia quântica (DQ) para sistemas quânticos multipartidos, bem como um estudo acerca da dinâmica dissipativa de operações lógicas de 1 (portas NOT e Z) e 2 (porta CNOT) qubits para uma computação quântica baseada em medidas projetivas (MBQC). Como resultado, expressões as quais generalizam relações de conservação entre EF e DQ puderam ser deduzidas, bem como relações de distribuição de DQ para sistemas de n partes. Ademais, ampliando os estudos referentes a sistemas multipartidos, uma pesquisa a respeito da influência dos canais amplitude damping (AD) e phase damping (PD) em uma MBQC considerando ambientes altamente não-Markovianos pôde ser desenvolvida. Nesse sentido, uma medida denominada fidelidade média (Fm) foi então proposta, a partir da qual expressões analíticas puderam ser deduzidas para os canais em questão, e sendo demonstrado que Fm resulta em valores idênticos para as portas X e Z. Além do mais, também foi possível realizar um estudo acerca dos tempos ótimos das medidas, segundo o qual pôde-se concluir que sua rápida execução não necessariamente implica em melhores resultados, tampouco sua lenta execução não necessariamente implica em piores. Nesse contexto, pôde-se também demonstrar que para o canal AD o conhecimento do mapa dissipativo já é o suficiente para intuitivamente determinar os melhores tempos de medidas, sendo que o mesmo não necessariamen... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work a study about the monogamous relations between entanglement of formation (EF) and quantum discord (QD) for multipartite quantum systems, as well the dissipative dynamics of 1 (NOT and Z gates) and 2 (CNOT gate) qubits for a measurement-based quantum computation (MBQC) could be developed. As a result, expressions which generalize conservation laws between EF and DQ could be deduced, as well as DQ distribution laws for n part quantum systems. In addition, expanding the multipartite systems studies, a research about the influence of the amplitude damping (AD) and phase damping (PD) channels in an MBQC considering highly non-Markovian environments also could be developed. In this sense, a measure called average gate fidelity (Fm) was proposed, from which we deduce analytical expressions for the channels and show that it is identical for the X and Z gates. In addition, we conducted a study of the optimal measurement times, where we conclude that neither fast application of the projective measurements necessarily implies better results, nor slow application necessarily implies worse results. Furthermore, it was also possible to demonstrate that while for the AD the knowledge of the dissipative map is sufficient to determine the best measurement times, the same is not necessarily true for the PD, where the time of the set of measures becomes crucial since a phase error in one qubit can fix the phase error that takes place in another. Finally, a study was carried out on ... (Complete abstract click electronic access below) / Doutor