\documentclass[10pt]{article}
\renewcommand{\figurename}{Fig.}
%\usepackage[utf8]{inputenc}
%\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[koi8-r,cp1251]{inputenc}
\usepackage[english]{babel}
\author{Lerner E.Yu.}
\date{}
\title{A counterexample of size~20 for the problem of finding a 3-dimensional stable matching with cyclic preferences}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{proposition}{Proposition}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\tikzset{cblue/.style={circle, draw, thin,fill=cyan!20, scale=0.7}}
\tikzset{cred/.style={circle, draw, thin, fill=red!20, scale=0.7}}
\tikzset{cgreen/.style={circle, draw, thin, fill=green!20, scale=0.7}}
\tikzset{cblack/.style={circle, draw, thin, fill=black, scale=0.3}}
\usepackage{hyperref}
\begin{document}
\maketitle
\begin{abstract}
Given $n$ men, $n$ women, and $n$ dogs, each man has a complete preference list of women, while each woman does a complete preference list of dogs, and each dog does a complete preference list of men. We understand a matching as a collection of $n$ nonintersecting triples, each of which contains a man, a woman, and a dog. A matching is said to be nonstable, if one can find a man, a woman, and a dog, which belong to different triples and prefer each other to their current partners in the corresponding triples. Otherwise, the matching is said to be stable (a weakly stable matching in 3DSM-CYC). E. Boros, V. Gurvich, S. Jaslar, and D. Krasner (2004) have proved that $k$-DSM-CYC is solvable if $n\leq k$. K. Eriksson, J. S\"ostrand, and P. Strimling (2006) state the conjecture that any 3DSM-CYC has a solution with any $n$ (and this is true for $n<6$). However, C.-K. Lam and G. Paxton (2019) have proposed an algorithm for constructing preference lists in 3DSM-CYC of size $n=90$ (or $n=45$ considering our recent results for 3DSMI-CYC, on which Lam and Paxton's result is based). This has allowed them to disprove the mentioned conjecture. We construct an instance of 3DSM-CYC with no stable matching, whose size $n=20$.
\end{abstract}
\section{Introduction}
Given $n$ men, $n$ women, and $n$ dogs such that each man (respectively, woman, dog) has a strictly ordered preference list over a subset of women (respectively dogs, men).
Recall that a 3-dimensional matching $\mu$ is a partition of the set of all men, women, and dogs into disjoint heterogeneous triples. 
For a triple $(m,w,d)$ in $\mu$, the symbol $\mu(m)$ means $w$, while $\mu(w)$ means $d$, and $\mu(d)$ does $m$.
A matching $\mu$ is (weakly) stable if it admits no blocking triple, i.e., a triple $(m,w,d)$ such that $m$ prefers $w$ to $\mu(m)$, $w$ prefers $d$ to $\mu(w)$, and $d$ prefers $m$ to $\mu(d)$. 
The 3DSM-CYC problem consists in finding a stable matching.

The interest to this problem is due to the publication of the paper~\cite{gurvich} by E.~Boros, V.~Gurvich, S.~Jaslar, and D.~Krasner. They have succeeded in proving the existence of a stable matching for $k$-DSM-CYC (with the evident definition of $k$-DSM-CYC) in a more general case, provided that $n\leqslant k$. 

The approach to finding a stable matching proposed in~\cite{gurvich} is based on the following idea.
Let us start with an arbitrary man $m$ (as an example, we consider 3DSM-CYC (or just 3DSM), i.e., the case of $k=3$), who chooses the woman~$w$ that he likes best, while the woman, in turn, chooses the dog~$d$ that she likes best. (In a general case, we repeat this best choice procedure until we form a complete family consisting of $k$ representatives of various genders). Then we add the formed family to the matching and take it out of consideration. We repeat the same procedure until no one is left. We can prove that with $n<k$ we get a stable matching. But with $n=k$ we cannot start with an arbitrary ``man'', and do not guaranteedly get a stable matching. 
However, according to the paper~\cite{gurvich}, the technique of the ``best choice among remaining alternatives'' also works in the considered case, provided that ``men'' who start the construction of their families are chosen properly. 
Nevertheless, authors of the mentioned paper demonstrate that this technique, generally speaking, does not work with $n>k$. Therefore, the existence of a stable matching of 3DSM with $n\leqslant 3$ is proved in~\cite{gurvich}.

In~\cite{Eriksson}, K.~Eriksson, J.~S\"ostrand, and P.~Strimling generalize this result for the case when $n=4$. Ibid, they state the conjecture that any 3DSM has a solution with any~$n$. Using the statement of the satisfiability problem and performing an extensive computer-assisted search, K.~Pashkovich, L.~Poirrier (see \cite{new}) prove the validity of the conjecture stated by K.~Eriksson et al. for~$n=5$.
D.~Manlove~\cite{manlove} writes: ``Perhaps the most intriguing open problem in this list, at least in view of the number of authors that have mentioned it, concerns 3DSM-CYC, and in particular the question of whether every instance $I$ of this problem admits a weakly stable matching.''

The conjecture stated by K.~Eriksson et al. has been recently disproved by C.-K.~Lam and C.G.~Plaxton~\cite{Lam}. 
They use 3DSMI (the problem of finding a stable matching with incomplete preference lists in the 3D-case). 

In 2010, P.~Bir\'o and E.~McDermid~\cite{Biro} gave a sufficiently simple example of 3DSMI of size $n = 6$, where no stable matching exists. 
C.-K.~Lam and C.G.~Plaxton associate 3DSMI with a certain 3DSM problem, where $n$ is 15 times greater than the initial size; this problem is solvable if and only if so is the initial 3DSMI problem. 
Thus, the size of this initial counterexample is equal to 90.

An evident way to reduce the size of counterexamples of 3DSM is to solve the P.~Bir\'o and E.~McDermid problem that implies the search of instances of 3DSMI with no stable matching for $n<6$. We solve the mentioned problem in the paper~\cite{old}. We prove the absence of such instances for $n<3$ and construct several counterexamples for 3DSMI with $n=3$. Therefore, the result obtained in~\cite{Lam} allows one to construct an instance of 3DSM with no stable matching for $n=45$.

Another approach to reducing the size of counterexamples of 3DSM is to reduce the value of the multiplier (its current value equals 15) when constructing an unsolvable instance of 3DSM from an unsolvable 3DSMI problem. We prove that one can associate each instance of 3DSMI of size $n$ with no stable matching with an instance of 3DSM of size $8n$ with the same property. This allows us to reduce the size of the counterexample of 3DSM to $3\times 8 = 24$.

Then by making use of specific features of a certain concrete instance of 3DSMI with no stable matching, we construct a counterexample for 3DSM of size $n=20$.

For clarity, we use the visual language of the graph theory.


\section{The statement of 3DSM (3DSMI) in terms of the graph theory}
Let $G$ be some directed graph. Denote the set of its edges by $E$ (or $E(G)$); assume that no edge is multiple. Assume that the vertex set~$V$ of the graph~$G$ is divided into three subsets, namely, the set of men~$M$, women~$F$, and dogs~$D$. 
Assume that edges $(v,v')$, $v,v'\in V$, of this graph are such that either $v\in M, v'\in F$, or $v\in F, v'\in D$, or $v\in D, v'\in M$.
Assume that $|M|=|F|=|D|$ (otherwise we supplement the corresponding subgraph with vertices that are not connected with the rest part of the graph). The number $n=|M|=|F|=|D|$ is called the problem \textit{size.} 

Each edge $(v,v')$, $v,v'\in V$, corresponds to some positive integer $r(v,v')$; it is called the rank of this edge. For fixed $v\in V$, all possible ranks $r(v,v_1),\ldots,r(v,v_k)$ coincide with $\{1,\ldots,k\}$, where $k$ is the outgoing vertex degree~$v$ (if $r(v, v') = 1$, then $v'$ is the best preference for $v$, and so on).

We understand a \textit{three-sided matching} as a subgraph~$H$ of the graph $G$, $V(H)=V(G)=V$, where each vertex $v\in V$ has at most one outgoing edge and the following condition is fulfilled: if a vertex $v$ has an outgoing edge, then this edge belongs to a cycle of length~3 in the graph~$H$. Cycles of length~3 in the graph $H$ are called \textit{families}. 

A \textit{matching} $\mu$ is a collection of all families of a three-sided matching $H$. For a vertex $v$, $v\in V$, in the matching $\mu$, the rank $R_\mu(v)$ is defined as the rank of the edge that goes out of this vertex in the subgraph $H$. If some vertex $v$ in the subgraph $H$ has no outgoing edge, then $R_\mu(v)$ is set to $+\infty$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cred] (5) at ( 0:1) {\bf 5};
        \node[cblue] (0) at ( 60:1) {0};
        \node[cgreen] (1) at ( 120:1) {1};
        \node[cred] (2) at ( 180:1) {\bf 2};
        \node[cblue] (3) at ( 240:1) {3};
        \node[cgreen] (4) at ( 300:1) {4};
        \node[cblue] (6) at ( 340:2.5) {6};
        \node[cgreen] (7) at ( 60:2) {7};
        \node[cred] (8) at ( 10:2.5) {\bf 8};

        \path[every node/.style={font=\sffamily\small}]
        (0) edge  []  node [] {} (1)
        (1) edge  []  node [] {} (2)
        (2) edge  []  node [] {} (3)
        (3) edge  []  node [] {} (4)
        (4) edge  []  node [] {} (5)
        (5) edge  []  node [] {} (0)

        (6) edge  []  node [] {} (4)
        (7) edge  []  node [] {} (8)
        (8) edge  []  node [] {} (0)
        
        (4) edge  [dashed]  node [] {} (8)
        (8) edge  [dashed]  node [] {} (6)
        (0) edge  [dashed] node [] {} (7)
        (4) edge  [dotted]  node [] {} (2)    
        (1) edge  [dashed]  node [] {} (5)
        (5) edge  [dashed]  node [] {} (3)
        (3) edge  [dashed] node [] {} (1)
        ;
\end{tikzpicture}
\caption{The graph~$H$ of 3DSMI of size~3 with no stable matching. 
For convenience, we numerate vertices~$H$ with numbers~$v$, $v=0,1,\ldots,8$. 
The value $v\bmod 3$ specifies the gender that corresponds to the vertex~$v$. The rank of each edge, which is represented by a solid line, equals~1. Dashed lines represent edges, whose rank equals~2. The rank of the edge~$(4,2)$ equals~3.}
\label{example}
\end{center}
\end{figure}

A triple $(v,v',v'')$ is said to be \textit{blocking} for some matching $\mu$, if it represents a cycle in the graph~$G$, and
\begin{equation}
\label{oldc}
r(v,v')<R_\mu(v),\quad r(v',v'')<R_\mu(v'),\quad r(v'',v)<R_\mu(v'').
\end{equation}
A matching $\mu$ is said to be \textit{stable} if no blocking triple exists for it.

Recall that \textit{3DSMI} consists of finding a stable matching for a given graph~$G$. 
\textit{3DSM} represents a particular case of 3DSMI, where the outgoing (and incoming) degree of each vertex of the corresponding graph equals the problem size~$n$.

\begin{lemma}[\cite{old}, Theorem~2]
3DSMI with the graph $G$ shown in Fig.~\ref{example} has no stable matching.
\label{app}
\end{lemma}
\noindent \textbf{Proof:}
There exist 7 families that form matchings in this problem, namely, $(0,1,5)$, $(0,7,8)$, $(1,2,3)$, $(1,5,3)$, $(2,3,4)$, $(3,4,5)$, and $(4,8,6)$.

Recall that a matching $\mu$ in 3DSMI defined by the graph~$G$ is said to be \textit{complementable}, if there exists a triple of vertices $(v,v',v'')$ such that $\mu(v)=v$, $\mu(v')=v'$, $\mu(v'')=v''$, and $\{(v,v'),(v',v'')(v'',v)\}\subseteq E(G)$.

Evidently, any complementable matching is not stable, and the triple $(v,v',v'')$ mentioned in the above paragraph is blocking for it. Therefore, for proving the absence of a stable matching, it suffices to find blocking triples for all noncomplementable matchings. 
For the graph shown in Fig.~\ref{example} there exists 8 noncomplementable matchings. Below we give their complete list together with blocking triples:\\
1) $\{(0,1,5),(2,3,4)\}$, the blocking triple is $(4,8,6)$;\\
2) $\{(0,1,5),(4,8,6)\}$, the blocking triple is $(1,2,3)$;\\
3) $\{(0,7,8),(1,2,3)\}$, the blocking triple is $(3,4,5)$;\\
4) $\{(0,7,8),(1,5,3)\}$, the blocking triple is $(2,3,4)$;\\
5) $\{(0,7,8),(2,3,4)\}$, the blocking triple is $(0,1,5)$;\\
6) $\{(0,7,8),(3,4,5)\}$, the blocking triple is $(0,1,5)$;\\
7) $\{(1,2,3),(4,8,6)\}$, the blocking triple is $(0,7,8)$ or $(3,4,5)$;\\
8) $\{(1,5,3),(4,8,6)\}$, the blocking triple is $(0,7,8)$. \qquad  $\square$

\bigskip

Let $H'$ be some subgraph of the graph of 3DSM. In what follows, we consider certain (specific for this paper) denotations and terms, which contain this subgraph. 
For any vertex $v\in V(H')$, we define the following values:
$$
\overline \rho_{H'}(v)=\max\limits_{(v,w)\in E(H')} r(v,w),\qquad {\underline \rho\,}_{H'}(v)=\min\limits_{(v,w)\in E(H')} r(v,w).
$$ 

Let $(x,y)\in E(H')$. We call the subgraph~$H'$ an \textit{$(x,y)$-attractor}, if for any 3DSM with a stable matching $\mu$,
the equality $\mu(x)=y$ implies the inclusion $\mu(y)\in V(H')$.
Informally speaking, an $(x,y)$-attractor ``covers'' any family in $\mu$, which contains its edge $(x,y)$.

Let us introduce one more definition. Assume, as above, that $x\in V(H')$. We call the subgraph~$H'$ an \textit{$x$-superattractor}, if for any 3DSM with a stable matching~$\mu$, the inequality $R_\mu(x)\geqslant {\underline \rho\,}_{H'}(x)$ implies the inclusion $\{\mu(x),\mu^{-1}(x)\}\subseteq V(H')$. In other words, the subgraph $H'$ contains a family $(x,y,z)$ from $\mu$, if the rank of the edge $(x,y)$ is not less than the rank of some edge of this subgraph incident to~$x$. 

Evidently, an $x$-superattractor is an $(x,y)$-attractor for any $(x,y)\in E(H')$. The above definition also implies that any subgraph $H''$ of the graph of 3DSM such that $H''\subseteq H'$ has the following properties:
\begin{enumerate}
\item If $H''$ is an $(x,y)$-attractor, then $H'$ also is an $(x,y)$-attractor.
\item Let the set of edges that are incident to the vertex $x$ be one and the same both in $H'$ and in $H''$. Then if $H''$ is an $x$-superattractor, then $H'$ also is an $x$-superattractor.
\end{enumerate}
We call properties~1 and~2 inheritance properties of the attractor (superattractor) obtained with the extension of the graph.

\section{The correspondence between unsolvable 3DSMI and 3DSM}
\begin{figure}[h]
\begin{center}
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cred] (c) at (0:0) {$\mathbf c$};
        \node[cred] (d) at (0:4) {$\mathbf d$};
        \node[cgreen] (e) at (90:1) {$e$};
        \node[cblue] (a) at ( 330:1.6) {$a$};
        \node[cblue] (t) at ( 29:3.3) {$t$};
        \node[cgreen] (x) at ( 292.5:1.84776) {$x$};
        \node[cblue] (b) at ( 225:1.2) {$b$};
        \node[cgreen] (s) at (15:3) {$s$};

        \path[every node/.style={font=\sffamily\small}]
        (e) edge  []  node [] {} (c)
        (c) edge  []  node [] {} (a)
        (d) edge  []  node [] {} (a)
        (a) edge  []  node [] {} (x)
        (b) edge  []  node [] {} (x)
        (t) edge  [dashed]  node [] {} (s)
        (t) edge  []  node [] {} (e)
        (s) edge  []  node [] {} (d)
        (e) edge  [dashed]  node [] {} (d)
        (c) edge  [dashed]  node [right] {} (b)
        (d) edge  [dashed]  node [right] {} (b)
        (x) edge  [dotted]  node [right] {$r'_x$} (c)
        (x) edge  [dotted]  node [right] {$r_x'+1$} (d)    
        (b) edge  [dotted]  node [right] {3} (s)    
        (d) edge  [dotted]  node [right] {3} (t)    
        (a) edge  [dashed]  node [] {} (e)
        (b) edge  [dashed]  node [] {} (e)
        ;
        \end{tikzpicture}
\caption{The subgraph~$H'$ of the preference graph considered in Lemma~\ref{key1}. 
Vertices of various colors correspond to various genders. Bold lines represent edges of rank~1, while dashed ones do those of rank~2. Ranks of edges represented by dotted lines equal $r'_x$, $r'_x+1$, or~3 (ranks are indicated near edges).}
\label{keyGraph}
\end{center}
\end{figure}

\begin{lemma}[The Key Lemma for Theorem~\ref{unSolvabable}]
\label{key1}
Let some subgraph of the graph of 3DSM take the form shown in~Fig.~\ref{keyGraph}, in particular,
\begin{equation}
\label{ranksRestrict}
r(b,s)=r(d,t)=3,\quad r(x,c)=r'_x,\ r(x,d)=r'_x+1,
\end{equation}
where $r'_x\in\{1,\ldots,n-1\}$. 
Then $H'$ is an $x$-superattractor. 
\end{lemma}

\noindent\textbf{The proof (scheme):}
\begin{lemma}\label{key11}
Assume that some subgraph $H''$ of the graph of 3DSM takes the form shown in Fig.~\ref{keyGraph11}.
Then $H''$ is an $(x,c)$-attractor. 
\end{lemma}


\begin{figure}[h]
\begin{center}
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cred] (c) at (0:0) {$\mathbf c$};
        \node[cgreen] (e) at (90:1) {$e$};
        \node[cblue] (a) at ( 330:1.6) {$a$};
        \node[cgreen] (x) at ( 292.5:1.84776) {$x$};
        \node[cblue] (b) at ( 225:1.2) {$b$};

        \path[every node/.style={font=\sffamily\small}]
        (e) edge  []  node [] {} (c)
        (c) edge  []  node [] {} (a)
        (a) edge  []  node [] {} (x)
        (b) edge  []  node [] {} (x)
        (c) edge  [dashed]  node [right] {} (b)
        (x) edge  [line width=0.6mm, dotted]  node [left] {} (c)
        (a) edge  [dashed]  node [] {} (e)
        (b) edge  [dashed]  node [] {} (e)
        ;
        \end{tikzpicture}
\caption{The subgraph~$H''$ of the preference graph considered in Lemma~\ref{key11}.
}
\label{keyGraph11}
\end{center}
\end{figure}


\begin{lemma}
\label{key111}
The subgraph $H'$ shown in Fig.~\ref{keyGraph} is an $(x,d)$-attractor.
\end{lemma}
Note that the first inheritance property and lemmas~\ref{key11} and~\ref{key111} imply that the subgraph~$H'$ is concurrently an $(x,c)$-attractor and an $(x,d)$-attractor.

\begin{lemma}
\label{key13}
Assume that some subgraph of the graph of 3DSM takes the form shown in Fig.~\ref{keyGraphOld}.
Let $\mu$ be a stable matching in this problem and $R_\mu(x)\geqslant r'_x$.  Then $\mu(x)\in\{c,d\}$.
\end{lemma}
\begin{figure}[h]
\begin{center}
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cred] (c) at (0:0) {$\mathbf c$};      
        \node[cred] (d) at (0:4) {$\mathbf d$};
        \node[cblue] (a) at ( 330:1.6) {$a$};
        \node[cgreen] (x) at ( 292.5:1.84776) {$x$};
        \node[cblue] (b) at ( 225:1.2) {$b$};   
        
        \path[every node/.style={font=\sffamily\small}]
        (c) edge  []  node [] {} (a)
        (d) edge  []  node [] {} (a)
        (a) edge  []  node [] {} (x)
        (b) edge  []  node [] {} (x)
        (c) edge  [dashed]  node [right] {} (b)
        (d) edge  [dashed]  node [right] {} (b)
        (x) edge  [dotted]  node [right] {$r'_x$} (c)
        (x) edge  [dotted]  node [right] {$r_x'+1$} (d)    
        ;
        \end{tikzpicture}
\caption{The part of the preference graph considered in Lemma~\ref{key13}. 
Solid lines represent edges of rank~1, while dashed ones do those of rank~2. 
Ranks of edges represented by dotted lines equal $r'_x$ and $r'_x+1$ (ranks are indicated near edges).
}
\label{keyGraphOld}
\end{center}
\end{figure}

The assertion of Lemma~\ref{key1} evidently follows from proved lemmas~\ref{key11},~\ref{key111}, and~\ref{key13}.

\begin{remark}
\label{r1}
In all figures, vertices that characterize genders are colored so as to make graph edges be directed only from red vertices to blue ones, from blue vertices to green ones, and from the latter to red ones. However, it is evident that one can ``shift these colors modulo~3''. 
\end{remark} 


\begin{theorem}
\label{unSolvabable}
Let $H$ be the graph of 3DSMI of size~$n$ with no stable matching. Let us use it for constructing the graph~$G$ of 3DSM in the following way. The graph $H$ is a subgraph of the graph~$G$ (with the same ranks of edges). To each vertex $x$ of the graph~$H$ we ``attach'' the corresponding copy of the graph $H'_x$ shown in Fig.~\ref{keyGraph} with vertices $a_x, b_x, c_x, d_x, e_x, s_x, t_x\not\in V(H)$ (all subgraphs $H'_x$ are pairwise disjoint). Moreover, let the value $r'_x$ in formulas~(\ref{ranksRestrict}) equal $\rho_H(x)+1$. Let us define ranks of the rest edges of the graph~$G$ of 3DSM arbitrarily. Then 3DSM with the graph $G$ has no stable matching. Here the size of 3DSM equals~$8n$.
\end{theorem}
\textbf{Proof (idea):}
Assume the contrary, i.e., assume that for 3DSM with the graph~$G$ there exists a stable matching $\mu_G$.  
We intend to construct the matching $\mu_H$ for 3DSMI defined by the graph~$H$ from the matching $\mu_G$. To this end, we will make use of Lemma~\ref{key1}.
Since the matching $\mu_H$ is not stable, we can find for it a blocking triple $(v,v',v'')$ composed of vertices of the subgraph~$H$.
Let us prove that the same triple $(v,v',v'')$ is blocking for $\mu_G$. 

Let $x\in V(H)$. Denote $y=\mu_G(x)$. The following alternatives are possible:

A) $y\not\in V(H)$. Then $\overline\rho_H(x)<R_{\mu_G}(x)$.
According to Lemma~\ref{key1}, we get the inclusion $\{y,\mu_G^{-1}(x)\}\subseteq V(H'_x)$.

B) $y\in V(H)$. Assume that $\mu_G(y)\not\in V(H)$. Then by Lemma~\ref{key1} we get the inclusion $\{\mu_G(y),\mu_G^{-1}(y)\}\subseteq V(H'_y)$. But since $\mu_G^{-1}(y)=x$, we get a contradiction. Consequently, in this case, $\mu_G(y)\in V(H)$.


Note that the latter property is very important. Informally speaking, it means that if a family is not ``catched'' by a superattractor, then it entirely lies in~$H$.

Let us associate the matching $\mu_G$ with the matching $\mu_H$ of 3DSMI with the graph~$H$. Assume that in the case of alternative~A, $\mu_H(x)=x$ (i.e., the agent $x$ remains single). In the case of alternative~B, we put $\mu_H(x)=\mu_G(x)$.

\ldots
\qquad  $\square$

Theorem~\ref{unSolvabable}, along with the result obtained in the paper~\cite{old} (see Lemma~\ref{app}), allows one to construct instances of 3DSM of size~24 with no stable matching.

\section{The Key Lemma for the further reduction of the counterexample size}
Recall that in Lemma~\ref{key1} we consider an $x$-superattractor, whose copy is ``$x$-attached'' to each vertex of the graph~$H$ that defines 3DSMI with no stable matching. In Lemma~\ref{key2}, we consider the subgraph, which in certain cases can have ``two attachments'' (vertices $x$ and $z$) to two vertices of such a graph~$H$. The ``cost'' of this effect is the supplement of the subgraph with the vertex~$f$ (apart from the ``attached'' vertex~$z$).
See Fig.~\ref{keyGraph2} for the graph under consideration.

\begin{remark}
The graph shown in Fig.~\ref{keyGraph} is a part of the graph shown in Fig.~\ref{keyGraph2}, only ranks of three edges in it are different. 
Namely, now the rank of edges directed from vertices $a$ and $b$ to the vertex~$z$ equals~2. Correspondingly, ranks of all edges that go from these vertices, which originally were not less than~2, now are larger by one, i.e., in the new graph, $r(a,e)=r(b,e)=3$ and $r(b,s)=4$. 
Ranks of all the rest edges in the subgraph of the graph shown in Fig.~\ref{keyGraph2}, which contains the same vertices~$x, a, b, c, d, e, s$, and $t$, are the same as in Fig.~\ref{keyGraph} (and no new edges appear in this subgraph). 
\label{r2}
\end{remark} 

\begin{figure}[h]
\begin{center}
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cblue] (f) at ( 139:2) {$f$};
        \node[cgreen] (x) at ( 319:2.7) {$x$};       
        \node[cred] (c) at (0:0) {$\mathbf c$};
        \node[cred] (d) at (0:4) {$\mathbf d$};
        \node[cgreen] (e) at (90:1) {$e$};
        \node[cblue] (a) at ( 330:1.6) {$a$};
        \node[cblue] (t) at ( 29:3.3) {$t$};
        \node[cgreen] (z) at ( 292.5:1.84776) {$z$};
        \node[cblue] (b) at ( 225:1.2) {$b$};
        \node[cgreen] (s) at (15:3) {$s$};

        \path[every node/.style={font=\sffamily\small}]
        (e) edge  []  node [] {} (c)
        (c) edge  []  node [] {} (a)
        (d) edge  []  node [] {} (a)
        (a) edge  []  node [] {} (x)
        (b) edge  []  node [] {} (x)
        (t) edge  [dashed]  node [] {} (s)
        (t) edge  [dashed]  node [] {} (s)
        (t) edge  []  node [] {} (e)
        (s) edge  []  node [] {} (d)
        (e) edge  [dashed]  node [] {} (d)
        (c) edge  [dashed]  node [right] {} (b)
        (d) edge  [dashed]  node [right] {} (b)
        (x) edge  [dotted]  node [left] {} (c)
        (x) edge  [dotted]  node [right] {} (d)    
        (b) edge  [dotted]  node [right] {4} (s)    
        (d) edge  [dotted]  node [right] {3} (t)    
        (a) edge  [dotted]  node [ left] {3} (e) 
        (b) edge  [dotted]  node [left] {3} (e)
        (z) edge  [dotted]  node [left] {} (c)
        (z) edge  [dotted]  node [right] {} (d)    
        (f) edge  []  node [] {} (e)
        (a) edge  [dashed]  node [right] {} (z)
        (b) edge  [dashed]  node [right] {} (z)
        (c) edge  [dotted]  node [left] {3} (f)
        ;        
        \end{tikzpicture}
\caption{The subgraph~$H'$ of the preference graph considered in Lemma~\ref{key2}. Ranks of edges $(x,c)$ and $(x,d)$ equal $r'_x$ and $r'_x+1$, those of edges $(z,c)$ and $(z,d)$ equal $r'_z$ and $r'_z+1$, correspondingly, the rank of edges $(c,f)$, $(b,e), (a,e)$, $(d,t)$ equals 3, while $r(b,s)=4$.}
\label{keyGraph2}
\end{center}
\end{figure}

For brevity of the further reasoning, we introduce one more definition (in fact, we have already used it implicitly when considering alternative~B in the proof of Theorem~\ref{unSolvabable}).
Let $H'$ be some subgraph of the graph of 3DSM, $w\in H'$. We say that it is \textit{$w$-detachable}, if for any stable matching $\mu$ of 3DSM the inequality 
$\mu(w)<\underline{\rho}\,_{H'} (w)$ implies that $\mu^{-1}(w)\not\in V(H')$.

\begin{lemma}[The Key Lemma for Theorem~\ref{exampleTh}]
\label{key2}
Assume that some subgraph~$H'$ of the graph of 3DSM takes the form shown in Fig.~\ref{keyGraph2}, where ranks are indicated near the corresponding edges.\\ 
A) If $H'$ is $z$-detachable, then $H'$ is an $x$-superattractor.\\
B) If any stable matching~$\mu$ of 3DSM satisfies the inequality $R_\mu(x)<r'_x$ and $H'$ is $x$-detachable (i.e., $\mu^{-1}(x)\not\in V(H')$), 
then $H'$ is a $z$-superattractor.
\end{lemma}

At the end part of Section~2, we mention inheritance properties possessed by an attractor and a superattractor with the extension of the subgraph. 
In this section, we need one more technique for constructing attractors and superattractors.

\begin{proposition}
\label{utv}
\it
Assume that $H'$ is a subgraph of the graph of 3SDM, which contains a certain edge $(v,w)$. Assume also that $\mu(v)\neq w$ for any stable matching~$\mu$ in the considered problem.
Let $H''$ be obtained from $H'$ by deleting the edge $(v,w)$ and subtracting one from ranks of all edges outgoing from the vertex ~$v$, which initially exceeded $r(v,w)$. If the resulting graph $H''$ is some $(x,y)$-attractor or $x$-superattractor, then so is the initial graph $H'$.
\end{proposition}

The validity of Proposition~\ref{utv} follows from the definition of an attractor and a superattractor, because the order of ranks of edges in the graph $H'$ is the same as that in the graph $H''$.

\medskip
\noindent\textbf{Proof of Lemma~\ref{key2} (scheme):}
Let us prove Lemma~\ref{key2} with the help of Lemma~\ref{key13}. But let us first consecutively prove analogs of lemmas~\ref{key11} and~\ref{key111}.
\begin{figure}[h]
\begin{center}
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,thick,main node/.style={rectangle,fill=blue!20,draw,font=\sffamily\Large\bfseries}]
        \node[cblue] (f) at ( 139:2) {$f$};
%        \node[cgreen] (x) at ( 319:2.7) {$x$};       
        \node[cred] (c) at (0:0) {$\mathbf c$};
        \node[cgreen] (e) at (90:1) {$e$};
        \node[cblue] (a) at ( 330:1.6) {$a$};
 %       \node[cgreen] (z) at ( 292.5:1.84776) {$z$};
        \node[cblue] (b) at ( 225:1.2) {$b$};
        
        \node[cgreen] (x) at ( 305:2.0) {$x$};
        \node[cgreen] (z) at ( 270:1.70711) {$z$}; 


        \path[every node/.style={font=\sffamily\small}]
        (e) edge  []  node [] {} (c)
        (c) edge  []  node [] {} (a)
        (a) edge  []  node [] {} (x)
        (b) edge  []  node [] {} (x)
        (c) edge  [dashed]  node [right] {} (b)
        (x) edge  [line width=0.6mm,dotted]  node [left] {} (c)
        (a) edge  [dotted]  node [right] {3} (e)
        (b) edge  [dotted]  node [left] {3} (e)
        (f) edge  []  node [] {} (e)
        (a) edge  [dashed]  node [right] {} (z)
        (b) edge  [dashed]  node [right] {} (z)
        (c) edge  [dotted]  node [left] {3} (f)
        ;        
        \end{tikzpicture}
\caption{The subgraph~$H''$ of the preference graph considered in Lemma~\ref{key21}.}
\label{keyGraph21}
\end{center}
\end{figure}

\begin{lemma}
\label{key21}
Assume that some subgraph~$H''$ of the graph of 3DSM takes the form shown in Fig.~\ref{keyGraph21}, where ranks are indicated near the corresponding edges. 
Then $H''$ is an $(x,c)$-attractor.
\end{lemma}

\begin{lemma}
\label{key211}
Assume that some subgraph~$H'$ of the graph of 3DSM takes the form shown in Fig.~\ref{keyGraph2}.
If $H'$ is $z$-detachable, then $H'$ is an $(x,d)$-attractor.
\end{lemma}

\noindent\textbf{Proof:} Let $\mu$ be a stable matching in 3DSM. 
In the case when $R_\mu(z)<r'_z$, we can make use of Proposition~\ref{utv} and the fact that $H'$ is $z$-detachable. \ldots

\bigskip
\noindent\textbf{Proof of Lemma~\ref{key2}:} 
The validity of item~A of the lemma follows from lemmas~\ref{key21},~\ref{key211}, and~\ref{key13} (cf. the proof of Lemma~\ref{key1}).
It remains to prove item~B. Let us use Proposition~\ref{utv}. \ldots


\section{An example of unsolvable 3DSM of size~20}

\begin{theorem}
\label{exampleTh}
Let the graph~$G$ of 3DSM contain the subgraph~$H$ shown in Fig.~\ref{example}. Assume that for all considered below subgraphs of the graph~$G$, which are copies of graphs mentioned in lemmas~\ref{key1} and~\ref{key2}, the value $r'_y$ in the corresponding copies coincides with $\rho_H(y)+1$; here $y$ is a certain vertex (we specify its number later). Thus, the graph~$G$ contains five disjoint subgraphs~$H'_0$, $H'_1$, $H'_2$, $H'_4$, and $H'_7$, which are copies of the graph mentioned in Lemma~\ref{key1}; the role of the vertex $x$ is played there, correspondingly, by vertices~0, 1, 2, 4, and~7 of the graph~$H$. Subgraphs $H'_0$, $H'_1$, $H'_2$, $H'_4$, and $H'_7$ have no other common vertices with the graph~$H$. Moreover, the graph $G$ has two disjoint subgraphs $H'_{3,6}$ and $H'_{5,8}$; they are copies of subgraphs mentioned in Lemma~\ref{key2}, the role of the vertex $x$ is played there by vertices~3 and~5, while the role of the vertex $z$ is played by vertices~6 and~8, correspondingly. 
Subgraphs $H'_{3,6}$ and $H'_{5,8}$ have no more common points with the graph~$H$. 
Assume that the graph~$G$ has no vertices except those considered above, i.e.,
$$V(G)= V(H'_{3,6})\cup  V(H'_{5,8})\bigcup_{v\in\{0,1,2,4,7\}} V(H'_v).$$ We treat ranks of edges of the graph~$G$, which were not considered above, as arbitrary values. 
Then 3DSM defined by the graph~$G$ has no stable matching.
\end{theorem}

\noindent\textbf{Proof of Theorem~\ref{exampleTh} (scheme):}

\begin{lemma}
Let~$\mu$ be a stable matching in 3DSM mentioned in assumptions of Theorem~\ref{exampleTh}. Then 
$\{ \mu(3),\mu^{-1}(3)\} \in V(H)$, and the subgraph $H'_{3,6}$ is a $6$-superattractor.
\label{last1}
\end{lemma}
\begin{lemma}
Let~$\mu$ be a stable matching in 3DSM mentioned in assumptions of Theorem~\ref{exampleTh}. Then 
$\{ \mu(5),\mu^{-1}(5)\} \in V(H)$, and the subgraph $H'_{5,8}$ is an $8$- superattractor.
\label{last2}
\end{lemma}

Assume that in the considered 3DSM problem there exists a stable matching $\mu_G$.
Let us associate the stable matching $\mu_G$ with the matching $\mu_H$ of 3DSMI with the graph~$H$. Let us do it similarly to the proof of Theorem~\ref{unSolvabable}.

\section{Concluding remarks and open problems}
It remains to consider the question about the least size~$n$ of a counterexample for 3DSM-CYC. According to the obtained result, $5<n \leqslant 20$. However, the following assertion calls into question the existence of such a counterexample for $n=6,7$.

\begin{proposition}
For $n=6,7$ there exists no counterexample for 3DSM-CYC, whose graph includes two disjoint subgraphs, which represent counterexamples for 3DSMI of size~3.
\end{proposition}

The matter of fact is that for any counterexamples~$H$ for 3DSMI of size~3 (see, e.g., Fig.~\ref{example}) there exists a stable matching~$\mu$ for 3DSM of size~3 with the subgraph~$H$ in which the inequality~$R_\mu(x)\leqslant \overline \rho_H(x)$ is valid for all vertices~$x$ that correspond to two genders.
Moreover, there exists more than one way to choose these two genders.
Therefore, for a disjoint union of such counterexamples, there exists a matching~$\mu$ with 6 families satisfying the same inequality, where $x$ belongs to the same two genders.
Evidently, the complement of such matching with some triple is a stable matching.

\begin{thebibliography}{99}
\bibitem{Biro}
Bir\'o, P., McDermid, E.: Three-sided stable matchings with cyclic preferences. Algorithmica \textbf{58}, 5--18 (2010). 
%
\bibitem{gurvich}
Boros, E., Gurvich, V., Jaslar, S., Krasner, D.: Stable matchings in three-sided systems with cyclic preferences. Discrete Math. \textbf{289}(1--3), 1--10 (2004).
%
\bibitem{Eriksson}
Eriksson, K., S\"ostrand, J., Strimling P.: Three-dimensional stable matching with cyclic preferences. Math. Soc. Sci. \textbf{52}(1), 77--87 (2006). 
%
\bibitem{Lam}
Lam, C.K., Plaxton, C.G.: On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences.
In: Lecture Notes in Computer Science, \textbf{11801}, Algorithmic Game Theory, pp. 329--342 (2019)
%  
\bibitem{old}
Lerner, E.Yu., Lerner, R.E.: Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences. arXiv:2101.08223 [math.CO], Discrete Mathematics, Algorithms and Applications, will be published \url{https://arxiv.org/abs/2101.08223} (2021)
%
\bibitem{manlove}
D.F.~Manlove, Algorithmics of matching under preferences, Theor. Comput. Sci. World Scientific, 2013.
%
\bibitem{new}
K.~Pashkovich, L.~Poirrier, Three-dimensional stable matching with cyclic preferences, Optimization Letters (2020).
\end{thebibliography}
\end{document}