Advertisement

In the past ** Jean-Paul Doignon** has collaborated on articles with

More information about

AbstractShort proofs are presented for two results due respectively to Tutte and Welsh.

AbstractAny 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, [7]).

AbstractThe binary choice polytope appeared in the investigation of the binary choice problem formulated by Guilbaud and Block and Marschak. It is nowadays known to be the same as the linear ordering polytope from operations research (as studied by Grötschel, Jünger and Reinelt).The central problem is to find facet-defining linear inequalities for the polytope. Fence inequalities constitute a prominent class of such inequalities (Cohen and Falmagne; Grötschel, Jünger and Reinelt). Two different generalizations exist for this class: the reinforced fence inequalities of Leung and Lee, and independently Suck, and the stability–critical fence inequalities of Koppen. Together with the fence inequalities, these inequalities form the fence family. Building on previous work on the biorder polytope by Christophe, Doignon and Fiorini, we provide a new class of inequalities which unifies all inequalities from the fence family. The proof is based on a projection of polytopes. The new class of facet-defining inequalities is related to a specific class of weighted graphs, whose definition relies on a curious extension of the stability number. We investigate this class of weighted graphs which generalize the stability–critical graphs.

AbstractTwo probabilistic models for subset choices are compared. The first one, due to Marley (1993), was dubbed the latent-scale model by Regenwetter, Marley, and Joe (1996). The second one is Falmagne and Regenwetter's (1996) size-independent model of approval voting. We show that for up to five choice alternatives, the choice probabilities generated by the latent-scale model can be explained also by the size-independent model. The proof uses the König–Hall theorem of graph theory and the characterization of the size-independent model by the approval-voting polytope of Doignon and Regenwetter (1997). The problem remains open for the case with more than five choice alternatives.

Advertisement