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

[pt] VICTOR D ANGELO COLACINO

[pt] MARTINGAIS

[pt] CONTAGEM DE SUBGRAFOS

[pt] TEORIA DOS GRAFOS

[pt] TAXA DE CONVERGENCIA

[pt] TEOREMA CENTRAL DO LIMITE

[en] MARTINGALES

[en] SUBGRAPH COUNT

[en] GRAPH THEORY

[en] RATES OF CONVERGENCE

[en] CENTRAL LIMIT THEOREM

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

SIMON RICHARD GRIFFITHS

ROBERTO IMBUZEIRO MORAES FELINTO DE OLIVEIRA

SIMON RICHARD GRIFFITHS

GLAUCO VALLE DA SILVA COELHO

SILVIUS KLEIN

MATHEUS SECCO TORRES DA SILVA

2021-05-27

2021-01-28

[pt] TEXTO

application/pdf

PORTUGUÊS

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

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

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