Search

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR PROGRAMA DE EXCELENCIA ACADEMICA Nessa dissertação vamos abordar a famosa lei do Semicírculo de Wigner, que dá uma descrição do comportamento do espectro de autovalores de matrizes aleatórias simétricas. A demonstração combina ideias e técnicas de Combinatória e Probabilidade, incluindo uma analise cautelosa dos momentos da distribuição de autovalores. In this dissertation we will approach the famous Wigner s Semicircle Law, which gives a description of the behavior of the eigenvalue spectrum of symmetric random matrices. The proof combines ideas and techniques from Combinatorics and Probability, including a careful analysis of the moments of the eigenvalue distribution.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR PROGRAMA DE EXCELENCIA ACADEMICA Nessa dissertação vamos introduzir, elaborar e combinar ideias da Teoria de martingais, a Teoria de grafos aleatórios e o Teorema Central do Limite. Em particular, veremos como martingais podem ser usados para representar desvios de contagem de subgrafos. Usando esta representação e o Teorema Central do Limite para martingais, conseguiremos demonstrar um Teorema Central do Limite para a contagem de subgrafos livres de triângulos no grafo aleatório Erdos-Rényi G(n,m) . Além disso, nossa demonstração também nos trará informação sobre a taxa de convergência, mostrando que a distribuição dos desvios converge rapidamente para a distribuição normal. In this dissertation we shall introduce, elaborate and combine ideas from martingale Theory, random graph Theory and the Central Limit Theorem. In particular, we will see how martingales can be used to represent deviations of subgraph counts. Using this representation and the Central Limit Theorem for martingales, we will be able to demonstrate a Central Limit Theorem for the triangle-free subgraph count in the Erdos-Rényi G(n,m) random graph. Furthermore, our proof also gives us information about the rate of convergence, showing that the distribution of deviations converges rapidly to the normal distribution.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR PROGRAMA DE EXCELENCIA ACADEMICA Esta dissertação tem o objetivo de aplicar os conceitos e ferramentas da Análise Real e Álgebra Linear num estudo sobre a teoria de existência, unicidade e estabilidade de soluções de sistemas de equações diferenciais ordinárias, considerando sistemas gerais parametrizados, lineares e não-lineares. This dissertation aims to apply the concepts and tools of Real Analysis and Linear Algebra to the theory of existence, uniquiness and stability of solutions of ordinary differential equations systems, considering general parametric, linear and non-linear systems.

Uma coloração de arestas é a atribuição de cores às arestas de um grafo, de modo que arestas adjacentes não recebam a mesma cor. O menor inteiro positivo para o qual um grafo admite uma coloração de arestas é dito seu índice cromático. Fizemos revisão bibliográfica dos principais resultados conhecidos nessa área. Uma coloração total, por sua vez, é a aplicação de cores aos vértices e arestas de um grafo de modo que elementos adjacentes ou incidentes recebam cores distintas. O número cromático total de um grafo é o menor inteiro positivo para o qual o grafo possui coloração total. Dada uma coloração total, se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração é equilibrada e o menor número inteiro positivo que satisfaz essa condição é dito o número cromático total equilibrado do grafo. Para tal valor, Wang (2002) conjecturou um limite superior. Um grafo multipartido completo balanceado é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes com a mesma quantidade de vértices, sendo adjacentes quaisquer dois vértices de diferentes partes da partição. Determinamos o número cromático total equilibrado dos grafos multipartidos completos balanceados, contribuindo, desta forma, com novos resultados na área de coloração de grafos. An edge coloring is the assignment of colors to the edges of a graph, so that adjacent edges do not receive the same color. The smallest positive integer for which a graph admits an edge coloring is said to be its chromatic index. We did a literature review of the main known results of this area. A total coloring, in turn, is the application of colors to the vertices and edges of a graph so that adjacent or incident elements receive distinct colors. The total chromatic number of a graph is the least positive integer for which the graph has a total coloring.Given a total coloring, if the difference between the cardinality of any two color classes is at most one, then we say that the coloring is equitable and the smallest positive integer that satisfies this condition is said to be the graph s equitable total chromatic number. For such value, Wang (2002) conjectured an upper bound. A complete multipartite balanced graph is the one in which the set of vertices can be partitioned into independent sets with the same quantity of vertices, being adjacent any two vertices of different parts of the partition. We determine the equitable total chromatic number of complete multipartite graphs, contributing, therefore, with new results in the area of graph coloring.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR PROGRAMA DE EXCELENCIA ACADEMICA O objetivo desta dissertação é apresentar algumas técnicas e ferramentas para a obtenção de cotas superiores e inferiores para tempos de mistura de cadeias de Markov. Para que isso se torne mais interessante, apresentaremos estes conceitos através de cadeias de Markov que atuam sobre o grupo simétrico, que podem ser vistas como embaralhamentos de cartas. Ademais, usaremos um destes embaralhamentos como toy model para o processo de exclusão simples simétrico, o que nos ajudará a determinar os tempos de mistura do embaralhamento e do famoso sistema de partículas. The aim of this dissertation is to introduce some techniques and tools to obtain upper and lower bounds for Markov chains mixing times. To make it more interesting, we introduce these concepts through Markov chains that act on the symmetric group, which can be seen as card shuffles. Furthermore, we use one of these shuffles as a toy model for the symmetric simple exclusion process, which helps us to determine mixing times for the shuffle and for the famous particle system.

Esta dissertação é dedicada ao estudo das taxas de convergência no Teorema Central do Limite para Martingais. Começamos a primeira parte da tese apresentando a Teoria de Martingais, introduzindo o conceito de esperança condicional e suas propriedades. Desta forma poderemos descrever o que é um Martingal, mostraremos alguns exemplos, e exporemos alguns dos seus principais teoremas. Na segunda parte da tese vamos analisar o Teorema Central do Limite para variáveis aleatórias, apresentando os conceitos de função característica e convergência em distribuição, que serão utilizados nas provas de diferentes versões do Teorema Central do Limite. Demonstraremos três formas do Teorema Central do Limite, para variáveis aleatórias independentes e identicamente distribuídas, a de Lindeberg-Feller e para uma Poisson. Após, apresentaremos o Teorema Central do Limite para Martingais, demonstrando uma forma mais geral e depois enunciaremos uma forma mais específica a qual focaremos o resto da tese. Por fim iremos discutir as taxas de convergência no Teorema Central do Limite, com foco nas taxas de convergência no Teorema Central do Limite para Martingais. Em particular, exporemos o resultado de [4], o qual determina, até uma constante multiplicativa, a dependência ótima da taxa de um certo parâmetro do martingal. This dissertation is devoted to the study of the rates of convergence in the Martingale Central Limit Theorem. We begin the first part presenting the Martingale Theory, introducing the concept of conditional expectation and its properties. In this way we can describe what a martingale is, present examples of martingales, and state some of the principal theorems and results about them. In the second part we will analyze the Central Limit Theorem for random variables, presenting the concepts of characteristic function and the convergence in distribution, which will be used in the proof of various versions of the Central Limit Theorem. We will demonstrate three different forms of the Central Limit Theorem, for independent and identically distributed random variables, Lindeberg-Feller and for a Poisson distribution. After that we can introduce the Martingale Central Limit Theorem, demonstrating a more general form and then stating a more specific form on which we shall focus. Lastly, we will discuss rates of convergence in the Central Limit Theorems, with a focus on the rates of convergence in the Martingale Central Limit Theorem. In particular, we state results of [4], which determine, up to a multiplicative constant, the optimal dependence of the rate on a certain parameter of the martingale.

O trabalho tem como objetivo ser uma introdução ao estudo de mercados financeiros tratados em tempo discreto com horizonte finito, bem como a dinâmica dos ativos financeiros principais. Descrevemos os tipos de ativos negociados em nosso mercado, dando enfoque aos contratos. Elaboraremos a hipótese central do modelo, a ausência de arbitragem e assim mostraremos como poderemos encontrar um preço correto ou então apresentaremos um intervalo de preços para os contratos. Posteriormente, mostraremos resultados gerais relativos à correta precificação de contratos, usando para isso os instrumentos de processos estocásticos e martingais. Apresentaremos alguns exemplos a título de ilustração. The dissertation aims to be an introduction to the study of financial markets in discrete time with finite horizon, as well as the dynamics of the main financial assets. We describe the types of assets traded in the market, focusing on contracts. We will elaborate the central hypothesis of the model, the absence of arbitrage and thus show how we can find a correct price or, at least, a range of prices of the contracts. Subsequently, we will show general results regarding how to find correct prices for contracts, using the machinery of stochastic processes and martingales.As an illustration, we present some examples.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.