# Turán's theorem for cosets of groups

Let $$G$$ be a finite group, $$G',H$$ be its subgroups and $$H'=G'\cap H$$. For each $$g\in G$$, we create a map $$f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$$. It's easy to see that the map is well defined and injective. Let $$S$$ be a subset of $$G/H$$, assume that there is no $$g\in G$$ such that $$f_g(G'/H')\subset S$$.

Question: I want to estimate and find some properties of $$M(G,G',H)=\max|S|$$ and $$\alpha(G,G',H)=\max\frac{|G/H|}{|G/H|-|S|}$$, for all or some particular cases of groups $$G,G',H$$. Note that we have $$M(G,G',H)=\left(1-\frac{1}{\alpha(G,G',H)}\right)|G/H|$$.

Some results that I have found:

a) $$1\leq\alpha(G,G',H)\leq |G'/H'|$$. The first inequality is trivial. Assume that $$|S|> \left(1-\frac{1}{|G'/H'|}\right)|G/H|$$ then:

$$\mathbb{E}_{g\in G}[|f_g(G'/H')\cap S|]=|G'/H'|\mathbb{P}_{a\in G'/H',g\in G}[f_g(a)\in S]=\frac{|G'/H'|}{|G/H|}|S|>|G'/H'|-1$$

So there exists $$g\in G$$ such that $$|f_g(G'/H')\cap S|=|G'/H'|\Rightarrow f_g(G'/H')\subset S$$.

b) If $$G'\subset H\Rightarrow H'=G'$$, then by a), $$\alpha(G,G',H)=1,M(G,G',H)=0$$.

c) If $$H,H'$$ is a trivial group then $$\alpha(G,G',H)=|G'|$$ because each coset of $$G/G'$$ contains at most $$|G'|-1$$ elements of $$S$$, so $$|S|\leq (|G'|-1)|G/G'|$$

d) If $$N$$ is a normal subgroup of $$G,H$$ and $$N'=N\cap G'$$ then $$\alpha(G/N,G'/N',H/N)=\alpha(G,G',H),M(G/N,G'/N',H/N)=M(G,G',H)$$, because the two set of left cosets and the set of all function $$f_g$$ are still the same under isomorphism after taking quotent by $$N$$ and $$N'$$.

e) By c), d), if $$G'$$ is a commutative group then $$\alpha(G,G',H)=\alpha(G/H,G'/H',{e})=|G'/H'|$$.

f) If $$N$$ is a subgroup of $$G,G'$$ such that $$N\cap H$$ be the trivial group and $$nh=hn,\forall n\in N, h\in H$$ then $$\alpha(G,G',H)=|N|\alpha(G,G',NH)$$ (I proof by dividing $$G/NH,G'/NH'$$ into $$|N|$$ parts but the proof is quite complicative so let's omit it).

g) If $$H'$$ is a trivial group and $$hg=gh, \forall h\in H, g\in G'$$ then $$\alpha(G,G',H)=|G'|\alpha(G,G',G'H)=|G'|$$ by f), b).

h) $$M(G,G',H)=|G/G'H|M(G'H,G',H), \alpha(G,G',H)=\alpha(G'H,G',H)$$

so we can assume $$G=G'H$$.

Motivation: Let $$P_S$$ be a group of permutation of the set $$S$$. Let $$\{1,2,...,n\},n\geq 3$$ be the sets of vertices of the complete graph $$K_n$$, we have a bijection from the set of left cosets $$P_{\{1,2,...,n\}}/(P_{\{3,4,...,n\}}\times P_{\{1,2\}})$$ to the set of edges of $$K_n$$ by map the coset $$\sigma(P_{\{3,4,...,n\}}\times P_{\{1,2\}})$$ to the edge $$(\sigma(1),\sigma(2))$$.

For each $$\sigma\in P_{\{1,2,...,n\}}$$, we see that the map $$f_{\sigma}: P_{\{1,2,...,r\}}/(P_{\{3,4,...,r\}}\times P_{\{1,2\}})\rightarrow P_{\{1,2,...,n\}}/(P_{\{3,4,...,n\}}\times P_{\{1,2\}})$$ corresponds to the complete subgraph $$K_r$$ of $$K_n$$ with vertices $$\sigma(1),\sigma(2),...\sigma(r)$$.

The subset $$S$$ of $$P_{\{1,2,...,n\}}/(P_{\{3,4,...,n\}}\times P_{\{1,2\}})$$ such that there is no $$\sigma\in P_{\{1,2,...,n\}}$$ such that $$f_{\sigma}(P_{\{1,2,...,r\}}/(P_{\{3,4,...,r\}}\times P_{\{1,2\}}))\subset S$$ creates a $$K_r$$-free graph of $$n$$ vertices, so $$M(P_{\{1,2,...,n\}},P_{\{1,2,...,r\}},P_{\{3,4,...,n\}}\times P_{\{1,2\}})= \left(1-\frac{1}{r}+o(1)\right)\frac{n^2}{2}\Rightarrow \alpha(P_{\{1,2,...,n\}},P_{\{1,2,...,r\}},P_{\{3,4,...,n\}}\times P_{\{1,2\}})=r+o(1)$$ with $$r$$ fixed and $$n$$ increase by Turán's theorem.

More questions:

1. When $$\alpha(G,G',H)=|G'/H'|$$?

2. Improve the lower bound of $$\alpha(G,G',H)$$ which is only depend on $$|G'/H'|$$ or show such bound doesn't exist.

We can view the bipartite graph $$K_{\{1,2,...,r\},\{r+1,r+2,...,2r\}}$$ as $$Aut(K_{\{1,2,...,r\},\{r+1,r+2,...,2r\}})/Aut(K_{\{1,2,...,r-1\},\{r,r+1,...,2r-2\}})$$, then by Erdős–Stone-Simonovits theorem we have

$$M(P_{\{1,2,...,n\}},Aut(K_{\{1,2,...,r\},\{r+1,r+2,...,2r\}}),P_{\{3,4,...,n\}}\times P_{\{1,2\}})=o(n^2)\Rightarrow \alpha(P_{\{1,2,...,n\}},Aut(K_{\{1,2,...,r\},\{r+1,r+2,...,2r\}}),P_{\{3,4,...,n\}}\times P_{\{1,2\}})=1+o(1)$$

as $$r$$ fixed and $$n$$ increase, so such bound in question 2 doesn't exist and we have a new question:

2'. Is it true that for all group $$G'$$, subgroup $$H'$$ of $$G'$$ and $$\varepsilon>0$$, there exists group $$G$$ and subgroup $$H$$ of $$G$$ such that $$M(G,G',H)$$ is defined and $$M(G,G',H)<\varepsilon|G/H|$$?

• It seems to me that the formula from the third line should be $f_g(G'/H')\subset S$. Commented Dec 13, 2022 at 4:04
• Thank you very much @kabenyuk Commented Dec 13, 2022 at 9:53
• Please be aware that every edit of a question or of one of its answers bumps the thread to the front page. This has happened for this thread already more than 10 times within just a few days, and this is a nuisance for other users. Please refrain from unnecessary edits to your posts. -- Usually, the vast majority of minor edits can be avoided by writing and proofreading a question or an answer (or any update to such) carefully before posting it. Commented Dec 14, 2022 at 22:40

Question 2': We choose $$G=P_{G'/H'\cup A},H=P_{\{(G'/H')-\{eH'\})\cup A}$$, use natural acting of $$G'$$ on $$G'/H'$$, we can view $$G'$$ as subgroup of $$G$$ and $$G/H=G'/H'\cup A$$. We have the stabilizer subgroup with respect to the left coset $$eH'$$ of $$G$$ and $$G'$$ are $$H$$ and $$H'$$ respectively so $$H'=G'\cap H$$. Let $$S\in G/H$$, if $$|S|\geq |G'/H'|$$, because $$G$$ is the permutation group of $$G/H$$ so there exists $$g\in G$$ such that $$f_g(G'/H')\subset S$$. So $$M(G,G',H)=|G'/H'|-1$$, now we just need to choose $$A$$ such that $$\varepsilon|G/H|>|G'/H'|-1$$.

Question 1:

Assume $$\alpha(G,G',H)=|G'/H'|$$, take $$S$$ statisfies the condition and $$|S|=(1-\frac{1}{|G'/H'|})|G/H|$$. We have:

$$\mathbb{E}_{g\in G}[|f_g(G'/H')\cap S|]=\frac{|G'/H'|}{|G/H|}|S|=|G'/H'|-1$$

but $$|f_g(G'/H')\cap S|\leq|G'/H'|-1$$ so $$|f_g(G'/H')\cap S|=|G'/H'|-1,\forall g\in G$$. Because $$gS$$ also has that properties of $$S$$ for $$g\in G$$, so we can assume $$\{eH\}\notin S$$.

Let $$R=G/H-S$$, then $$eH\in R$$,$$|R|=\frac{|G/H|}{|G'/H'|}$$ and $$|f_g(G'/H')\cap R|=1, \forall g\in G$$. If $$\{r\}=f_g(G'/H')\cap R$$ then we take $$h(r)=f_{hg}(G'/H')\cap R$$. We see that this is a transitive action of $$G$$ on $$R$$. We have $$g(eH)=eH$$ if and only if $$gH\in G'/H'\Rightarrow g\in \{xy|x\in G',y\in H\}$$ so $$\{xy|x\in G',y\in H\}$$ must be a subgroup of $$G$$ (stable group of $$eH\in R$$).

Now if $$\{xy|x\in G',y\in H\}$$ is a subgroup of $$G$$, we have $$G'H=\{xy|x\in G',y\in H\}$$ and $$|G'H|=\frac{|G'||H|}{|H'|}$$ (Example 3.25 Page 15). Take $$L$$ be the left transversal for $$G'H$$ in $$G$$ and take $$R=\{lH|l\in L\}$$, it can be check that $$|R|=\frac{|G/H|}{|G'/H'|}$$ and $$|f_g(G'/H')\cap R|=1, \forall g\in G$$, we take $$S=G/H-R$$ then we have $$\alpha(G,G',H)=|G'/H'|$$.

So $$\alpha(G,G',H)=|G'/H'|$$ if and only if $$\{xy|x\in G',y\in H\}$$ is a subgroup of $$G$$. This result might suggest duality property of this problem.