Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores
Mathématiques informatique et sciences humaines, Tome 118 (1992), pp. 53-68

Dans cet article, nous définissons un paramètre σ(T) à partir des scores d’un tournoi T. Ce paramètre évalue un éloignement entre le tournoi T et les tournois transitifs de même ordre. Appelant i(T) le nombre minimum d’arcs à inverser pour rendre T transitif, nous montrons que l’on a σ(T)≤i(T). Nous déterminons ensuite des bornes sur la valeur maximum de i(T) pour les tournois T à σ donné. Nous en déduisons enfin, en fonction du nombre de sommets de T et de σ(T), un encadrement de l’indice de Slater d’un tournoi quelconque.

In this paper, we define a parameter σ(T) from the scores of a tournament T. This parameter measures a remoteness between the tournament T and the transitive tournaments of same order. Calling i(T) the minimum number of arcs to reverse to make T transitive, we show the relation σ(T)≤i(T). Then we give bounds on the maximum value of i(T) for tournaments T with given value of σ. Last, according to σ(T) and the number of vertices of T, we deduce bounds of i(T) for any tournament T.

@article{MSH_1992__118__53_0,
     author = {Charon-Fournier, Ir\`ene and Germa, Anne and Hudry, Olivier},
     title = {Encadrement de l'indice de slater d'un tournoi \`a l'aide de ses scores},
     journal = {Math\'ematiques informatique et sciences humaines},
     pages = {53--68},
     year = {1992},
     publisher = {Ecole des hautes-\'etudes en sciences sociales},
     volume = {118},
     zbl = {0846.05040},
     language = {fr},
     url = {https://www.numdam.org/item/MSH_1992__118__53_0/}
}
TY  - JOUR
AU  - Charon-Fournier, Irène
AU  - Germa, Anne
AU  - Hudry, Olivier
TI  - Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores
JO  - Mathématiques informatique et sciences humaines
PY  - 1992
SP  - 53
EP  - 68
VL  - 118
PB  - Ecole des hautes-études en sciences sociales
UR  - https://www.numdam.org/item/MSH_1992__118__53_0/
LA  - fr
ID  - MSH_1992__118__53_0
ER  - 
%0 Journal Article
%A Charon-Fournier, Irène
%A Germa, Anne
%A Hudry, Olivier
%T Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores
%J Mathématiques informatique et sciences humaines
%D 1992
%P 53-68
%V 118
%I Ecole des hautes-études en sciences sociales
%U https://www.numdam.org/item/MSH_1992__118__53_0/
%G fr
%F MSH_1992__118__53_0
Charon-Fournier, Irène; Germa, Anne; Hudry, Olivier. Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores. Mathématiques informatique et sciences humaines, Tome 118 (1992), pp. 53-68. https://www.numdam.org/item/MSH_1992__118__53_0/

[1] Barthélémy J.-P., Monjardet B., "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences 1 (1981), 235-267. | Zbl | MR

[2] Bermond J.-C., "Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Mathématiques et Sciences Humaines 37 (1972), 5-25. | Zbl | MR | Numdam

[3] Chartrand G., Geller D., Hedetniemi S., "Graphs with forbidden subgraphs", Journal of Combinatorial Theory B, vol.10, n°1 (1971), 12-41. | Zbl | MR

[4] Guénoche A., "Order at minimum distance of a valued tournament" , présenté à la Table Ronde Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3) (1988), Marseille-Luminy.

[5] Landau H.G. "On dominance relations and the structure of animal societies III. The condition for a score structure", Bulletin of Mathematical Biophysics 13 (1953),1-19. | MR

[6] Moon J.W., Topics on tournaments, Holt, New York,1968. | Zbl | MR

[7] Reid K.B., "On set of arcs containing no cycles in tournaments", Canadian Mathematical Bulletin 12 (1969), 261-264. | Zbl | MR

[8] Skolem Th., "On certain distributions of integers in pairs with given differences", Math. Scand. 5 (1957), 57-68. | Zbl | MR

[9] Slater P. "Inconsistencies in a schedule of paired comparisons", Biometrika 53 (1961), 143-149.