**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Matching in hypergraphs

Summary

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (15)

Rainbow matching

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors. A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges. Rainbow matchings are of particular interest given their connection to transversals of Latin squares.

Transversal (combinatorics)

In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal: One variation is that there is a bijection f from the transversal to C such that x is an element of f(x) for each x in the transversal.

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

Related lectures (33)

Related courses (3)

Tactical Configurations: Rödl Nibble

Explores tactical configurations, covering the minimal size of subsets needed to cover element sets and the concept of K-sets and base points.

Set Coverings and Uniformity Theorems

Explores set coverings and uniformity theorems in hypergraphs, revealing insights into their structures.

AI in Chemistry: Hypergraph and Single-Step Ritual Synthesis

Explores AI applications in chemistry, hypergraphs, single-step ritual synthesis, and retro-synthetic models evaluation.

A first course in statistical network analysis and applications.

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte