Discrete Mathematics & Theoretical Computer Science |

Recent research on the combinatorics of finite sets has explored the structure of symmetric difference-closed sets, and recent research in combinatorial group theory has concerned the enumeration of commuting involutions in $S_{n}$ and $A_{n}$. In this article, we consider an interesting combination of these two subjects, by introducing classes of symmetric difference-closed sets of elements which correspond in a natural way to commuting involutions in $S_{n}$ and $A_{n}$. We consider the natural combinatorial problem of enumerating symmetric difference-closed sets consisting of subsets of sets consisting of pairwise disjoint $2$-subsets of $[n]$, and the problem of enumerating symmetric difference-closed sets consisting of elements which correspond to commuting involutions in $A_{n}$. We prove explicit combinatorial formulas for symmetric difference-closed sets of these forms, and we prove a number of conjectured properties related to such sets which had previously been discovered experimentally using the On-Line Encyclopedia of Integer Sequences.

Source : oai:HAL:hal-01345066v4

Volume: Vol. 19 no. 1

Section: Combinatorics

Published on: March 23, 2017

Accepted on: March 23, 2017

Submitted on: March 22, 2017

Keywords: symmetric difference-closed set,commuting involution,Klein four-group,permutation group,combinatorics of finite sets,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

This page has been seen 642 times.

This article's PDF has been downloaded 976 times.