In model networks of E-cells and I-cells (excitatory and inhibitory neurons, respectively), synchronous rhythmic spiking often comes about from the interplay between the two cell groups: the E-cells synchronize the I-cells and vice versa. Under ideal conditions-homogeneity in relevant network parameters and all-to-all connectivity, for instance-this mechanism can yield perfect synchronization. We find that approximate, imperfect synchronization is possible even with very sparse, random connectivity. The crucial quantity is the expected number of inputs per cell. As long as it is large enough (more precisely, as long as the variance of the total number of synaptic inputs per cell is small enough), tight synchronization is possible. The desynchronizing effect of random connectivity can be reduced by strengthening the E --> I synapses. More surprising, it cannot be reduced by strengthening the I --> E synapses. However, the decay time constant of inhibition plays an important role. Faster decay yields tighter synchrony. In particular, in models in which the inhibitory synapses are assumed to be instantaneous, the effects of sparse, random connectivity cannot be seen.