Instructor: Laszlo Babai
Scribe: Daniel Stefankovic
Proof of Minkowski's Theorem.
Combinatorial games. Evaluation of the game tree. Existence
of a winning strategy. Proof that the first player has a winning
strategy in the ``Divisor'' game.
Solution to the harder Erdos puzzle: If is a set of
numbers from 1 to then one of them divides another.
The solution to the Erdos puzzle was based on the following observation.
From this it follows by the Pigeon Hole Principle that
no antichain can have more than elements, proving Erdos's
claim. This is an instance of a remarkable general result at work:
(Note that
is straightforward.)
The comparability graph of a poset has for its
set of vertices; comparable elements are adjacent.
The next exercise shows that the vs. behavior of most graphs is diametrically opposite to comparability graphs.
Note that blocking sets are the complements of the
independent sets.