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 Graph Search.
Concept
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. 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.
About this result
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.
Ontological neighbourhood
Related courses (2)
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
Related lectures (18)
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.
Related publications (24)
Additive and geometric transversality of fractal sets in the integers
By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...
2024Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Mikhail Kapralov, Jakab Tardos
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...
ASSOC COMPUTING MACHINERY2021Additive and geometric transversality of fractal sets in the integers
By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...
2021Related people (3)
Related concepts (6)
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).
Bipartite hypergraph
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.
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.