LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 60 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T12:13:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:33:44Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-07-14T15:33:44Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom.

Seja E(X) a cardinalidade dos números pares menores ou iguais a X que não podem ser escritos como soma de dois primos. O objetivo central desta dissertação é apresentar uma demonstração de uma estimativa para E(X) dada por Hugh L. Montgomery e Robert C. Vaughan em [22]. Mais precisamente, estabeleceremos a existência de uma constante positiva (efetivamente computável) tal que E(X) X1 ; para todo X su cientemente grande. / Let E(X) the cardinality of even numbers not exceeding X which cannot be written as a sum of two primes. The main goal of this dissertation is to present a proof of an estimate for E(X) given by Hugh L. Montgomery e Robert C. Vaughan in [22]. More precisely, we will establish the existence of a positive constant (e ectively computable) such that E(X) X1 for all su ciently large X:

Orientador: Prof. Dr. Ever Aldo Arroyo Montero / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Física, 2015. / Nesta dissertação vamos utilizar da teoria de campos de cordas abertas para estudar a conjectura de Sen a partir do cálculo do potencial do táquion, que será obtido através do método numérico Level Truncation. Para isso, será feita uma introdução sobre teoria de cordas, passando por teoria de campos conforme em duas dimensões, a quantização BRST, as interações entre cordas abertas, e por fim estudar o formalismo da teoria de Witten de campos de cordas, desde a construção da ação cubica, até sua aplicação ao calcular o potencial do táquion "off-shell"para testar a conjectura de Sen e encontrar a relação entre o vácuo instável e o estável, a chamada condensação do táquion. / In this dissertation, it will be used the open string eld theory to study Sen's conjecture. We will calculate the tachyon potential through the numerical method known as the Level Truncation. To this purpose, we will study the following topics: an introduction to string theory through two dimensional conformal eld theory, BRST quantization, interactions between open strings and nally Witten's open cubic string eld theory together with its application which includes the calculation of the tachyon potential and the numerical test of Sen's conjecture. We are also going to analyze the relation between unstable and stable vacuum, namely, the tachyon condensation.

We introduce the historical context and motivation for the search for magnetic monopoles or monopole-like objects. Beginning the theoretical part we investigate the properties of groups as they relate to symmetries in physical theories. Using this as a basis we investigate the requirements for global and local gauge invariance for a scalar field, the latter giving the non-trivial connection to a gauge field. From this we present the Georgi-Glashow model and develop its particle spectrum using the connected Higgs field and its associated Higgs mechanism. We then present the electromagnetic duality by extending the Maxwell's equations toinclude magnetic sources. Using the assumption of magnetic sources we present the Dirac quantization condition, motivating the quantization of electric charge. Returning to our model we present the 't Hooft-Polyakov ansatz and investigate its defining properties as a finite energy soliton in our Higgs field. We show the magnetic properties and motivate its validity as a monopole like object. Continuing we define BPS-states on the lower bound for the mass of a monopole like object with magnetic and electric charge. Giving a BPS monopole as a solution in the vein of 't Hooft and Polyakov. Returning to the electromagnetic duality we propose the Montonen-Olive conjecture by exchanging massive vector bosons in our model with the BPS monopoles we developed. We shortly comment on evident problems and present supersymmetry as a possible solution. Finally we present the Witten Effect by allowing a CP violating term in our Lagrangian. From this we extend the Montonen-Olive conjecture to include invariance under the SL(2,Z) group.

Made available in DSpace on 2015-05-15T11:46:13Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 572294 bytes, checksum: 1c46e916c7cc2e4689880e2687dbee0b (MD5) Previous issue date: 2012-03-08 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This word is concerned with the study of bounded solutions of semilinear elliptic equations u − F0(u) = 0 in the whole space Rn, under the assumption that u is monotone in one direction, say, @u/@xn > 0 em Rn. The goal is to establish the one-dimensional character or symmetry of u, namely, that u only depends on one variable or, equivalently, that the level sets of u are hyperplanos. This type of symmetry question was raised by de Giorgi in 1978 (see [6]), who made the folowing conjecture: Conjecture Suppose that u 2 C2(Rn) is solution of the equation u + u − u3 = 0 satisfying |u(x)| 1 and @u @xn > 0 in the whole Rn. Then the level sets of u must be hyperplanes. We show a stronger version of De Giorgi s conjecture is indeed true in dimension 2 and 3 using some techniques in the linear theory developed by Berestychi, Caffarelli and Nirenberg [5] in one of their papers on qualitative properties of solutions of semilinear elliptic equations. / Este trabalho se preocupa com o estudo de soluções limitadas de equações elípticas semilineares u − F0(u) = 0 em todo espaço Rn, sob o pressuposto que u é monótona em uma direção, digamos @u/@xn > 0 em Rn. O objetivo é estabelecer o caráter unidimensional ou simetria de u, ou seja, que u depende apenas de uma variável ou equivalentemente, que os conjuntos de nível de u são hiperplanos. Este tipo de questão da simetria foi levantada por De Giorgi em 1978 (ver [6]), que fez a seguinte conjectura: Conjectura Suponha que u 2 C2(Rn) é solução da equação u + u − u3 = 0 satisfazendo |u(x)| 1 e @u @xn > 0 em todo Rn. Então os conjuntos de nível de u são hiperplanos. Mostraremos que uma versão forte da conjectura de De Giorgi é de fato verdade em dimensão 2 e 3 usando somente técnicas da teoria linear desenvolvida por Berestychi, Caffarelli e Nirenberg [5] em um dos seus artigos sobre as propriedades qualitativas de equações elípticas semilineares.

Seja E(X) a cardinalidade dos números pares menores ou iguais a X que não podem ser escritos como soma de dois primos. O objetivo central desta dissertação é apresentar uma demonstração de uma estimativa para E(X) dada por Hugh L. Montgomery e Robert C. Vaughan em [22]. Mais precisamente, estabeleceremos a existência de uma constante positiva (efetivamente computável) tal que E(X) X1 ; para todo X su cientemente grande. / Let E(X) the cardinality of even numbers not exceeding X which cannot be written as a sum of two primes. The main goal of this dissertation is to present a proof of an estimate for E(X) given by Hugh L. Montgomery e Robert C. Vaughan in [22]. More precisely, we will establish the existence of a positive constant (e ectively computable) such that E(X) X1 for all su ciently large X:

A ênfase do trabalho recai na análise da taxa temporal de produção de entropia em sistemas de rede determinados por suas propriedades de simetria, no intuito de constituí-la como uma ferramenta paradigmática no estudo de sistemas irreversíveis. Nesse sentido, uma vez que se consegue consolidar uma definição consistente dessa grandeza para este campo, propõe-se uma abordagem estocástica para o modelamento da dinâmica dos exemplares considerados. O grupo de simetria C_ descreve as propriedades de invariância em sistemas com ampla relevância em física, de maneira que resulta natural elaborar a construção dos modelos em torno a sua estrutura, mais ainda quando se pode assumir que as características de simetria, no relativo à determinação da classe de universalidade dos modelos, são condições mais relevantes que a presença do não-equilíbrio, em coerência com a conjetura de Grinstein. Aliás, o modelo de Potts de três estados também apresenta propriedades de simetria próprias daquele grupo, além de ser passível de certo rigor no seu tratamento matemático, de maneira que oferece resultados consideravelmente satisfatórios e propícios para, por comparação, analisar os sistemas que concernem neste estudo. Assim, o procedimento tem como fim a determinação numérica da produção de entropia em sistemas com dinâmica irreversível e invariantes ante as transformações de simetria que compõem o grupo C_3v, partindo para isso de simulações de Monte Carlo em modelos estruturados sobre redes quadradas. A determinação da produção de entropia segue a prescrição de Schnakenberg (Schnakenberg [1976]), fundamentada nas correntes de probabilidade que surgem no sistema como consequência da violação da reversibilidade microscópica; a qual, por sua vez, estabelece a necessidade para os sistemas em equilíbrio de que todas as sequências cíclicas possíveis entre estados consecutivos sejam percorridas com igualdade de probabilidade num sentido quanto no inverso. Como uma segunda instância deste trabalho, também foram estudadas as propriedades de escalabilidade apresentadas por estos modelos durante seus primeiros instantes de evolução, isso, a partir da determinação numérica dos exponentes dinâmicos e sua caracterização dentro do marco teórico conhecido como \"short time scaling\'\' (Jansen et al. (1989)). Nesse sentido foram consideradas algumas das prescrições concernentes que tem apresentado melhor desempenho nos últimos anos. O observado mostra um comportamento coerente com a satisfação do que implicaria a conjetura de Grinstein para estes sistemas irreversíveis, indicando sua pertença à classe de universalidade do modelo de Potts de três estados, e, com isso, reafirmando os resultados obtidos em relação à produção de entropia. / This work is proposed as a study of the entropy production rate in lattice systems determined by its symmetries, looking for its consolidation as a paradigmatic tool in the area of irreversible and nonequilibrium systems. Henceforth, given the actual possibility of defining this quantity on that field, a stochastic perspective is adopted for modeling the dynamics of the considered systems. The C_ symmetry group describes the invariance properties of a wide range of physical systems, hence it results sensitive building the models to be dealt in accordance with its intrinsic characteristics, even more when it comes to be just fair, at the sight of the previous available analysis as well of the Grinstein conjecture, considering the invariance properties of systems as a more relevant factor than the reversibility conditions in what concerns the establishment of its universality class. The three states Potts model, indeed, shares its symmetry characteristics with those owned by the elements of the referred group and, also, concerning it there is a considerable amount of well confirmed information, becoming suitable for contrasting the results obtained. Henceforth, this work is focused on the numerical determination of the entropy production rate in irreversible systems whose invariance properties are the ones defined by the C_ symmetry group, implementing for that porpoise Monte Carlo simulations over square lattices models with the proper symmetries. By its own, the entropy production is determined in accordance with the Schnakenberg prescription (Scnhakenberg [1976]); deeply related with the probability currents emerging within irreversible systems as consequence of microscopic reversibility violation, which, in equilibrium, is imposed due to the mandatory equality between the evolution directions of all possible cyclic paths through a succession of states assumed by the system. As a second instance of this work, the scaling properties of the studied models during the first period of its evolution, just after the microscopic scale of time, were also analyzed. Henceforth, the determination of its dynamical exponents, as well as its characterization within the context of \"short time scaling\'\' (Jansent et al. [1989]) was realized through the calculus of some quantities with proven signatures of presenting an scalable \"initial slip\'\', finding strong suggestions for the models of being in the same universality class of the three state Potts model, fact coherent with the Grinstein conjecture if extended over them, but also with the observed behavior of the entropy production.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-LovÂasz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloraÃÃo està entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teorica e prÃtica. Dado que o problema de colorir os vÃrtices de um grafo G qualquer com a menor quantidade de cores à NP-difÃcil, vÃrias heurÃsticas de coloraÃÃo sÃo estudadas a fim de obter uma coloraÃÃo prÃpria com um nÃmero de cores razoavelmente pequeno. Dado um grafo G, a heurÃstica b de coloraÃÃo se resume a diminuir a quantidade de cores utilizadas em uma coloraÃÃo prÃpria c, de modo que, se todos os vÃrtices de uma classe de cor deixam de ver alguma cor em sua vizinhanÃa, entÃo podemos modificar a cor desses vÃrtices para qualquer cor inexistente em sua vizinhanÃa. Dessa forma, obtemos uma coloraÃÃo c′ com uma cor a menos que c. Irving e Molove definiram a b-coloraÃÃo de um grafo G como uma coloraÃÃo onde toda classe de cor possui um vÃrtice que à adjacente as demais classes de cor. Esses vÃrtices sÃo chamados b-vÃrtices. Irving e Molove tambÃm definiram o nÃmero b-cromÃtico como o maior inteiro k tal que G admite uma b-coloraÃÃo por k cores. Eles mostraram que determinar o nÃmero b-cromÃtico de um grafo qualquer à um problema NP-difÃcil, mas polinomial para Ãrvores. Irving e Molove tambÃm definiram o m-grau de um grafo, que à o maior inteiro m(G) tal que existem m(G) vÃrtices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau à um limite superior para nÃmero b-cromÃtico e mostraram que o mesmo à igual a m(T) ou a m(T)−1, para toda Ãrvore T, onde o nÃmero b-cromÃtico à igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertaÃÃo, verificamos a relaÃÃo entre a cintura, que à o tamanho do menor ciclo, e o nÃmero b-cromÃtico de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G à pelo menos g∗, entÃo o nÃmero b-cromÃtico à igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ à no mÃximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de ErdÃs-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ à 9. Caracterizamos os grafos cuja cintura à pelo menos 6 e nÃo possuem um conjunto bom e mostramos como b-colori-los de forma Ãtima. AlÃm disso, mostramos como bicolorir, tambÃm de forma Ãtima, os grafos cuja cintura à pelo menos 7 e nÃo possuem conjunto bom.

Provamos que \'C POT. 1\' genericamente difeomorfismos simpléticos ou são Anosov ou possuem entropia topológica limitada por baixo pelo supremo sobre o menor expoente de Lyapunov positivo dos pontos periódicos hiperbólicos. Usando isto exibimos exemplos de difeomorfismos conservativos sobre superfícies que não são pontos de semicontinuidade superior para a entropia topológica. Provamos também que \'C POT. 1\' genericamente difeomorfismos simpléticos não Anosov não admitem extensões simbólicas. Mudando de assunto, Hayashi estendeu um resultado de Mañé, provando que todo difeomorfismo f que possui uma \'C POT. 1\' vizinhança U, onde todos os pontos periódicos de qualquer g \'PERTENCE A\' U são hiperbólicos, é de fato um difeomorfismo Axioma A. Aqui, provamos o resultado análogo a este no caso conservativo, e a partir deste é possível exibir uma demonstração de um fato \"folclore\", a conjectura de Palis no caso conservativo / We prove that a \'C POT.1\' generic symplectic diffeomorphism is either Anosov or the topological entropy is bounded from below by the supremum over the smallest positive Lyapunov exponent of the periodic points. By means of that we give examples of area preserving diffeomorphisms which are not point of upper semicontinuity of entropy function in \'C POT. 1\' topology. We also prove that \'C POT. 1\'- generic symplectic diffeomorphisms outside the Anosov ones do not admit symbolic extension. Changing of subject, Hayashi has extended a result of Mañé, proving that every diffeomorphism f which has a \'C POT. 1\'-neighborhood U, where all periodic points of any g \'IT BELONGS\' U are hyperbolic, it is an Axiom A diffeomorphism. Here, we prove the analogous result in the volume preserving scenario, and using it we prove a \"folklore\" fact, the Palis conjecture in this context

Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.