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)$.

  • 1
    $\begingroup$ Interesting question! $\endgroup$ Aug 28 at 15:44
  • $\begingroup$ It is not possible for $n=2$ or $n=4$. Did you mean instead $n>4$? $\endgroup$
    – RobPratt
    Aug 28 at 17:13
  • $\begingroup$ There are such matchings when $n$ is an odd number larger than $1$. Namely, for $k=1,2,\ldots,n-1$, let $M_k:=\{u_i v_{i\oplus k}: i=1,2,\ldots,n\}$, where $i\oplus k:=((i-1+k)\bmod n)+1$. The case where $n$ is even looks much less trivial. $\endgroup$
    – Algernon
    Aug 28 at 20:29

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.

  • $\begingroup$ Is there any known algorithm to construct an $N_2$ latin square for every given $n$, especially when $n$ is even? $\endgroup$
    – Xin Zhang
    Aug 29 at 10:07
  • 3
    $\begingroup$ The theorem is constructive, so in that sense, yes. There is no single construction I know of that works for all cases; rather there are several different constructions which between them cover all cases. See Kotzig, Anton; Turgeon, Jean On certain constructions for Latin squares with no Latin subsquares of order two. Discrete Math. 16 (1976), 263–270 and Wanless, I. M. On McLeish's construction for Latin squares without intercalates. Ars Combin. 58 (2001), 313–317 and the references therein. Happy to send you copies to people. $\endgroup$ Aug 30 at 0:00

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\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.