Doctor of Philosophy / Department of Mathematics / Pietro Poggi-Corradini / This thesis contains six chapters. In the first chapter, the continuous and the discrete cases of p-modulus is introduced. We present properties of p-modulus and its connection to classical quantities. We also introduce use Arne Beurling's criterion for extremality to build insight and intuition regarding the modulus. After building an intuitive understanding of the p-modulus, we then proceed to switch perspectives to that of convex analysis. Using the theory of convex analysis, the uniqueness and existence of extremal densities is shown. We end this chapter with the introduction of the probabilistic interpretation of Modulus. In the second chapter, we introduce the Fulkerson duality. After defining the Fulkerson dual, we will investigate the blocking duality for different families of objects that the NODE research group has been studying and has been established. An important result that connects the Fulkerson dual and modulus is given at the end of this chapter. This important theorem will be used in proving one of the main results that [delta]p (introduced in Chapter 4) is a metric on graphs. The third chapter will discuss about metrics and ultrametrics on networks. Among these metrics, effective resistance is given special attention because the proof of [delta]p metric also serves as a new proof that effective resistance is a metric on graphs. We define effective resistance and give two different proves that show it is a metric, namely flows and the Laplacian. Two new families of metrics on graphs that arises through modulus are introduced in the fourth chapter. We also show how the two families are related as the d_p metric is viewed as a snowflaked version of the [delta]p metric. We end this chapter with some numerical examples that proves this connection and also serves as a set of plentiful examples of modulus calculations. Clutters and blockers is also another topic that is very much related to families of objects. While it has different rules and conditions, the study of clutters and blockers can give more insights to both modulus and clutters. We explore these relations in chapter 5. We provide some examples of clutters and blockers and finally reveal the relationship between the blocker and Fulkerson dual. Finally, in chapter 6, we end the thesis by presenting some of the open questions that we would like to explore and find answers in the future. In the second chapter, we introduce the Fulkerson duality. After defining the Fulkerson dual, we will investigate the blocking duality for different families of objects that the NODE research group has been studying and has been established. An important result that connects the Fulkerson dual and modulus is given at the end of this chapter. This important theorem will be used in proving one of the main results that delta_p (introduced in Chapter 4) is a metric on graphs. The third chapter will discuss about metrics and ultrametrics on networks. Among these metrics, effective resistance is given special attention because the proof of delta_p metric also serves as a new proof that effective resistance is a metric on graphs. We define effective resistance and give two different proves that show it is a metric, namely flows and the Laplacian. Two new families of metrics on graphs that arises through modulus are introduced in the fourth chapter. We also show how the two families are related as the d_p metric is viewed as a snowflaked version of the delta_p metric. We end this chapter with some numerical examples that proves this connection and also serves as a set of plentiful examples of modulus calculations. Clutters and blockers is also another topic that is very much related to families of objects. While it has different rules and conditions, the study of clutters and blockers can give more insights to both modulus and clutters. We explore these relations in chapter 5. We provide some examples of clutters and blockers and finally reveal the relationship between the blocker and Fulkerson dual. Finally, in chapter 6, we end the thesis by presenting some of the open questions that we would like to explore and find answers in the future.

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.

On étudie la distance de Prokhorov, la distance de Geffroy et la distance de Fortet-Mourier-Wasserstein. On résout en particulier le problème du calcul des distances. On traite quelques problèmes relatifs à l'estimation. Puis on donne une condition nécessaire et suffisante de non séparation asymptotique de deux chaines de Markov lorsque l'espace des états est de cardinal M

This thesis is concerned with the efficient computation of Jacobian matrices of nonlinear vector maps using automatic differentiation (AD). Specifically, we propose the use of two directed edge separator methods, the weighted minimum separator and natural order separator methods, to exploit the structure of the computational graph of the nonlinear system.This allows for the efficient determination of the Jacobian matrix using AD software. We will illustrate the promise of this approach with computational experiments.