10
$\begingroup$

Every game of Red-Blue Hackenbush represents a surreal number. Is the converse true? Assuming that it is false, what can be said about the class of surreal numbers that are representable by such games?

For instance, it is obvious that this class is a group under addition, but I can't visualize why it should even be closed under multiplication.

Edit (by request): A game of Red-Blue Hackenbush is a rooted graph G whose edges are either red or blue. It's helpful to think of the surreal value of the game G as the number of moves by which Blue is ahead. The addition operation is simply the disjoint union with roots identified. The additive inverse of a game is found by changing the color of every edge. [Of course, this is only an inverse after passing to equivalence classes, which are surreal numbers.]

A finite path graph beginning with a blue edge at the root represents a positive dyadic rational number, which you find as follows:

  • Each blue edge that appears before the first red edge is worth 1.
  • Beginning with the first red edge, every edge is worth half as much as the edge before.
  • The value of the game is the sum of the values of the blue edges minus the sum of the values of the red edges.

This algorithm is presented by Tom Davis in pp. 11-13 of this paper, where you can find a full explanation of what's going on.

By using graphs with infinitely many edges, we can represent many surreal numbers. If I understand correctly, the game {1|9} (for example) is not literally a Red-Blue Hackenbush game, but it is equivalent to 2={-1,0,1|3}, which is represented by a 3-edge blue path joined at the root to a single red edge.

Is there a surreal number that is not equivalent to any Red-Blue Hackenbush game?

$\endgroup$
  • 1
    $\begingroup$ It would be very kind of you to help us out by showing how the dyadic rationals arise, and also how some various ordinals arise? $\endgroup$ – Joel David Hamkins Aug 26 '17 at 11:53
  • $\begingroup$ have you read Winning Ways? ONAG? $\endgroup$ – john mangual Aug 27 '17 at 23:09
  • 2
    $\begingroup$ Are you sure that "Every game of Red-Blue Hackenbush represents a surreal number. " is true in this level of generality (arbitrary graphs)? What about single node with infinitely many red edges? On the other hand if you have a finiteness condition, which is it? $\endgroup$ – Will Sawin Aug 28 '17 at 6:08
  • $\begingroup$ @WillSawin - A single node with $\omega$ red edges represents the surreal number $-\omega$, etc. $\endgroup$ – swensonj Aug 28 '17 at 19:14
  • 2
    $\begingroup$ @swensonj But how can that be the case when you can move from that graph to itself? Or what about a node with infinitely many red edges and infinitely many blue edges? $\endgroup$ – Will Sawin Aug 28 '17 at 19:42
4
$\begingroup$

All surreal numbers are representable by a Red–Blue Hackenbush game. This is discussed in On Numbers and Games, although it is left to the reader to fill in the details of the proof for the transfinite case. In Chapter 3 it is explained that every (surreal) number has a sign expansion. Then in Chapter 8 it is explained that the value of a Red–Blue Hackenbush chain is the number whose sign expansion is given by reading off the colors of the edges of the chain from the ground up, interpreting black edges as + and white edges as –. Of course one has to allow chains (or "beanstalks") whose edges are arranged in accordance with the structure of an arbitrary ordinal.

$\endgroup$
  • 1
    $\begingroup$ But this isn't really a rooted graph, right? $\endgroup$ – Will Sawin Aug 28 '17 at 6:04
  • $\begingroup$ @WillSawin : I'm not sure what you mean by a "rooted graph" but what I described is a valid Red-Blue Hackenbush game. It is a graph in the sense that it consists of vertices and edges, and it is rooted in that there is no ambiguity which vertex is the smallest in the total order that we impose. $\endgroup$ – Timothy Chow Aug 28 '17 at 18:14
  • 1
    $\begingroup$ The order is not determined by the edge structure as soon as your ordinal is greater than $\omega$. So you would be playing, instead of a game on graphs, a game on some generalized objects. $\endgroup$ – Will Sawin Aug 28 '17 at 18:37
  • $\begingroup$ I used the expression "rooted graph" in my question to mean a graph in which one vertex has been declared to be the "root." Of course this represents the ground: when a player deletes a cut edge, the game reduces to the connected component of the root. $\endgroup$ – swensonj Aug 28 '17 at 19:24
  • 1
    $\begingroup$ @TimothyChow It's a bit strange to ask and answer a mathematical question about a mathematical object that is not completely well-defined, but of course you're completely right that Conway has pinned down the definition well enough to answer this question. $\endgroup$ – Will Sawin Aug 29 '17 at 16:17
1
$\begingroup$

If you only allow connected graphs, and in particular do not allow ordinal numbers, the answer is no, unless you assign surreal numbers to Hackenbush games by a means other than induction.

First it's important to realize that, contrary to what's stated in the question, not every rooted graph with edges colored red and blue corresponds to a surreal number. To assign a surreal number to a game, you can only handle a game if every move takes you to a game already handled, which means you can't handle a game if there is some infinite sequence of legal moves (for either player).

This means a graph that corresponds to a surreal number cannot have infinitely many leaves, infinitely many loops, or infinitely many topological ends. Otherwise we could move infinitely often by chopping off leaves, by cutting loops, or by chopping off ends. (For the third case, you can start by cutting off loops until the graph is a tree, then observing that if a vertex has infinitely many ends among its descendents, at some point oen of its descendents must split in such a way that at least one side doesn't contain all but finitely many of the ends, and you can cut off that side, then repeat).

If a graph does correspond to a surreal number, the graph is a finite graph glued to finitely many infinite paths. This is because after chopping off the finitely many loops, the graph is a tree with finitely many ends, hence finitely many branch points, and there can only be finitely many edges between any two branch points.

Thus, the ordinal for when the game finishes is $< n \omega$, where $n$ is the number of infinite paths - i.e. we can bound the time until we are forced to chop one of the infinite paths, then bound the time until we are forced to chop the next path, etc. a finite number of times.

So you cannot express this way any surreal number that occurs in the generation $\omega^2$ or after.

$\endgroup$
  • 1
    $\begingroup$ In The Book of Numbers, Conway and Guy explicitly say, "Hackenbush chains can be infinite! Indeed, we allow the height of our Hackenbush chains to be any of Cantor's ordinal numbers." As an example they show (among other things) a picture of $\sqrt\omega$, whose order type is $\omega^2$. $\endgroup$ – Timothy Chow Aug 29 '17 at 0:55
  • $\begingroup$ Will, doesn't your example in the comments still refute the claim that "every red-blue hackenbush game is a surreal number"? Perhaps it would be good to include a discussion of this in your answer. $\endgroup$ – Joel David Hamkins Aug 29 '17 at 15:22
  • 1
    $\begingroup$ @JoelDavidHamkins I thought I was discussing this. I guess I'll make it more explicit. $\endgroup$ – Will Sawin Aug 29 '17 at 16:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.