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. In this case, the transversal is also called a system of distinct representatives (SDR). The other, less commonly used, does not require a one-to-one relation between the elements of the transversal and the sets of C. In this situation, the members of the system of representatives are not necessarily distinct. In computer science, computing transversals is useful in several application domains, with the input family of sets often being described as a hypergraph. A fundamental question in the study of SDR is whether or not an SDR exists. Hall's marriage theorem gives necessary and sufficient conditions for a finite collection of sets, some possibly overlapping, to have a transversal. The condition is that, for every integer k, every collection of k sets must contain in common at least k different elements. The following refinement by H. J. Ryser gives lower bounds on the number of such SDRs. Theorem. Let S1, S2, ..., Sm be a collection of sets such that contains at least k elements for k = 1,2,...,m and for all k-combinations {} of the integers 1,2,...,m and suppose that each of these sets contains at least t elements. If t ≤ m then the collection has at least t ! SDRs, and if t > m then the collection has at least t ! / (t - m)! SDRs. One can construct a bipartite graph in which the vertices on one side are the sets, the vertices on the other side are the elements, and the edges connect a set to the elements it contains.

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

Related courses (1)

Related lectures (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).

Transversal (combinatorics)

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.

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

Explores directed networks with asymmetric relationships and hypergraphs that generalize graphs by allowing edges to connect any subset of nodes.

Introduces hypergraphs, generalizing graphs by allowing subsets of nodes to form edges and exploring their applications in various fields.

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.