  We study $k$-divisible partition structures, which are families of random set
partitions whose block sizes are divisible by an integer $k=1,2,\ldots$. In
this setting, exchangeability corresponds to the usual invariance under
relabeling by arbitrary permutations; however, for $k>1$, the ordinary deletion
maps on partitions no longer preserve divisibility, and so a random deletion
procedure is needed to obtain a partition structure. We describe explicit
Chinese restaurant-type seating rules for generating families of exchangeable
$k$-divisible partitions that are consistent under random deletion. We further
introduce the notion of {\em Markovian partition structures}, which are
ensembles of exchangeable Markov chains on $k$-divisible partitions that are
consistent under a random process of {\em Markovian deletion}. The Markov
chains we study are reversible and refine the class of Markov chains introduced
in {\em J.\ Appl.\ Probab.}~{\bf48}(3):778--791.
