(Asymptotically?) Minimal set of single-use swaps to generate all permutations

23 Views Asked by At

Define

$SWAP_n = \{ \sigma \in S_n : \lvert Fix(\sigma) \rvert = n - 2 \}$

For every $n, L \in \mathbb{N}$, and every $G : \{1, ..., L \} \to SWAP_n$, if for every $\tau \in S_n$, there exist $k \le L$, and an increasing function $f_{G, \tau} : \{1, ..., k\} \to \{ 1 ..., L\}$ such that

$$\tau = (G \circ f_{G, \tau}(1)) \circ ... \circ (G \circ f_{G, \tau}(k))$$

we say that $G$ single-use generates $S_n$, and we denote $len(G) = L$

Q1 (optimistic): is there a way to write down, for every $n \in \mathbb{N}$, a $G_n$ that single-use generates $S_n$, and such that, for every $H$ that single-use generates $S_n$, it holds $len(H) \ge len(G_n)$ ?

Q2: In case that is not possible, is there a way to write down a sequence $(G_n)_{n \in \mathbb{N}}$ such that, for every $n \in \mathbb{N}$, it holds that $G_n$ single-use generates $S_n$, and such that, for every other sequence $(H_n)_{n \in \mathbb{N}}$ satisfying the same property,

$$ \liminf_{n \to \infty} \frac{len(H_n)}{len(G_n)} \ge 1 $$

holds?