L. Babai has shown that a faithful permutation representation of a nonsplit extension of a group by an alternating group Ak must have degree at least k2(12−o(1)), and has asked how sharp this lower bound is. We prove that Babai’s bound is sharp (up to a constant factor), by showing that there are such nonsplit extensions that have faithful permutation representations of degree 32k(k−1). We also reprove Babai’s quadratic lower bound with the constant 1/2 improved to 1 (by completely different methods).