THE COMBINATORICS BEHIND NUMBER-THEORETIC SIEVES

Ever since Viggo Brun's pioneering work, number theorists have develop ed increasingly sophisticated refinements of the sieve of Eratosthenes to attack problems such as the twin prime conjecture and Goldbachs co njecture. Ever since Gian-Carlo Rota's pioneering work, combinatoriali sts have found more and more areas of combinatorics where sieve method s (or Mobius inversion) are applicable. Unfortunately, these two devel opments have proceeded largely independently of each other even though they are closely related. This paper begins the process of bridging t he gap between them by showing that much of the theory behind the numb er-theoretic refinements carries over readily to many combinatorial se ttings. The hope is that this will result in new approaches to;nd more powerful tools for sieve problems in combinatorics such as the comput ation of chromatic polynomials, the enumeration of permutations with r estricted position, rind the enumeration of regions in hyperplane arra ngements. (C) 1998 Academic Press.