DIMACS Theory Lunch


Neighborhood principle in tic-tac-toe-like games and complexity


Jozsef Beck
Rutgers University


Room 402, Dept. of Computer Sciences, Computer Science Building,
35 Olden Street (corner of Olden and William Street), Princeton University


11:50 AM - 1:15 PM
Friday, March 3, 1995


A generalized tic-tac-toe game is played on an arbitrary hypergraph, the underlying set is the ``board", and the hyperedges are the ``winning sets". The players alternately mark points (elements of the board), and that player wins who first occupies a winning set. There are surprising principles like the ``random game principle" and the ``neighborhood principle". (These two principles together usually beat the ``pairing strategy".) At the end I want to show an application on the ``parallel matching complexity" of Ramsey theorem.

Host: Sanjeev Arora, Princeton University

If you have any questions, contact Sandy Barbu . As usual, we will serve the lunch at 11:50 and the talk will begin at 12:10.

Document last modified on March 1, 1995