Transversal (combinatorics)

Last updated October 24, 2023

In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section^[1]^[2]^[3]) 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).^[4]^: 29
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.^[5]^: 692^[6]^: 322

In computer science, computing transversals is useful in several application domains, with the input family of sets often being described as a hypergraph.

Existence and number

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.^[4]^: 29

The following refinement by H. J. Ryser gives lower bounds on the number of such SDRs.^[7]^: 48

Theorem. Let S₁, S₂, ..., S_m be a collection of sets such that $S_{i_{1}}\cup S_{i_{2}}\cup \dots \cup S_{i_{k}}$ contains at least k elements for k = 1,2,...,m and for all k-combinations { $i_{1},i_{2},\ldots ,i_{k}$ } 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.

Relation to matching and covering

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. Then, a transversal (defined as a system of distinct representatives) is equivalent to a perfect matching in this graph.

One can construct a hypergraph in which the vertices are the elements, and the hyperedges are the sets. Then, a transversal (defined as a system of not-necessarily-distinct representatives) is a vertex cover in a hypergraph.

Examples

In group theory, given a subgroup H of a group G, a right (respectively left) transversal is a set containing exactly one element from each right (respectively left) coset of H. In this case, the "sets" (cosets) are mutually disjoint, i.e. the cosets form a partition of the group.

As a particular case of the previous example, given a direct product of groups $G=H\times K$ , then H is a transversal for the cosets of K.

In general, since any equivalence relation on an arbitrary set gives rise to a partition, picking any representative from each equivalence class results in a transversal.

Another instance of a partition-based transversal occurs when one considers the equivalence relation known as the (set-theoretic) kernel of a function, defined for a function $f$ with domain X as the partition of the domain $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}$ . which partitions the domain of f into equivalence classes such that all elements in a class map via f to the same value. If f is injective, there is only one transversal of $\operatorname {ker} f$ . For a not-necessarily-injective f, fixing a transversal T of $\operatorname {ker} f$ induces a one-to-one correspondence between T and the image of f, henceforth denoted by $\operatorname {Im} f$ . Consequently, a function $g:(\operatorname {Im} f)\to T$ is well defined by the property that for all z in $\operatorname {Im} f,g(z)=x$ where x is the unique element in T such that $f(x)=z$ ; furthermore, g can be extended (not necessarily in a unique manner) so that it is defined on the whole codomain of f by picking arbitrary values for g(z) when z is outside the image of f. It is a simple calculation to verify that g thus defined has the property that $f\circ g\circ f=f$ , which is the proof (when the domain and codomain of f are the same set) that the full transformation semigroup is a regular semigroup. $g$ acts as a (not necessarily unique) quasi-inverse for f; within semigroup theory this is simply called an inverse. Note however that for an arbitrary g with the aforementioned property the "dual" equation $g\circ f\circ g=g$ may not hold. However if we denote by $h=g\circ f\circ g$ , then f is a quasi-inverse of h, i.e. $h\circ f\circ h=h$ .

Common transversals

A common transversal of the collections A and B (where $|A|=|B|=n$ ) is a set that is a transversal of both A and B. The collections A and B have a common transversal if and only if, for all $I,J\subset \{1,...,n\}$ ,

|(\bigcup _{i\in I}A_{i})\cap (\bigcup _{j\in J}B_{j})|\geq |I|+|J|-n

^[8]

Generalizations

A partial transversal is a set containing at most one element from each member of the collection, or (in the stricter form of the concept) a set with an injection from the set to C. The transversals of a finite collection C of finite sets form the basis sets of a matroid, the transversal matroid of C. The independent sets of the transversal matroid are the partial transversals of C.^[9]

An independent transversal (also called a rainbow-independent set or independent system of representatives) is a transversal which is also an independent set of a given graph. To explain the difference in figurative terms, consider a faculty with m departments, where the faculty dean wants to construct a committee of m members, one member per department. Such a committee is a transversal. But now, suppose that some faculty members dislike each other and do not agree to sit in the committee together. In this case, the committee must be an independent transversal, where the underlying graph describes the "dislike" relations.^[10]

Another generalization of the concept of a transversal would be a set that just has a non-empty intersection with each member of C. An example of the latter would be a Bernstein set , which is defined as a set that has a non-empty intersection with each set of C, but contains no set of C, where C is the collection of all perfect sets of a topological Polish space. As another example, let C consist of all the lines of a projective plane, then a blocking set in this plane is a set of points which intersects each line but contains no line.

Category theory

In the language of category theory, a transversal of a collection of mutually disjoint sets is a section of the quotient map induced by the collection.

Computational complexity

The computational complexity of computing all transversals of an input family of sets has been studied, in particular in the framework of enumeration algorithms.

Related Research Articles

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number a is equal to itself (reflexive). If a = b, then b = a (symmetric). If a = b and b = c, then a = c (transitive).

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

In mathematics, a group is a set with an operation that satisfies the following constraints: the operation is associative, has an identity element, and every element of the set has an inverse element.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group $G$ is isomorphic to a subgroup of a symmetric group. More specifically, $G$ is isomorphic to a subgroup of the symmetric group $whose elements are the permutations of the underlying set of G . Explicitly,$

Homological algebra is the branch of mathematics that studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology and abstract algebra at the end of the 19th century, chiefly by Henri Poincaré and David Hilbert.

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In mathematics, specifically group theory, the index of a subgroup H in a group G is the number of left cosets of H in G, or equivalently, the number of right cosets of H in G. The index is denoted $or or . Because G is the disjoint union of the left cosets and because each left coset has the same size as H, the index is related to the orders of the two groups by the formula$

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coproduct of a family of objects is essentially the "least specific" object to which each object in the family admits a morphism. It is the category-theoretic dual notion to the categorical product, which means the definition is the same as the product but with all arrows reversed. Despite this seemingly innocuous change in the name and notation, coproducts can be and typically are dramatically different from products.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of $A$ is $B$ , then the dual of $B$ is $A$ . Such involutions sometimes have fixed points, so that the dual of $A$ is $A$ itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about the representation in a more condensed form. Georg Frobenius initially developed representation theory of finite groups entirely based on the characters, and without any explicit matrix realization of representations themselves. This is possible because a complex representation of a finite group is determined by its character. The situation with representations over a field of positive characteristic, so-called "modular representations", is more delicate, but Richard Brauer developed a powerful theory of characters in this case as well. Many deep theorems on the structure of finite groups use characters of modular representations.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if $and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation,$

In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.

The Grothendieck construction is a construction used in the mathematical field of category theory. It is a fundamental construction in the theory of descent, in the theory of stacks, and in fibred category theory. In categorical logic, the construction is used to model the relationship between a type theory and a logic over that type theory, and allows for the translation of concepts from indexed category theory into fibred category theory, such as Lawvere's concept of hyperdoctrine.

An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a capacity constraint - a maximum number of allowed elements from this category. The independent sets of a partition matroid are exactly the sets in which, for each category, the number of elements from this category is at most the category capacity.

Matroid partitioning is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms. Its goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of computing the arboricity of an undirected graph, the minimum number of forests needed to cover all of its edges. Matroid partitioning may be solved in polynomial time, given an independence oracle for the matroid. It may be generalized to show that a matroid sum is itself a matroid, to provide an algorithm for computing ranks and independent sets in matroid sums, and to compute the largest common independent set in the intersection of two given matroids.

References

↑ John Mackintosh Howie (1995). Fundamentals of Semigroup Theory. Clarendon Press. p. 63. ISBN 978-0-19-851194-6.
↑ Clive Reis (2011). Abstract Algebra: An Introduction to Groups, Rings and Fields. World Scientific. p. 57. ISBN 978-981-4335-64-5.
↑ Bruno Courcelle; Joost Engelfriet (2012). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press. p. 95. ISBN 978-1-139-64400-6.
1 2 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 978-0-13-602040-0
↑ Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, Mathematical Association of America
↑ E. C. Milner (1974), TRANSVERSAL THEORY, Proceedings of the international congress of mathematicians, p. 161
↑ Oxley, James G. (2006), Matroid Theory, Oxford graduate texts in mathematics, vol. 3, Oxford University Press, p. 48, ISBN 978-0-19-920250-8 .
↑ Haxell, P. (2011-11-01). "On Forming Committees". The American Mathematical Monthly. 118 (9): 777–788. doi:10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.