Georgia Institute of Technology College of Sciences

In the study of combinatorial aspects of symmetric groups, a major problem arising from applications to Genetics consists in finding a minimum factorization of any permutation with factors from a given generating set. The difficulty in developing an adequate theory as well as the hardness of the computational complexity may heavily vary depending on the generator set. In this talk, the generating set consists of all block transpositions introduced by Bafna and Pevzner in 1998 for the study of a particular ''genome rearrangement problem''. Results, open problems, and generalizations are discussed in terms of Cayley graphs and their automorphism groups.

For a nonnegative random variable Y with finite nonzero mean \mu, we say that Y^s has the Y-size bias distribution if E[Yf(Y)] = \mu E[f(Y^s)] for all bounded, measurable f. If Y can be coupled to Y^s having the Y-size bias distribution such that for some constant C we have Y^s \leq Y + C, then Y satisfies a 'Poisson tail' concentration of measure inequality. This yields concentration results for examples including urn occupancy statistics for multinomial allocation models and Germ-Grain models in stochastic geometry, which are members of a class of models with log concave marginals for which size bias couplings may be constructed more generally. Similarly, concentration bounds can be shown when one can construct a bounded zero bias coupling or a Stein pair for a mean zero random variable Y. These latter couplings can be used to demonstrate concentration in Hoeffding's permutation and doubly indexed permutations statistics. The bounds produced, which have their origin in Stein's method, offer improvements over those obtained by using other methods available in the literature. This work is joint with J. Bartroff, S. Ghosh and L. Goldstein.