Consider the graph whose vertices are all n! permutations of numbers 1..n and there is an edge between two vertices iff we can get from one to another by an adjacent transposition. We call this graph the permutohedron. In this graph, for a subset S of edges, we define perimeter of it to be the number of edges that have on end inside S and one end outside of it.
Question. What is the subset that has the minimum ratio of perimeter/size in the permutohedron? if there is no exact answer is there any upper or lower bound on this ratio?
I suppose you want to consider subsets $S$ such that $|S| \leq |G|/2$.
You are asking for the edge expansion of the 1-skeleton of the permutohedron of order $n$. Equivalently, it's the Cayley graph of symmetric group $S_n$ under the generators $(12), (23), \dotsc, (n-1,n)$. Let's write $G_n$ for the $n$-th graph and $h(G_n)$ its edge expansion.
I present a simple upper bound. Suppose that we represent every vertex in the permutohedron by a string of length $n$ representing a permutation. Suppose that $n = 2k$ is an even number. Consider the subset $S$ of the strings that end with a number in $\{1, \dotsc, k \}$. Then, of the $n-1$ neighbours, only the one exchanging the two last elements can be outside $S$. This happens only when the next to last element in the string is in $\{ k+1, \dotsc, 2k \}$. Using this, a simple count shows that there are $k^2(2k-2)!$ edges in the perimeter of $S$.
As $|S| = (2k)!/2$, the perimeter/size ratio for $S$ is $k/(2k-1)$, and so, $h(G_{2k}) \leq k/(2k-1)$. For $n = 2k+1$, a similar construction implies $h(G_{2k+1}) \leq 2k/(4k^2-1)$.
This bound is sharp for $n \leq 3$, as one easily checks by inspection. I suspect this is not sharp for $n > 3$.