Explicit permutation representation of the Schur double cover of the symmetric group Main question: How can we describe the double covers $(2\cdot\mathfrak{S}_n)^+$ and $(2\cdot\mathfrak{S}_n)^-$ of the symmetric group $\mathfrak{S}_n$ as permutation groups?  (I.e., what sort of set with combinatorial structure do they act faithfully upon?)
I am not necessarily asking for the minimal permutation degree (I think this is an open problem; also see PS at bottom), but for some explicit combinatorial construction, reasonably uniform in $n$, that is hopefully reasonably small (perhaps merely exponential in $n$).
For a long time, I wrongly believed that one could form such a permutation representation of degree $2^{\lfloor n/2\rfloor}$ (or perhaps twice or four times that, or thereabouts) by taking an appropriate basis in the basic spin representation (and their negatives, and perhaps also times the imaginary unit), but I now realize that this does not work (at least, not as I thought it would).  So I wonder if something else can be done.
The following question may is closely related to the above (trying to lift some $\mathfrak{S}_n$-set $X$ to a $(2\cdot \mathfrak{S}_n)$-set $\tilde X$ consisting of "signed" elements of $X$):
Alternate question: Given a set $X$ on which $\mathfrak{S}_n$ acts faithfully and transitively, with stabilizer $H$, is there some way to detect (merely by looking at $X$) whether $H$ lifts in $2\cdot \mathfrak{S}_n$ to a direct product $\{\pm 1\}\times H$, or equivalently (see below), whether the wreath product $1 \to \{\pm 1\}^X \to \{\pm 1\}\wr_X\mathfrak{S}_n \to \mathfrak{S}_n\to 1$ contains a non-split extension $1 \to \{\pm 1\} \to 2\cdot \mathfrak{S}_n \to \mathfrak{S}_n\to 1$?
Indeed, if $2\cdot \mathfrak{S}_n$ acts transitively on a set $\tilde X$, with stabilizer $H$, and the action does not factor through $\mathfrak{S}_n$, then $H$ intersects $\{\pm 1\}$ (center of $2\cdot\mathfrak{S}_n$) trivially, so maps isomorphically to a subgroup of $\mathfrak{S}_n$, which we can also call $H$, and the latter lifts to $2\cdot\mathfrak{S}_n$ as a direct product $\{\pm 1\}\times H$ (and we can see $\tilde X = (2\cdot\mathfrak{S}_n)/H$ as a double covering of $X = \mathfrak{S}_n/H$).  But then, it follows from Derek Holt's paper "Embeddings of Group Extensions into Wreath Products" (Quarter. J. Math. Oxford 29 (1978) 463–468), theorem 2, that the wreath product contains our $2\cdot \mathfrak{S}_n$.  Conversely, when this is the case, $2\cdot \mathfrak{S}_n$ acts faithfully and transitively (through the wreath product) on $\tilde X := \{\pm 1\}\times X$.
For example, if $H$ is generated by an $n$-cycle, and either $n$ is odd or we $n\equiv 2\pmod{4}$ if we are considering $(2\cdot\mathfrak{S}_n)^+$, we get a permutation action of degree $2(n-1)!$ on the set $\mathfrak{S}_n/H$ of cyclic orders with a sign added.  But this isn't a great improvement over the regular action ($2n!$) and it's not very explicit, so I'm hoping we can do better.
PS: If my computations with Gap are correct, the minimal permutation representation for (Gap's choice) $(2\cdot\mathfrak{S}_n)^-$ is $16,48,80,240,240,480$ for $n=4,5,6,7,8,9$.  This is not in the OEIS, I wonder if it's worth adding.
PPS: The corresponding values for $(2\cdot\mathfrak{S}_n)^+$ are $8,40,80,240,480,480$ (also not in the OEIS), so apparently they're not the same.  (The trick I found to represent $(2\cdot\mathfrak{S}_n)^+$ under Gap is to multiply by a fourth root of unity the generators of $(2\cdot\mathfrak{S}_n)^-$ that lift an odd permutation.)
 A: I hope you are correct that minimal degree is an open question, as I am currently working on the related question of minimal degree for $2\cdot A_n$, but as this embeds into $(2\cdot S_n)^\pm$ with index $2$ I can give you a permutation representation which I believe to have degree at most $4$ times the minimal degree (for large enough $n$).

For a particularly good permutation representation assume $n$ is even and take the natural embedding $A_\frac{n}{2}\times A_\frac{n}{2}\hookrightarrow S_n$ or $A_\frac{n}{2}\times A_\frac{n}{2}\hookrightarrow S_{n+1}$ (to deal with odd case) and let $H$ be the subdirect product of $A_\frac{n}{2}\times A_\frac{n}{2}$ consisting of all pairs $(\sigma,\sigma)$ with $\sigma\in A_\frac{n}{2}$. The preimage of $H$ is $S_n$, or $S_{n+1}$ is isomorphic to $C_2\times H$. Hence we may identify $H$ as a subgroup of $2\cdot S_n$ or $2\cdot S_{n+1}$. The action of $G$ on the cosets of $H$ is faithful of degree $4n!/\frac{n}{2}!$ or $4(n+1)!/\frac{n}{2}!$.

It's not a particularly nice combinatorial structure (or at least I can't identify it as one), but it's what I've used to construct $2\cdot A_n$ as a permutation group in MAGMA.
Explanation:
As the socle $Z$ of $(2\cdot S_n)^\pm$ is a simple group, it has a minimal permutation representation which is transitive and is therefore the coset action of $(2\cdot S_n)^\pm$ on one of its subgroups. In fact, one can show that any minimal permutation representation of $(2\cdot S_n)^\pm$ is given by the coset action of $(2\cdot S_n)^\pm$ on one of its largest core-free subgroups, where a subgroup is core-free if it contains no normal subgroup of $(2\cdot S_n)^\pm$. In this case a subgroup $H$ of $(2\cdot S_n)^\pm$ is core-free if and only if it intersects $Z$ trivially. It can therefore be identified with it's image in $S_n$.
The choice of $H$ I've given is a particularly good one, though when $n$ is divisible by $8$ you may take $H\times C_2$ where $C_2$ 'swaps' the two copies of $A_n$.
It's a bit of work, but you can show $H$ is core-free using the finite presentation of $2\cdot S_n$. The main restriction is that whenever an element of order $2$ appears in $H$ it has to be a product of a multiple of $4$ transpositions. Hence two copies of $A_n$. Anything significantly larger than $A_\frac{n}{2}$ will end up having an element of order $2$ which does not satisfy this, so you really can't get much better than this.
