= System of distinct representatives
{title2=$x_i\in A_i,\quad x_i\neq x_j\ (i\neq j)$}
= Systems of distinct representatives
{synonym}
A <system of distinct representatives> for a finite indexed family of finite <sets> $(A_i)_{i\in I}$ chooses one element $x_i\in A_i$ per index, with all choices distinct. Form a <bipartite graph> with left <vertex set> $I$, right <vertex set> $\bigcup_{i\in I}A_i$, and <edges> $ix$ whenever $x\in A_i$. <Matching saturation> of $I$ is precisely a <system of distinct representatives>. Hence <Hall's marriage theorem> says that such choices exist exactly when $|\bigcup_{i\in J}A_i|\geq|J|$ for every <subset> $J\subseteq I$. Repeated equal <sets> still have separate indices and separate demands.
Back to article page
