[pt] O MÉTODO DE EQUAÇÕES DIFERENCIAIS E CONJUNTOS INDEPENDENTES EM HIPERGRAFOS

[en] THE DIFFERENTIAL EQUATIONS METHOD AND INDEPENDENT SETS IN HYPERGRAPHS

[pt] IGOR ALBUQUERQUE ARAUJO

[pt] MARTINGAIS

[pt] HIPERGRAFOS

[pt] GRAFOS ALEATORIOS

[pt] METODO DE EQUACAO DIFERENCIAL

[pt] PROCESSOS ALEATORIOS

[en] MARTINGALES

[en] HYPERGRAPHS

[en] RANDOM GRAPHS

[en] DIFFERENTIAL EQUATIONS METHOD

[en] RANDOM PROCESSES

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

SIMON RICHARD GRIFFITHS

NICOLAU CORCAO SALDANHA

ROBERTO IMBUZEIRO MORAES FELINTO DE OLIVEIRA

ROBERT DAVID MORRIS

SIMON RICHARD GRIFFITHS

2019-09-18

2019-06-24

[pt] TEXTO

application/pdf

INGLÊS

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

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

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