Spelling suggestions: "subject:"martingales."" "subject:"martingale.""
11 |
[en] RATE OF CONVERGENCE OF THE CENTRAL LIMIT THEOREM FOR THE MARTINGALE EXPRESSION OF DEVIATIONS OF TRIANGLE-FREE SUBGRAPH COUNTS IN G(N,M) RANDOM GRAPHS / [pt] TAXA DE CONVERGÊNCIA DO TEOREMA CENTRAL DO LIMITE PARA A EXPRESSÃO MARTINGAL DE DESVIO DA CONTAGEM DE SUBGRAFOS LIVRES DE TRIÂNGULOS EM GRAFOS ALEATÓRIOS G(N,M)VICTOR D ANGELO COLACINO 27 May 2021 (has links)
[pt] 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. / [en] 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.
|
12 |
[pt] O MÉTODO DE EQUAÇÕES DIFERENCIAIS E CONJUNTOS INDEPENDENTES EM HIPERGRAFOS / [en] THE DIFFERENTIAL EQUATIONS METHOD AND INDEPENDENT SETS IN HYPERGRAPHSIGOR ALBUQUERQUE ARAUJO 18 September 2019 (has links)
[pt] Nesta dissertação, discutiremos o método de equações diferenciais de Wormald, que possui muitas aplicações recentes em Combinatória. Esse método explora a interação entre a matemática discreta e contínua e pode ser usado para provar concentração em uma grande quantidade de processos aleatórios discretos. Em particular, estudaremos o processo livre de H e o algoritmo guloso aleatório para gerar conjuntos independentes em hipergrafos. Esses processos tem sido amplamente estudados nos últimos
anos, culminando com o recente grande avanço de Tom Bohman e Patrick Bennett em 2016, que obtiveram uma cota inferior para hipergrafos com certas condições de densidade. Nós não só reproduzimos sua demonstração mas também obtemos um resultado mais forte (expandindo seu resultado para hipergrafos mais esparsos) e analisamos o caso de hipergrafos lineares, com o intuito de progredir rumo a uma conjectura de Johnson e Pinto sobre o processo livre de Q2 no hipercubo Qd. / [en] In this dissertation, we will discuss Wormald s differential equations method, which has recently had many intriguing applications in Combinatorics. This method explores the interplay between discrete and continuous mathematics and it can be used to prove concentration in a number of discrete random processes. In particular, we will discuss the H-free process and the random greedy algorithm to obtain independent sets in hypergraphs. These processes had been extensively studied through the past few years, culminating in the recent breakthrough of Tom Bohman and Patrick Bennett in 2016, who obtained a lower bound for hypergraphs with certain density conditions. We not only reproduce the proof given by them but also obtain a stronger result (expanding their result to sparser hypergraphs) and we analyze the case of linear hypergraphs, in order to make progress towards a conjecture by Johnson and Pinto concerning the Q2-free process in the hypercube Qd.
|
13 |
[pt] DUAS ABORDAGENS EM DESVIOS MODERADOS PARA CONTAGEM DE TRIÂNGULOS EM GRAFOS G(N, M) / [en] TWO APPROACHES TO MODERATE DEVIATIONS IN TRIANGLE COUNT IN G(N, M) GRAPHSGABRIEL DIAS DO COUTO 04 August 2022 (has links)
[pt] O estudo de desvios, e em particular grandes desvios, tem uma história
longa na teoria de probabilidade. Nas últimas décadas muitos artigos consideraram essas questões no contexto de subgrafos de grafos aleatórios G(n, p) e
G(n, m). Esta dissertação considera a cauda inferior para o número de triângulos no grafo aleatório G(n, m). Duas abordagens estão consideradas: Martingales, a partir artigo de Christina Goldschmidt, Simon Griffiths e Alex Scott; e
Teoria Espectral de Grafos, a partir do artigo de Joe Neeman, Charles Radin e
Lorenzo Sadun. Essas duas abordagens conseguem encontrar o comportamento
da cauda em dois regimes diferentes. Na dissertação discutiremos a visão geral
do artigo de Goldschmidt, Griffiths e Scott, e discutiremos em detalhes o artigo de Neeman, Radin e Sadun. Em particular, exploraremos a conexão entre
a cauda inferior do número de triângulos e o comportamento dos autovalores mais negativos da matriz de adjacência. Veremos que a contagem tende a
depender, essencialmente, do autovalor mais negativo. / [en] The study of deviations, and in particular large deviations, has a long
history in Probability Theory. In recent decades many articles have considered
these questions in the context of subgraphs of the random graphs G(n, p) and
G(n, m). This dissertation considers the lower tail for the number of triangles in
the random graph G(n, m). Two approaches are considered: Martingales, based
on the article of Christina Goldschmidt, Simon Griffiths and Alex Scott; and
Spectral Graph Theory, based on the article of Joe Neeman, Charles Radin and
Lorenzo Sadun. These two approaches manage to find the behavior of the tail
in two different regimes. In this dissertation we give an overview of the article of
Goldschmidt, Griffiths and Scott, discuss in detail the article of artigo Neeman,
Radin and Sadun. In particular, we shall explore the connection between the
lower tail of the number of triangles and the behavior of the most negative
eigenvalues of the adjacency matrix. We shall see that the triangle count tends
to especially depend on the most negative eigenvalue.
|
Page generated in 0.0395 seconds