[pt] DESVIOS MODERADOS DO NÚMERO DE TRIÂNGULOS EM GRAFOS ALEATÓRIOS ESPARSOS

[en] MODERATE DEVIATIONS OF TRIANGLE COUNTS IN SPARSE RANDOM GRAPHS

[pt] LEONARDO GONCALVES DE OLIVEIRA

[pt] MARTINGAIS

[pt] DESIGUALDADES DE CONCENTRACAO

[pt] DESVIOS MODERADOS

[pt] GRAFOS ALEATORIOS

[en] MARTINGALES

[en] CONCENTRATION INEQUALITIE

[en] MODERATE DEVIATIONS

[en] RANDOM GRAPHS

[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.

SIMON RICHARD GRIFFITHS

MARCOS CRAIZER

ROBERTO IMBUZEIRO MORAES FELINTO DE OLIVEIRA

ROBERT DAVID MORRIS

SIMON RICHARD GRIFFITHS

JOSE DIEGO ALVARADO MORALES

LEANDRO PINTO RODRIGUES PIMENTEL

2022-11-09

2022-09-28

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61161@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61161@2

https://doi.org/10.17771/PUCRio.acad.61161