NDLI: Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Please wait, while we are loading the content...

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Content Provider	Springer Nature Link
Author	Charon, Irène Hudry, Olivier
Copyright Year	2010
Abstract	Given a tournament T = (X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n − 1)/2 if T is any tournament on an odd number n of vertices, to (n $^{2}$ − 3n + 2)/2 if T is any tournament on an even number n of vertices, to n(n − 1)/2 if T is strongly connected with an odd number n of vertices, to (n $^{2}$ − 3n − 2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n $^{2}$ − 5n + 6)/2 if T has an odd number n of vertices and only one Slater order, to (n $^{2}$ − 5n + 8)/2 if T has an even number n of vertices and only one Slater order.
Starting Page	99
Ending Page	119
Page Count	21
File Format	PDF
ISSN	01678094
Journal	Order
Volume Number	28
Issue Number	1
e-ISSN	15729273
Language	English
Publisher	Springer Netherlands
Publisher Date	2010-06-30
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Majority tournament Tournament solutions Slater orders Slater winners Copeland orders Copeland winners Symmetric difference distance Arc-disjoint circuits in circular tournaments Convex and Discrete Geometry Theory of Computation Geometry
Content Type	Text
Resource Type	Article
Subject	Algebra and Number Theory Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the difficulty of computing the winners of a tournament

Domination Number of Certain Infinite Tournaments

Partial Orders on Weak Orders Convex Subsets

On the Poset of Computation Rules for Nonassociative Calculus

Orthocomplemented Posets with a Symmetric Difference

Groups of Automorphisms of Tournaments

Free Triangle Orders

Basic Interval Orders

Almost Connected Orders

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Similar Documents

On the difficulty of computing the winners of a tournament

Domination Number of Certain Infinite Tournaments

Partial Orders on Weak Orders Convex Subsets

On the Poset of Computation Rules for Nonassociative Calculus

Orthocomplemented Posets with a Symmetric Difference

Groups of Automorphisms of Tournaments

Free Triangle Orders

Basic Interval Orders

Almost Connected Orders

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments