1 |
[pt] DESVIOS MODERADOS DO NÚMERO DE TRIÂNGULOS EM GRAFOS ALEATÓRIOS ESPARSOS / [en] MODERATE DEVIATIONS OF TRIANGLE COUNTS IN SPARSE RANDOM GRAPHSLEONARDO GONCALVES DE OLIVEIRA 09 November 2022 (has links)
[pt] Na primeira parte dessa tese, estudamos o desvio no número de triângulos
com respeito à média em ambos os modelos de grafos aleatórios G(n,m) e
G(n, p). Focamos no caso em que o grafo aleatório é esparso, no qual a densidade
de arestas vai para zero quando o número de vértices cresce para o
infinito. Nosso foco também reside no caso de desvios moderados, i.e., aqueles
cuja ordem está entre o desvio padrão e a média. Além disso, também derivamos
o mesmo tipo de resultado para cerejas (caminhos de comprimento dois).
Na segunda parte dessa tese, estudamos a desigualdade de Freedman. Essa desigualdade
fornece limitantes para a probabilidade de desvio de um martingal
limitado usando sua variância condicional. No nosso trabalho, obtemos uma
versão mais forte da desigualdade de Freedman, impondo condições adicionais
de simetria nos incrementos do processo martingal. / [en] In the first part of this thesis, we study the deviation of the number of
triangles with respect to its mean in both the random graph models G(n,m)
and G(n, p). We focus on the case where the random graph is sparse, in which
the edge density goes to zero as the number of vertices increases to infinity.
Also, our focus is in the case of moderate deviations, i.e., those of order in
between the standard deviation and the mean. In addition, we derive the same
kind of results for cherries (paths of length two). In the second part of this
thesis, we study Freedman s inequality. This inequality gives bounds on the
probability of the deviation of a bounded martingale using its conditional
variance. In our work, we obtain a strengthening of Freedman s inequality,
under additional symmetry conditions on the increments of the martingale
process.
|
2 |
[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.
|
3 |
[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.03 seconds