Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: The Majority Rule and Combinatorial Geometry (via the Symmetric Group)
Speaker: James Abello, DIMACS Research Faculty
Date: Thursday, April 12, 2012 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Marquis du Condorcet recognized 200 years ago that majority rule can produce intransitive group preferences if the domain of possible (transitive) individual preference orders is unrestricted. We present results on the cardinality and structure of those maximal sets of permutations for which majority rule produces transitive results (Consistent Sets). Consistent sets that contain a maximal chain in the Weak Bruhat Order (i.e. a balanced tableau of staircase shape) inherit from it an upper semi modular sub lattice structure. They are intrinsically related to a special class of Hamiltonian graphs called persistent graphs. These graphs in turn have a clean geometric interpretation. We highlight the main tools used to prove these connections and state computationally open research questions.