David Eppstein is Chancellor’s Professor of Computer Science at the University of California, Irvine. In Forbidden Configurations, he examines a number of seemingly simple problems in plain geometry concerning finite sets of points and lines in the plane. Although most of these problems should prove relatively easy to grasp for the uninitiated, general solutions to these problems are not known. Each of these problems also leads, in turn, to others.
Here are some examples.
Suppose we have a set of n points in the plane, and suppose that no three of them lie on a line. How many different configurations of these points are there? To understand what is meant by configurations, consider the case n = 5. The following three configurations can be formed: a convex pentagon, i.e., one whose points can be connected as a cycle in which all interior angles are less than 180 degrees; a convex quadrilateral with a point inside; and a triangle with two points inside. The number of configurations for general n is unknown. There are, in fact, several different ways to define the notion of configuration. The number of configurations is unknown for all the usual ones for large n values.
If these three configurations are drawn on a piece of paper, it becomes apparent that each contains four points that form a convex quadrilateral. This means that the only configuration of at least four points without containing a convex quadrilateral has exactly four points – the configuration consisting of a triangle with a point inside. Similarly, there is a configuration with eight points that does not contain a convex pentagon while all configurations with nine points contain five that form a convex pentagon. Is the largest number of points for which there is a configuration lacking a convex k-gon always 2 raised to the power k – 2, which is true for these small cases? It is known that there are configurations of that size for all k that contain no convex k-gons. Are there any configurations of one more than 2k – 2 points that have no convex k-gon among their points? The question is open.
Suppose that one is tasked with choosing as many squares as possible from an n by n checkerboard, such that no line of squares of whatever slope contains three or more chosen squares. How many can be chosen? Since two squares, at most, out of the n in each row of the board can be chosen and there are n rows, there is an obvious upper bound of 2n. In general, the best bounds are unknown, but there are lots of curious bounds on the answer for large n. For sufficiently small n, 2n squares can be chosen. Finding a way to choose such squares is an interesting exercise. The best possible result is unknown for n = 14 and higher. The largest possible size seems to approach something like 1.81n.
Each problem asking how large something can be leads, in turn, to further questions: How difficult is it to construct large configurations? How close can one come to optimal results with simple algorithms? How do such questions relate to the hierarchy of difficulty that has been developed by theoretical computer scientists? In this new book, Eppstein provides background for such questions.
Forbidden Configurations has a distinct advantage over most mathematical works focused on problems of current interest to mathematicians. The nature of the questions Eppstein examines are easily understandable for non-mathematicians, and the treatment is, for the most part, accessible to well-informed readers. The book will be of great interest for budding mathematicians, in particular, who will find plenty of stimulating questions to consider, many of which are not usually encountered as part of a mathematics curriculum.
Does a non-mathematician really have anything to gain from attempting to read Forbidden Configurations? If approached as if it were a novel, or a series of exercises to be learned, the lay reader will, in all likelihood, quickly tire of the book. Progress will seem like hard work—a chore that can easily be avoided by never picking it up again.
Fortunately, there is another way to approach the book that is not only much more enjoyable, but also may make more sense for non-mathematicians. This approach involves focusing purely on the mathematics: pick one of the theorems and attempt to prove it in the manner described by the author.
To begin with, carefully examine the statement of the result. After reading the statement a number of times, close the book and try to prove the theorem. Most readers will likely struggle at first, but they should not be discouraged. Patience and perseverance are essential. If progress is proving difficult, hints can be found by briefly examining the method the author uses to prove the theorem and then closing the book again and trying again to prove it. After consulting the text enough times the route to the proof will eventually become apparent.
The overall experience is not dissimilar to that of mathematicians undertaking their own research. Specialists also begin with a problem whose solution is not immediately obvious to them. The feeling is a little like being lost in an unfamiliar town or city. Through a process of exploration and experimentation, information is gathered until, with sufficient luck and perseverance, the goal, whatever it may be, is reached. This approach is also useful when seeking solutions for non-mathematical problems. It is a style of thinking and problem-solving with many practical applications.
The ideas developed during this process can be used to devise games or puzzles. Consider the following example, based on the task of selecting as many squares as possible from a checkerboard where no line of any slope can contain three or more chosen squares. To begin with, try to find ten squares in a five by five checkerboard that follow this rule. If my own experience is anything to go by, readers will likely start by picking out ten squares and checking to see if they contain any three in lines. This method did not lead me anywhere. No matter what I tried—even after looking at a configuration given in the book—the result was the same: There were three in a line somewhere. A different approach was needed.
Upon reflection, it became apparent that choosing the middle square would never work. Exactly eight lines pass through the middle square, and every other square can be found in one of them. If the middle square is selected, the no-three-squares-in-a-line rule means that, at most, only one other square in each of those lines can be chosen. The result is that 8 + 1 squares, or 9 in total, can be chosen, and not 10. The problem therefore cannot be solved if the middle square is chosen.
In this case, a solution can be found by picking two squares in each of two rows, and extending choices one square at a time, marking the other squares that are excluded because they lie on lines with two other already chosen squares. If three are excluded in any row or column, these selections are then forced to be the other two squares there. These forcings will either, lead to a ten square solution or fail to do so. There are only a few possibilities in any two rows, especially if the symmetry of the problem is taken into account. One more square that isn’t forced may be left out, but in any column there will be, at most, three possibilities. Different choices in the two rows can be tested to see if they quickly lead to a solution. If these possible choices are tested systematically, a solution will become apparent after, at most, four or five choices in those rows.
But don’t take my word for it, try it for yourself.
At this point, a hint may prove helpful. It can be assumed that there is an orientation of the five by five checkerboard in which the middle square in the bottom row can be chosen. If this were not the case, for every orientation the second and fourth square in the middle row or column must be chosen. This particular configuration of four squares cannot form part of a solution. The only squares not eliminated by such a choice are located on the two main diagonals, which can contain only four chosen points. Adding these to the four already chosen makes, at most, eight points. There are, in fact, only two possible choices for the bottom row, up to symmetry that contain its middle square. Both choices can lead to a solution.
Once a solution has been found, another hint may still prove useful. The same approach can be used for n = 6, n = 7, and n = 8 provided the middle 4, 9, and 16 squares, respectively, are avoided. After these squares are excluded, all that remains is an outside rim, two squares wide—which can also be seen for n = 5. Finding these solutions is a similar challenge to solving a sudoku, but much more satisfying to complete. Checking possible solutions is straightforward. Only rows, columns, diagonals, and knight’s moves need be checked for possible three-squares-in-a-line rule violations.
There is much to be gained from studying the problems described in Forbidden Configurations. Their solutions favor approaches that involve taking a series of small steps, examining the consequences at each step, and using that information to move on to the next step. This approach will prove far more effective than relying on initial knowledge, or intuition, to generate complete attempts at solutions. This is a lesson worth noting.
Anyone with time on their hands, or feeling bored, could profit from investigating a problem inspired by this book. You may even find an enticing puzzle or game based on such a problem.
