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. For every $n\in\mathbb N$ do we have an $m=O(poly(n))$ and an $m'=O(poly(n))$ such that there are elements $g_1,\dots,g_m\in S_n$ and subgroups of $G_1,\dots,G_m$ of $S_n$ such that for at least $\frac1{poly(n)}$ of all such $\mathcal T$ there is a subset $\mathcal D\subseteq\{1,\dots,m\}$ with $$\mathcal T\subseteq\cup_{i\in\mathcal D}g_iG_i$$ $$\big(|\mathcal T|-\sum_{i\in\mathcal D}|G_i\big)^2\leq m'$$ holds?

  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\in\mathcal D}g_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.