Combinatorics Semnar

Fix any integer n>1 and consider the binomial coefficients {{n} \choose {k}}, 1 \leq k \leq n-1. We want to know the smallest number m=m(n) so that the set of such binomial coefficients can be partitioned into m subsets A_1,...,A_m in such a way that, for each i, the gcd of the elements of A_i is larger than one.

A theorem of Kummer shows that m(n)=1 if and only if n is a prime power. There is no known n such that m(n)>2. In joint work with Russ Woodroofe, we showed that m(n) \leq 2 if n \leq 1,000,000,000 and that if one assumes either the Riemann Hypothesis or Cramer's Conjecture, then the asymptotic density of those n for which m(n) \leq 2 is 1. Moreover, we showed that this asymptotic density is very close to 1 with no such assumptions. I will explain how this problem arose (although we were able to get around it) in our work on a problem involving topological combinatorics and group theory.

Let G be a finite group and consider the set C(G) of all cosets of all proper subgroups of G, partially ordered by inclusion. Let D(G) be the simplicial complex whose k-dimensional faces are the chains (totally ordered subsets) of k+1 elements from C(G). Settling a question of Ken Brown, we showed that D(G) is never contractible. The main tools in our proof are Smith Theory (which concerns group actions on topological spaces) and the Classification of Finite Simple Groups. 

A version of the binomial coefficient problem above arose in work of Cheryl Praeger, Silvio Dofli, Bob Guralnick and Marcel Herzog on generation of finite simple groups. If time permits, I will discuss this work.