Abstract

The Majority Rule and Combinatorial Geometry

James Abello
Mon Apr. 26 at 1:10pm in the Graduate Student Lounge

In 1785, the Marquis du Condorcet realized that unrestricted choice under majority rule can produce intransitive results (this is one of several paradoxes of voting). We show how the Weak Bruhat Order of the Symmetric Group is useful to characterize those subsets of permutations for which the majority rule produces transitive results. The combinatorial tools are balanced tableaux and a new class of graphs that we call persistent graphs. By relating maximal chains of the Weak Bruhat Order to non-degenerate point configurations we sketch a proof of why persistent graphs turn out to be a polynomial time recognizable class of visibility graphs of simple polygons (The general visibility graph recognition problem is only known to be in PSPACE).

In summary, from the symmetric group we go to graphs, from graphs to point configurations and return to ponder about the relation between oriented matroid realizability and transitivity of the majority rule.

The talk will be self-contained and it will point out tantalizing areas for further research.