Presentation of the symmetric group of a cartesian product of finite sets Let $X$ and $Y$ be finite sets. For any set $A$, I will write $\mathfrak{S}(A)$ for its symmetric group, ie the group of bijections $A\to A$. Then $\mathfrak{S}(X\times Y)$ is generated by the subgroups $\mathfrak{S}(X)^Y$ (the permutations which perserve each $X\times \{y\}$) and $\mathfrak{S}(Y)^X$ (the permutations which perserve each $\{x\}\times Y$).
Is there a reference for finding the relations between the elements of those subgroups so that we get a presentation of $\mathfrak{S}(X\times Y)$? So, in other terms, a nice set of generators of the kernel of $\mathfrak{S}(X)^Y\ast \mathfrak{S}(Y)^X\to \mathfrak{S}(X\times Y)$ (where $G\ast H$ is the free product of $G$ and $H$)?
I would already be completely happy with the case $|Y|=2$, so that the big group is $\mathfrak{S}(X\coprod X)$, and the subgroups are the Young subgroup $\mathfrak{S}(X)\times \mathfrak{S}(X)$ and the group $(\mathbb{Z}/2\mathbb{Z})^X$ acting by exchanging corresponding elements in the two copies of $X$. The presentation could for instance be in terms of the standard transpositions $(i,\, i+1)$ in each $\mathfrak{S}(X)$ (if we order $X$) and the standard basis elements of $(\mathbb{Z}/2\mathbb{Z})^X$ (so the transpositions exchanging two copies of one element).
It seems to me that this should be a somewhat classical consideration in combinatorics or representation theory, but it is not that easy, and I have not been able to find any reference so far.

Edit: It occurred to me that perhaps a nice way to formulate the issue is the following: given a connected simple graph with set of vertices $A$, the transpositions corresponding to each edge generate the symmetric group $\mathfrak{S}(A)$. How to describe the relations between those generators in terms of the geometry of the graph? This is very wide, but the question above corresponds to the graph being an $n\times m$ grid, with an edge between any adjacent vertices in the grid, vertically and horizontally.
 A: Obviously I should have thought about this a little more before posting the question, it is actually not that hard. It turns out that in the graph formulation of the question, the global geometry of the graph does not matter at all: if $\tau_e$ is the transposition attached to the edge $e$, then we get a presentation of the full symmetric group of the vertices using the relations: $\tau_e^2=1$, $\tau_e\tau_f=\tau_f\tau_e$ if $e$ and $f$ do not have a common vertex, and $(\tau_e\tau_f)^3=1$ if $e$ and $f$ have one common vertex.
This is the classical presentation when the graph is just a linear chain, but I initially thought that more complicated graphs would add extra relations. It is actually not the case. To see this, let $A$ be a finite set, and let $G_A$ be the set of all simple graphs with set of vertices $A$. To each such graph $\mathcal{G}$, one can associate the group presentation
$$ S_\mathcal{G} = \langle \tau_e, e \text{ edge in $\mathcal{G}$} \,|\, \tau_e^2=1, 
(\tau_e\tau_f)^3=1 \text{ if $e$ and $f$ are adjacent}, \tau_e\tau_f = \tau_f\tau_e \text{ otherwise} \rangle $$
and there is a canonical injective morphism $S_\mathcal{G}\to \mathfrak{S}(A)$ where $\tau_e$ is sent to the transposition exchanging the vertices of $e$. Now let $H_A\subset G_A$ be the subset of graphs such that this morphism is an isomorphism. Then we have the following facts:

*

*if $\mathcal{G}$ is a subgraph of $\mathcal{G}'$ and $\mathcal{G}\in H_A$, then $\mathcal{G}'\in H_A$;

*given subsets $A_i\subset A$ such that any pair of elements of $A$ is in at least one $A_i$, and $\mathcal{G}_i\in H_{A_i}$, then $\mathcal{G}=\bigcup_i \mathcal{G}_i\in H_A$;

*If $\mathcal{G}\in G_A$ is a linear chain, then $\mathcal{G}\in H_A$.

Only the last claim is nontrivial, but it is a reformulation of the classical presentation of the symmetric group (as a Coxeter group). Then we can prove that $\mathcal{G}\in H_A$ if and only if it is connected: the fact that it is necessary to be connected is obvious, and if it is the case, first choose a covering subtree $\mathcal{T}\subset \mathcal{G}$, and then for each pair of endpoints of $\mathcal{T}$ consider the unique path $\mathcal{T}_i\subset \mathcal{T}$ between those endpoints. By basic properties of trees, any pair of points is in such a path, and those paths are linear (there is no loop involved). Then the third claim shows that $\mathcal{T_i}$ is in $H_{A_i}$ (where $A_i$ is its set of vertices), the second claim implies that $\mathcal{T}\in H_A$, and the first allows us to conclude that $\mathcal{G}\in H_A$.

For my original question, this means that we get a presentation of $\mathfrak{S}(X\times Y)$ from the transpositions $\tau_{x_1,x_2;y}$ exchanging $(x_1,y)$ and $(x_2,y)$ (which generate $\mathfrak{S}(X)^Y$), and $\tau'_{x;y_1,y_2}$ exchanging $(x,y_1)$ and $(x,y_2)$ (which generate $\mathfrak{S}(Y)^X$), by simply adding the relations that $\tau_{x_1,x_2;y}$ and $\tau'_{x;y_1,y_2}$ commute when
$x\neq x_1,x_2$ or $y\neq y_1,y_2$, and $(\tau_{x_1,x_2;y}\tau'_{x;y_1,y_2})^3=1$
when $x=x_i$ and $y=y_j$.
