This thesis focuses on the use of extremal techniques in analyzing problems that historically have been associated with other areas of discrete mathematics. We establish new techniques for analyzing combinatorial problems with two different types of nonlinear orders, and then use them to solve important previously-open problems in mathematics. In addition, we use entropy techniques to establish a variety of bounds in the theory of sumsets. In the second chapter, we examine a problem of Furedi and Hajnal regarding forbidden patterns in (0,1)-matrices. We introduce a new technique that gives an asymptotically tight bound on the number of 1-entries that a (0,1)-matrix can contain while avoiding a fixed permutation matrix. We use this result to solve the Stanley-Wilf conjecture, a well-studied open problem in enumerative combinatorics. We then generalize the technique to give results on d-dimensional matrices. In the third chapter, we examine a problem of Pinchasi and Radoicic on cyclically order sets. To do so, we prove an upper bound on the sizes of such sets, given that their orders have the intersection reverse property. We then use this to give an upper bound on the number of edges that a graph can have, assuming that the graph can be drawn so that no cycle of length four has intersecting edges. This improves the previously best known bound and (up to a log-factor) matches the best known lower bound. This result implies improved bounds on a number of well-studied problems in geometric combinatorics, most notably the complexity of pseudo-circle arrangements. In the final chapter, we use entropy techniques to establish new bounds in the theory of sumsets. We show that such sets behave fractionally submultiplicatively, which in turn provides new Plunecke-type inequalities of the form first introduced by Gyarmati, Matolcsi, and Ruzsa.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-22T15:43:28Z (GMT). No. of bitstreams: 1 Rodrigues_ChristianeBuffo_M.pdf: 948322 bytes, checksum: be5636b0d15a131df52736cd4f4782d0 (MD5) Previous issue date: 2013 / Resumo: Este trabalho trata da aplicação do Método Simbólico na resolução de problemas de Combinatória. A vantagem desta técnica é o cálculo direto de uma expressão fechada para a Função Geradora F(z) do problema escrito como uma Série de Potências. Consequentemente garantimos a facilidade na enumeração da sequência que queremos a partir do coeficiente de zn de F(z). O desenvolvimento de nosso estudo foi feito aplicando-se o método a dois tipos de Classes: Rotuladas e não Rotuladas, apontando as diferenças básicas entre elas através de exemplos e resultados teóricos. Ao final, concluímos que a enumeração independe do tipo de modelagem feita para o problema / Abstract: This work deals with the application of the Symbolic Method in the solutions of combinatorial problems. The advantage of this technique is the direct calculus for the exact expression of the Generating Function F(z) of the problem, written as a Power Series. Consequently, we ensure the enumeration of the desired sequence, from the coefficient of zn of F(z). Our study was developed by applying the method in two types of Classes: Labeled and unlabelled, pointing the basic differences between them through examples and theoretical results. Finally, we concluded that the enumeration does not depend of the type of the model chosen for the problem / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Bacterial taxonomy is the science of classifying, naming, and identifying bacteria. The scope and practice of taxonomy has evolved through history with our understanding of life and our growing and changing needs in research, medicine, and industry. As in animal and plant taxonomy, the species is the fundamental unit of taxonomy, but the genetic and phenotypic diversity that exists within a single bacterial species is substantially higher compared to animal or plant species. Therefore, the current "type"-centered classification scheme that describes a species based on a single type strain is not sufficient to classify bacterial diversity, in particular in regard to human, animal, and plant pathogens, for which it is necessary to trace disease outbreaks back to their source. Here we discuss the current needs and limitations of classic bacterial taxonomy and introduce LINbase, a Web service that not only implements current species-based bacterial taxonomy but complements its limitations by providing a new framework for genome sequence-based classification and identification independently of the type-centric species. LINbase uses a sequence similarity-based framework to cluster bacteria into hierarchical taxa, which we call LINgroups, at multiple levels of relatedness and crowdsources users' expertise by encouraging them to circumscribe these groups as taxa from the genus-level to the intraspecies-level. Circumscribing a group of bacteria as a LINgroup, adding a phenotypic description, and giving the LINgroup a name using the LINbase Web interface allows users to instantly share new taxa and complements the lengthy and laborious process of publishing a named species. Furthermore, unknown isolates can be identified immediately as members of a newly described LINgroup with fast and precise algorithms based on their genome sequences, allowing species- and intraspecies-level identification. The employed algorithms are based on a combination of the alignment-based algorithm BLASTN and the alignment-free method Sourmash, which is based on k-mers, and the MinHash algorithm. The potential of LINbase is shown by using examples of plant pathogenic bacteria. / Doctor of Philosophy / Life is always easier when people talk to each other in the same language. Taxonomy is the language that biologists use to communicate about life by 1. classifying organisms into groups, 2. giving names to these groups, and 3. identifying individuals as members of these named groups. When most scientists and the general public think of taxonomy, they think of the hierarchical structure of “Life”, “Domain”, “Kingdom”, “Phylum”, “Class”, “Order”, “Family”, “Genus” and “Species”. However, the basic goal of taxonomy is to allow the identification of an organism as a member of a group that is predictive of its characteristics and to provide a name to communicate about that group with other scientists and the public. In the world of micro-organism, taxonomy is extremely important since there are an estimated 10,000,000 to 1,000,000,000 different bacteria species. Moreover, microbiologists and pathologists need to consider differences among bacterial isolates even within the same species, a level, that the current taxonomic system does not even cover. Therefore, we developed a Web service, LINbase, which uses genome sequences to classify individual microbial isolates. The database at the backend of LINbase assigns Life Identification Numbers (LINs) that express how individual microbial isolates are related to each other above, at, and below the species level. The LINbase Web service is designed to be an interactive web-based encyclopedia of microorganisms where users can share everything they know about micro-organisms, be it individual isolates or groups of isolates, for professional and scientific purposes. To develop LINbase, efficient computer programs were developed and implemented. To show how LINbase can be used, several groups of bacteria that cause plant diseases were classified and described.

Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.

In its theoretical part, this thesis sums up the basic knowledge concerning permutations. Besides the representation of permutations and determination of their fundamental characteristics, the theoretical part is, first of all, aimed at results concerning the decomposition of permutations into disjoint cycles and at finding the number of permutations with a certain characteristic. We introduce the fundamental bijection that is useful for solving many problems concerning the permutations. Further on, we focus on the number of permutations without a fixed point, Eulerian numbers expressing the number of permutations with a given number of descents, and the number of permutations with a given number of excedances, Stirling numbers of the first kind expressing the number of permutations with a given number of cycles, and Catalan numbers representing the number of permutations avoiding a chosen pattern of length three. Attention is also paid to the Gilbreath permutations and their characteristics. The practical part consists of 14 solved problems. The solutions rely on the results presented in the theoretical part, and there are deduced some further interesting results concerning random permutations.

Ce travail est la synthèse de travaux de recherches en mathématiques, dont les thèmes sont empruntés à la géométrie algébrique, la combinatoire analytique et les probabilités. La première partie concerne les variétés algébriques complexes de dimension trois. On y présente un calcul de la cohomologie singulière de variétés toriques lisses non complètes, ainsi que la construction d'un modèle toroïdal des singularités-quotient, dont le calcul nécessite l'étude combinatoire fine de l'action des groupes finis de matrices unitaires sur le plan projectif. La deuxième partie développe une adaptation "hybride" de la méthode de Darboux et de l'analyse des singularités pour le développement asymptotique des coefficients d'une série entière dans certains cas de frontière naturelle d'analyticité. De nombreux exemples issus de l'analyse combinatoire sont ainsi traités, dont celui de l'analyse d'algorithmes de factorisation de polynômes sur les corps finis qui sont utilisés en calcul formel et pour les codes correcteurs d'erreurs. La troisième partie résout une conjecture sur les arbres $m$-aires de recherche qui sont une structure fondamentale de l'algorithmiques des ensembles de données. Le modèle considéré est un modèle d'urnes qui se généralise en la notion de processus aléatoires de Pòlya dont le comportement asymptotique général est étudié. Dans la quatrième partie, on construit un arbre aléatoire associé à la \emph{Chaos Game Representation} utilisée en bio-mathématique et en bio-informatique du génôme. Les asymptotiques de la hauteur et de la profondeur d'insertion de ces arbres y sont établies.

L'un des objectifs principaux de l'imagerie par résonance magnétique fonctionnelle (IRMf) est la localisation in vivo et de manière non invasive des zones cérébrales associées à certaines fonctions cognitives. Le cerveau présentant une très grande variabilité anatomo-fonctionnelle inter-individuelle, les études d'IRMf incluent généralement plusieurs sujets et une analyse de groupe permet de résumer les résultats intra-sujets en une carte d'activation du groupe représentative de la population d'intérêt. L'analyse de groupe « standard » repose sur une hypothèse forte d'homogénéité des effets estimés à travers les sujets. Dans un premier temps, nous étudions la validité de cette hypothèse par une méthode multivariée diagnostique et un test de normalité univarié (le test de Grubbs). L'application de ces méthodes sur une vingtaine de jeux de données révèle la présence fréquente de données atypiques qui peuvent invalider l'hypothèse d'homogénéité. Nous proposons alors d'utiliser des statistiques de décision robustes calibrées par permutations afin d'améliorer la spécificité et la sensibilité des tests statistiques pour l'analyse de groupe. Puis nous introduisons de nouvelles statistiques de décision à effets mixtes fondées sur le rapport de vraisemblances maximales, permettant de pondérer les sujets en fonction de l'incertitude sur l'estimation de leurs effets. Nous confirmons sur des jeux de données que ces nouvelles méthodes d'inférence permettent un gain en sensibilité significatif, et nous fournissons l'ensemble des outils développés lors de cette thèse à la communauté de neuro-imagerie dans le logiciel DISTANCE.

.

Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage.

El tema d'aquesta tesi és l'enumeració de permutacions amb subseqüències prohibides respecte a certs estadístics, i l'enumeració de permutacions que eviten subseqüències generalitzades.Després d'introduir algunes definicions sobre subseqüències i estadístics en permutacions i camins de Dyck, comencem estudiant la distribució dels estadístics -nombre de punts fixos' i -nombre d'excedències' en permutacions que eviten una subseqüència de longitud 3. Un dels resultats principals és que la distribució conjunta d'aquest parell de paràmetres és la mateixa en permutacions que eviten 321 que en permutacions que eviten 132. Això generalitza un teorema recent de Robertson, Saracino i Zeilberger. Demostrem aquest resultat donant una bijecció que preserva els dos estadístics en qüestió i un altre paràmetre. La idea clau consisteix en introduir una nova classe d'estadístics en camins de Dyck, basada en el que anomenem túnel.A continuació considerem el mateix parell d'estadístics en permutacions que eviten simultàniament dues o més subseqüències de longitud 3. Resolem tots els casos donant les funcions generadores corresponents. Alguns casos són generalitzats a subseqüències de longitud arbitrària. També descrivim la distribució d'aquests paràmetres en involucions que eviten qualsevol subconjunt de subseqüències de longitud 3. La tècnica principal consisteix en fer servir bijeccions entre permutacions amb subseqüències prohibides i certs tipus de camins de Dyck, de manera que els estadístics en permutacions que considerem corresponen a estadístics en camins de Dyck que són més fàcils d'enumerar.Tot seguit presentem una nova família de bijeccions del conjunt de camins de Dyck a sí mateix, que envien estadístics que apareixen en l'estudi de permutacions amb subseqüències prohibides a estadístics clàssics en camins de Dyck, la distribució dels quals s'obté fàcilment. En particular, això ens dóna una prova bijectiva senzilla de l'equidistribució de punts fixos en les permutacions que eviten 321 i en les que eviten 132. A continuació donem noves interpretacions dels nombres de Catalan i dels nombres de Fine. Considerem una classe de permutacions definida en termes d'aparellaments de 2n punts en una circumferència sense creuaments. N'estudiem l'estructura i algunes propietats, i donem la distribució de diversos estadístics en aquests permutacions.En la següent part de la tesi introduïm una noció diferent de subseqüències prohibides, amb el requeriment que els elements que formen la subseqüència han d'aparèixer en posicions consecutives a la permutació. Més en general, estudiem la distribució del nombre d'ocurrències de subparaules (subseqüències consecutives) en permutacions. Resolem el problema en diversos casos segons la forma de la subparaula, obtenint-ne les funcions generadores exponencials bivariades corresponents com a solucions de certes equacions diferencials lineals. El mètode està basat en la representació de permutacions com a arbres binaris creixents i en mètodes simbòlics.La part final tracta de subseqüències generalitzades, que extenen tant la noció de subseqüències clàssiques com la de subparaules. Per algunes subseqüències obtenim nous resultats enumeratius. Finalment estudiem el comportament assimptòtic del nombre de permutacions de mida n que eviten una subseqüència generalitzada fixa quan n tendeix a infinit. També donem fites inferiors i superiors en el nombre de permutacions que eviten certes subseqüències.