Tiling the symmetric group by transpositions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917455340765184 |
|---|---|
| author | Fang, Teng Xia, Binzhou |
| author_facet | Fang, Teng Xia, Binzhou |
| contents | For nonempty subsets $X$ and $Y$ of a group $G$, we say that $(X,Y)$ is a tiling of $G$ if every element of $G$ can be uniquely expressed as $xy$ for some $x\in X$ and $y\in Y$. In 1966, Rothaus and Thompson studied whether the symmetric group $S_n$ with $n\geq3$ admits a tiling $(T_n,Y)$, where $T_n$ consists of the identity and all the transpositions in $S_n$. They showed that no such tiling exists if $1+n(n-1)/2$ is divisible by a prime number at least $\sqrt{n}+2$. In this paper, we establish a new necessary condition for the existence of such a tiling: the subset $Y$ must be partition-transitive with respect to certain partitions of $n$. This generalizes the result of Rothaus and Thompson, as well as a result of Nomura in 1985. We also study whether $S_n$ can be tiled by the set $T_n^*$ of all the transpositions, which finally leads us to conjecture that neither $T_n$ nor $T_n^*$ tiles $S_n$ for any $n\geq4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00360 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tiling the symmetric group by transpositions Fang, Teng Xia, Binzhou Combinatorics Representation Theory For nonempty subsets $X$ and $Y$ of a group $G$, we say that $(X,Y)$ is a tiling of $G$ if every element of $G$ can be uniquely expressed as $xy$ for some $x\in X$ and $y\in Y$. In 1966, Rothaus and Thompson studied whether the symmetric group $S_n$ with $n\geq3$ admits a tiling $(T_n,Y)$, where $T_n$ consists of the identity and all the transpositions in $S_n$. They showed that no such tiling exists if $1+n(n-1)/2$ is divisible by a prime number at least $\sqrt{n}+2$. In this paper, we establish a new necessary condition for the existence of such a tiling: the subset $Y$ must be partition-transitive with respect to certain partitions of $n$. This generalizes the result of Rothaus and Thompson, as well as a result of Nomura in 1985. We also study whether $S_n$ can be tiled by the set $T_n^*$ of all the transpositions, which finally leads us to conjecture that neither $T_n$ nor $T_n^*$ tiles $S_n$ for any $n\geq4$. |
| title | Tiling the symmetric group by transpositions |
| topic | Combinatorics Representation Theory |
| url | https://arxiv.org/abs/2506.00360 |