Disjoint perfect matchings in complete bipartite graph

Question

Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\{u_1v_1,u_2v_2,\ldots,u_nv_n\}$.

Since $K^-_{n,n}$ is now $(n-1)$-regular, it has $n-1$ disjoint perfect matchings. My question is whether the edges of $K^-_{n,n}$ with $n\geq 4$ can be decomposed into $n-1$ disjoint perfect matchings in such a way that in each matching $M$, if $u_iv_j\in E(M)$ then $v_iu_j\not\in E(M)$.

Answer 1

The answer is that this is possible for all $n>4$.

Your question is equivalent to asking whether there exists a unipotent Latin square $L$ of order $n$ with $L_{ij}\ne L_{ji}$ for $i\ne j$. The equivalence is obtained by using $L_{ij}$ to record the index of the matching that contains the edge $u_i v_j$ (and putting $L_{ii}=n$ for each $i$).

The existence of such a Latin square follows from a stronger property. It is a theorem (collectively due to the work of Kotzig, McLeish, Turgeon and others) that for all $n\notin\{2,4\}$ there exists a Latin square of order $n$ that has no intercalates (an intercalate is a $2\times2$ submatrix that is itself a Latin square). This property of Latin squares is called $N_2$ in the literature.

If you permute the rows of any $N_2$ Latin square you can make every symbol on the main diagonal equal to $n$. You then have what you need.

Answer 2

For fixed $n$, you can solve the problem via integer linear programming as follows. For edge $(i,j)\in E$ and matching $k\in\{1,\dots,n-1\}$, let binary decision variable $x_{i,j,k}$ indicate whether edge $(i,j)$ appears in matching $k$. The constraints are \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all $(i,j)$} \tag1\\ \sum_{(i,j)\in E} x_{i,j,k} &= 1 &&\text{for all $i$ and $k$} \tag2\\ \sum_{(i,j)\in E} x_{i,j,k} &= 1 &&\text{for all $j$ and $k$} \tag3\\ x_{i,j,k} + x_{j,i,k} &\le 1 &&\text{for all $(i,j)$ and $k$} \tag4\\ x_{1,j,j-1} &= 1 &&\text{for $j\in\{2,\dots,n\}$} \tag5 \end{align}

Constraint $(1)$ enforces one matching per edge. Constraint $(2)$ enforces one edge per left node and matching. Constraint $(3)$ enforces one edge per right node and matching. Constraint $(4)$ prevents edges $(i,j)$ and $(j,i)$ from appearing in the same matching. Constraint $(5)$ is optional and breaks symmetry. The problem is infeasible for $n\in\{2,4\}$ and feasible for $n\in\{1,\dots,40\}\setminus\{2,4\}$.