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
Bipartite hypergraph
Summary
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. Every bipartite graph G = (X+Y, E) is 2-colorable: each edge contains exactly one vertex of X and one vertex of Y, so e.g. X can be colored blue and Y can be colored yellow and no edge is monochromatic.
The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called Property B.
A stronger definition of bipartiteness is: a hypergraph is called bipartite if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge contains exactly one element of X. Every bipartite graph is also a bipartite hypergraph.
Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges:{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }This H is 2-colorable, for example by the partition X = {1,2} and Y = {3,4}. However, it is not bipartite, since every set X with one element has an empty intersection with one hyperedge, and every set X with two or more elements has an intersection of size 2 or more with at least two hyperedges.
Hall's marriage theorem has been generalized from bipartite graphs to bipartite hypergraphs; see Hall-type theorems for hypergraphs.
An stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices. An n-uniform hypergraph is called n-partite if its vertex set V can be partitioned into n subsets such that each hyperedge contains exactly one element from each subset.
Official source
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.
Related courses (1)
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
Related publications (20)
Molecular hypergraph neural networks
Philippe Schwaller, Junwu Chen
Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...
Aip Publishing2024Hypergraph-Based Fast Distributed AC Power Flow Optimization
Colin Neil Jones, Yuning Jiang, Yingzhao Lian, Xinliang Dai
This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...
New York2023Motif Cut Sparsifiers
Mikhail Kapralov, Mikhail Makarov, Jakab Tardos
A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...
IEEE COMPUTER SOC2022Related people (6)
Related concepts (4)
Vertex cover in hypergraphs
In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph. An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges. Another equivalent term, used more in a combinatorial context, is transversal.
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.
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).