0/1-Polytopes related to Latin squares autotopisms

Abstract

The set LS(n) of Latin squares of order $n$ can be represented in ${\mathbb{R}}^{n^3}$ as a $(n-1{)}^3$-dimensional 0/1-polytope. Given an autotopism $\Theta =(\alpha ,\beta ,\gamma )\in {\mathfrak{A}}_n$, we study in this paper the 0/1-polytope related to the subset of LS(n) having $\Theta$ in their autotopism group. Specifically, we prove that this polyhedral structure is generated by a polytope in ${\mathbb{R}}^{(({\mathbf{n}}_{\alpha }-{\mathbf{l}}_{\alpha }^1)\cdot n^2+{\mathbf{l}}_{\alpha }^1\cdot {\mathbf{n}}_{\beta }\cdot n)-({\mathbf{l}}_{\alpha }^1\cdot {\mathbf{l}}_{\beta }^1\cdot (n-{\mathbf{l}}_{\gamma }^1)+{\mathbf{l}}_{\alpha }^1\cdot {\mathbf{l}}_{\gamma }^1\cdot ({\mathbf{n}}_{\beta }-{\mathbf{l}}_{\beta }^1)+{\mathbf{l}}_{\beta }^1\cdot {\mathbf{l}}_{\gamma }^1\cdot ({\mathbf{n}}_{\alpha }-{\mathbf{l}}_{\alpha }^1))}$, where ${\mathbf{n}}_{\alpha }$ and ${\mathbf{n}}_{\beta }$ are the number of cycles of $\alpha$ and $\beta$, respectively, and ${\mathbf{l}}_{\delta }^1$ is the number of fixed points of $\delta$, for all $\delta \in \{\alpha ,\beta ,\gamma \}$. Moreover, we study the dimension of these two polytopes for Latin squares of order up to 9.

8 pages, 2 tables