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.

Cette thèse vise à contribuer à l’approche DDL (Data-Driven Learning) dans l’enseignement du lexique en FLE. Dans le cadre de l’approche DDL, on fait appel aux corpus pour enseigner différentes composantes d’une langue. Le lexique, étant un des premiers besoins d’un apprenant, car il donne accès à la communication en langue étrangère, fait l’objet de nombreux travaux de recherche actuels en linguistique et en didactique. L’idiomaticité, trait constitutif de toutes les langues, se manifeste sous forme d’expressions variées. Elle relève du champ de la lexicologie, et plus spécifiquement de la phraséologie. La linguistique de corpus permet d’observer ce fait de langue dans un cadre structure/sens. Les expressions idiomatiques en général, et en particulier les collocations, sont mises au centre de la démarche didactique dans cette thèse. Les collocations à verbe support restent une source d’erreurs importante même aux niveaux avancés d’apprentissage. Le matériel didactique présenté aux lecteurs de cette étude cherche à promouvoir l’exploitation directe des corpus bilingues par les apprenants en classe afin d’identifier ces collocations en L1 et en L2, de les comprendre, de trouver des correspondances et de les employer de manière appropriée. L’approche comparative français-russe renforcée par une observation des lignes de concordance issues de corpus authentiques devraient permettre une meilleure acquisition des faits linguistiques visés. Ce travail s’inscrit dans une perspective d’apprentissage déductif et d’autonomisation des apprenants. / This thesis aims to contribute to the DDL (Data-Driven Learning) approach in French vocabulary teaching. In the framework of the DDL approach we use corpora to teach different language phenomena. Vocabulary, one of the immediate needs of a language learner because it makes a communication in a foreign language possible, has become a popular research theme in the fields of linguistics and language teaching. Idiomaticity, an inherent part of all languages, manifests through various expressions. Phraseology studies different ways of expressing idiomaticity. Corpus linguistics permits to observe this language phenomenon in a structure/sense framework. Idiomatic expressions in general and collocations in particular are the heart and the main focus of the teaching perspective described in this thesis. Even advanced language learners make errors in light verb constructions. The teaching material presented in this study seeks to promote the search in bilingual corpora in the classroom in order to identify these collocations in L1 and in L2, to understand them, to find equivalents and finally, to use them correctly. A comparative French-Russian approach reinforced by a study of concordance lines from authentic corpora might contribute to better understanding of a particular language feature. This study falls in line with deductive learning practices and with the learners’ autonomisation perspective.

This dissertation is divided into four chapters. In Chapter 2 the equivariant homology groups of upper order ideals in the partition lattice are computed. The homology groups of these filters are written in terms of border strip Specht modules as well as in terms of links in an associated complex in the lattice of compositions. The classification is used to reproduce topological calculations of many well-studied subcomplexes of the partition lattice, including the d-divisible partition lattice and the Frobenius complex. In Chapter 3 the box polynomial B_{m,n}(x) is defined in terms of all integer partitions that fit in an m by n box. The real roots of the box polynomial are completely characterized, and an asymptotically tight bound on the norms of the complex roots is also given. An equivalent definition of the box polynomial is given via applications of the finite difference operator Delta to the monomial x^{m+n}. The box polynomials are also used to find identities counting set partitions with all even or odd blocks, respectively. Chapter 4 extends results from Chapter 3 to give combinatorial proofs for the ordinary generating function for set partitions with all even or all odd block sizes, respectively. This is achieved by looking at a multivariable generating function analog of the Stirling numbers of the second kind using restricted growth words. Chapter 5 introduces a colored variant of the ordered partition lattice, denoted Q_n^{\alpha}, as well an associated complex known as the alpha-colored permutahedron, whose face poset is Q_n^\alpha. Connections between the Eulerian polynomials and Stirling numbers of the second kind are developed via the fibers of a map from Q_n^{\alpha} to the symmetric group on n-elements

In this thesis, we study hash functions. We focus mainly on the famous Merkle-Damg˚ard construction and its generalisation. We show that even this generalised construction is not resistant to multicollision attacks. Combinatorics on words plays a fundamental role in the construction of our attack. We prove that regularities unavoidably appear in long words with bounded number of symbol occurences. We present our original results concerning regularities in long words. We lower some earlier published estimates, thus reducing the comlexity of the attack. Our results show that generalised iterated hash functions are interesting rather from the theoretical than practical point of view. 1

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Este trabalho aborda o uso de Objetos de Aprendizagem (OAs) voltado para o ensino de CombinatÃria e como esses objetos podem auxiliar no processo de aprendizagem dos alunos. Nesse sentido, o objetivo desse trabalho à verificar se a utilizaÃÃo de OAs nas aulas de MatemÃtica promovem uma melhor assimilaÃÃo dos conteÃdos relacionados à CombinatÃria, buscando despertar no aluno a curiosidade e a investigaÃÃo nesta Ãrea. Por isso, optou-se por um estudo experimental do qual participaram 20 alunos do 3o ano do Ensino MÃdio da Escola de Ensino Fundamental e MÃdio JoÃo Mattos, localizada em Fortaleza, CearÃ. Esses alunos foram escolhidos de forma aleatÃria e divididos entre dois grupos, experimental e controle, com 10 alunos em cada grupo. Para a coleta dos dados, foram utilizados, um questionÃrio socioeconÃmico e um teste de mÃltipla escolha sobre permutaÃÃo, arranjo e combinaÃÃo. Esses dados foram organizados e analisados com o auxÃlio do programa Microsoft Office Excel 2010. Os resultados mostram que o grupo que teve uma abordagem diferenciada (experimental) obteve um melhor desempenho em relaÃÃo ao grupo que teve uma abordagem tradicional (controle). / This work approaches the use of Learning Objects (LOs) facing the teaching of Combinatorics and how these objects can help in the learning process of students. Accordingly, the aim of this work is to check that the use of LOs in Math classes promotes a better assimilation of the contents related to Combinatorics, seeking to awaken in the student curiosity and research in this area. Therefore, we opted for an experimental study involving 20 students of the senior year of High School from School JoÃo Mattos, located in Fortaleza, CearÃ. These students were chosen at random and divided between two groups, experimental and control, with 10 students in each group. For the collect of data, were used, a socioeconomic questionnaire and a multiple choice test about permutation, arrangement and combination. These data were organized and analyzed with the help of Microsoft Office Excel 2010 program. The results show that the group that had a differentiated approach (experimental) obtained a better performance compared to the group that had a traditional approach (control). .

Esta dissertação apresenta o desenvolvimento de uma pesquisa referente ao ensino da Análise Combinatória, por meio da Resolução de Problemas, em uma turma de 6º ano do Ensino Fundamental. Para isso, elaborou-se uma sequência didática que buscava proporcionar aos educandos um contato com esse conteúdo antes do Ensino Médio. A partir dessa sequência analisou-se como a Resolução de Problemas, segundo Onuchic e Allevato, auxiliou os alunos a compreender os conceitos iniciais de Análise Combinatória, buscando também como referencial teórico o estudo referente ao Pensamento Matemático, de David Tall. Concluímos que a Resolução de Problemas auxiliou a expandir e modificar as Imagens dos Conceitos que os alunos possuíam com relação à Análise Combinatória. / This dissertation shows the development of research related to teaching Combinatorics, through Problem Solving, at a 6th grade level. A lesson plan was prepared and aimed to confront students of middle school with problems involving Combinatorics, allowing them to work with such concepts before high school. Based on this lesson plan, our intent was to verify how Problem Solving, according to Onuchic e Allevato, helped the students to understand initial concepts of Combinatorics. Also, using David Tall’s studies about Mathematical Thinking as reference. We could verify that the Problem Solving Theory helped the students to expand and modify their Concept Images related to Combinatorics.

Estudamos o comportamento da familia aresta-triangulo de grafos aleatorios exponenciais (ERG) usando metodos de Monte Carlo baseados em Cadeias de Markov. Comparamos contagens de subgrafos e correlacoes entre arestas de ergs as de Grafos Aleatorios Binomiais (BRG, tambem chamados de Erdos-Renyi). E um resultado teorico conhecido que para algumas parametrizacoes os limites das contagens de subgrafos de ERGs convergem para os de BRGs, assintoticamente no numero de vertices [BBS11, CD11]. Observamos esse fenomeno em grafos com poucos (20) vertices em nossas simulacoes. / We study the behavior of the edge-triangle family of exponential random graphs (ERG) using the Markov Chain Monte Carlo method. We compare ERG subgraph counts and edge correlations to those of the classic Binomial Random Graph (BRG, also called Erdos-Renyi model). It is a known theoretical result that for some parameterizations the limit ERG subgraph counts converge to those of BRGs, as the number of vertices grows [BBS11, CD11]. We observe this phenomenon on graphs with few (20) vertices in our simulations.

This thesis presents an introduction to Schur rings (S-rings) and their various properties. Special attention is given to S-rings that are commutative. A number of original results are proved, including a complete classification of the central S-rings over the simple groups PSL(2,q), where q is any prime power. A discussion is made of the counting of symmetric S-rings over cyclic groups of prime power order. An appendix is included that gives all S-rings over the symmetric group over 4 elements with basic structural properties, along with code that can be used, for groups of comparatively small order, to enumerate all S-rings and compute character tables for those S-rings that are commutative. The appendix also includes code optimized for the enumeration of S-rings over cyclic groups.

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.