IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Two-level poset games

  • March 4, 2013
  • 2 p.m.
  • LeConte 312

Abstract

We discuss the complexity of determining the winner of a game played on a finite two-level partially ordered set. This is a natural question, as Daniel Grier has shown recently that determining the winner of a finite three-level poset game is PSPACE-complete. We give a simple formula allowing one to compute the status of a type of two-level poset game that we call, “parity-uniform.” This class of posets includes significantly more easily solvable two-level games than was known previously. We also establish general equivalences between various two-level games. This implies that for any n, only finitely many two-level posets with n minimal elements need be considered. We have a similar result for posets with n maximal elements.

This is joint work with Rohit Gurjar (IIT Kanpur), Arpita Korwar (IIT Kanpur), and Thomas Thierauf (U. Aalen)

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC