Let $\Omega_n$ denote the symmetric/permutation group on $n$ objects. Let $T_n \subseteq \Omega_n$ denote the set of transpositions. Drop the $n$-subscripts.

Define the *Cayley graph* $G = (\Omega, E)$ by saying that $\sigma, \sigma' \in \Omega$ are *adjacent* if $\sigma^{-1} \sigma \in T$, ie they differ by a transposition.
One can use the Aldous spectral gap conjecture to show that the spectral gap of (the simple random walk on) this graph is $1/n$.
A standard result by multiple authors (Jerrum and Sinclair, to name two) then says that
$1/n^2 \lesssim \Phi_* \lesssim 1/n$ where $\Phi_*$ is the isoperimetric constant:
$$
\Phi(S) := \frac{|\partial S|}{|S|}
\quad\text{and}\quad
\Phi_* := \min_{|S| \le |\Omega|/2} \Phi(S),$$
where $\partial S$ is the *edge boundary* of the set $S$.
This is a *worst-case* bound.

I am interested in a better understanding of the isoperimetric profile $\Phi(S)$, not just for the worst-case $S$. References and the like would be appreciated.

Consider this example. Define $S$ by including every permutation independently with probability $\tfrac12$. (I just mean site $\tfrac12$-percolation by this.) Fix any transposition $\tau \in T$. Define $$ \partial_\tau S := \{ \sigma \tau \mid \sigma \in S \text{ and } \sigma \tau \notin S \}. $$ One can pair up all the permutations: $(\sigma, \sigma \tau)$ where $\sigma$ ranges over a set of size $\tfrac12 |\Omega|$. This outlook shows that $$ |\partial_\tau S| \sim \textrm{Bin}(|\Omega|, \tfrac14). $$ Indeed, for every point in $S$ there is a $\tfrac12$ chance that its pair is not in $S$. Also, $|S| \sim \textrm{Bin}(|\Omega|, \tfrac12)$. Thus $ \Phi(S) \approx \tfrac12. $ So if $S$ is drawn in this sense then typically it has isoperimetric expansion roughly $\tfrac12$. This is much better than the worst-case, which is at least as bad as $1/n$.

Ideally I would like to determine some characterisation of the set of 'expanding' sets, ie ones with $\Phi(S) \asymp 1$. More formally, define $\mathcal P_c := \{ S \subseteq \Omega \mid \Phi(S) \ge c \}$ for $c \ge 0$. Then $\mathcal P_0$ is just the power set of $\Omega$. I am after some characterisation of $\mathcal P_c$, or some large subset of it, for $c > 0$ fixed and $n \to \infty$.

bestcase: having a large boundary is easy, one only needs to add wrinkles or holes every now and then. What is dificult is to have small perimeter. So, I would fear that your question could have no good answer: most sets should have large perimeter, as well shown from your probabilistic argument. Maybe you should explain what type of characterization you seek? $\endgroup$evolving setsto be precise). It grows/shrinks proportionally to its boundary. Namely, either the entire external boundary is added or the entire internal boundary is deleted; it is slightly more likely to add than remove so overall grows. I want to show that it grows quickly and thus want a large boundary. "Small boundary" is thus bad for me. The "characterisation" is very informal. I just want this process to satisfy $\Phi(S_t) \asymp 1$ for lots of $t$ $\endgroup$mustbe the case that $\Phi(S_t)$ is typically order 1, since $|\Omega|$ goes somewhat like $e^{n \log n}$ $\endgroup$1more comment