Defesa de Tese.

Banca examinadora: Robert Morris (IMPA) Carlos Gustavo Moreira (IMPA Maurício Collares (UFMG) Guilherme Oliveira Mota (Usp) Simon Griffiths (PUC Rio) Suplente: Roberto Imbuzeiro (IMPA)

Abstract: In this thesis we study extremal properties of random and pseudorandom structures. In Erdös-Rényi random graph we focus on the class of bounded degree trees, proving an approximate random analogue of the Erdös-Sós conjecture and applying it to extend to this setting a theorem of Chvátal on the Ramsey goodness of trees. In the pseudorandom setting, we focus on 3-uniform hypergraphs and provide asymptotically optimal conditions for Hamiltonicity. First we prove that with high probability every subgraph of G(n,p) contains every linear sized tree with bounded degree, provided that p is above a natural threshold. We prove this result for trees with asymptotically best size and with best possible density of the random graphs, up to a constant factor. This is a sparse analogue of the Erdös-Sós conjecture that states that every graph with every degree d contains every tree with d edges. Secondly we apply this result to extend, to the setting of random graphs, a theorem due to Chvátal that concerns the Ramsey number of trees and cliques. More precisely, we find density thresholds of a random graph G(n,p) that ensure that with high probability every red-blue coloring of the edges of G(n,p) contains a blue clique or a red copy of each bounded degree tree of appropriate sizes. Finally we study sufficient conditions for the existence of Hamilton cycles in hypergraphs. We consider 3-uniform hypergraphs H on n vertices, with minimum degree of order n², such that for any set of vertices X and for any collection P of pairs of vertices, the number of hyperedges composed by a pair belonging to P and one vertex from X is at least roughly |X||P|/4. We show that hypergraphs with these properties contain a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context .