Math, Games, and Ronald Graham

In memory of Ron Graham, 1935-2020

You’ve probably already guessed the agenda behind my rambling about chess, but here it is explicitly: I claim that math (pure math, anyway) is as much a game as a science. The objects of mathematical thought, like the pieces in chess, are defined not by what they “are” but by the rules of play that govern them. The fact that in math the pieces exist only in our imaginations and the moves are mental events doesn’t make the rules any less binding. And even though the rules are human creations, once we’ve agreed to them, the answer to a question like “Is chess a win for the first player?” or “Is the Riemann Hypothesis true?” aren’t matters of individual opinion or group consensus; the answers to our questions are out of our hands, irrespective of whether we like those answers or even know what they are.1

PEOPLE AT A PARTY

I’ll illustrate my point with a gem of discrete mathematics that can be traced back to a polymathic prodigy named Frank Ramsey who made deeply original contributions to math, philosophy, and economics before dying in 1930 at the age of 26. (For more about Ramsey see the Anthony Gottlieb article and the Cheryl Misak book listed in the References.) I learned most of what I know about the body of mathematical work known today as Ramsey Theory from a great book I read back in the 1980s by Ronald Graham (who died earlier this month; more about him later) and his coauthors Bruce Rothschild and Joel Spencer. Two good article-length introductions to the topic (both originally published in Scientific American) are Martin Gardner’s 1977 article and Graham and Spencer’s 1990 article, listed in the References.

The mathematical gem is a puzzle often phrased in terms of a party attended by six people. Must it be true that you can find three of the six who are mutual acquaintances or three of the six who are mutual nonacquaintances?2 That formulation of the puzzle can lead to confusion, hinging on questions like “If A is acquainted with B, must B be acquainted with A?” (answer: for purposes of the puzzle, yes); “Isn’t it possible for there to be degrees of acquaintanceship, with no clear dividing line between acquaintances and nonacquaintances?” (answer: for purposes of this puzzle, it doesn’t matter where you draw the line, as long as you draw it somewhere); “Isn’t being acquainted time-dependent?” (answer: sure, but the claim is that at any given moment you can find three mutual acquaintances or three mutual nonacquaintances).

If you find such real-world issues distracting, you might prefer a pictorial model. If we have six points (call them vertices3) arranged in a regular hexagon, and we connect each pair of vertices by either a red line segment or a blue line segment (call these segments edges), must it be true that you can find three vertices that are joined up by red edges or three vertices that are joined up by blue edges?

Since it gets tiresome to keep saying “three vertices that are joined up by red edges” let’s call such a trio of vertices a “red triangle”, and likewise let’s call a trio of vertices that are joined by blue edges a “blue triangle”. We have to keep in mind that points where edges cross are not vertices, so the picture below does not actually contain what we mean by a red triangle. Likewise for blue triangles. In making these stipulations we’re not trying to legislate reality; we’re just saying how terms are defined in Ramsey theory.

Here’s a picture that I generated by putting in colors at random. There are 4 red triangles and 2 blue triangles. How quickly can you find them all (if that’s your kind of thing)?

Part of what makes the six-people puzzle tricky is that it’s just on the line between doable and undoable; if instead of six vertices you have a smaller number (or equivalently if there are fewer than six people at the party), finding three mutual acquaintances, or failing that three mutual nonacquaintances, might under some circumstances be an impossible task. For instance, if there’s a party consisting of two men who are acquaintances and two women who are acquaintances but neither of the men is acquainted with either of the women, then there won’t be three mutual acquaintances nor will there be three mutual nonacquaintances. You might enjoy trying to come up with a situation where there five people at a party but there are no three mutual acquaintances and no three mutual nonacquaintances. For an answer expressed pictorially, see Endnote #4.

You might enjoy pondering the six-person party puzzle on your own for a bit, but if you’d like a hint to get you started, try this: Suppose that you are one of the people at the party. You look around at the other five people. If the majority of them are people you’re acquainted with, there must be at least three such people; mentally single them out in some way (imagine them wearing silly hats if you like). Alternatively, if the majority of the five are people you’re unacquainted with, there must be at least three such people; mentally single out three people you’re not acquainted with. Either way, consider the situation that prevails among the three people you’ve singled out and how they relate to one another and you in terms of who is acquainted with whom. If you’re still stumped, check Endnote #5.

Although I used parties and colored drawings to anchor the puzzle in physical reality in a hopefully helpful way, the question isn’t a question about the real world. If you attend a party and you find two people who you deem to be neither acquainted nor unacquainted but rather “half-acquainted”, that doesn’t break the logic of the solution to the puzzle; it just means that the assumptions of the puzzle don’t apply to your party. Likewise, if you want to challenge the red/blue dichotomy underlying the puzzle by arguing that there are intermediate colors that some people call red and others call blue (an issue that actually arises in the real world for blue and green, which many people have trouble distinguishing) — then you’re doing psychology or optics but you’re not doing Ramsey theory, in much the same way that Alexander the Great in cutting the Gordian knot wasn’t doing knot theory.

SIM

One thing that complicates my tidy analogy between doing math and playing games is that sometimes people invent math to analyze games or invent games to exemplify math. An instance of this that I’ve already written about is the interplay between combinatorial games and Conway’s system of surreal numbers. I’ve also invented a game of my own called Swine in a Line for the purpose of illustrating a mathematical process called chip-firing (which itself is often called a game even though it isn’t one).

A game related to Ramsey Theory is the pencil game Sim, invented by mathematician Gustavus Simmons, played on a sheet of paper initially marked with six vertices arranged in a regular hexagon and no edges connecting them. You’ll need two colored pencils for this game, say red and blue. You and your adversary take turns connecting the vertices with red edges and blue edges (one of you drawing red edges, the other drawing blue) until either a red triangle or a blue triangle is created, at which instant the person who created the triangle loses. The Ramsey theorem I mentioned above — telling us that when every edge has been added in red or blue, there must be a red triangle or a blue triangle (or both) — tells us that when all fifteen possible edges have been drawn if not sooner, there must be at least one such triangle, so the game can’t end in a draw. It’s now known, thanks to a brute-force computer search that inventoried all positions and all moves, that the second player has a winning strategy, but nobody has been able to come up with a simple way to implement that strategy, short of consulting the computer’s annotated list of all positions and all moves.

Ben Orlin (of Math With Bad Drawings fame) is writing a not-yet-named book about mathematical games, and Sim is one of the games he writes about. He actually prefers a slightly different version he calls “Jim Sim”, after his father Jim Orlin who came up with it; in Jim Sim, the six vertices are drawn at the corners of two nested triangles.

Ben prefers this arrangement because it cuts down on the number of places where edges cross other edges and create visual clutter. Personally, I prefer the extra symmetry of the standard version. But mathematically, the difference between ordinary Sim and Jim Sim is purely cosmetic. (Ben proposes a special rule to handle situations where a player has won without knowing it, allowing the losing player to win; it’s cute but mean.)

PLAYING BY THE RULES

In any game, it’s important to specify the rules as precisely as possible, but it’s hard to anticipate every conceivable misunderstanding. Some misunderstandings are innocent; others are mischievous. I still don’t know what to think about a misunderstanding in my own life that took place almost fifty years ago. According to a well-known result that long predates (and in a way prefigures) Ramsey theory and the game of Sim, tic-tac-toe always ends in a draw if both players play intelligently. At the age of twelve, I became aware of this fact and boasted to a six-year-old that I couldn’t lose at tic-tac-toe. She promptly “beat” me, playing X to my O, like this:

I wasn’t able to convince her that the game isn’t played this way; she thought I was just being a sore loser. Or was she trolling me?

A lot of math-trolling on the web about standard mathematical facts is based on a misunderstanding of the rules of the game. Some misunderstandings are innocent, others seem willful, and others are hard to classify. For instance, I once saw someone critique a valid algebraic proof saying “But look, you added 0 to the left-hand-side of the equation but not the right hand side! In algebra, you always have to do the same thing to both sides!”. I suspect that that person’s real quarrel is not with the mathematical establishment but with a teacher who didn’t describe the rules of algebra with sufficient clarity a decade or two ago.

THE IMPOSSIBLE PROBLEM

Whether you know it or not, we’ve been talking about graph theory. That’s the mathematical discipline that allows one to get rid of all the annoying real-world ambiguities inherent in the people-at-a-party scenario. If a mathematician at a party with six or more people, in an effort to be accessible, tells a non-mathematician the people-at-a-party-puzzle, and the non-mathematician willfully and repeatedly tries to dissolve the puzzle by making real-world-based objections, what’s a peeved mathematician to do but to create a domain of the mind in which the mathematical solution is impervious to quibbles because the assumptions of the puzzle hold by definition?

In analytic geometry a graph is a picture representing a function like y = mx + b or y = x2, but that’s a different context.6 In graph theory, a graph is a collection of points and a collection of segments joining those points, called vertices and edges respectively. One special sort of graph with n vertices contains all the possible edges joining them; this is called a complete graph on n vertices, sometimes abbreviated Kn. The way a graph theorist would ask the people-at-a-party puzzle is, given any red-blue coloring of the edges of a K6, must there always be three vertices that form a red K3 or three vertices that form a blue K3? We’ve seen that the answer is “yes”, and the same is true if we replace 6 by any larger number (just focus on six of the vertices and ignore the rest). Meanwhile, we saw that if we replace 6 by 5 (see Endnote #4) or any smaller number, the answer flips from “yes” to “no”. So there’s a cutoff between 5 and 6. We say that the “Ramsey number” that prevails in this situation is 6. More specifically, we say that R(3,3) is 6, where the first 3 tells us we’re looking for a red K3 and the second 3 tells us that we’re looking for a blue K3, and the 6 tells us we’re sure to be able to find one or the other as long as the number of vertices is 6 or larger. More generally, R(a,b) is the smallest number n with the property that in any graph with n vertices with each edge colored red or blue, there’s bound to be a red Ka or a blue Kb.

What about other values of a and b? It’s long been known that R(4,4) is 18. That is, if you have a K18 and you color each of its edges red or blue, it must contain a red K4 or a blue K4. Or (going back to the other model) if there is a party attended by 18 people, you can always find four people who are mutual acquaintances or four who are mutual nonacquaintances (or both). And 18 is the smallest number with this property; if you replace 18 by 17 the claim becomes false, as can be shown by analysis of the highly symmetrical figure below (where two circles are connected by a path if and only if the two associated people are acquaintances).

In an astonishingly original piece of work, Ramsey proved that this cutoff phenomenon is universal. Pick any positive integer k you like; once the number of people at the party becomes large enough, you can be sure that there will be k guests who are mutual acquaintances or k guests who are mutual nonacquaintances (or both). The hard part is figuring out what “large enough” means. When k is 3, large enough means 6 people; when k is 4, large enough means 18 people; and when k is 5, nobody knows exactly where the cutoff is, even though Ramsey proved that the cutoff exists! Back when Graham et al. wrote their book on Ramsey theory, all that was known about the Ramsey number R(5,5) is that it’s somewhere between 43 and 49 inclusive. In 2017, Vigleik Angeltveit and Brendan McKay were able to shave that 49 down to 48. Similarly, all we currently know about the Ramsey number R(6,6) is that it’s somewhere between 102 and 165 inclusive.

Part of what’s poignant about such Ramsey problems is that each one, taken individually, is a question that could in principle be solved by brute force on a computer capable of systematically examining the brutally large but still finite set of possibilities.7 Evelyn Lamb takes a look at the issue through the lens of Moore’s Law, and the results are discouraging. Even with Moore’s Law on our side, computers will never be powerful enough to pin down the Ramsey number R(6,6) unless we come up with a better way to think about it.

The mathematician Paul Erdős, an early pioneer of Ramsey theory, didn’t think the human race was smart enough to find a better way. He once asked an audience to imagine a scenario in which super-powerful aliens threaten humankind, saying they’ll destroy our species unless we compute some specified Ramsey number. In the case R(5,5), Erdős imagined that, if we threw all our computer power and brain power into the effort, with the threat of annihilation providing extra motivation, humanity could determine whether the Ramsey number is 43, 44, 45, 46, 47, or 48. In contrast, in the case of R(6,6), Erdős opined that our best chance of survival lay not in meeting the aliens’ challenge but in finding ways to defeat them militarily, because as tough as those aliens are, they can’t be as tough as Ramsey problems. In his book “Inevitable Randomness in Discrete Mathematics”, Jószef Beck writes: “Ramsey Games represent a humiliating challenge for Combinatorics.”

Though Erdős’ parable is farfetched, I can think of something even more implausible: aliens who show up threatening to destroy us unless we prove or disprove the proposition that chess is a win for the first player. Let me be clearer about the scenario I’m discussing and disbelieving. I can swallow aliens who’ve studied our culture, including our quaint game of “chess”, and who taunt us by challenging us to prove something about it. What I can’t swallow is aliens who have come up with the game of chess independently of us. That’s because there are just too many possible chess-like games and not enough life-bearing planets in the galaxy.8 In contrast, I believe Ramsey theory gets invented on most planets that develop space-faring civilizations. Indeed, one of the animating impulses behind Ramsey theory can be experienced when one looks up at the night sky, observes geometric patterns in the stars, and wonders “How many of these seemingly meaningful patterns actually become inevitable once you have enough stars in your sky?”

RON GRAHAM

I had the pleasure of knowing Ron Graham. He may be best known to the public at large for having invented “Graham’s number”9 in the course of his work on Ramsey theory, but I was very influenced by other work of his (much of it joint with his wife, the mathematician Fan Chung) on quasirandom graphs. He was generous to me in various ways, of which I’ll mention three:

1) In the late 1980s Ron gave me an article to referee for a journal, saying “I think you’ll like it.” Spending a few weeks immersed in that article gave me ideas that were at the the center of my research for more than a decade.

2) Around the same time Ron gave me a puzzle from his office called a Panex. It’s similar to the Tower of Hanoi puzzle, but harder. In the case of the Tower of Hanoi puzzle, which involves moving disks between three spindles, it’s known exactly how many moves are required to solve the problem when there are n disks. In contrast, the optimal solution to the general version of the Panex puzzle is still unknown. The Panex that Ron gave me is still in my office. If you want to give the puzzle a try, here’s a virtual version.

3) Back in the early 1990s Ron invited me to attend a conference I’d never heard of. It was a “Gathering 4 Gardner“, the second such gathering in an ongoing series, and these biennial meetings have been a big part of my mathematical life ever since.

Ron also gave me a suggestion thirty years ago that I hope to bring to fruition during the coming year. Visiting MIT in the mid-90s, Ron passed an elevator bay along one of the corridors near the math department and quipped that it ought to sport a sign that said “L(η)” (if you don’t get the joke, try saying it the way a mathematician would if L were a function and η were the argument to which the function was being applied). At the time I was just an assistant professor at MIT with no voice in departmental decor. But now that I am a full professor at UMass Lowell, I plan to put up an L(η) sign next to the elevator bank at our department’s new headquarters.

My first thought when I read this claim was that I must have misunderstood it. If I start with a typical large number n, the sum of its digits is likely to be close to the logarithm of n, give or take a factor of 10.10 So Graham and his coauthors seem to be saying that if you start with any number n, however large, and take the logarithm three times in succession, you get to an answer that’s ten or smaller. You don’t need Graham’s number to see that that’s ridiculous; even as comparatively puny a quantity as

will do.

But do you see the mistake I made? Nobody said Ron has to insert plus signs everywhere. It’s true that if I want the very next number in the number-chain to be as small as possible, inserting plus signs everywhere is the way to go, but that strategy may show its short-sightedness further down the line; the race doesn’t always go to the strongest starter. For instance, consider the starting number 919; if Ron turns it into 91+9 instead of 9+1+9, he can get to the final answer 1 in two steps (91+9 = 100; 1+0+0 = 1) instead of three steps (9+1+9 = 19; 1+9 = 10; 1+0 = 1).

“Fair enough,” you might say, “But Ron got lucky that time; if he inserts plus signs into a string of digits at random, it won’t happen very often that the insert-and-add operation will lead to a number with so many zeroes.”

But wait: Ron doesn’t need this proliferation of zeroes to be something that happens at random. As long as there’s some way of inserting the plus signs to make lots of zeroes appear, that’s good enough for him. And there are exponentially many ways to insert those plus signs, so he has lots of ways to potentially win.

So maybe it’s not so surprising that if Ron plays the insert-and-add game wisely, he can arrive at a single-digit answer in fewer steps than if he naively puts in plus-signs everywhere. But just three steps? No matter how big the original number is? That’s kind of amazing. See the Butler, Graham, and Stong article for details. (It’s a bit more complicated than making sure you get lots of zeroes right away.)

To get a sense of Ron Graham as a person, I urge you to check out George Csicsery’s short video portrait of Graham, entitled “Something New Every Day”.

In addition to being a mathematician, Graham was also an avid juggler, and once said “The problem with juggling is, the balls go where you throw them, not where you wish they would go, or where they are supposed to go.” Once a ball leaves your grip, its trajectory is out of your hands. Graham might have added that, analogously, the problem with math is that it follows the rules you set up. Once you’ve launched a definition into the air, it goes where you sent it, and the theorem that lands in your hands, possibly much later, may be very different from what you expected. At times this discrepancy can be a source of frustration, but for the mathematician it can also be a source of delight.

Thanks to Jeremy Cote, Sandi Gubin, David Jacobi, Andy Latto, Joe Malkevitch, Gareth McCaughan, Ben Orlin, Evan Romer, and Rich Schroeppel.

ENDNOTES:

#1: Here I’m stressing the “internal” view of math. There is an equally important external view that situates math in historical and cultural context, dealing with such topics as “What questions get asked in the first place? Why these particular definitions and rules, and not others?” Nearly all mathematics has some real-world phenomenon as its point of departure, and much mathematics that has left the real world far behind can orbit back and have real-world applications. But that’s not what I’m talking about here.

#2: Here and elsewhere, “or” is meant in the inclusive, “and/or” sense; if you can find three mutual acquaintances and three mutual nonacquaintances among the six people, all the better!

#3: Martin Gardner used the plural noun “vertexes”, but I think this is less common nowadays. Have any of you seen this in recent publications? How about “matrixes” instead of “matrices”?

#4: Here’s a graph with 5 vertices whose whose edges have been colored red and blue, containing no red triangle and no blue triangle.

#5: Say the three people you’ve singled out are all people you’re acquainted with. If any two of them are acquaintances, then the two of them, along with you, form an acquainted threesome. On the other hand, if no two of them are acquaintances, then the three of them form an unacquainted threesome. Similar logic applies in the case where the three people you’ve singled out are all people you’re unacquainted with.

#6: The word “graph” is used in rather different senses in analytic geometry and discrete mathematics. Do mathematicians writing in languages other than English have to contend with this ambiguity? Let me know in the Comments.

We allow the edges to cross one another, but we don’t allow an edge to pass through extra vertices en route from one vertex to another. To make the pictures nicer, we sometimes allow the edges to curve, but we don’t allow a curved edge to join a vertex to itself, nor do we allow more than one edge between two particular vertices.

If you push mathematicians hard they will retreat even further from reality and say that a graph isn’t actually a picture at all, but rather an abstract collection of entities called vertices that are unspecified objects of pure thought, along with other entities called edges that are unordered pairs of vertices. So don’t push us.

#7: Remember the “find the 4 red triangles and 2 blue triangles” challenge from earlier? Solving it is just a matter of patience, not cleverness, since there are only twenty trios to try. If you disliked that puzzle, I don’t blame you; I’m more interested in problems that require intelligence. Most famous mathematical problems aren’t reducible to exhaustive examination of finitely many cases; for instance, both Fermat’s Last Theorem (solved) and the Riemann Hypothesis (still open) are “infinitary” in this sense.

#8: If you doubt this, take a look at all the variants listed in the Wikipedia page on chess variants and now imagine all the variants that could be listed there but aren’t. If nevertheless you think that chess stands out as one of the best of the bunch, for reasons that would apply throughout the galaxy, please explain!

If you’re wondering why I’m not worried about invasions from other galaxies, it’s because even though interstellar distances are large, intergalactic distances are ridiculously large. Any intergalactic being that tried to pop over to slake its thirst for conquest would become millions of years old and eventually forget why it had wanted to come to our galaxy in the first place. Multigenerational voyages wouldn’t solve the problem either: after the initial crew died, later generations would rebel against being cooped up in a spaceship on a journey they’d never get to finish, especially when the whole idea of the trip wasn’t theirs to begin with.

#9: Graham’s number is big. Really big. You just won’t believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it’d be hard to write out all the digits of nine raised to the ninth power nine times, but that’s just peanuts to Graham’s number. If you’re itching to know more, filmmaker Brady Haran has what you crave. Haran is the creator of the trilogy of mathematico-cinematic blockbusters “Graham’s Number”, “How Big Is Graham’s Number?”, and “Wait, What Is Graham’s Number Again?”, which he followed with a fourth video, entitled “Well, That About Wraps It Up For Graham’s Number”. (The actual names of some videos have been changed to be more like something Douglas Adams would have come up with.)

As far as I know, nobody has proposed a game playable by pan-dimensional beings in which the impossibility of the game ending in a draw is proved by the theorem of Graham and Rothschild that led Graham to invent his number. But if anyone did, the game would clearly deserve to be called “GRim” (in honor of Graham and Rothschild).

#10: Suppose n has k digits, and suppose that n contains each of the digits 0 through 9 in roughly equal proportion, so that the average of the digits is around 4.5; then the sum of the digits should be about 4.5 times k, which is about 4.5 times the base ten logarithm of n.

REFERENCES

Jószef Beck, Inevitable Randomness in Discrete Mathematics.

Alexander Bogomolny, “Ramsey’s Number R(4,4)” at cut-the-knot.org.

Anthony Bonato, “Breakthrough in Ramsey Theory”, The Intrepid Mathematician, April 5, 2017, https://anthonybonato.com/2017/04/05/breakthrough-in-ramsey-theory/ .

Steve Butler, Ron Graham, and Richard Stong, Inserting Plus Signs and Adding, The American Mathematical Monthly, 123(3), March 2016, 274-279, http://orion.math.iastate.edu/butler/papers/16_03_insert_and_add.pdf .

Fan Chung, About Ron Graham, http://www.math.ucsd.edu/~fan/ron/ .

F. R. K. Chung, R. L. Graham, and R. M. Wilson, “Quasi-random graphs”, Combinatorica, volume 9, pages 345–362 (1989), http://www.math.ucsd.edu/~fan/wp/quasirandom1.pdf .

George Csicsery, “Something New Every Day: The Math & Magic of Ron Graham”, Zala Films; https://vimeo.com/136044050 .

Martin Gardner, “Digital Roots”, in “The Second Scientific American Book of Mathematical Puzzles and Diversions”.

Martin Gardner, “Ramsey Theory”, chapter 17 of “Penrose Tiles to Trapdoor Ciphers… and the Return of Dr. Matrix”.

Martin Gardner, “Sim, Chomp, and Racetrack”, chapter 9 of “Knotted Doughnuts and Other Mathematical Entertainments”.

Anthony Gottlieb, “The Man Who Thought Too Fast”, The New Yorker, April 27, 2020, https://www.newyorker.com/magazine/2020/05/04/the-man-who-thought-too-fast .

Ronald Graham, Papers of Ron Graham, http://www.math.ucsd.edu/~ronspubs/ .

Ronald Graham, Bruce Rothschild, and Joel Spencer, “Ramsey Theory”, Wiley Press; available through https://www.wiley.com/en-us/Ramsey+Theory%2C+2nd+Edition-p-9780471500469 .

Ronald L. Graham and Joel H. Spencer, “Ramsey Theory”, Scientific American, Vol. 263, No. 1 (July 1990), pp. 112-117. http://www.math.ucsd.edu/~fan/ron/papers/90_06_ramsey_theory.pdf

Ronald Graham and Persi Diaconis, Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks, Princeton University Press; available through https://press.princeton.edu/books/hardcover/9780691151649/magical-mathematics .

Evelyn Lamb, “Overthinking an Erdos Quote”, https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/

Cheryl Misak, “Frank Ramsey: A Sheer Excess of Powers”, Oxford University Press; available through https://global.oup.com/academic/product/frank-ramsey-9780198755357? .

2 thoughts on “Math, Games, and Ronald Graham”

1. Bill O

If you had an object that performed certain operations on L(eta) would that be an L(eta) operator?

Like