3-dimensional matching

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-uniform hypergraphs. Finding a largest 3-dimensional matching is a well-known NP-hard problem in computational complexity theory. In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-uniform hypergraphs. Finding a largest 3-dimensional matching is a well-known NP-hard problem in computational complexity theory. Let X, Y, and Z be finite, disjoint sets, and let T be a subset of X × Y × Z. That is, T consists of triples (x, y, z) such that x ∈ X, y ∈ Y, and z ∈ Z. Now M ⊆ T is a 3-dimensional matching if the following holds: for any two distinct triples (x1, y1, z1) ∈ M and (x2, y2, z2) ∈ M, we have x1 ≠ x2, y1 ≠ y2, and z1 ≠ z2. The figure on the right illustrates 3-dimensional matchings. The set X is marked with red dots, Y is marked with blue dots, and Z is marked with green dots. Figure (a) shows the set T (gray areas). Figure (b) shows a 3-dimensional matching M with |M| = 2, and Figure (c) shows a 3-dimensional matching M with |M| = 3. The matching M illustrated in Figure (c) is a maximum 3-dimensional matching, i.e., it maximises |M|. The matching illustrated in Figures (b)–(c) are maximal 3-dimensional matchings, i.e., they cannot be extended by adding more elements from T. Here is example interactive visualistaion in javascript A 2-dimensional matching can be defined in a completely analogous manner. Let X and Y be finite, disjoint sets, and let T be a subset of X × Y. Now M ⊆ T is a 2-dimensional matching if the following holds: for any two distinct pairs (x1, y1) ∈ M and (x2, y2) ∈ M, we have x1 ≠ x2 and y1 ≠ y2. In the case of 2-dimensional matching, the set T can be interpreted as the set of edges in a bipartite graph G = (X, Y, T); each edge in T connects a vertex in X to a vertex in Y. A 2-dimensional matching is then a matching in the graph G, that is, a set of pairwise non-adjacent edges. Hence 3-dimensional matchings can be interpreted as a generalization of matchings to hypergraphs: the sets X, Y, and Z contain the vertices, each element of T is a hyperedge, and the set M consists of pairwise non-adjacent edges (edges that do not have a common vertex). In case of 2-dimensional matching, we have Y = Z. A 3-dimensional matching is a special case of a set packing: we can interpret each element (x, y, z) of T as a subset {x, y, z} of X ∪ Y ∪ Z; then a 3-dimensional matching M consists of pairwise disjoint subsets.