Matching in hypergraphs

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.^[1]^{: 466–470} ^[2]

Definition

Recall that a hypergraph $H$ is a pair $(V, E)$ , where $V$ is a set of vertices and $E$ is a set of subsets of $V$ called hyperedges. Each hyperedge may contain one or more vertices.

A matching in $H$ is a subset $M$ of $E$ , such that every two hyperedges $e 1$ and $e 2$ in $M$ have an empty intersection (have no vertex in common).

The matching number of a hypergraph $H$ is the largest size of a matching in $H$ . It is often denoted by $ν(H)$ .^[1]^: 466 ^[3]

As an example, let $V$ be the set ${1,2,3,4,5,6,7}.$ Consider a 3-uniform hypergraph on $V$ (a hypergraph in which each hyperedge contains exactly 3 vertices). Let $H$ be a 3-uniform hypergraph with 4 hyperedges:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Then $H$ admits several matchings of size 2, for example:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

However, in any subset of 3 hyperedges, at least two of them intersect, so there is no matching of size 3. Hence, the matching number of $H$ is 2.

Intersecting hypergraph

A hypergraph $H = (V, E)$ is called intersecting if every two hyperedges in $E$ have a vertex in common. A hypergraph $H$ is intersecting if and only if it has no matching with two or more hyperedges, if and only if $ν(H) = 1$ .^[4]

Matching in a graph as a special case

A graph without self-loops is just a 2-uniform hypergraph: each edge can be considered as a set of the two vertices that it connects. For example, this 2-uniform hypergraph represents a graph with 4 vertices ${1,2,3,4}$ and 3 edges:

{ {1,3}, {1,4}, {2,4} }

By the above definition, a matching in a graph is a set $M$ of edges, such that each two edges in $M$ have an empty intersection. This is equivalent to saying that no two edges in $M$ are adjacent to the same vertex; this is exactly the definition of a matching in a graph.

Fractional matching

A fractional matching in a hypergraph is a function that assigns a fraction in $[0,1]$ to each hyperedge, such that for every vertex $v$ in $V$ , the sum of fractions of hyperedges containing $v$ is at most 1. A matching is a special case of a fractional matching in which all fractions are either 0 or 1. The size of a fractional matching is the sum of fractions of all hyperedges.

The fractional matching number of a hypergraph $H$ is the largest size of a fractional matching in $H$ . It is often denoted by $ν *(H)$ .^[3]

Since a matching is a special case of a fractional matching, for every hypergraph $H$ :

Matching-number( $H$ ) ≤ fractional-matching-number( $H$ )

Symbolically, this principle is written:

\nu (H)\leq \nu ^{*}(H)

In general, the fractional matching number may be larger than the matching number. A theorem by Zoltán Füredi^[4] provides upper bounds on the fractional-matching-number( $H$ ) / matching-number( $H$ ) ratio:

If each hyperedge in $H$ contains at most $r$ vertices, then

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

In particular, in a simple graph:^[5]

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$

- The inequality is sharp: Let $H r$ be the $r$ -uniform finite projective plane. Then $ν (H r) = 1$ since every two hyperedges intersect, and $ν*(Hr) = r – 1 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/r⁠$ by the fractional matching that assigns a weight of $⁠ 1 / r ⁠$ to each hyperedge (it is a matching since each vertex is contained in $r$ hyperedges, and its size is $r - 1 + ⁠ 1 / r ⁠$ since there are $r 2 - r + 1$ hyperedges). Therefore the ratio is exactly $r - 1 + ⁠ 1 / r ⁠$ .
If $r$ is such that the $r$ -uniform finite projective plane does not exist (for example, $r = 7$ ), then a stronger inequality holds:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

If $H$ is $r$ -partite (the vertices are partitioned into $r$ parts and each hyperedge contains a vertex from each part), then:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

In particular, in a bipartite graph, $ν *(H) = ν (H)$ . This was proved by András Gyárfás.^[4]

- The inequality is sharp: Let $H r-$ be the truncated projective plane of order $r - 1$ . Then $ν (H r -) = 1$ since every two hyperedges intersect, and $ν *(H r -) = r - 1$ by the fractional matching that assigns a weight of $⁠ 1 / r ⁠$ to each hyperedge (there are $r 2 - r$ hyperedges).

Perfect matching

A matching $M$ is called perfect if every vertex $v$ in $V$ is contained in exactly one hyperedge of $M$ . This is the natural extension of the notion of perfect matching in a graph.

A fractional matching $M$ is called perfect if for every vertex $v$ in $V$ , the sum of fractions of hyperedges in $M$ containing $v$ is exactly 1.

Consider a hypergraph $H$ in which each hyperedge contains at most $n$ vertices. If $H$ admits a perfect fractional matching, then its fractional matching number is at least $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}|V| ⁄n$ . If each hyperedge in $H$ contains exactly $n$ vertices, then its fractional matching number is at exactly $| V | ⁄ n$ .^[6] ^: sec.2 This is a generalization of the fact that, in a graph, the size of a perfect matching is $| V | ⁄ 2$ .

Given a set $V$ of vertices, a collection $E$ of subsets of $V$ is called balanced if the hypergraph $(V, E)$ admits a perfect fractional matching.

For example, if $V = {1,2,3,a,b,c}$ and $E = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} },$ then $E$ is balanced, with the perfect fractional matching ${ 1/2, 1/2, 1/2, 1/2, 1 }.$

There are various sufficient conditions for the existence of a perfect matching in a hypergraph:

Hall-type theorems for hypergraphs - presents sufficient conditions analogous to Hall's marriage theorem, based on sets of neighbors.
Perfect matching in high-degree hypergraphs - presents sufficient conditions analogous to Dirac's theorem on Hamiltonian cycles, based on degree of vertices.
Keevash and Mycroft developed a geometric theory for hypergraph matching.^[7]

Balanced set-family

A set-family $E$ over a ground set $V$ is called balanced (with respect to $V$ ) if the hypergraph $H = (V, E)$ admits a perfect fractional matching.^[6] ^: sec.2

For example, consider the vertex set $V = {1,2,3,a,b,c}$ and the edge set $E = {1-a, 2-a, 1-b, 2-b, 3-c}.$ $E$ is balanced, since there is a perfect fractional matching with weights ${1/2, 1/2, 1/2, 1/2, 1}.$

Computing a maximum matching

The problem of finding a maximum-cardinality matching in a hypergraph, thus calculating $\nu (H)$ , is NP-hard even for 3-uniform hypergraphs (see 3-dimensional matching). This is in contrast to the case of simple (2-uniform) graphs in which computing a maximum-cardinality matching can be done in polynomial time.

Matching and covering

A vertex-cover in a hypergraph $H = (V, E)$ is a subset $T$ of $V$ , such that every hyperedge in $E$ contains at least one vertex of $T$ (it is also called a transversal or a hitting set, and is equivalent to a set cover). It is a generalization of the notion of a vertex cover in a graph.

The vertex-cover number of a hypergraph $H$ is the smallest size of a vertex cover in $H$ . It is often denoted by $τ (H)$ ,^[1]^: 466 for transversal.

A fractional vertex-cover is a function assigning a weight to each vertex in $V$ , such that for every hyperedge $e$ in $E$ , the sum of fractions of vertices in $e$ is at least 1. A vertex cover is a special case of a fractional vertex cover in which all weights are either 0 or 1. The size of a fractional vertex-cover is the sum of fractions of all vertices.

The fractional vertex-cover number of a hypergraph $H$ is the smallest size of a fractional vertex-cover in $H$ . It is often denoted by $τ *(H)$ .

Since a vertex-cover is a special case of a fractional vertex-cover, for every hypergraph $H$ :

fractional-vertex-cover-number ( $H$ ) ≤ vertex-cover-number ( $H$ ).

Linear programming duality implies that, for every hypergraph $H$ :

fractional-matching-number ( $H$ ) = fractional-vertex-cover-number( $H$ ).

Hence, for every hypergraph $H$ :^[4]

\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)

If the size of each hyperedge in $H$ is at most $r$ then the union of all hyperedges in a maximum matching is a vertex-cover (if there was an uncovered hyperedge, we could have added it to the matching). Therefore:

\tau (H)\leq r\cdot \nu (H).

This inequality is tight: equality holds, for example, when $V$ contains $r \cdot ν (H) + r - 1$ vertices and $E$ contains all subsets of $r$ vertices.

However, in general $τ *(H) < r \cdot ν (H)$ , since $ν *(H) < r \cdot ν (H)$ ; see Fractional matching above.

Ryser's conjecture says that, in every $r$ -partite $r$ -uniform hypergraph:

\tau (H)\leq (r-1)\nu (H).

Some special cases of the conjecture have been proved; see Ryser's conjecture.

Kőnig's property

A hypergraph has the Kőnig property if its maximum matching number equals its minimum vertex-cover number, namely if $ν (H) = τ (H)$ . The Kőnig-Egerváry theorem shows that every bipartite graph has the Kőnig property. To extend this theorem to hypergraphs, we need to extend the notion of bipartiteness to hypergraphs.^[1]^: 468

A natural generalization is as follows. A hypergraph is called 2-colorable if its vertices can be 2-colored so that every hyperedge (of size at least 2) contains at least one vertex of each color. An alternative term is Property B. A simple graph is bipartite iff it is 2-colorable. However, there are 2-colorable hypergraphs without Kőnig's property. For example, consider the hypergraph with $V = {1,2,3,4}$ with all triplets $E = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }.$ It is 2-colorable, for example, we can color ${1,2}$ blue and ${3,4}$ white. However, its matching number is 1 and its vertex-cover number is 2.

A stronger generalization is as follows. Given a hypergraph $H = (V, E)$ and a subset $V'$ of $V$ , the restriction of $H$ to $V'$ is the hypergraph whose vertices are $V$ , and for every hyperedge $e$ in $E$ that intersects $V'$ , it has a hyperedge $e'$ that is the intersection of $e$ and $V'$ . A hypergraph is called balanced if all its restrictions are essentially 2-colorable, meaning that we ignore singleton hyperedges in the restriction.^[8] A simple graph is bipartite iff it is balanced.

A simple graph is bipartite iff it has no odd-length cycles. Similarly, a hypergraph is balanced iff it has no odd-length circuits. A circuit of length $k$ in a hypergraph is an alternating sequence $(v 1, e 1, v 2, e 2, \dots, v k, e k, v k +1 = v 1)$ , where the $v i$ are distinct vertices and the $e i$ are distinct hyperedges, and each hyperedge contains the vertex to its left and the vertex to its right. The circuit is called unbalanced if each hyperedge contains no other vertices in the circuit. Claude Berge proved that a hypergraph is balanced if and only if it does not contain an unbalanced odd-length circuit. Every balanced hypergraph has Kőnig's property.^[9]^[1]^{: 468–470}

The following are equivalent:^[1]^{: 470–471}

Every partial hypergraph of $H$ (i.e., a hypergraph derived from $H$ by deleting some hyperedges) has the Kőnig property.
Every partial hypergraph of $H$ has the property that its maximum degree equals its minimum edge coloring number.
$H$ has the Helly property, and the intersection graph of $H$ (the simple graph in which the vertices are $E$ and two elements of $E$ are linked if and only if they intersect) is a perfect graph.

Matching and packing

The problem of set packing is equivalent to hypergraph matching.

A vertex-packing in a (simple) graph is a subset $P$ of its vertices, such that no two vertices in $P$ are adjacent.

The problem of finding a maximum vertex-packing in a graph is equivalent to the problem of finding a maximum matching in a hypergraph:^[1]^: 467

Given a hypergraph $H = (V, E)$ , define its intersection graph $Int(H)$ as the simple graph whose vertices are $E$ and whose edges are pairs $(e 1, e 2)$ such that $e 1$ , $e 2$ have a vertex in common. Then every matching in $H$ is a vertex-packing in $Int(H)$ and vice versa.
Given a graph $G = (V', E')$ , define its star hypergraph $St(G)$ as the hypergraph whose vertices are $E'$ and whose hyperedges are the stars of the vertices of $G$ (i.e., for each vertex $v'$ in $V'$ , there is a hyperedge in $St(G)$ that contains all edges in $E'$ that are adjacent to $v'$ ). Then every vertex-packing in $G$ is a matching in $St(G)$ and vice versa.
Alternatively, given a graph $G = (V', E')$ , define its clique hypergraph $Cl(G)$ as the hypergraph whose vertices are the cliques of $G$ , and for each vertex $v'$ in $V'$ , there is a hyperedge in $Cl(G)$ containing all cliques in $G$ that contain $v'$ . Then again, every vertex-packing in $G$ is a matching in $Cl(G)$ and vice versa. Note that $Cl(G)$ cannot be constructed from $G$ in polynomial time, so it cannot be used as a reduction for proving NP-hardness. But it has some theoretical uses.

References

^ ^a ^b ^c ^d ^e ^f ^g Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
^ Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland.
^ ^a ^b Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
^ ^a ^b ^c ^d Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.
^ Lovász, L. (1974). "Minimax theorems for hypergraphs". In Berge, Claude; Ray-Chaudhuri, Dijen (eds.). Hypergraph Seminar. Lecture Notes in Mathematics. Vol. 411. Berlin, Heidelberg: Springer. pp. 111–126. doi:10.1007/BFb0066186. ISBN 978-3-540-37803-7.
^ ^a ^b Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "Fair division with multiple pieces". Discrete Applied Mathematics. 283: 115–122. arXiv:1710.09477. doi:10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.
^ Keevash, Peter; Mycroft, Richard (2015-01-01). A geometric theory for hypergraph matching. Memoirs of the American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.
^ Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), "CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory", A Survey of Combinatorial Theory, North-Holland, pp. 15–23, ISBN 978-0-7204-2262-7, retrieved 2020-06-19
^ Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences. 175 (1): 32–40. Bibcode:1970NYASA.175...32B. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.

[lp-1] ^ ^a ^b ^c ^d ^e ^f ^g Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[2] Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland.

[:1-3] Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.

[:2-4] Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[5] Lovász, L. (1974). "Minimax theorems for hypergraphs". In Berge, Claude; Ray-Chaudhuri, Dijen (eds.). Hypergraph Seminar. Lecture Notes in Mathematics. Vol. 411. Berlin, Heidelberg: Springer. pp. 111–126. doi:10.1007/BFb0066186. ISBN 978-3-540-37803-7.

[:0-6] Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "Fair division with multiple pieces". Discrete Applied Mathematics. 283: 115–122. arXiv:1710.09477. doi:10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.

[7] Keevash, Peter; Mycroft, Richard (2015-01-01). A geometric theory for hypergraph matching. Memoirs of the American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.

[8] Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), "CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory", A Survey of Combinatorial Theory, North-Holland, pp. 15–23, ISBN 978-0-7204-2262-7, retrieved 2020-06-19

[9] Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences. 175 (1): 32–40. Bibcode:1970NYASA.175...32B. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]