Hall-type Theorems For Hypergraphs

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

Preliminaries

Hall's marriage theorem provides a condition guaranteeing that a bipartite graph admits a perfect matching, or - more generally - a matching that saturates all vertices of . The condition involves the number of neighbors of subsets of . Generalizing Hall's theorem to hypergraphs requires a generalization of the concepts of bipartiteness, perfect matching, and neighbors.

1. Bipartiteness: The notion of a bipartiteness can be extended to hypergraphs in many ways (see bipartite hypergraph). Here we define a hypergraph as bipartite if it is ''exactly 2- colorable'', i.e., its vertices can be 2-colored such that each hyperedge contains exactly one yellow vertex. In other words, can be partitioned into two sets and , such that each hyperedge contains exactly one vertex of . A bipartite graph is a special case in which each edge contains exactly one vertex of and also exactly one vertex of ; in a bipartite hypergraph, each hyperedge contains exactly one vertex of but may contain zero or more vertices of . For example, the hypergraph with and is bipartite with and

2. Perfect matching: A matching in a hypergraph is a subset of , such that every two hyperedges of are disjoint. If is bipartite with parts and , then the size of each matching is obviously at most . A matching is called ''-perfect'' (or ''-saturating'') if its size is exactly . In other words: every vertex of appears in exactly one hyperedge of . This definition reduces to the standard definition of a -perfect matching in a bipartite graph.

3. Neighbors'': ''Given a bipartite hypergraph and a subset of , the neighbors of are the subsets of that share hyperedges with vertices of . Formally:
:$N_H(Y_0) := \.$
For example, in the hypergraph from point 1, we have: and and Note that, in a bipartite graph, each neighbor is a singleton - the neighbors are just the vertices of that are adjacent to one or more vertices of . In a bipartite hypergraph, each neighbor is a set - the neighbors are the subsets of that are "adjacent" to one or more vertices of .

Since contains only subsets of , one can define a hypergraph in which the vertex set is and the edge set is . We call it the neighborhood-hypergraph of and denote it:
:$H_H(Y_0) := (X, N_H(Y_0)).$
Note that, if is a simple bipartite graph, the neighborhood-hypergraph of every contains just the neighbors of in , each of which with a self-loop.

Insufficiency of Hall's condition

Hall's condition requires that, for each subset of , the set of neighbors of is sufficiently large. With hypergraphs this condition is insufficient. For example, consider the tripartite hypergraph with edges:

Let Every vertex in has a neighbor, and itself has two neighbors: But there is no -perfect matching since both edges overlap.

One could try to fix it by requiring that contain at least ''disjoint'' edges, rather than just edges. In other words: should contain a ''matching'' of size at least . The largest size of a matching in a hypergraph is called its matching number and denoted by (thus admits a -perfect matching if and only if ). However, this fix is insufficient, as shown by the following tripartite hypergraph:

Let Again every vertex in has a neighbor, and itself has four neighbors: Moreover, since admits a matching of size 2, e.g. However, H does not admit a -perfect matching, since every hyperedge that contains 1 overlaps every hyperedge that contains 2.

Thus, to guarantee a perfect matching, a stronger condition is needed. Various such conditions have been suggested.

Aharoni's conditions: largest matching

Let be a bipartite hypergraph (as defined in 1. above), in which the size of every hyperedge is exactly , for some integer . Suppose that, for every subset of , the following inequality holds:
:$\nu(N_H(Y_0)) \geq (r-1)\cdot (, Y_0, - 1) + 1$
In words: the neighborhood-hypergraph of admits a matching larger than . Then admits a -perfect matching (as defined in 2. above).

This was first conjectured by Aharoni. It was proved with Ofra Kessler for bipartite hypergraphs in which and for . It was later proved for all -uniform hypergraphs.

In simple graphs

For a bipartite simple graph , and Aharoni's condition becomes:
:$\nu(H_H(Y_0)) \geq , Y_0, .$
Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of . Since singletons do not intersect, the entire set of singletons is a matching. Hence, the number of neighbors of . Thus, Aharoni's condition becomes, for every subset of :
:$, N_H(Y_0), \geq , Y_0, .$
This is exactly Hall's marriage condition.

Tightness

The following example shows that the factor cannot be improved. Choose some integer . Let be the following -uniform bipartite hypergraph:

*
* is the union of (where is the set of hyperedges containing vertex ), and:
** For each in contains disjoint hyperedges of size :

$\, \ldots , \.$

** contains hyperedges of size :

$\ , \ldots, \$

Note that edge in meets all edges in .

This does not admit a -perfect matching, since every hyperedge that contains intersects all hyperedges in for some .

However, every subset of satisfies the following inequality
:$\nu(H_H(Y_0)) \geq (r-1)\cdot (, Y_0, - 1)$
since contains at least hyperedges, and they are all disjoint.

Fractional matchings

The largest size of a ''fractional matching'' in is denoted by . Clearly . Suppose that, for every subset of , the following weaker inequality holds:
:$\nu^*(H_H(Y_0)) \geq (r-1)\cdot (, Y_0, - 1) +1$
It was conjectured that in this case, too, admits a -perfect matching. This stronger conjecture was proved for bipartite hypergraphs in which .

Later it was proved that, if the above condition holds, then admits a -perfect ''fractional'' matching, i.e., . This is weaker than having a -perfect matching, which is equivalent to .

Haxell's condition: smallest transversal

A ''transversal'' (also called ''vertex-cover'' or ''hitting-set'') in a hypergraph is a subset of such that every hyperedge in contains at least one vertex of . The smallest size of a transversal in is denoted by .

Let be a bipartite hypergraph in which the size of every hyperedge is at most , for some integer . Suppose that, for every subset of , the following inequality holds:
:$\tau(H_H(Y_0)) \geq (2r-3)\cdot (, Y_0, - 1) + 1$
In words: the neighborhood-hypergraph of has no transversal of size or less.

Then, admits a -perfect matching (as defined in 2. above).

In simple graphs

For a bipartite simple graph so , and Haxell's condition becomes:
:$\tau(H_H(Y_0)) \geq , Y_0, .$
Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of . In a hypergraph of singletons, a transversal must contain all vertices. Hence, the number of neighbors of . Thus, Haxell's condition becomes, for every subset of :
:$, N_H(Y_0), \geq , Y_0, .$
This is exactly Hall's marriage condition. Thus, Haxell's theorem implies Hall's marriage theorem for bipartite simple graphs.

Tightness

The following example shows that the factor cannot be improved. Let be an -uniform bipartite hypergraph with:

* $Y = \$
* $X = \$

o

* $E = E_0 \cup E_1,$

where:

**$E_0 = \$

o contains hyperedges

** $E_1 = \$

o contains hyperedges

This does not admit a -perfect matching, since every hyperedge that contains 0 intersects every hyperedge that contains 1.

However, every subset of satisfies the following inequality:
:$\tau(H_H(Y_0)) \geq (2r-3)\cdot (, Y_0, - 1)$
It is only slightly weaker (by 1) than required by Haxell's theorem. To verify this, it is sufficient to check the subset , since it is the only subset for which the right-hand side is larger than 0. The neighborhood-hypergraph of is where:
:$E_ = \$
:$E_ = \$

One can visualize the vertices of as arranged on an grid. The hyperedges of are the rows. The hyperedges of are the selections of a single element in each row and each column. To cover the hyperedges of we need vertices - one vertex in each row. Since all columns are symmetric in the construction, we can assume that we take all the vertices in column 1 (i.e., for each in . Now, since contains all columns, we need at least additional vertices - one vertex for each column All in all, each transversal requires at least vertices.

Algorithms

Haxell's proof is not constructive. However, Chidambaram Annamalai proved that a perfect matching can be found efficiently under a slightly stronger condition.

For every fixed choice of and , there exists an algorithm that finds a -perfect matching in every -uniform bipartite hypergraph satisfying, for every subset of :
:$\tau(H_H(Y_0)) \geq (2r-3 +\epsilon)\cdot (, Y_0, - 1) + 1$
In fact, in any -uniform hypergraph, the algorithm finds either a -perfect matching, or a subset violating the above inequality.

The algorithm runs in time polynomial in the size of , but exponential in and .

It is an open question whether there exists an algorithm with run-time polynomial in either or (or both).

Similar algorithms have been applied for solving problems of fair item allocation, in particular the santa-claus problem.

Aharoni–Haxell conditions: smallest pinning sets

We say that a set of edges ''pins'' another set of edges if every edge in intersects some edge in . The ''width'' of a hypergraph , denoted , is the smallest size of a subset of that pins . The ''matching width'' of a hypergraph , denoted , is the maximum, over all matchings in , of the minimum size of a subset of that pins . Since contains all matchings in , the width of H is obviously at least as large as the matching-width of .

Aharoni and Haxell proved the following condition:

Let be a bipartite hypergraph. Suppose that, for every subset of , the following inequality holds:

$mw(N_H(Y_0)) \geq , Y_0,$

n other words: contains a matching such that at least disjoint edges from are required for pinning Then, admits a -perfect matching.

They later extended this condition in several ways, which were later extended by Meshulam as follows:

Let be a bipartite hypergraph. Suppose that, for every subset of , at least one of the following conditions hold:

$mw(N_H(Y_0)) \geq , Y_0,$ or

$w(N_H(Y_0)) \geq 2 , Y_0, - 1$

Then, admits a -perfect matching.

In simple graphs

In a bipartite simple graph, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of . Since singletons do not intersect, the entire set of neighbors is a matching, and its only pinning-set is the set itself, i.e., the matching-width of is , and its width is the same:
:$w(N_H(Y_0)) = mw(N_H(Y_0)) = , N_H(Y_0), .$
Thus, both the above conditions are equivalent to Hall's marriage condition.

Examples

We consider several bipartite graphs with and The Aharoni–Haxell condition trivially holds for the empty set. It holds for subsets of size 1 if and only if each vertex in is contained in at least one edge, which is easy to check. It remains to check the subset itself.

# Here Its matching-width is at least 2, since it contains a matching of size 2, e.g. which cannot be pinned by any single edge from . Indeed, H admits a -perfect matching, e.g.
# Here Its matching-width is 1: it contains a matching of size 2, e.g. but this matching can be pinned by a single edge, e.g. The other matching of size 2 is but it too can be pinned by the single edge While is larger than in example 1, its matching-width is smaller - in particular, it is less than . Hence, the Aharoni–Haxell sufficient condition is not satisfied. Indeed, does not admit a -perfect matching.
# Here, as in the previous example, so the Aharoni–Haxell sufficient condition is violated. The width of is 2, since it is pinned e.g. by the set so Meshulam's weaker condition is violated too. However, this does admit a -perfect matching, e.g. which shows that these conditions are not necessary.

Set-family formulation

Consider a bipartite hypergraph where The Hall-type theorems do not care about the set itself - they only care about the neighbors of elements of . Therefore can be represented as a collection of families of sets where for each in , the set-family of neighbors of . For every subset of , the set-family is the union of the set-families for in . A ''perfect matching'' in is a set-family of size , where for each in , the set-family is represented by a set in , and the representative sets are pairwise-disjoint.

In this terminology, the Aharoni–Haxell theorem can be stated as follows.

Let be a collection of families of sets. For every sub-collection of , consider the set-family - the union of all the in . Suppose that, for every sub-collection of , this contains a matching such that at least disjoint subsets from are required for pinning . Then admits a system of disjoint representatives.

Necessary and sufficient condition

Let be a bipartite hypergraph. The following are equivalent:

* admits a -perfect matching.
* There is an assignment of a matching in for every subset of , such that pinning requires at least disjoint edges from

In set-family formulation: let be a collection of families of sets. The following are equivalent:

* admits a system of disjoint representatives;
* There is an assignment of a matching in for every sub-collection of , such that, for pinning , at least edges from are required.

Examples

Consider example #3 above: Since it admits a -perfect matching, it must satisfy the necessary condition. Indeed, consider the following assignment to subsets of :

*
*
*

In the sufficient condition pinning required at least two edges from it did not hold.

But in the necessary condition, pinning required at least two edges from it does hold.

Hence, the necessary+sufficient condition is satisfied.

Proof

The proof is topological and uses Sperner's lemma. Interestingly, it implies a new topological proof for the original Hall theorem.

First, assume that no two vertices in have exactly the same neighbor (it is without loss of generality, since for each element of , one can add a dummy vertex to all neighbors of ).

Let They consider an -vertex simplex, and prove that it admits a triangulation with some special properties that they call ''economically-hierarchic triangulation''. Then they label each vertex of with a hyperedge from in the following way:

* (a) For each in , The main vertex of the simplex is labeled with some hyperedge from the matching .
* (b) Each vertex of on a face spanned by a subset of , is labeled by some hyperedge from the matching .
* (c) For each two adjacent vertices of , their labels are either identical or disjoint.

Their sufficient condition implies that such a labeling exists. Then, they color each vertex of with a color such that the hyperedge assigned to is a neighbor of .

Conditions (a) and (b) guarantee that this coloring satisfies Sperner's boundary condition. Therefore, a fully-labeled simplex exists. In this simplex there are hyperedges, each of which is a neighbor of a dif and only iferent element of , and so they must be disjoint. This is the desired -perfect matching.

Extensions

The Aharoni–Haxell theorem has a deficiency version. It is used to prove Ryser's conjecture for .

Meshulam's conditions - the topological Hall theorems

In abstract simplicial complexes

Let be a set of vertices. Let be an abstract simplicial complex on . Let (for in ) be subsets of . A '' transversal'' is a set in (an element of ) whose intersection with each contains exactly one vertex. For every subset of , let
:$V_ := \bigcup_ V_y.$
Suppose that, for every subset of , the homological connectivity plus 2 of the sub-complex induced by $V_$ is at least , that is:
:\eta_H(C _ \geq , Y_0, .
Then there exists a transversal. That is: there is a set in that intersects each by exactly one element. This theorem has a deficiency version. If, for every subset of :
:\eta_H(C _ \geq , Y_0, -d,
then there exists a partial -transversal, that intersects some sets by 1 element, and the rest by at most 1 element. More generally, if is a function on positive integers satisfying , and for every subset of :
:\eta_H(C _ \geq g(, Y_0, ),
then there is a set in that intersects at least of the by at one element, and the others by at most one element.

Meshulam's game

Using the above theorem requires some lower bounds on homological connectivity. One such lower bound is given by ''Meshulam's game''. This is a game played by two players on a graph. One player - CON - wants to prove that the graph has a high homological connectivity. The other player - NON - wants to prove otherwise. CON offers edges to NON one by one; NON can either disconnect an edge, or explode it; an explosion deletes the edge endpoints and all their neighbors. CON's score is the number of explosions when all vertices are gone, or infinity if some isolated vertices remain. The value of the game on a given graph (the score of CON when both players play optimally) is denoted by . This number can be used to get a lower bound on the homological connectivity of the ''independence complex'' of , denoted :
:$\eta_H(\mathcal(G)) \geq \Psi(G).$
Therefore, the above theorem implies the following. Let be a set of vertices. Let be a graph on . Suppose that, for every subset of :
:\Psi(G _ \geq , Y_0, .
Then there is an independent set in , that intersects each by exactly one element.

In simple bipartite graphs

Let be a bipartite graph with parts and . Let be the set of ''edges'' of . Let the line graph of . Then, the independence complex is equal to the matching complex of H, denoted . It is a simplicial complex on the edges of , whose elements are all the matchings on . For each vertex in , let be set of edges adjacent to (note that is a subset of ). Then, for every subset of , the induced subgraph G _/math> contains a clique for every neighbor of (all edges adjacent to , that meet at the same vertex of , form a clique in the line-graph). So there are disjoint cliques. Therefore, when Meshulam's game is played, NON needs explosions to destroy all of , so . Thus, Meshulam's condition
:\Psi(G _ \geq , Y_0,
is equivalent to Hall's marriage condition. Here, the sets are pairwise-disjoint, so a -transversal contains a unique element from each , which is equivalent to a -saturating matching.

In matching complexes

Let be a bipartite hypergraph, and suppose is its matching complex . Let (for in ) be sets of edges of . For every subset of , is the set of matchings in the sub-hypergraph:
:$\bigcup_ H_y.$
If, for every subset of :
:$\eta_H(\mathcal(H_)) \geq , Y_0,$
Then there exists a matching that intersects each set exactly once (it is also called a ''rainbow matching'', since each can be treated as a color).

This is true, in particular, if we define as the set of edges of containing the vertex of . In this case, is equivalent to - the multi-hypergraph of neighbors of ("multi" - since each neighbor is allowed to appear several times for several different ).

The matching complex of a hypergraph is exactly the independence complex of its line graph, denoted . This is a graph in which the vertices are the edges of , and two such vertices are connected iff their corresponding edges intersect in . Therefore, the above theorem implies:
:$\eta_H(\mathcal(H)) \geq \Psi(L(H))$
Combining the previous inequalities leads to the following condition.
:Let be a bipartite hypergraph. Suppose that, for every subset of , the following condition holds:
::$\Psi(L(N_H(Y_0))) \geq , Y_0, ,$
:where is considered a multi-hypergraph (i.e., it may contain the same hyperedge several times, if it is a neighbor of several different elements of ). Then, admits a -perfect matching.

Examples

We consider several bipartite hypergraphs with and The Meshulam condition trivially holds for the empty set. It holds for subsets of size 1 iff the neighbor-graph of each vertex in is non-empty (so it requires at least one explosion to destroy), which is easy to check. It remains to check the subset itself.
s
# Here The graph has three vertices: Only the last two are connected; the vertex Aa is isolated. Hence, . Indeed, admits a -perfect matching, e.g.
#''H'' = . Here has four vertices: and four edges: For any edge that CON offers, NON can explode it and destroy all vertices. Hence, . Indeed, does not admit a -perfect matching.
# Here is the same as in the previous example, so Meshulam's sufficient condition is violated. However, this does admit a -perfect matching, e.g. which shows that this condition is not necessary.
No necessary-and-sufficient condition using is known.

More conditions from rainbow matchings

A rainbow matching is a matching in a simple graph, in which each edge has a different "color". By treating the colors as vertices in the set , one can see that a rainbow matching is in fact a matching in a bipartite ''hypergraph''. Thus, several sufficient conditions for the existence of a large rainbow matching can be translated to conditions for the existence of a large matching in a hypergraph.

The following results pertain to ''tripartite hypergraph''s in which each of the 3 parts contains exactly vertices, the degree of each vertex is exactly , and the set of neighbors of every vertex is a matching (henceforth "-tripartite-hypergraph"):

* Every -tripartite-hypergraph has a matching of size .
* Every -tripartite-hypergraph has a matching of size .
* Every -tripartite-hypergraph has a matching of size .
*H. J. Ryser

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases