Applied to the population of Europe, this threshold seems to happen about 1000 years in the past. So it's fairly likely that everyone with even a single European ancestor within the past 100 years or so can, in fact, claim descent from Charlemagne.
There are two technical assumptions in this paper. One is constant population size; it seems like it would be straightforward, although a technical pain in the ass, to relax this. The other more interesting one is that it assumes a random mating model; i.e., the probability that someone in generation t is a parent of someone in generation t+1 is uniform. This obviously isn't correct, but I can think of a good way to model something more realistic - consider a set of k populations of size fk, each of which has random mating within it, and with a cross-mating probability distribution pk k'. This could model the existence of disjoint social or geographic groups. I'm rather curious about whether this would substantially change the results. One interesting question is, given a total population size and a decomposition into subgroups, whether or not there's a "critical size" for a subpopulation which will lead in finite time to that population dying out, becoming completely assimilated, or becoming ancestors of everybody.
