<p>How about the following counter-example?</p>
<p><span class="math-container">$m=2$</span>, <span class="math-container">$n=4$</span>.</p>
<p><span class="math-container">$A=\{a_1,a_2\}$</span>, <span class="math-container">$B=\{b_1,b_2\}$</span>, <span class="math-container">$C=\{c_1,c_2\}$</span>.</p>
<p><span class="math-container">$T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$</span>.</p>
<p>With the partition
<span class="math-container">$A\cup B\cup C = \{a_1,b_1\}\cup\{a_2,b_2\}\cup\{c_1\}\cup\{c_2\}$</span>.</p>

CC BY-SA 4.0
2021-05-22T22:22:28.043Z
2021-05-22T22:22:28.043Z
Tassle
<p>I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes&quot; instances, i.e., admit a 3D matching.</p>
<p>We are given 3 sets <span class="math-container">$A,B,C$</span> containing <span class="math-container">$m$</span> elements each, and <span class="math-container">$n$</span> tuples <span class="math-container">$\{T_i\}_{i\in [n]}$</span> where <span class="math-container">$T_i \in A\times B\times C$</span>. We further know:</p>
<p>(i) Each element of <span class="math-container">$A\cup B \cup C$</span> occurs exactly in two tuples. Simple counting shows <span class="math-container">$n = 2m$</span>.</p>
<p>(ii) The elements of <span class="math-container">$A\cup B \cup C$</span> can be <strong>partitioned</strong> into <span class="math-container">$m$</span> singleton elements, and <span class="math-container">$m$</span> pairs <span class="math-container">$(x,y)$</span> where <span class="math-container">$\{x,y\} \subset T_i$</span> for some <span class="math-container">$i\in [n]$</span>.</p>
<p>I want to know if such an instance admits a 3D matching. Is there a simple counter-example?</p>

<graph-theory><matching><bipartite-graphs><examples>
Do such instances always admit a 3D matching?
ashtavakra
# Do such instances always admit a 3D matching?

(Asked by: username_0 on 2021-05-22)

I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.

We are given 3 sets $A,B,C$ containing $m$ elements each, and $n$ tuples $\{T\_i\}\_{i\in [n]}$ where $T\_i \in A\times B\times C$. We further know:

(i) Each element of $A\cup B \cup C$ occurs exactly in two tuples. Simple counting shows $n = 2m$.

(ii) The elements of $A\cup B \cup C$ can be **partitioned** into $m$ singleton elements, and $m$ pairs $(x,y)$ where $\{x,y\} \subset T\_i$ for some $i\in [n]$.

I want to know if such an instance admits a 3D matching. Is there a simple counter-example?

**Tags:** graph-theory, matching, bipartite-graphs, examples


---

## 1 answers

### Answer by username_1 on 2021-05-22. Score: 2 | Accepted answer

How about the following counter-example?

$m=2$, $n=4$.

$A=\{a\_1,a\_2\}$, $B=\{b\_1,b\_2\}$, $C=\{c\_1,c\_2\}$.

$T=\{(a\_1,b\_1,c\_1), (a\_1,b\_2,c\_2), (a\_2,b\_1,c\_2), (a\_2,b\_2,c\_1)\}$.

With the partition
$A\cup B\cup C = \{a\_1,b\_1\}\cup\{a\_2,b\_2\}\cup\{c\_1\}\cup\{c\_2\}$.


---

