**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# Hall-type theorems for hypergraphs

Summary

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.
Hall's marriage theorem provides a condition guaranteeing that a bipartite graph (X + Y, E) admits a perfect matching, or - more generally - a matching that saturates all vertices of Y. The condition involves the number of neighbors of subsets of Y. Generalizing Hall's theorem to hypergraphs requires a generalization of the concepts of bipartiteness, perfect matching, and neighbors.

- 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, V can be partitioned into two sets X and Y, such that each hyperedge contains exactly one vertex of Y. A bipartite graph is a special case in which each edge contains exactly one vertex of Y and also exactly one vertex of X; in a bipartite hypergraph, each hyperedge contains exactly one vertex of Y but may contain zero or more vertices of X. For example, the hypergraph (V, E) with V = {1,2,3,4,5,6} and E = { {1,2,3}, {1,2,4}, {1,3,4}, {5,2}, {5,3,4,6} } is bipartite with Y = {1,5} and X = {2,3,4,6}.
- Perfect matching: A matching in a hypergraph H = (V, E) is a subset F of E, such that every two hyperedges of F are disjoint. If H is bipartite with parts X and Y, then the size of each matching is obviously at most . A matching is called Y-perfect (or Y-saturating) if its size is exactly . In other words: every vertex of Y appears in exactly one hyperedge of M. This definition reduces to the standard definition of a Y-perfect matching in a bipartite graph.
- Neighbors: Given a bipartite hypergraph H = (X + Y, E) and a subset Y_0 of Y, the neighbors of Y_0 are the subsets of X that share hyperedges with vertices of Y_0.

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 (8)

Related courses (1)

Related lectures (18)

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

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.

In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph. Property B The weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H can be 2-colored so that no hyperedge is monochromatic.

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.

Probability Theory: Markov's Theorem

Explores Markov's theorem, Chernoff bound, and probability theory fundamentals, including good coloring, 2-colorable graphs, and rare events.

A first course in statistical network analysis and applications.