Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is the number N of disjoint sets of size 2 from [n] such that for each $\sigma_i$ , $i \in [k]$ the maximum stack depth is $O(n^{0.9})$ when processing following sequence of push and pops obtained from these sets and $\sigma_i$ (ie, upper bound on maximum number of elements in the stack at any time is $O(n^{0.9})$).
for each set $S_l= \{a,b\}, l\in [N]$, if replace 'a' (let 'a' appears first when we scan the permutation $\sigma_i$ left to right, i.e, $\sigma_i(1),\sigma_i(2),...,\sigma_i(n)$) by push({a,b}) and 'b' (in the left to right scan 'b' appears after 'a') by pop({a,b}). We ignore all elements $e \in [n]$ which does not belong any of this disjoint sets.
When processing a pop({a,b}), if {a,b} is not top, then we pop all elements until we pop {a,b} and push back all popped elements except {a,b}.
Note that: (1) Across permutations, disjoint sets $S_1,...,S_N$ are fixed. (2) The stack depth condition should hold for each of the permutation $\sigma_i, i\in [k]$.
We may apply some process like choosing a permutation $\rho$ from set of all permutations (it can depend on the given permutations) and look for these N sets in $\rho.\sigma_1,\rho.\sigma_2,...,\rho.\sigma_k \in S_n$ instead of in the original permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$, but we are not allowed to use different processes for different permutations.
For any stack depth D, where $\sqrt{n} \leq D \leq n^{1-\epsilon}$, where $0<\epsilon<1/2$ is a constant, Is it possible to get N to be $\Omega(D.n^{\delta})$, where $\delta>0$ is a constant?
