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.

Este trabalho tem por objetivo estudar algumas variações do teorema de Banach- Stone. Elas podem ser encontradas no artigo Variations on the Banach- Stone Theorem, [14]. Além disso, apresentamos um resultado, provado por D. Amir em [1], que generaliza a versão clássica do Teorema de Banach- Stone. Consideramos os espaços C(K) e C(L), que representam os espaços de funções contínuas de K em R e de L em R respectivamente, onde K e L são espaços Hausdor compactos. O enunciado da versão clássica do teorema de Banach- Stone é a seguinte: \"Sejam K e L espaços Hausdor compactos. Então C(K) é isométrico a C(L) se e somente se, K e L são homeomorfos\". Apresentamos a primeira das variações que considera isomorfismo entre álgebras e foi feita por Gelfand e Kolmogoro em [15], no ano de 1939. A segunda versão apresentada trata de isomorfismo isométrico e a demonstração é originalmente devida a Arens e Kelley e é encontrada em [2]. Finalmente, estudamos o teorema provado por D. Amir e apresentado em [1]. Este teorema generaliza o teorema clássico de Banach- Stone e tem o seguinte enunciado: Se K e L são espaços Hausdor compactos e T é um isomorfismo linear de C(K) sobre C(L), com ||T||.||T^||< 2 então K e L são homeomorfos / This work aims to study some variations of the Banach- Stone theorem. They can be found in the article Variations on the Banach- Stone Theorem, [14]. In addition, we present a result, proved by D. Amir in [1], that generalizes the classic version of the Theorem Banach- Stone. We consider the spacesC(K) andC(L), representing the spaces of continuous functions from K into R and from L into R respectively, where K and L are compact Hausdor spaces. The wording of the classic version of the Banach- Stone theorem is as follows: \"Let K e L be compact Haudor spaces. Then C(K) isisometrictoC(L) if,andonlyif, K and L are homeomorphic\".Here the first of the variations that considers isomorphism between algebras and was made by Gelfand and Kolmogoro in [15], in 1939. The second version presented is about isometric isomorphisms and the demonstration is originally due to Arens and Kelley and it is found in [2]. Finally, we study the theorem proved by D. Amir and presented in [1]. This theorem generalizes the classical theorem Banach- Stone and states the following: \"Let K e L be compact Haudor spaces and let T be a linear isomorphism from C(K) into C(L), with ||T||.||T^||< 2. Then K and L are homeomorphic\".

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.

Este trabalho tem por objetivo estudar algumas variações do teorema de Banach- Stone. Elas podem ser encontradas no artigo Variations on the Banach- Stone Theorem, [14]. Além disso, apresentamos um resultado, provado por D. Amir em [1], que generaliza a versão clássica do Teorema de Banach- Stone. Consideramos os espaços C(K) e C(L), que representam os espaços de funções contínuas de K em R e de L em R respectivamente, onde K e L são espaços Hausdor compactos. O enunciado da versão clássica do teorema de Banach- Stone é a seguinte: \"Sejam K e L espaços Hausdor compactos. Então C(K) é isométrico a C(L) se e somente se, K e L são homeomorfos\". Apresentamos a primeira das variações que considera isomorfismo entre álgebras e foi feita por Gelfand e Kolmogoro em [15], no ano de 1939. A segunda versão apresentada trata de isomorfismo isométrico e a demonstração é originalmente devida a Arens e Kelley e é encontrada em [2]. Finalmente, estudamos o teorema provado por D. Amir e apresentado em [1]. Este teorema generaliza o teorema clássico de Banach- Stone e tem o seguinte enunciado: Se K e L são espaços Hausdor compactos e T é um isomorfismo linear de C(K) sobre C(L), com ||T||.||T^||< 2 então K e L são homeomorfos / This work aims to study some variations of the Banach- Stone theorem. They can be found in the article Variations on the Banach- Stone Theorem, [14]. In addition, we present a result, proved by D. Amir in [1], that generalizes the classic version of the Theorem Banach- Stone. We consider the spacesC(K) andC(L), representing the spaces of continuous functions from K into R and from L into R respectively, where K and L are compact Hausdor spaces. The wording of the classic version of the Banach- Stone theorem is as follows: \"Let K e L be compact Haudor spaces. Then C(K) isisometrictoC(L) if,andonlyif, K and L are homeomorphic\".Here the first of the variations that considers isomorphism between algebras and was made by Gelfand and Kolmogoro in [15], in 1939. The second version presented is about isometric isomorphisms and the demonstration is originally due to Arens and Kelley and it is found in [2]. Finally, we study the theorem proved by D. Amir and presented in [1]. This theorem generalizes the classical theorem Banach- Stone and states the following: \"Let K e L be compact Haudor spaces and let T be a linear isomorphism from C(K) into C(L), with ||T||.||T^||< 2. Then K and L are homeomorphic\".

In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\{1,2,\ldots,t\}$ (for some integer $t\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\{1,2,\ldots,t\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \in \{2k-1, 2k\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\sqrt{\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \ge \Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\{x_1,\ldots ,x_k\}$ and $\{y_1,\dots,y_k\}$ there are directed vertex disjoint paths $P_1,\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.

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.

This thesis lies in the field of probabilistic and extremal combinatorics: we study discrete structures, with a focus on thresholds, when the behaviour of a structure changes from one mode into another. From a probabilistic perspective, we consider models for a random structure depending on some parameter. The questions we study are then: When (i.e. for what values of the parameter) does the probability of a given property go from being almost 0 to being almost 1? How do the models behave as this transition occurs? From an extremal perspective, we study classes of structures depending on some parameter. We are then interested in the following questions: When (for what value of the parameter) does a particular property become unavoidable? What do the extremal structures look like? The topics covered in this thesis are random geometric graphs, dependent percolation, extremal hypergraph theory and combinatorics in the hypercube.

The focus of this thesis is extremal dependence among spatial observations. In particular, this research extends the notion of the extremogram to the spatial process setting. Proposed by Davis and Mikosch (2009), the extremogram measures extremal dependence for a stationary time series. The versatility and flexibility of the concept made it well suited for many time series applications including from finance and environmental science. After defining the spatial extremogram, we investigate the asymptotic properties of the empirical estimator of the spatial extremogram. To this end, two sampling scenarios are considered: 1) observations are taken on the lattice and 2) observations are taken on a continuous region in a continuous space, in which the locations are points of a homogeneous Poisson point process. For both cases, we establish the central limit theorem for the empirical spatial extremogram under general mixing and dependence conditions. A high level overview is as follows. When observations are observed on a lattice, the asymptotic results generalize those obtained in Davis and Mikosch (2009). For non-lattice cases, we define a kernel estimator of the empirical spatial extremogram and establish the central limit theorem provided the bandwidth of the kernel gets smaller and the sampling region grows at proper speeds. We illustrate the performance of the empirical spatial extremogram using simulation examples, and then demonstrate the practical use of our results with a data set of rainfall in Florida and ground-level ozone data in the eastern United States. The second part of the thesis is devoted to bootstrapping and variance estimation with a view towards constructing asymptotically correct confidence intervals. Even though the empirical spatial extremogram is asymptotically normal, the limiting variance is intractable. We consider three approaches: for lattice data, we use the circular bootstrap adapted to spatial observations, jackknife variance estimation, and subsampling variance estimation. For data sampled according to a Poisson process, we use subsampling methods to estimate the variance of the empirical spatial extremogram. We establish the (conditional) asymptotic normality for the circular block bootstrap estimator for the spatial extremogram and show L2 consistency of the variance estimated by jackknife and subsampling. Then, we propose a portmanteau style test to check the existence of extremal dependences at multiple lags. The validity of confidence intervals produced from these approaches and a portmanteau style test are demonstrated through simulation examples. Finally, we illustrate this methodology to two data sets. The first is the amount of rainfall over a grid of locations in northern Florida. The second is ground-level ozone in the eastern United States, which are recorded on an irregularly spaced set of stations.

No description available.