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. 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). 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. 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. 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. 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.