2. GALVIN'S ORIGINAL GAME, THE RESTRICTED GAME, AND THE RELATIONS R AND ER Definition 2.1. By a tree we mean a partially ordered set (T, ) such that for every x € T {y € T: y T x} is well-ordered by T furthermore, we will assume that T has a unique -minimal element, which we call the root of T. The elements of T will be called nodes, and y S x will mean that the node y is an immediate successor of node x a node x having no successors is called terminal. A branch of T is a maximal linearly ordered subset of T, and T is called branch-finite if T has no infinite branches. A tree consisting of a single node will be called trivial. For x € T, T will denote {y € T: y x}, along with restricted to this set. We x T T will often abuse notation by identifying T with x. We let T denote the class of all branch-finite trees. Definition 2.2. Let T1 and T2 be non-trivial branch-finite trees. The Galvin game [T1:T?] is defined as follows: start with a white pawn at the root of T1 and a black pawn at the root of T2- Two players, white and black, move alternately, with white moving first. A move consists of push- ing either pawn from the node on which it sits to any immediate successor node. The game ends when one of the pawns reaches a terminal node ("queens"), and the player whose pawn does this is declared the winner. (Note that the game must end in finitely many moves since T- and T2 are both branch-finite.) Remark 2.3. Since we are dealing here with branch-finite trees, we could have defined our trees as being certain types of directed graphs, rather than partially ordered sets this is just a matter of taste. Moreover, in Chapter 8 we will briefly consider trees of height oo,and the natural way to regard such trees is as partially ordered sets. Note also that we may assume without loss of generality that T- and T2 have no non-trivial auto- morphisms, in which case they may be identified with sets in the obvious way: label each node of the tree with the set of labels of its immediate successors. The Galvin game [T-:T2] can then be reformulated as follows: we start with the ordered pair (T1,T2)/ and, given a position (X,Y) in the game, a move consists of replacing X by some x € X to give (x,Y) or Y by some y 6 Y to give (X,y) the game ends when one of the coordinates becomes 0, and white wins if it is the first coordinate, black if it is the second. The natural question to ask is whether white can always win the game [T:T]. Intuitively, getting to move first should give white the advantage since the game is essentially a race, but the fact that the players can di- vert each other makes the question non-trivial white cannot simply march up the shortest branch, since black may be able to divert white onto a very

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 1985 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.