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.

Official source

https://en.wikipedia.org/wiki/Hall-type_theorems_for_hypergraphs

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)

CS-450: Algorithms II

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 repertory of basic algorithmic solutions to problems in many ...

Related lectures (17)

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.

Hypergraphs and Link Prediction: Statistical Analysis of Network Data

Covers hypergraphs, complete hypergraphs, link prediction, and scoring methods in network data analysis.

Related people (1)

Ola Nils Anders Svensson

Related concepts (3)

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.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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.

Official source

https://en.wikipedia.org/wiki/Hall-type_theorems_for_hypergraphs

About this result

Related courses (1)

CS-450: Algorithms II

Related lectures (17)

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.

Hypergraphs and Link Prediction: Statistical Analysis of Network Data

Covers hypergraphs, complete hypergraphs, link prediction, and scoring methods in network data analysis.

Related publications (13)

Lower bounds for Ramsey numbers of bounded degree hypergraphs

We prove that, for all k≥3, and any integers Δ,n with n≥Δ, there exists a k-uniform hypergraph on n vertices with maximum degree at most Δ whose 4-color Ramsey number is at least twk(ckΔ)⋅n, for some constant ck>0, where twk denotes the tower function. For k≥4, this is tight up to the constant ck and for k=3 it is known to be tight up to a factor of log⁡Δ on top of the tower. Our bound extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from

Elsevier2026

Monotone Circuit Complexity of Matching

We show that the perfect matching function on

n

-vertex graphs requires monotone circuits of size

\smash{2^{n^{Ω(1)}}}

. This improves on the

n^{Ω(\log n)}

lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.

ACM2026

Anonymous Linear Bandits for Multi-User Systems

We provide the first anonymity-preserving algorithm for a centralized decision maker in linear bandit-based multiuser systems. Our algorithm employs successive elimination techniques for linear bandits to build an assignment multi-graph (from users to arms) along with a greedy matching algorithm that efficiently allocates the arms to users. We provide lower and upper bounds for this problem, showing that our algorithm is regret optimal up to a √ 𝐶𝐾 factor. CCS Concepts • Theory of computation → Sequential d