Necessary and sufficient conditions are given for the existence of isomorphic decompositions of the complete bipartite graph, the complete graph with a hole, and the λ-fold complete graph into copies of a 4-cycle with a pendant edge.

A design is a set of points, V, together with a set of subsets of V called blocks. A classic type of design is a balanced incomplete block design, where every pair of points occurs together in a block the same number of times. This ‘balanced’ condition can be replaced with other properties. An adesign is a design where instead every pair of points occurs a different number of times together in a block. The number of times a specified pair of points occurs together is called the pair frequency. Here, a special type of adesign is explored, called a Sarvate-Beam design, named after its founders D.G. Sarvate and W. Beam. In such an adesign, the pair frequencies cover an interval of consecutive integers. Specifically the existence of Sarvate-Beam group divisible designs are investigated. A group divisible design, in the usual sense, is a set of points and blocks where the points are partitioned into subsets called groups. Any pair of points contained in a group have pair frequency zero and pairs of points from different groups have pair frequency one. A Sarvate-Beam group divisible design, or SBGDD, is a group divisible design where instead the frequencies of pairs from different groups form a set of distinct nonnegative consecutive integers. The SBGDD is said to be uniform when the groups are of equal size. The main result of this dissertation is to completely settle the existence question for uniform SBGDDs with blocks of size three where the smallest pair frequency, called the starting frequency, is zero. Higher starting frequencies are also considered and settled for all positive integers except when the SBGDD is partitioned into eight groups where a few possible exceptions remain. A relationship between these designs and graph decompositions is developed and leads to some generalizations. The use of matrices and linear programming is also explored and give rise to related results. / Graduate

In the study of design theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings and coverings of the complete digraph with each of the six transitive triples with a pendant arc.

Evolutionary game theory has recently emerged as a key paradigm in various behavioral science disciplines. In particular it provides powerful tools and a conceptual framework for the analysis of the time evolution of strategic interdependence among players and its consequences, especially when the players are spatially distributed and linked in a complex social network. We develop various evolutionary game models, analyze these models using appropriate techniques, and study their applications to complex phenomena. In the second chapter, we derive integro-differential equations as deterministic approximations of the microscopic updating stochastic processes. These generalize the known mean-field ordinary differential equations and provide powerful tools to investigate the spatial effects on the time evolutions of the agents' strategy choices. The deterministic equations allow us to identify many interesting features of the evolution of strategy profiles in a population, such as standing and traveling waves, and pattern formation, especially in replicator-type evolutions. We introduce several methods of decomposition of two player normal form games in the third chapter. Viewing the set of all games as a vector space, we exhibit explicit orthonormal bases for the subspaces of potential games, zero-sum games, and their orthogonal complements which we call anti-potential games and anti-zero-sum games, respectively. Perhaps surprisingly, every anti-potential game comes either from Rock-paper-scissors type games (in the case of symmetric games) or from Matching Pennies type games (in the case of asymmetric games). Using these decompositions, we prove old (and some new) cycle criteria for potential and zero-sum games (as orthogonality relations between subspaces). We illustrate the usefulness of our decompositions by (a) analyzing the generalized Rock-Paper-Scissors game, (b) completely characterizing the set of all null-stable games, (c) providing a large class of strict stable games, (d) relating the game decomposition to the Hodge decomposition of vector fields for the replicator equations, (e) constructing Lyapunov functions for some replicator dynamics, (f) constructing Zeeman games -games with an interior asymptotically stable Nash equilibrium and a pure strategy ESS. The hierarchical modeling of evolutionary games provides flexibility in addressing the complex nature of social interactions as well as systematic frameworks in which one can keep track of the interplay of within-group dynamics and between-group competitions. For example, it can model husbands and wives' interactions, playing an asymmetric game with each other, while engaging coordination problems with the likes in other families. In the fourth chapter, we provide hierarchical stochastic models of evolutionary games and approximations of these processes, and study their applications

No description available.

L'objectif de cette thèse est de réussir à utiliser des décompositions de graphes afin de résoudre des problèmes algorithmiques sur les graphes. Notre objet d'étude principal est la classe des graphes de Berge apprivoisés. Les graphes de Berge sont les graphes ne possédant ni cycle de longueur impaire supérieur à 4 ni complémentaire de cycle de longueur impaire supérieure à 4. Dans les années 60, Claude Berge a conjecturé que les graphes de Berge étaient des graphes parfaits. C'est-à-dire que la taille de la plus grande clique est exactement le nombre minimum de couleurs nécessaire à une coloration propre et ce pour tout sous-graphe. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont démontré cette conjecture en utilisant un théorème de structure: les graphes de Berge sont basiques ou admettent une décomposition. Ce résultat est très utile pour faire des preuves par induction. Cependant, une des décompositions du théorème, la skew-partition équilibrée, est très difficile à utiliser algorithmiquement. Nous nous focalisons donc sur les graphes de Berge apprivoisés, c'est-à-dire les graphes de Berge sans skew-partition équilibrée. Pour pouvoir faire des inductions, nous devons adapter le théorème destructure de Chudnovsky et al à notre classe. Nous prouvons un résultat plus fort: les graphes de Berge apprivoisés sont basiques ou admettent une décomposition telle qu'un côté de la décomposition soit toujours basique. Nous avons de plus un algorithme calculant cette décomposition. Nous utilisons ensuite notre théorème pour montrer que les graphes de Berge apprivoisés admettent la propriété du grand biparti, de la clique-stable séparation et qu'il existe un algorithme polynomial permettant de calculer le stable maximum. / The goal of this these is to use graph's decompositions to solve algorithmic problems on graphs. We will study the class of Berge tame graphs. A Berge graph is a graph without cycle of odd length at least 4 nor complement of cycle of odd length at least 4.In the 60's, Claude Berge conjectured that Berge graphs are perfect graphs. The size of the biggest clique is exactly the number of colors required to color the graph. In 2002, Chudnovsky, Robertson, Seymour et Thomas proved this conjecture using a theorem of decomposition: Berge graphs are either basic or have a decomposition. This is a useful result to do proof by induction. Unfortunately, one of the decomposition, the skew-partition, is really hard to use. We arefocusing here on Berge tame graphs, i.e~Berge graph without balanced skew-partition. To be able to do induction, we must first adapt the Chudnovsky et al's theorem of structure to our class. We prove a stronger result: Berge tame graphs are basic or have a decomposition such that one side is always basic. We also have an algorithm to compute this decomposition. We then use our theorem to prouve that Berge tame graphs have the big-bipartite property, the clique-stable set separation property and there exists a polytime algorithm to compute the maximum stable set.

La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.

Cette thèse contribue à l'approche économétrique de la croissance pro-pauvre. Elle présente des apports théoriques et empiriques. En premier lieu, elle présente les différentes définitions, indices et politiques de croissance pro-pauvre proposées dans la littérature théorique. Elle examine également les modèles théoriques et empiriques portant sur les interactions entre distribution du revenu et croissance. Elle montre que les mesures traditionnelles, en plus de leurs caractères partiels, peuvent conduire à des résultats contradictoires. Pour contourner ces limites, cette thèse privilégie l'approche alternative qui consiste à utiliser des modèles économétriques. Cette dernière approche, bien qu'elle présente l'avantage d'inclure l'ensemble des dimensions de la pauvreté, souffre de deux types de biais : le biais de sélection et le biais d'endogeneité. Ces derniers s'expliquent par les limitations inhérentes des données : erreurs de mesures, points aberrants. En outre, les résultats obtenus avec cette approche sont sensibles aux formes fonctionnelles choisies. Ainsi, il y'a de bonnes raisons d'utiliser la régression Gini. Malheureusement, les régressions de type Gini n'existaient qu'en coupe instantanée et en séries temporelles. Ainsi, dans un second temps, cette thèse propose d'étendre la réflexion sur la régression Gini en panel. Elle introduit les estimateurs intragroupes, intergroupes, le test d'existence de l'effet individuel et l'estimateur Aitken Gini. Enfin, cette thèse présente des applications empiriques qui illustrent de façon concrète la robustesse de nos estimateurs. Elle s'intéresse particulièrement aux conséquences de la méthode d'estimation et à la section de l'échantillon. Elle conclut que le processus de croissance favorise la réduction de la pauvreté à condition que les inégalités de revenu soient maîtrisées. Mais aussi, que l'impact de la croissance agricole sur la réduction de la pauvreté varie en fonction du niveau de développement du pays. / This thesis contributes to the econometric approach to pro-poor growth. It presents theoretical and empirical contributions. First, it presents the different definitions, indices and the policies of pro-poor growth proposed in the theoretical literature. It also examines the theoretical and empirical models on the interactions between income distribution and growth. It shows that the traditional measures, in addition to their partial characters, can lead to contradictory results. To avoid these limits this thesis emphasizes the alternative approach by using econometric models. The latter approach, although it has the advantage of including all the dimensions of poverty, suffering from two types of bias: selection bias and bias of endogeneity. These are due to the limitations of the data: measurement error, outliers. In addition, the results obtained with this approach are sensitive to selected functional forms. So, There are good reasons to use the Gini regression. Unfortunately, the Gini regressions existed only cross sectional and time series. Thus, in a second time, this thesis proposes to extend the Gini regression on the panel. It introduces within and between estimators, the individual effect test and the Gini Aitken estimator. Finally, this thesis presents empirical applications that illustrate the robustness of our estimators. She is particularly interested in the consequences of the estimation method and the sample section. It concludes that the growth process promotes poverty reduction when income inequalities are overcome. But also, the impact of agricultural growth on poverty reduction varies depending on the country's level of development.

No description available.

For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.   The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.     In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.