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.

No description available.

With the fast growth of data-intensive distributed systems today, more novel and principled approaches are needed to improve the system efficiency, ensure the service quality to satisfy the user requirements, and lower the system running cost. This dissertation studies the design issues in the data-intensive distributed systems, which are differentiated from other systems by the heavy workload of data movement and are characterized by the fact that the destination of each data flow is limited to a subset of available locations, such as those servers holding the requested data. Besides, even among the feasible subset, different locations may result in different performance. The studies in this dissertation improve the data-intensive systems by exploiting the data storage location flexibility. It addresses how to reasonably determine the data placement based on the measured request patterns, to improve a series of performance metrics, such as the data access latency, system throughput and various costs, by the proposed hypergraph models for data placement. To implement the proposal with a lower overhead, a sketch-based data placement scheme is presented, which constructs the sparsified hypergraph under a distributed and streaming-based system model, achieving a good approximation on the performance improvement. As the network can potentially become the bottleneck of distributed data-intensive systems due to the frequent data movement among storage nodes, the online data placement by reinforcement learning is proposed which intelligently determines the storage locations of each data item at the moment that the item is going to be written or updated, with the joint-awareness of network conditions and request patterns. Meanwhile, noticing that distributed memory caches are effective measures in lowering the workload to the backend storage systems, the auto-scaling of memory cache clusters is studied, which tries to balance the energy cost of the service and the performance ensured. As the outcome of this dissertation, the designed schemes and methods essentially help to improve the running efficiency of data-intensive distributed systems. Therefore, they can either help to improve the user-perceived service quality under the same level of system resource investment, or help to lower the monetary expense and energy consumption in maintaining the system under the same performance standard. From the two perspectives, both the end users and the system providers could obtain benefits from the results of the studies. / Graduate

In this thesis, we bring forward the study of the spectral properties of graphs and we extend this theory for chemical hypergraphs, a new class of hypergraphs that model chemical reaction networks.

Graph polynomials are polynomials associated to graphs that encode the number of subgraphs with given properties. We list different frameworks used to define graph polynomials in the literature. We present the edge elimination polynomial and introduce several graph polynomials equivalent to it. Thereby, we connect a recursive definition to the counting of colorings and to the counting of (spanning) subgraphs. Furthermore, we define a graph polynomial that not only generalizes the mentioned, but also many of the well-known graph polynomials, including the Potts model, the matching polynomial, the trivariate chromatic polynomial and the subgraph component polynomial. We proof a recurrence relation for this graph polynomial using edge and vertex operation. The definitions and statements are given in such a way that most of them are also valid in the case of hypergraphs.

Large chemical reaction networks often exhibit distinctive features that can be interpreted as higher-level structures. Prime examples are metabolic pathways in a biochemical context. We review mathematical approaches that exploit the stoichiometric structure, which can be seen as a particular directed hypergraph, to derive an algebraic picture of chemical organizations. We then give an alternative interpretation in terms of set-valued set functions that encapsulate the production rules of the individual reactions. From the mathematical point of view, these functions define generalized topological spaces on the set of chemical species. We show that organization-theoretic concepts also appear in a natural way in the topological language. This abstract representation in turn suggests the exploration of the chemical meaning of well-established topological concepts. As an example, we consider connectedness in some detail.

In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on n vertices that contains each of the many possible graphs of a smaller size k < n as an induced subgraph. A hypergraph is a discrete structure on n vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. If a 3-uniform hypergraph can have edges colored one of a colors, then it is called a 3-uniform hypergraph with a colors. Analogously with universal graphs, a universal, induced, 3-uniform, k-hypergraph, with a possible edge colors is then defined to be a 3-uniform a-colored hypergraph on n vertices that contains each of the many possible 3-uniform a-colored hypergraphs on k vertices, k < n. In this thesis, we study conditions for the existence of a such a universal hypergraph, and address the question of how large n must be, given a fixed k, so that hypergraphs on n vertices are universal with high probability. This extends the work of Alon, [2] who studied the case of a = 2, and that too for graphs (not hypergraphs).

Traditionally, optimization problems in operations research have been studied in a complete information setting; the input/data is collected and made fully accessible to the user, before an algorithm is sequentially run to generate the optimal output. However, the growing magnitude of treated data and the need to make immediate decisions are increasingly shifting the focus to optimizing under incomplete information settings. The input can be partially inaccessible to the user either because it is generated continuously, contains some uncertainty, is too large and cannot be stored on a single machine, or has a hidden structure that is costly to unveil. Many problems providing a context for studying algorithms when the input is not entirely accessible emanate from the field of matching theory, where the objective is to pair clients and servers or, more generally, to group clients in disjoint sets. Examples include ride-sharing and food delivery platforms, internet advertising, combinatorial auctions, and online gaming. In this thesis, we study three different novel problems from the theory of matchings. These problems correspond to situations where the input is hidden, spread across multiple processors, or revealed in two stages with some uncertainty. In particular, we present in Chapter 1 the necessary definitions and terminology for the concepts and problems we cover. In Chapter 2, we consider a two-stage robust optimization framework that captures matching problems where one side of the input includes some future demand uncertainty. We propose two models to capture the demand uncertainty: explicit and implicit scenarios. Chapters 3 and 4 see us switch our attention to matchings in hypergraphs. In Chapter 3, we consider the problem of learning hidden hypergraph matchings through membership queries. Finally, in Chapter 4, we study the problem of finding matchings in uniform hypergraphs in the massively parallel computation (MPC) model where the data (e.g. vertices and edges) is distributed across the machines and in each round, a machine performs local computation on its fragment of data, and then sends messages to other machines for the next round.

This thesis contributes to the methodology and application of network theory, the study of graphs as a representation of real systems. In particular, we present four essays on problems related to social network analysis, link analysis, and biological network analysis. Chapters 1 and 2 present two pieces of work on social network analysis, where we model and optimize product diffusion through Word-of-Mouth on social networks. Specifically, we use a directed graph and a limiting case of the Erdős–Rényi random graph to respectively model exact and approximate social network structures. We then build mathematical models to describe how information diffuses among connected individuals in these networks. Using our network-based diffusion models, we design algorithms to optimally control product diffusion and maximize revenue from influencer marketing and referral marketing. Chapter 3 explores link analysis of crowd-sourced data on user-item ratings. We represent these ratings with a bipartite network containing user vertices and item vertices. Such a network representation encodes crucial relationship information among users and items that are not apparent from isolated ratings. We propose network-based algorithms to extract useful information from the structure of the bipartite network to predict award outcomes. In using movie ratings data to predict Academy Award nominees and winners, our proposed algorithms significantly outperform other rating-based baselines and state-of-the-art algorithms. Our algorithms can also predict award outcomes and future item popularity in other domains such as books, music, and dramas where user-item ratings are available, without task-specific feature engineering. Chapter 4 is inspired by an application of biological network analysis: learning effective drug combinations, which can be cast as the problem of learning a hidden hypergraph with n vertices and m hyperedges, where a vertex corresponds to a drug and a hyperedge represents a minimal set of drugs that are an effective treatment. We can learn the hidden hyperedges using membership queries: each query corresponds to a test evaluating whether a subset of the drugs is effective. If the query result is positive, then it means that the tested subset contains at least one hyperedge. We propose the first algorithms with poly(n, m) query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.

Le but des modèles traditionnels en classification (comme les partitions et les hiérarchies de parties) est de permettre de discriminer sans ambiguïté et donc de produire des classes non empiétantes (i.e. l’intersection de deux classes est vide ou une classe est incluse dans l'autre). Cependant, cette exigence de non ambiguïté peut conduire à occulter de l’information. Dans le cas des plantes hybrides en biologie par exemple ou encore de textes appartenant à plusieurs genres en analyse textuelle. Les modèles généraux comme les hypergraphes ou les treillis permettent de prendre en compte l’empiétance entre les classes. Plus précisément, les modèles dits "totalement équilibrés" autorisent l'empiétance tout en conservant certaines contraintes utiles en classification.En apprentissage automatique, les arbres de décision, très utilisés pour leur simplicité d'utilisation et de compréhension réalisent à chaque étape un partitionnement d'un ensemble en deux sous-ensembles.Nous montrons dans ce travail différents liens entre la classification traditionnelle et l'apprentissage automatique supervisé et montrons certains apports que chacun des deux mondes peut faire à l'autre.Nous proposons deux méthodes de classification mêlant les deux univers puis étendons la notion de binarité, très utilisée dans le cas des arbres, aux hypergraphes et aux treillis. Nous montrons alors l'équivalence entre les systèmes binarisables et les systèmes totalement équilibrés, faisant de ces derniers de parfaits candidats à la réalisation de modèles de classification en classes empiétantes. Nous proposons également diverses approximations de systèmes par des systèmes totalement équilibrés. / Traditionally, classification models (such as partitions and hierarchies) aim at separating without ambiguities and produce non-overlapping clusters (i.e two clusters are either disjoint or one is included in the other). However, this non ambiguity may lead to mask information such as in the case of hybrid plants in biology or of texts which belong to two (or more) different genres in textual analysis for instance. General models like hypergraphs or lattices allow to take into account overlapping clusters. More precisely, "totally balanced" models allows class infringement and presents some useful constraints for classification.In machine learning, decision trees are a widely used model as they are simple to use and understand. They are also based on the idea of partition of sets.We show in this work different links between traditional classification and supervised machine learning and show what each world can bring to the other.We propose two methods of classification which link the two universes. We then extend the notion of binarity, widely-used for trees, to hypergraphs and lattices. We show the equivalence between binarizable systems and totally balanced systems, which makes of totally balanced structures a great candidate for classification models with class infringement. We also propose some approximation methods of any system (lattice, hypergraph, dissimilarity) by a totally balanced one.