Transversal (of a family S)

Transversal (of a family [math]\displaystyle{ S }[/math]) --- трансверсаль (семейства [math]\displaystyle{ S }[/math]).

The set [math]\displaystyle{ T }[/math] is called a transversal of a family of sets [math]\displaystyle{ S = \{A_{i}\} }[/math], if

1. [math]\displaystyle{ T \cap A_{i} \neq \emptyset }[/math], for any [math]\displaystyle{ i }[/math];

2. for any [math]\displaystyle{ a_{j} \in T }[/math] there exists [math]\displaystyle{ A_{i_{j}} }[/math] such that [math]\displaystyle{ A_{i_{j}} \cap T = a_{j} }[/math].

The maximum number of pairwise disjoint sets from the class [math]\displaystyle{ S }[/math] is called the independence number of [math]\displaystyle{ S }[/math] and denoted as [math]\displaystyle{ \alpha(G) }[/math]. [math]\displaystyle{ \tau(G) }[/math] denotes the transversal number of [math]\displaystyle{ S }[/math], that is the size of the minimum transversal of [math]\displaystyle{ S }[/math].

See also

• System of distinct representatives.

For a hypergraph [math]\displaystyle{ {\mathcal H} = (V,{\mathcal E}) }[/math], a transversal is a transversal of [math]\displaystyle{ {\mathcal E} }[/math].