Tiling symmetric groups by transpositions

2025/05/31 by Fang, Teng, Xia, Binzhou
#Combinatorics (math.CO) #FOS: Mathematics #Representation Theory (math.RT)

paper · doi:10.48550/arxiv.2506.00360

Abstract

For two 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∈ X and y∈ Y. In 1966, Rothaus and Thompson studied whether the symmetric group S_n with n≥3 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 √(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 transpositions, which finally leads us to conjecture that neither T_n nor T_n^* tiles S_n for any n≥3.

Citations

• Proof of a conjecture of Green and Liebeck on codes in symmetric groups
• Spread approximations for forbidden intersections problems
• On codes in the projective linear group PGL(2,q)
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• A comment on Intersecting Families of Permutations
• Frankl-Rödl type theorems for codes and permutations
• Intersecting Families of Permutations
• A new notion of transitivity for groups and sets of permutations

Related

• Undecidable translational tilings with only two tiles, or one nonabelian tile
• Combinatorial and harmonic-analytic methods for integer tilings
• Algorithms for translational tiling
• Edge-transitivity of Cayley graphs generated by transpositions
• A new notion of transitivity for groups and sets of permutations