We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work.

Motivated by primality and integer factorization, this thesis introduces generalizations of standard binary multiplication to commutative n-ary operations based upon geometric construction and representation. This class of operations are constructed to preserve commutativity and identity so that binary multiplication is included as a special case, in order to preserve relationships with ordinary multiplicative number theory. This leads to a study of their expression in terms of elementary symmetric polynomials, and connections are made to results from the theory of polyadic (n-ary) groups. Higher order operations yield wider factorization and representation possibilities which correspond to reductions in the set of primes as well as tiered notions of primality. This comes at the expense of familiar algebraic properties such as associativity, and unique factorization. Criteria for primality and a naive testing algorithm are given for the ternary arithmetic, drawing heavily upon modular arithmetic. Finally, connections with the theory of partitions of integers and quadratic forms are discussed in relation to questions about cardinality of primes.

Cette thèse se situe à l'interface de la combinatoire énumérative et algébrique et porte sur l'étude des probabilités du processus d'exclusion partiellement asymétrique (PASEP).Dans un premier temps, nous démontrons bijectivement une conjecture de Novelli-Thibon-Williams concernant l'interprétation combinatoire de coefficients de matrices de transition dans l'algèbre des fonctions symétriques non-commutatives. Plus précisément, ces matrices expriment les coefficients de changement de base des bases complètes et rubans d'une part vers les bases monomiales et fondamentales introduites par Tevlin d'autre part. Les coefficients de ces matrices donnent un raffinement des probabilités du PASEP et sont décrits en utilisant de nouvelles statistiques sur les permutations. La conjecture stipule que ce raffinement peut se formuler via des statistiques déjà connues dans le monde du PASEP. Nous nous intéressons ensuite à une généralisation du PASEP avec deux types de particules dans le modèle : le 2-PASEP. Nous donnons ainsi plusieurs interprétations combinatoires des probabilités de ce modèle. Pour ce faire, nous introduisons une nouvelle famille de chemins généralisant les histoires de Laguerre : les histoires de Laguerre marquées. Nous généralisons ensuite la bijection de Françon-Viennot entre les histoires de Laguerre et les permutations pour définir les permutations partiellement signées qui nous donneront une seconde interprétation combinatoire de ces probabilités. Dans une troisième partie, nous généralisons les travaux de Tevlin afin de définir des bases monomiales et fondamentales dans l'algèbre des compositions segmentées. Afin de décrire les matrices de changement de base entre ces bases et d'autres déjà connues dans cette algèbre, nous définissons une algèbre indexée par les permutations partiellement signées en utilisant les statistiques définies précédemment pour décrire la combinatoire du 2-PASEP. Nous définissons également des q-analogues de ces bases afin de faire le lien avec les probabilités du 2-PASEP en fonction du paramètre q de ce modèle. Enfin, en utilisant le fait que les permutations partiellement signées sont en bijection avec les permutations segmentées, nous nous inspirons des statistiques définies précédemment pour introduire des descentes sur ces objets et ainsi définir une généralisation des polynômes eulériens sur les permutations segmentées. Pour étudier ces polynômes, nous utilisons les outils algébriques développés dans la partie précédente / This thesis comes within the scope of enumerative and algebraic combinatorics and studies the probabilities of the partially asymmetric exclusion process (PASEP).First, we bijectively prove a conjecture of Novelli-Thibon-Williams concerning the combinatorial interpretation of the entries of the transition matrices between some bases of the noncommutative symmetric functions algebra. More precisely, these matrices correspond to the transition matrices of, on the one hand the complete and ribbon bases and on the other hand the monomial and fundamental bases, both introduced by Tevlin. The coefficients of these matrices provide a refinement of the probabilities of the PASEP and are described using new statistics on permutations. This conjecture states that this refinement can also be described using classical statistics of the PASEP. In the second part, we study a generalization of the PASEP using two kinds of particles: the 2-PASEP. Hence, we give several combinatorial interpretations of the probabilities of this model. In order to do so, we define a new family of paths generalizing the Laguerre histories: the marked Laguerre histories. We also generalize the Françon-Viennot bijection between Laguerre histories and permutations to define partially signed permutations giving another combinatorial interpretation of these probabilities. In a third part, we generalize Tevlin's work in order to define a monomial basis and a fundamental basis on the algebra over segmented compositions. In order to describe the transition matrices between these bases and other bases already known in this algebra, we define an algebra indexed by partially signed permutations using the statistics previously defined to describe the combinatorics of the 2-PASEP. We also define some q-analogues of these bases related to the probabilities of the 2-PASEP according to the q parameter of this model. Finally, using the fact that partially signed permutations and segmented permutations are in bijection, we use the statistics defined previously to define descents on these objects and get a generalization of the Eulerian polynomials on segmented permutations. To study these polynomials, we use the algebraic tools introduced in the previous part

The use of permutations in data compression is an aspect that is worthy of further exploration. The work that has been done in video compression based on permutations was primarily oriented towards lossless algorithms. The study of previous algorithms has led to a new algorithm that could be either lossless or lossy, for which the amount of compression and the quality of the output can be controlled. The lossless version of our algorithm performs close to lossy versions of H.264 and it improves on them for the majority of the videos that we analyzed. Our algorithm could be used in situations where there is a need for lossless compression and the video sequences are part of a single scene, e.g., medical videos, where loss of information could be risky or expensive. Some results on permutations, which may be of independent interest, arose in developing this algorithm. We report on these as well. / by Amalya Mihnea. / Thesis (Ph.D.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.

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.

Velleman beweist die Konsistenz der Existenz vereinfachte Gap 2 Moraste (ein Begriff gleichwertig zu den ursprünglichen Morasten, geschafft von Jensen). Wir haben einen noch einfachen Begriff des vereinfachten Morastes in der Dissertation vorgeschlagen, Details aufgefüllt und wesentlich auch einen verschiedenen Beweis des Satzes erfunden und zwar in beide Stufe des Forcingverfahrens. Wir benötigen auch keine Squarefunktionereihenfolge (die ganz Kohärenzvoraussetzung fehlt aber ist linear und konfinal) sondern ein ``erratendes'' Verfahren für Sequenze, das nicht fest ist und nicht die ganze Kohärenzbedigung erfüllt wie bei Velleman. Wir hoffen, wir haben so eingelegt die Basis für einen zukunftigen Beweis des allgemeines Falls n in ZFC. / Velleman proved the consistency of the existence of simplified gap 2 morasses (equivalent to the concrete morasses defined by Jensen) using a two stage forcing. We give an essentially different proof of the same result and fill up some details from Velleman's paper which were not clear or imcomplete. In fact the proof uses a simpler definition of simplified gap 2 morasses. We have also eliminated the use of square-like sequences in the second stage, employing a ``guessing'' procedure for sequences which are not fixed and do not satisfy full coherence requirement. With these steps we hope to have laid the foundation for a future proof of gap n morasses in ZFC.

Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrées (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques. / Phylogenetic networks generalize the tree concept to model Evolution, by allowing edges between branches inside the tree to reflect genetic material exchanges between coexisting species. Lots of combinatorial approaches have been designed to reconstruct networks from data extracted from a set of contradictory gene trees. These approaches can be divided into several categories depending on the kind of input, i.e. triplets, quartets, clusters and splits, and on the kind of structure restrictions they impose on reconstructed networks.We particularly analyze the structure of one class of such restricted networks, namely level-k phylogenetic networks, and adapt this level parameter to the unrooted context. We also give new combinatorial methods to reconstruct phylogenetic networks from clusters - implemented in Dendroscope - or quartets. We study the limits of combinatorial methods (complexity explosion, noise and silence in the data, ambiguity in the reconstucted network), and the way to tackle them, in particular with an appropriate data preprocessing. Finally we illustrate the results of these reconstruction methods on a dataset, and we conclude on how to use them in a global methodology which integrates statistical aspects.

O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

In this thesis we consider three different issues of analytic number theory. Firstly, we investigate how residues modulo q may be expressed as products of small primes. In Chapter 1, we work in the regime in which these primes are less than q, and present some partial results towards an open conjecture of Erdös. In Chapter 2, we consider the kinder regime in which these primes are at most q^C , for some constant C that is greater than 1. Here we reach an explicit version of Linnik's Theorem on the least prime in an arithmetic progression, saving that we replace 'prime' with 'product of exactly three primes'. The results of this chapter are joint with Prof. Olivier Ramaré. The next two chapters concern equidistribution modulo 1, specifically the notion that an infinite set of integers is metric poissonian. This strong notion was introduced by Rudnick and Sarnak around twenty years ago, but more recently it has been linked with concepts from additive combinatorics. In Chapter 3 we study the primes in this context, and prove that the primes do not enjoy the metric poissonian property, a theorem which, in passing, improves upon a certain result of Bourgain. In Chapter 4 we continue the investigation further, adapting arguments of Schmidt to demonstrate that certain random sets of integers, which are nearly as dense as the primes, are metric poissonian after all. The major work of this thesis concerns the study of diophantine inequalities. The use of techniques from Fourier analysis to count the number of solutions to such systems, in primes or in other arithmetic sets of interest, is well developed. Our innovation, following suggestions of Wooley and others, is to utilise the additive-combinatorial notion of Gowers norms. In Chapter 5 we adapt methods of Green and Tao to show that, even in an extremely general framework, Gowers norms control the number of solutions weighted by arbitrary bounded functions. We use this result to demonstrate cancellation of the Möbius function over certain irrational patterns.