Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano. / The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano. / The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.