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

• Ano de defesa: 2019
• Autor(a) principal: IGOR ALBUQUERQUE ARAUJO
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [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
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=45389&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=45389&idi=2; http://doi.org/10.17771/PUCRio.acad.45389

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