2
$\begingroup$

I am studying R. Diestel's Book Graph Theory and I encountered a formulation which I don't quiet understand. Mr. Diestel speaks in this proof on page 180 (Google Books Link) in the second last line of a unique minimal partition.

I know what a partition is. And if he speaks of a unique partition I understand, that there is no other partition like this one. But what does the word minimal mean in this context? Is it, that there is no more refined partition?

Thanks for any enlightenment!

1 Answers 1

3

It’s explicitly defined in the parenthetical remark that follows:

In other words, if we consider two elements of $C_i$ as equivalent whenever they lie in the same partition set of $C_{ij}$ for every $j\ne i$, then $\mathcal{C}_i$ is the set of equivalence classes.

Among all partitions that refine every partition $\mathcal{C}_{ij}$ with $j\ne i$, this partition $\mathcal{C}_i$ is minimal in the sense that it has the fewest members. Alternatively, it’s the coarsest partition that refines every partition $\mathcal{C}_{ij}$ with $j\ne i$: every other partition that refines every partition $\mathcal{C}_{ij}$ with $j\ne i$ also refines $\mathcal{C}_i$.

  • 0
    Thank you for your alternative explanation! Helped me a lot!2011-10-27