Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$.

  1. Do we have an $m=O(poly(n))$ and an $m'=O(poly(n))$ such that for at least $\frac1{poly(n)}$ of all such $\mathcal T$ there are elements $g_1,\dots,g_m\in S_n$ and subgroups of $G_1,\dots,G_m$ of $S_n$ with $$\mathcal T\subseteq\cup_{i=1}^mg_iG_i$$ $$\big(|\mathcal T|-\sum_{i=1}^m|G_i\big)^2\leq m'?$$

  2. Does $m=O(poly(n))$ hold if $m'=0$ for at least $\frac1{poly(n)}$ of all $\mathcal T$ (giving $\mathcal T=\cup_{i=1}^mg_iG_i$)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.