MBS 94-24
Well-graded Families of Relations
Jean-Paul Doignon, Jean-Claude Falmagne
Any semiorder on a finite set can be reached from any other semiorder
on the same set by elementary steps consisting either in the addition or
in the removal of a single ordered pair, in such a way that only semiorders
are generated at every step, and also that the number of steps equals the
distance between the two semiorders. Similar results are also established
for other families of relations (partial orders, biorders, interval orders).
These combinatorial results are used in another paper to develop a stochastic
theory describing the emergence and the evolution of preference relations
(Falmagne and Doignon, in preparation).