[pt] Sabemos pelo Teorema da Incompletude de Godel que existem afirmações verdadeiras sobre números naturais que não podem ser demonstradas na aritmética de Peano. Paris e Harrington deram um exemplo de uma variação do Teorema de Ramsey finito que não pode ser demonstrada em aritmética de Peano apesar de ser facilmente demonstrável na Teoria de Conjuntos usual. Este é geralmente considerado o primeiro exemplo matematicamente natural de uma sentença indecidível. Além da demonstração original, apresentamos nessa dissertação outra usando Teoria de Modelos. / [en] From Godel’s Incompleteness Theorem we know that there are true sentences about natural numbers which can not be proved in Peano Arithmetic. Paris and Harrington gave an example of a variation of the finite Ramsey Theorem which can not be proved in Peano Arithmetic although it can be easily proved in usual Set Theory. This is usually considered the first example of a mathematically natural undecidable sentence. Besides the original proof, another one, using Model Theory, is presented in this dissertation.

Thesis (Ph. D.)--University of Chicago, Dept. of Economics, August 1997. / Includes bibliographical references. Also available on the Internet.

University, Diss., 2005--Münster (Westfalen).

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2017. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2017-04-04T15:49:49Z No. of bitstreams: 1 2017_AnnaCarolinaFernandesdaSilva.pdf: 1408612 bytes, checksum: b2a670f5b830e1c5a1dc178ed08238ca (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2017-04-13T13:05:59Z (GMT) No. of bitstreams: 1 2017_AnnaCarolinaFernandesdaSilva.pdf: 1408612 bytes, checksum: b2a670f5b830e1c5a1dc178ed08238ca (MD5) / Made available in DSpace on 2017-04-13T13:05:59Z (GMT). No. of bitstreams: 1 2017_AnnaCarolinaFernandesdaSilva.pdf: 1408612 bytes, checksum: b2a670f5b830e1c5a1dc178ed08238ca (MD5) / Essa dissertação trata da teoria combinatória dos números em conjuntos finitos de inteiros contendo progressões aritméticas, bem como da teoria de Ramsey, do teorema de Szemerédi e de alguns resultados adjacentes importantes. Além de apresentar o teorema de Freiman e exibir uma demonstração de uma generalização do teorema de Freiman, dada por Ruzsa, nós daremos duas importantes aplicações deste teorema, sendo que uma delas prova a versão quantitativa de uma conjectura de Erdös. / This work is about combinatorial number theory in finite sets of integers containing arithmetic progression. Also, we present Ramsey’s theory, Szemerédi’s theorem and some important ad-jacent results. Besides that, we introduce Freiman’s theorem and exhibit a demonstration of its generalization, given two applications of this theorem, one of which proves the quantitative. Version of an Erdos conjecture.

Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible. The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles. The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs. We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices. Finally, the fourth part deals with tight-cycles in a more general setting. We prove that for every $k,r \in \N$, the vertices of every $r$-edge-coloured complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles, confirming a conjecture of Gy\'arf\'as. We further prove that for every $r,p \in \N$, the vertices of every $r$-edge-coloured complete graph can be partitioned into a bounded number of $p$-th powers of cycles, settling a problem of Elekes, D. Soukup, L. Soukup and Szentmikl\'ossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number. / CONICYT/Doctorado Nacional/2014-21141116, CMM-Conicyt PIA AFB170001

Apresentamos um estudo sobre o fenômeno da decoerência durante a evolução temporal de um estado atômico ao interagir com o campo eletromagnético de uma cavidade não ideal. Apresentamos um modelo em que o campo da cavidade esta acoplado a um banho externo e mostramos os efeitos dissipativos que este acoplamento pode gerar na decoerência para um sistema átomo campo. Discutimos as grandezas relevantes para analise da decoerência através de modelos analíticos e numéricos, principalmente entre os acoplamentos átomo campo e campo banho. Sugerimos que o retardamento observado no processo de decoerência seja uma característica geral em sistemas analisáveis como constituídos de três subsistemas acoplados sequencialmente, com propriedades espectrais e acoplamentos suficientemente assimétricos. / We present a study of the phenomenon of decoherence in the time evolution of an atomic state with the electromagnetic field of a non-ideal cavity. We present a model where the cavity field is coupled to an external bath and show the dissipative effects this coupling can generate in the decoherence of the atom field system. We discuss the relevant variables for the analysis of decoherence in terms of analytic and numerical models, especially the atom-field and field-bath couplings. We suggest that the observed hindrance of the decoherence process may be a general property in systems which can be considered as formed by three subsystems coupled sequentially, with spectral properties and sufficiently asymmetric coupling.

nÃo hà / A privatizaÃÃo iniciada na dÃcada de 90 teve no setor de energia elÃtrica, que tem caracterÃsticas de monopÃlio natural nos segmentos de transmissÃo e distribuiÃÃo, o seu grande impulsionador. Junto a essas privatizaÃÃes veio a necessidade da regulaÃÃo do setor elÃtrico, de forma a beneficiar nÃo sà o consumidor como tambÃm as empresas que nele estavam investindo. Para conseguir esse fim os ÃrgÃos reguladores se utilizam de mecanismos de regulaÃÃo tarifÃria na maioria das vezes jà existentes em outros paÃses. No Brasil podemos citar o price-caps, ou preÃo teto, com um dos mecanismos adotados pela ANEEL ÃrgÃo regulador brasileiro. Esse trabalho por sua vez se baseia na teoria de preÃos de Ramsey- Boiteux para o monopÃlio natural de distribuiÃÃo de energia elÃtrica no Estado do Cearà dividido em dois mercados: o residencial e o nÃo-residencial. Sabemos das limitaÃÃes dessa teoria, mas sua aplicaÃÃo à bastante ampla e crescente nÃo se limitando apenas a serviÃos pÃblicos. Pode ser aplicada a economias de mercado e estende-se inclusive a organizaÃÃes com propÃsitos nÃo-lucrativos, que teriam como restriÃÃo na sua funÃÃo-objetivo um eventual lucro negativo, em vez de lucro zero ou lucro competitivo, atendendo dessa forma a questÃes de eficiÃncia alocativa como condiÃÃo bÃsica na consecuÃÃo de seus objetivos. / The privatization process initiated in the 90âs had in the sector of electric energy, which has characteristics of natural monopoly in the transmission and distribution sectors, its great booster. These privatizations brought together the need of the regulation of the electric sector, in a way to benefit not only the consumer, but also the companies that were investing on the consumer. To accomplish this objective, the regulating agencies use several tax regulation mechanisms. One example in Brazil is the price-caps, as one of the mechanisms adopted by the ANEEL - The Brazilian regulating agency. This article is based on the Ramsey-Boiteuxâs theory of prices for the natural monopoly of distribution of electric energy in the State of the Cearà divided in two markets: residential and non-residential market. Despite the difficulties of this theory, its application is wide and increasing and it is limited to public services. It may be applied to market economies and may be extended to non-profit organizations, which would have as a constraint in its objective function, a possible negative profit, instead of null profit or competitive profit, which is in accordance with the issues of allocative efficiency as a basic condition to the achievement of its objectives.

Ramsey Theorem, in the most simple form, states that if we are given a positive integer l, there exists a minimal integer r(l), called the Ramsey number, such any partition of the edges of K_r(l) into two sets, i.e. a 2-coloring, yields a copy of K_l contained entirely in one of the partitioned sets, i.e. a monochromatic copy of Kl. We prove an extension of Ramsey's Theorem, in the more general form, by replacing complete graphs by multipartite graphs in both senses, as the partitioned set and as the desired monochromatic graph. More formally, given integers l and k, there exists an integer p(m) such that any 2-coloring of the edges of the complete multipartite graph K_p(m);r(k) yields a monochromatic copy of K_m;k . The tools that are used to prove this result are the Szemeredi Regularity Lemma and the Blow Up Lemma. A full proof of the Regularity Lemma is given. The Blow-Up Lemma is merely stated, but other graph embedding results are given. It is also shown that certain embedding conditions on classes of graphs, namely (f , ?) -embeddability, provides a method to bound the order of the multipartite Ramsey numbers on the graphs. This provides a method to prove that a large class of graphs, including trees, graphs of bounded degree, and planar graphs, has a linear bound, in terms of the number of vertices, on the multipartite Ramsey number.

Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment avec deux questions d’Erdős de 1957 et 1961. Nous commençons par montrer qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z2 . Le premier résultat répond à une question ouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances nème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir en facteur. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance (exponentiel ou polynomial) du langage les évitant. / In this document, we study the avoidability of different kind of repetitions in words. We firstshow that under some conditions one can decide whether a morphic word avoids abelian n-thpowers. This algorithm can decide over a wider class of morphism than the previousalgorithms. We generalize this algorithm and use it to show that long abelian squares areavoidable over the ternary alphabet and that additive squares are avoidable over Z2 . The firstresult answers a weak version of a question formulated by Mäkelä in 2003 and the second oneis related to an open question from 1994 about the avoidability of additive squares over Z.Another generalization of this algorithm can be used to study avoidability of patterns in theabelian sense. In particular, we show that binary patterns of length more than 14 areavoidable over the binary alphabet in the abelian sense. This improves considerably theprevious bound of 118.We give sufficient conditions for a morphism to be long k-abelian n-th power-free. This resultallows us to compute for every k ≥ 3 the number of different k-abelian squares that a binaryword must contain. We prove that long 2-abelian squares are avoidable over the binaryalphabet and that over the ternary alphabet there exists a word that contains only one 2-abelian square.We also give a complete classification of binary formulas based on the size of the smallestalphabet over which they are avoidable and on the growth (exponential or polynomial) of theassociated language.

Apresentamos um estudo sobre o fenômeno da decoerência durante a evolução temporal de um estado atômico ao interagir com o campo eletromagnético de uma cavidade não ideal. Apresentamos um modelo em que o campo da cavidade esta acoplado a um banho externo e mostramos os efeitos dissipativos que este acoplamento pode gerar na decoerência para um sistema átomo campo. Discutimos as grandezas relevantes para analise da decoerência através de modelos analíticos e numéricos, principalmente entre os acoplamentos átomo campo e campo banho. Sugerimos que o retardamento observado no processo de decoerência seja uma característica geral em sistemas analisáveis como constituídos de três subsistemas acoplados sequencialmente, com propriedades espectrais e acoplamentos suficientemente assimétricos. / We present a study of the phenomenon of decoherence in the time evolution of an atomic state with the electromagnetic field of a non-ideal cavity. We present a model where the cavity field is coupled to an external bath and show the dissipative effects this coupling can generate in the decoherence of the atom field system. We discuss the relevant variables for the analysis of decoherence in terms of analytic and numerical models, especially the atom-field and field-bath couplings. We suggest that the observed hindrance of the decoherence process may be a general property in systems which can be considered as formed by three subsystems coupled sequentially, with spectral properties and sufficiently asymmetric coupling.