Decomposition

Mathematics too has profited from the idea that sometimes things of interest might have a structure which allowed them to be decomposed into simpler parts…

Joe Malkevitch
York College (CUNY)

Introduction

One way to get insights into something one is trying to understand better is to break the thing down into its component parts, something simpler. Physicists and chemists found this approach very productive—to understand water or salt it was realized that common table salt was sodium chloride, a compound made of two elements, sodium and chlorine and that water was created from hydrogen and oxygen. Eventually, many elements (not the Elements of Euclid!) were discovered. The patterns noticed in these building block elements lead to the theoretical construct called the periodic table, which showed that various elements seemed to be related to each other. The table suggested that there might be elements which existed but had not been noticed; the "holes" in the table were filled when these elements were discovered, sometimes because missing entries were sought out. The table also suggested "trans-uranium" elements, which did not seem to exist in the physical world but could be created, and were created, in the laboratory. These new elements were in part created because the periodic table suggested approaches as to how to manufacture them. The work done related to understanding the structure of the periodic table suggested and lead to the idea that elements were also made up of even smaller pieces. This progression of insight lead to the idea of atoms, and that atoms too might have structure lead to the idea of subatomic particles. But some of these "fundamental" particles could be decomposed into smaller "parts." We now have a zoo of quarks and other "pieces" to help us understand the complexities of the matter we see in the world around us.

Shiny crystals of the element gallium



Crystals of gallium, an element whose existence was predicted using the periodic table. Photo by Wikipedia user Foobar, CC BY-SA 3.0.

Prime patterns

Mathematics too has profited from the idea that sometimes things of interest might have a structure which allowed them to be decomposed into simpler parts. A good example is the number 111111111. It is an interesting pattern already, because all of its digits are 1’s when written in base 10. We could compare 111111111 with the number that it represents when it is interpreted in base 2 (binary)—here it represents 511. But it might be interesting to study any relation between numbers with all 1’s as digits and compare them to numbers in other bases, not only base 2! Mathematics grows when someone, perhaps a computer, identifies a pattern which can be shown to hold in general, rather than for the specific example that inspired the investigation. A number of the form 1111….1 is called a repunit. Can we find interesting patterns involving repunits?

One approach to decomposing a number (here strings of digits are to be interpreted as being written in base 10) is to see if a number can be written as the product of two other numbers different from 1 and itself. For example, 17 can only be written as the product of the two numbers 17 and 1. On the other hand, 16 can be written as something simpler, as $2 \times 8$ but there are "simpler" ways to write 16, as $4 \times 4$, and since 4 can be decomposed as $2 \times 2$ we realize that 16 can be written as $2 \times 2 \times 2 \times 2$. Seeing this pattern, mathematicians are trained to ask questions, such as whether numbers which are all the products of the same number which cannot be broken down have any special interest. But we are getting ahead of ourselves here. What are the "atoms" of the multiplicative aspect of integers? These are the numbers called the primes, 2, 3, 5, 7, 11, … Notice that 11 is also a repunit. This takes us back to the idea that there might be many numbers of the form 11111…….111111 that are prime! Are there infinitely many primes all of whose digits in their base 10 representation are one? Answer!! No one knows. But it has been conjectured that there might be infinitely many repunit primes. Note that numbers like 111, 111111, 111111111, … where the number of digits is a multiple of 3, can’t be prime.

Note 11 base 2 is 3, which is also prime. Similarly, 1111111111111111111 is prime, and 1111111111111111111 base 2 represents the number 524287, which is also prime. If a repunit is prime, must the decimal number it represents treated as a base 2 number be prime?

By looking for "parts" that were building blocks for the integers, mathematics has opened a rich array of questions and ideas many of which have spawned major new mathematical ideas both theoretical and applied. Having found the notion of prime number as a building block of the positive number system, there are natural and "unnatural" questions to ask:

1. Are there infinitely many different primes?

2. Is there a "simple" function (formula) which generates all of the primes, or if not all primes, only primes?

While the fact that there are infinitely many primes was already known by the time of Euclid, the irregularity of the primes continues to be a source of investigations to this day. Thus, the early discovered pattern that there seemed to be pairs of primes differing by two (e.g. 11 and 13, 41 and 43, 139 and 141), which lead to the "guess" that perhaps there are infinitely many numbers of the form $p$ and $p+2$ that are both primes (known as twin primes) is still unsolved today. While more and more powerful computers made possible finding larger and larger twin prime pairs, no one could find a proof of the fact that there might be infinitely many such pairs. There were attempts to approach this issue via a more general question. Were there always primes which were some fixed bound of numbers apart? Little progress was made on this problem until in 2013 a mathematician whose name was not widely known in the community showed that there was a large finite uniform bound on a fixed size gap which could appear infinitely many times. This work by Yitang Zhang set off a concerted search to improve his methods and alter them in a way to get better bounds for the size of this gap. While Zhang’s breakthrough has been improved greatly, the current state of affairs is still far from proving that the twin-prime conjecture is true.

Photo of Yitang Zhang

Photo of Yitang Zhang. Courtesy of Wikipedia.

Mathematical ideas are important as a playground in which to discover more mathematical ideas, thus enriching our understanding of mathematics as an academic subject and sometimes making connections between mathematics and other academic subjects. Today there are strong ties between mathematics and computer science, an academic subject that did not even exist when I was a public school student. Mathematics can be applied in ways that not long ago could not even be imagined, no less carried out. Who would have thought that the primes would help make possible communication that prevents snooping by others as well as protecting the security of digital transactions? From ancient times, codes and ciphers were used to make it possible to communicate, often in military situations, so that should a communication fall into enemy hands it would not assist them. (Codes involve the replacement of words or strings of words with some replacement symbol(s), while ciphers refer to replacing each letter in an alphabet with some other letter in order to disguise the meaning of the original text.) Human ingenuity has been remarkable in developing clever systems for carrying out encryption of text rapidly and has allowed the receiver to decrypt the message in a reasonable amount of time but would, at the very least, slow down an enemy who came into possession of the message. But the development of calculators and digital computers made it harder to protect encrypted messages, because many systems could be attacked by a combination of brute force (try all possible cases) together with using ideas about how the design of the code worked. There was also the development of statistical methods based on frequency of letters and/or words used in particular languages that were employed to break codes. You can find more about the interactions between mathematics, ciphers, and internet security in the April 2006 Feature Column!



Earlier we looked at "decomposing" numbers into their prime parts in a multiplication of numbers setting. Remarkably, a problem about decomposing numbers under addition has stymied mathematics for many years, despite the simplicity of stating the problem. The problem is named for Christian Goldbach (1690-1764).

Letter from Euler to Goldbach

Letter from Goldbach to Euler asking about what it is now known as Goldbach’s Conjecture. Image courtesy of Wikipedia.

Goldbach’s Conjecture (1742)

Given an even positive integer $n$, $n$ can be written as the sum of two primes.

For example, 10 = 3 +7 or also 5 +5, 20 = 3 + 17, 30 = 11 + 19. We allow the primes to be either the same or different in the decomposition. While computers have churned out larger and larger even numbers for which the conjecture is true, the problem is still open after hundreds of years.

What importance should one attach to answering a particular mathematical question? This is not an easy issue to address. Some mathematical questions seem to be "roadblocks" to getting insights into what seem to be important questions in one area of mathematics and in some cases answering a mathematical question seems to open doors on many mathematical issues. Another measure of importance might be in terms of aesthetic properties of a particular mathematical result. The aesthetic may be from the viewpoint that something seems surprising or unexpected or the aesthetic may be that a result seems to have "beauty"—a trait that whether one is talking about beautiful music, fabrics, poems etc. seems to differ greatly from one person to the next. It is hard to devise an objective yardstick for beauty. Another scale of importance is the "value" of a mathematical result to areas of knowledge outside of mathematics. Some results in mathematics have proved to be insightful in many academic disciplines like physics, chemistry, biology but other mathematics seems only to be relevant to mathematics itself. What seems remarkable is that over and over again mathematics that seemed only to have value within mathematics itself or to be only of "theoretical" importance, has found use outside of mathematics. Earlier I mentioned some applications of mathematical ideas to constructing ciphers to hide information. There are also codes designed to correct errors in binary strings and to compress binary strings. Cell phones and streaming video use these kinds of ideas: it would not be possible to have the technologies we now have without the mathematical ideas behind error correction and data compression.

Partitions

The word decompose has some connotations in common with the word partition. Each of these words suggests breaking up something into pieces. Often common parlance guides the use of the technical vocabulary that we use in mathematics, but in mathematics one often tries to be very careful to be precise in what meaning one wants a word to have. Sometimes in popularizing mathematics this attempt to be precise is the enemy of the public’s understanding the mathematics involved. Sometimes precise words are used to define a concept which are mathematically precise but obscure the big picture of what the collection of ideas/concepts that are being defined precisely are getting at. Here I try to use "mathematical terminology" to show the bigger picture of the ideas involved.

Given a positive integer $n$, we can write $n$ as a sum of positive integers in different ways. For example, $3 = 3$, $3 = 2+1$, and $3 = 1 + 1 + 1$. In counting the number of decompositions possible, I will not take order of the summands into account—thus, $1 +2$ and $2 +1$ will be considered the same decomposition. Each of these decompositions is considered to be a partition of 3. In listing the partitions of a particular number $n$, it is common to use a variant of set theory notation where the entries in set brackets below can be repeated. Sometimes the word multiset is used to generalize the idea of set, so that we can repeat the same element in a set. Thus we can write the partitions of three as $\{3\}$, $\{2,1\}$, $\{1,1,1\}$. A very natural question is to count how many different partitions there are of $n$ for a given positive integer. You can verify that there are 5 partitions of the number 4, and 11 partitions of the number 5. Although for very large values of $n$ the number of partitions of $n$ has been computed, there is no known formula which computes the number of partitions of $n$ for a given positive integer $n$. Sometimes the definition of partition insists that the parts making up the partition be listed in a particular order. It is usual to require the numbers in the partition not to increase as they are written out. I will use this notational convention here: The partitions of 4 are: $\{4\}$, $\{3,1\}$, $\{2, 2\}$, $\{2, 1, 1\}$, $\{1,1,1,1\}$. Sometimes in denoting partitions with this convention exponents are used to indicate runs of parts: $4$; $3,1$; $2^2$; $2, 1^2$; $1^4$. The notation for representing partitions varies a lot from one place to another. In some places for the partition of 4 consisting of $2 + 1 + 1$ one sees $\{2,1,1\}$, $2+1+1$, $211$ or $2 1^2$ and other variants as well! It may be worth noting before continuing on that we have looked at partitions of $n$ in terms of the sum of smaller positive integers but there is another variant that leads in a very different direction. This involves the partition of the set $\{1,2,3,\dots,n\}$ rather than the partition of the number $n$. In this framework the partition of a set $S$ consists of a set of non-empty subsets of the set $S$ whose union is $S$. (Remember that the union of two sets $U$ and $V$ lumps together the elements of $U$ and $V$ and throws away the duplicates.)

Example: Partition the set $\{1,2,3\}$:

Solution:

$$\{1,2,3\}, \{1,2\} \cup \{3\}, \{1, 3\} \cup \{2\}, \{2,3\} \cup \{1\}, \{1\} \cup \{2\} \cup {3}$$

While there are 3 partitions of the number 3 there are 5 partitions of the set $\{1,2,3\}$. The number of partitions of $\{1,2,3,\dots,n\}$ are counted by the Bell numbers, developed by Eric Temple Bell (1883-1960). While the "standard" name for these numbers now honors Bell, other scholars prior to Bell also studied what today are known as the Bell numbers, including the Indian mathematician Srinivasa Ramanujan (1887-1920).

Sketch of E.T. Bell



A sketch of Eric Temple Bell. Courtesy of Wikipedia.



Partitions have proved to be a particularly intriguing playground for studying patterns related to numbers and have been used to frame new questions related to other parts of mathematics. When considering a partition of a particular number $n$, one can think about different properties of the entries in one of the partitions:

  • How many parts are there?
  • How many of the parts are odd?
  • How many of the parts are even?
  • How many distinct parts are there?

For example, for the partition $\{3, 2, 1, 1\}$, this partition has 4 parts, the number of odd parts is 3, the number of even parts 1, and the number of distinct parts is 3.

Closely related to partitions is using diagrams to represent partitions. There are various versions of these diagrams, some with dots for the entries in the partition and others with cells where the cell counts in the rows are the key to the numbers making up the partition.

Thus for the partition $3+2+1$ of 6 one could display this partition in a visual way:

X X X

X X

X

There are various conventions about how to draw such diagrams. One might use X’s as above but traditionally dots are used or square cells that abut one another.

These are known as Ferrers’s (for Norman Macleod Ferrers, 1829-1903) diagrams or sometimes tableaux, or Young’s Tableaux. The name honors Alfred Young (1873-1940). Young was a British mathematician and introduced the notion which bears his name in 1900.

Norman Ferrers



Norman Ferrers. Image courtesy of Wikipedia.

The term Young’s Tableau is also used for diagrams such as the one below where numbers chosen in various ways are placed inside the cells of the diagram.

Ferrers diagram, cells

A representation of the partition 10 with parts 5, 4, 1



Ferrers diagram, dots

A representation of the partition of 11 ($\{5,3,2,1\}$) using rows of dots.



While these diagrams show partitions of 10 and 11 by reading across the rows, one also sees that these diagrams display partitions of 10, and 11, namely, 3,2,2,1 and 4,3,2,1,1 respectively, by reading in the vertical direction rather than the horizontal direction. Thus, each Ferrers’s diagram gives rise to two partitions, which are called conjugate partitions. Some diagrams will read the same in both the horizontal and vertical directions; such partitions are called self-conjugate. Experiment to see if you can convince yourself that the number of self-conjugate partitions of $n$ is the same as the number of partitions of $n$ with odd parts that are all different!

The next figure collects Ferrers’s diagrams for the partitions of small integers.



Diagram of partitions of 1 to 8



Ferrers’s diagrams of partitions of the integers starting with 1, lower right, and increasing to partitions of 7. Courtesy of Wikipedia.



Often to get insights into mathematical phenomena one needs data. Here for example, complementing the previous figure, is a table of the ways to write the number $n$ as the sum of $k$ parts. For example, 8 can be written as a sum of two parts in 4 ways. These are the partitions of 8 which have two parts: $7+1$, $6+2$, $5+3$, and $4+4$.

$n$ into $k$ parts 1 2 3 4 5 6 7 8
1 1              
2 1 1            
3 1 1 1          
4 1 2 1 1        
5 1 2 2 1 1      
6 1 3 3 2 1 1    
7 1 3 4 3 2 1 1  
8 1 4 5 5 3 2 1 1
Fill in next row!!                


Table: Partition of the number $n$ into $k$ parts

While many people have contributed to the development of the theory of partitions, the prolific Leonhard Euler (1707-1783) was one of the first.

Portrait of Euler



Leonhard Euler. Image courtesy of Wikipedia.

Euler was one of the most profound contributors to mathematics over a wide range of domains, including number theory, to which ideas related to partitions in part belongs. Euler showed a surprising result related to what today are called figurate numbers. In particular he discovered a result related to pentagonal numbers. Euler was fond of using power series (a generalized polynomial with infinitely many terms) which in the area of mathematics dealing with counting problems, combinatorics, is related to generating functions. If one draws a square array of dots, one sees $1, 4, 9, 16, \dots$ dots in the pattern that one draws. What happens when one draws triangular, pentagonal, or hexagonal arrays of dots? In the next two figures, we see a sample of the many ways one can visualize the pentagonal numbers: $1, 5, 12, 22, \dots$

Diagram of pentagonal numbers Diagram of pentagonal numbers

(a)                                             (b)



Two ways of coding the pentagonal numbers. Courtesy of Wikipedia.



Diagram of pentagonal numbers



The pentagonal numbers for side lengths of the pentagon from 2 to 6. Courtesy of Wikipedia.



Godfrey Harold Hardy (1877-1947), Ramanujan and in more modern times, George Andrews and Richard Stanley have been important contributors to a deeper understanding of the patterns implicit in partitions and ways to prove that the patterns that are observed are universally correct.

Photo of G.H. Hardy





Photo of G. H. Hardy. Photo courtesy of Wikipedia.



Ramanujan



Srinivasa Ramanujan. Image courtesy of Wikipedia.

Photo of George Andrews

Photo of George Andrews. Courtesy of Wikipedia.

Photo of Richard Stanley



Photo of Richard Stanley. Courtesy of Wikipedia.

What is worth noting here is that the methodology of mathematical investigations is both local and global. When one hits upon the idea of what can be learned by “decomposing’ something one understands in the hope of getting a deeper understanding, it also has implications in other environments where one uses the broader notion (decomposition). So understanding primes as building blocks encourages one to investigate primes locally in the narrow arena of integers but also makes one think about other kinds of decompositions that might apply to integers. We are interested in not only decompositions of integers from a multiplicative point of view but also decompositions of integers from an additive point of view. Here in a narrow sense one sees problems like the Goldbach Conjecture but in a broader sense it relates to the much larger playground of the partitions of integers. When one develops a new approach to looking at a situation (e.g. decomposing something into parts) mathematicians invariably try to "export" the ideas discovered in a narrow setting to something more global, including areas of mathematics that are far from where the original results were obtained. So if decomposition is useful in number theory, why not try to understand decompositions in geometry as well? Thus, there is a whole field of decompositions dealing with plane polygons, where the decompositions are usually called dissections.

As an example of a pattern which has been discovered relatively recently and which illustrates that there are intriguing mathematical ideas still to be discovered and explored, consider this table:



Partition Distinct elements Number 1’s
4 1 0
3+1 2 1
2+2 1 0
2+1+1 2 2
1+1+1+1 1 4
Total 7 7





See anything interesting—some pattern? Not all of the column entries are odd or even in the second and third columns. However, Richard Stanley noted that the sum of the second and third columns are equal! Both add to 7. And this is true for all values of $n$. How might one prove such a result? One approach would be to find a formula (function involving $n$) for the number of distinct elements in the partitions of $n$ and also find a formula for the number of 1’s in the partitions of $n$. If these two formulas are the same for each value of $n$, then it follows that we have a proof of the general situation that is illustrated for the example $n = 4$ in the table above. However, it seems unlikely that there is a way to write down closed form formulas for either of these two different quantities. However, there is a clever approach to dealing with the observation above that is also related to the discovery of Georg Cantor (1845-1918) that there are sets with different sizes of infinity.

Consider the two sets, $\mathbb{Z}^+$ the set of all positive integers and the set $\mathbb{E}$ of all of the even positive integers. $\mathbb{Z}^+ = \{1,2,3,4,5, \dots\}$ and $\mathbb{E}={2,4,6,8,10,\dots}$. Both of these are infinite sets. Now consider the table:

1 paired with 2

2 paired with 4

3 paired with 6

4 paired with 8

.

.

.

Note that each of the entries in $\mathbb{Z}^+$ will have an entry on the left in this "count" and each even number, the numbers in $\mathbb{E}$, will have an entry on the right in this "count." This shows that there is a one to one and onto way to pair these two sets, even though $\mathbb{E}$ is a proper subset of $\mathbb{Z}^+$ in the sense that every element of $\mathbb{E}$ appears in $\mathbb{Z}^+$ and there are elements in $\mathbb{Z}^+$ that don’t appear in $\mathbb{E}$. There seems to be a sense in which $\mathbb{E}$ and $\mathbb{Z}^+$ have the same "size." This strange property of being able to pair elements of a set with a proper subset of itself can only happen for an infinite collection of things. Cantor showed that in this sense of size, often referred to as the cardinality of a set, some pairs of sets which seemed very different in size had the same cardinality (size). Thus, the set of positive integers Cantor showed had the same cardinality as the set of positive rational numbers (numbers of the form $a/b$ where $a$ and $b$ are positive integers with no common factor for $a$ and $b$). Remarkably, he was also able to show that the set of positive integers had a different cardinality from the set of real numbers. To this day there are questions dating back to Cantor’s attempt to understand the different sizes that infinite sets can have that are unresolved.

What many researchers are doing for old and new results about partitions is to show that counting two collections, each defined differently but for which one gets the same counts, the equality of the counts can be shown by constructing a bijection between the two different collections. When such a one-to-one and onto correspondence (function) can be shown for any value of a positive integer n, then the two collections of things must have the same size. Such bijective proofs often show more clearly the connection between seemingly unrelated things rather than showing that the two different concepts can be counted with the same formula. These bijective proofs often help generate new concepts and conjectures.

Try investigating ways that decompositions might give one new insights into ideas you find intriguing.

References

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society’s MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

Andrews, G.E., 1998. The theory of partitions (No. 2). Cambridge University Press.

Andrews, G.E. and Eriksson, K., 2004. Integer partitions. Cambridge University Press.

Atallah, Mikhail J., and Marina Blanton, eds. Algorithms and theory of computation handbook, volume 2: special topics and techniques. CRC Press, 2009.

Bóna, M. ed., 2015. Handbook of enumerative combinatorics (Vol. 87). CRC Press.

Fulton, Mr William, and William Fulton. Young tableaux: with applications to representation theory and geometry. No. 35. Cambridge University Press, 1997.

Graham, Ronald L. Handbook of combinatorics. Elsevier, 1995.

Gupta H. Partitions – a survey. Journal of Res. of Nat. Bur. Standards-B Math. Sciences B. 1970 Jan 1;74:1-29.

Lovász, László, József Pelikán, and Katalin Vesztergombi. Discrete mathematics: elementary and beyond. Springer Science & Business Media, 2003.

Martin, George E. Counting: The art of enumerative combinatorics. Springer Science & Business Media, 2001.

Matousek, Jiri. Lectures on discrete geometry. Vol. 212. Springer Science & Business Media, 2013.

Menezes, Alfred J., Paul C. Van Oorschot, and Scott A. Vanstone. Handbook of applied cryptography. CRC Press, 2018.

Pak, Igor. "Partition bijections, a survey." The Ramanujan Journal 12.1 (2006): 5-75.

Rosen, Kenneth H., ed. Handbook of discrete and combinatorial mathematics. CRC Press, 2017.

Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.

Sjöstrand, Jonas. Enumerative combinatorics related to partition shapes. Diss. KTH, 2007.

Stanley, Richard P. Ordered structures and partitions. Vol. 119. American Mathematical Soc., 1972.

Stanley, Richard P. "What is enumerative combinatorics?." Enumerative combinatorics. Springer, Boston, MA, 1986. 1-63.

Stanley, Richard P. "Enumerative Combinatorics Volume 1 second edition." Cambridge studies in advanced mathematics (2011).

Stanley, Richard P., and S. Fomin. "Enumerative combinatorics. Vol. 2, volume 62 of." Cambridge Studies in Advanced Mathematics (1999).

Stanley, Richard P. Catalan numbers. Cambridge University Press, 2015.

Toth, Csaba D., Joseph O’Rourke, and Jacob E. Goodman, eds. Handbook of discrete and computational geometry. CRC Press, 2017.

In Praise of Collaboration

Take a look at an extraordinary collaboration in discrete geometry and related geometrical mathematics, the collaboration of Branko Grünbaum and Geoffrey Colin Shephard.

Joe Malkevitch
York College (CUNY)

Introduction

Point and line do many activities together—their collaborations create a rich texture for many mathematicians and geometers, as well as artists/designers/weavers, to enjoy, study and admire. But point and line are generally undefined terms in the axiom systems that are at the foundations of different types of geometry (Euclidean, projective, hyperbolic, taxicab, etc.) as a mathematical investigation. Despite this, the study of the interactions of points and lines are definitely worthy of exploration.

Pappus configuration containing 9 points and 9 lines



Figure 1 (A Pappus configuration in the Euclidean plane. There are 9 points and 9 lines with three points per line and three lines passing through each point. In the Euclidean plane the line displayed in the space between the two labeled lines MUST pass through the three points indicated.)

Finite Fano plane containing 7 points and 7 lines



Figure 2 (The finite Fano Plane, seven points and seven lines in a finite plane where every line intersects each other line in one point and cannot be drawn with straight lines with exactly 3 points per line in the Euclidean plane. This fact is related to the Sylvester-Gallai Theorem.)

Scholarly work in experimental physics is typically published with the names of a large team of scientists, often not at the same institution, who collaboratively worked together on the experimental design and the carrying out of the project involved. By comparison, mathematics is sometimes viewed as a rather solitary activity—a subject which, if one is armed with a pencil and paper, one can make major or minor original contributions to. Even before the advent of the Web and the internet, mathematics had examples, usually of pairs of people, who enriched each other’s work by a collaboration. My goal here is to make the results of one such collaboration, by Branko Grünbaum (1929-2018) and Geoffrey Shephard (1927-2016) in the area of discrete geometry more widely known. (Grünbaum and Shephard are sometimes abbreviated G&S below—shades of the great operetta collaboration of Gilbert and Sullivan!) At the same time I want to point out collaboration as a model for doing effective and important research in mathematics.

Mathematical collaborations

The list of superstar contributions to mathematics that are attached to the names of individual people date back in time within many cultures—names include:

Euclid, Archimedes, Newton, Euler, Gauss, Kovalevskaya, Noether, Lagrange, Ramanujan, …

These distinguished individuals, whose names belong to a list that stretches over long periods of time and in many countries/cultures, did not work in a vacuum. They were inspired by others and in turn inspired others to do important mathematics. Famously, Newton pointed out:

“If I have seen further it is by standing on the shoulders of giants.”

However, mathematical collaborations prior to the 20th century seem to be relatively rare. There are examples of mathematicians consulting with one another via correspondence, but this did not typically result in joint publications with the letter exchangers working together. In past eras scholars often could only communicate easily via written letters because travel between distant places (e.g. England and Germany) was costly and time consuming.

One often-cited example of a productive collaboration was between Geoffrey Hardy (1887-1947) and John Edensor Littlewood (1885-1977). Hardy is perhaps most famous for his book A Mathematician’s Apology but also made significant contributions to number theory, many of these with Littlewood.

Photo of G.H. Hardy Photo of J. E. Littlewood

Figure 3 (Photos of G.H. Hardy (left) and J. E. Littlewood (right). Courtesy of Wikipedia)

Photo of Hardy and Littlewood

Figure 4 (A photo of G. H. Hardy and J. E. Littlewood)


One of the conjectures made by Hardy and Littlewood is still unsolved to this day. The conjecture states that the number of primes in the interval $(m,m+n]$ (this is the interval not containing its left endpoint but containing its right endpoint) will be less than or equal to the number of primes in the interval $[2,n]$ (this interval includes both its left and right endpoints).

Hardy and Littlewood certainly had a successful collaboration and it seemed to survive with time. According to their contemporary Harald Bohr, they operated their collaboration using the following rules:

  • It didn’t matter whether what they wrote to each other was right or wrong.
  • There was no obligation to reply, or even to read, any letter one sent to the other.
  • They should not try to think about the same things.
  • To avoid any quarrels, all papers would be under joint name, regardless of whether one of them had contributed nothing to the work.

There is considerable discussion about whether these rules are ethical, but presumably they did guide Hardy and Littlewood.

Below, I would like to take a look at an extraordinary collaboration in discrete geometry and related geometrical mathematics, the collaboration of Branko Grünbaum and Geoffrey Colin Shephard. I will begin by giving some biographical information about these two distinguished mathematicians, then discuss their collaboration and some of its accomplishments.

Brief biography of Geoffrey Colin Shephard

Photo of Geoffrey Shephard

Figure 5 (Photo of Geoffrey Shephard. Photo courtesy of the Oberwolfach photo collection.)



Shephard was born in 1927. He studied mathematics at Cambridge and received his undergraduate degree in 1948. His doctorate degree was also from Cambridge University (Queens College), completed in 1954. His doctoral thesis adviser was John Todd. The title of his thesis was Regular Complex Polytopes. After working at the University of Birmingham he later moved to the University of East Anglia in 1967 and retired from there in 1984. He had at least two doctoral students—the geometer Peter McMullen (who works on problems about regular, primarily convex polyhedra in 3-dimensions and higher) and the specialist in convexity geometry, Roger Webster. You can get some idea of the mathematical topics that Shephard made scholarly contributions to from this list generated by MathSciNet:

  • Combinatorics
  • Convex and discrete geometry
  • Geometry
  • Group theory and generalizations
  • History and biography
  • Linear and multilinear algebra; matrix theory
  • Manifolds and cell complexes
  • Number theory

Shephard, who was an active member of the London Mathematical Society (LMS), provided money for LMS to fund what is known as the Shephard Prize. Here is its description:

"The Shephard Prize is awarded by the London Mathematical Society to a mathematician or mathematicians for making a contribution to mathematics with a strong intuitive component which can be explained to those with little or no knowledge of university mathematics, though the work itself may involve more advanced ideas."

The prize has been awarded to Keith Ball and Kenneth Falconer (both of whom are fellows of the Royal Society).

Brief biography of Branko Grünbaum

Photo of Branko Grünbaum

Figure 6 (A photo of Branko Grünbaum, courtesy of Wikipedia.)


Grünbaum was born in Osijek, in what today is known as Croatia, which at various times was part of the conglomerate country known as Yugoslavia. Though he was of Jewish background, he lived with his Catholic maternal grandmother during World War II, a period during which the Nazis occupied Yugoslavia. In high school he met his future wife, Zdenka Bienenstock, from a Jewish family, who survived the war hidden in a convent. Grünbaum began studies at the University of Zagreb but unsettled times in Yugoslavia resulted in Grünbaum and his bride-to-be emigrating to Haifa in Israel in 1949. Grünbaum found work and eventually resumed his mathematical studies at Hebrew University, earning a Master’s degree in 1954. This was also the year he married Zdenka, who trained to be a chemist. He did work for the Israeli air force in operations research while continuing his studies culminating with his doctorate in 1957. While many think of Grünbaum’s doctoral thesis adviser Areheh Dvoretsky (1916-2008) as a functional analyst, it was his budding talent as a geometer that Dvoretsky fostered. His doctoral dissertation was in Hebrew and entitled On Some Properties of Minkowski Spaces. At the completion of his military service Grünbaum came to America to do postdoctoral work at the Institute for Advanced Study with his family. By 1960 he had gone on to the University of Washington in Seattle, where the distinguished geometer Victor Klee (1925-2007) was already teaching. Eventually, after returning for a period to Israel, Grünbaum made his way back to a long career at the University of Washington where he taught until his retirement in 2001, and was part of the group of scholars there working in discrete geometry. He had 19 doctoral students and many more mathematical descendants. It was problems that he posed that I solved in my own doctoral dissertation. Grünbaum’s academic descendants include some of the most prominent discrete geometers of our time, in particular, Noga Alon and Gil Kalai. Over the years he won many prizes including the Lester R. Ford Award (1976) and the Carl B. Allendoerfer Award (2005).

The list of research publication areas of Grünbaum from MathSciNet can be compared with the one earlier for Shephard:

  • Algebraic topology
  • Combinatorics
  • Computer science
  • Convex and discrete geometry
  • Differential geometry
  • Functional analysis
  • General
  • General topology
  • Geometry
  • History and biography
  • Manifolds and cell complexes
  • Mathematical logic and foundations
  • Ordinary differential equations
  • Topology

Some of Geoffrey Shephard’s "solo" work:

Before his collaboration with Grünbaum, Shephard was particularly interested in the properties of convex sets, not merely convex polyhedra. For example he did important work related to convex polytopes and geometric inequalities. He also wrote several papers about the Steiner Point. Shephard also studied the issue of when various convex sets could be written as a Minkowski sum. The idea was to see when convex sets could not be "factored" into "simpler" sets, an approached modeled on the idea of the importance of prime numbers in number theory. A convexity problem due to Shephard that is still actively being looked at concerns centrally symmetric convex closed and bounded sets $U$ and $V$ in $n$-dimensional Euclidean space. Suppose the volumes of the projections of $U$ on a hyperplane always are smaller or equal than that of $V$. Shephard conjectured that in this case the volume of $U$ is less than or equal to that of $V$.

One particularly intriguing question has recently been associated with Geoffrey Shephard’s name. The problem involves an idea which is often linked to the name of Albrecht Dürer.

Portrait of Albrecht Dürer

Figure 7 (A self-portrait of Albrecht Dürer. Courtesy of Wikipedia.)



Dürer (1471-1528), in his work Underweysung der Messung, explored ways to represent 3-dimensional objects in paintings in a "realistic" manner. This lead to his investigating questions about perspective and in particular perspective involving 3-dimensional polyhedra. He had noticed that one way to represent a polyhedron on a flat piece of paper was to show the polygons that make up the polyhedron as a drawing in the plane with each polygon shown by a flat region which shared one or more edges with other polygons that made up the polyhedron. Dürer produced examples of such drawings for Platonic and other solids which consisted of regular polygons. Figure 8 shows an example of the kind of diagram that interested Dürer, in this case for the regular dodecahedron, a Platonic Solid with 12 congruent regular polygons as faces.

Net of a regular dodecahedron

Figure 8 (The polygons shown can be assembled into a regular dodecahedron by properly gluing the edges.)

Such drawings have come to be called nets but there is considerable variance in exactly what is meant by this term. It would be best to restrict this term to a collection of polygons that arises from a (strictly) convex bounded 3-dimensional polyhedron $P$ (sometimes called a 3-polytope) which arises from the cutting of the edges of the vertex-edge graph of the polyhedron along edges that are connected, contain no circuit and include all of the vertices of the polyhedron (i.e., a spanning tree of the polyhedron). If the initial polyhedron had $V$ vertices then the number of edges of the spanning tree whose cuts enable the unfolding of the polyhedron will be equal to $V – 1$. Since each of the edges of the cut-tree is incident to exactly 2 faces, it follows that the boundary polygon of a net will be a simple polygon with $(2V – 2)$ sides. Note that while the original polyhedron may be strictly convex, the polygonal boundary of the net while a simple polygon (when the unfolding forms a net), is typically not convex and will often have pairs of edges that lie along a straight line. (See Figure 9 for all of the nets of a regular $1\times 1\times 1$ 3-dimensional cube.)

11 nets of the 3-cube

Figure 9 (The 11 nets of the 3-dimensional cube. Courtesy of Wikipedia.)



Even for some tetrahedra (4 vertices, 4 faces and 6 edges) it is known that one can cut along 3 edges of a spanning tree and "unfold" the resulting polygons so that the result overlaps in the plane. However, it turns out that no polyhedron has ever been found where cutting edges of SOME spanning tree will not result in an assemblage of polygons without overlap. The complexity of the issues involved in such folding and unfolding problems has been explored by Eric Demaine (MIT) and Joseph O’Rourke (Smith) and others. Shephard specifically looked at the question of when such an unfolding would result in a convex polygon in the plane but in light of his work on this collection of ideas I like to refer to the following still open problem as:

Shephard’s Conjecture

Every strictly convex bounded 3-dimensional polyhedron can be unfolded to a net (non-overlapping polygons one for each face of the polyhedron) by cutting edges of the polyhedron that form a spanning tree. (Often one gets different results depending on what spanning tree one cuts.)

Intriguingly, experts lack consensus as to whether the result should be true or false. There are many polyhedra where nearly all spanning trees lead to overlapping unfoldings while there are some infinite classes of convex polyhedra where a net has been shown to exist. One source of confusion about the concept of a net is that if one starts with a polyhedron $P$ and cuts along a spanning tree to result in the net $N$, it is possible that the net can be folded by using the boundary edges of the net to a polyhedron different from the one one started with—Alexandrov’s Theorem. Thus, to recover the polyhedron one started with one has to provide gluing instructions about which edges to glue to which other edges. There are "nets" that fold (edges glued to edges) to several non-isomorphic convex polyhedra, and there are "nets" that, when glued along boundary edges one way, give rise to a convex polyhedron but a different gluing of boundary edges yields a non-convex polyhedron.

Some of Branko Grünbaum’s "solo work"

Grünbaum’s webpage, still in place after his death in 2018, includes a list of his published works from 1955 to 2003, though he published many more additional works before his death in 2018. It is intriguing to compare the first 10 and last 10 titles in this bibliography:

  1. On a theorem of Santaló.

    Pacific J. Math. 5(1955), 351 – 359.

  2. A characterization of compact metric spaces. [In Hebrew]

    Riveon Lematematika 9(1955), 70 – 71.

  3. A generalization of a problem of Sylvester. [In Hebrew]

    Riveon Lematematika 10(1956), 46 – 48.

  4. A proof of Vázsonyi’s conjecture.

    Bull. Research Council of Israel 6A(1956), 77 – 78.

  5. A simple proof of Borsuk’s conjecture in three dimensions.

    Proc. Cambridge Philos. Soc. 53(1957), 776 – 778.

  6. Two examples in the theory of polynomial functionals. [In Hebrew]

    Riveon Lematematika 11(1957), 56 – 60.

  7. Borsuk’s partition conjecture in Minkowski planes.

    Bull. Research Council of Israel 7F(1957), 25 – 30.

  8. On common transversals.

    Archiv Math. 9(1958), 465 – 469.

  9. On a theorem of Kirszbraun.

    Bull. Research Council of Israel 7F(1958), 129 – 132.

  10. On a problem of S. Mazur.

    Bull. Research Council of Israel 7F(1958), 133 – 135.

  1. A starshaped polyhedron with no net.

    Geombinatorics 11(2001), 43 – 48.

  2. Isohedra with dart-shaped faces (With G. C. Shephard)

    Discrete Math. 241(2001), 313 – 332.

  3. Convexification of polygons by flips and by flipturns.

    (With J. Zaks)

    Discrete Math. 241(2001), 333 – 342.

  4. The Grunert point of pentagons.

    Geombinatorics 11(2002), 78 – 84.

  5. Levels of orderliness: global and local symmetry.

    Symmetry 2000, Proc. of a symposium at the Wenner–Gren Centre, Stockholm. Hargitai and T. C. Laurent, eds. Portland Press, London 2002. Vol. I, pp. 51 – 61.

  6. No-net polyhedra.

    Geombinatorics 11(2002), 111 – 114.

  7. Connected (n4) configurations exist for almost all n – an update.

    Geombinatorics 12(2002), 15 – 23.

  8. "New" uniform polyhedra.

    Discrete Geometry: In Honor of W. Kuperberg’s 60th Birthday

    Monographs and Textbooks in Pure and Applied Mathematics, vol. 253.

    Marcel Dekker, New York, 2003. Pp. 331 – 350.

  9. Convex Polytopes. 2nd ed., V. Kaibel, V. Klee and G. M. Ziegler, eds. Graduate Texts in Mathematics, vol. 221. Springer, New York 2003.
  10. Families of point-touching squares. Geombinatorics 12(2003), 167 – 174.

Grünbaum had a particularly remarkable talent of seeing new geometry ideas "hiding in plain sight" where other geometers had not noticed these issues. A good example of this is extending the definition of what should be meant by a regular polyhedron which led to many interesting new regular polyhedra. Today these new regular polyhedra are known as the Grünbaum/Dress polyhedra because Andreas Dress noticed one example missing in Grünbaum’s initial enumeration.

You can find some samples of the remarkable work of Grünbaum in this earlier Feature Column article.

An amazing collaboration

In trying to determine how Shephard and Grünbaum started their collaboration, one might look to MathSciNet for their earliest joint paper, but in the case at hand this would not return information about a joint venture they were part of. Grünbaum’s highly influential book Convex Polytopes was published in 1967 and one has to look at the table of contents and preface (or the list of Related names on MathSciNet) to realize that some of the chapters were prepared by other people. One of these people was Geoffrey Shephard. In 2005 this book won the American Mathematical Society Steele Prize for Mathematical Exposition.

While their earlier research had some aspects of convexity and the properties of polyhedra in common, Grünbaum’s work in many cases had an enumerative flavor. This approach to geometry was less present in Shephard’s work. It was aspects of their common roots but non-identical styles of work that perhaps made their collaboration so fruitful. Shephard points to the fact that G&S met for the first time face-to-face in Copenhagen, Denmark in 1965 at a convexity conference. At a meeting organized by the London Mathematical Society in July of 1975 it seems G&S set in motion the idea that they work together on a 12-chapter book about geometry, with discussion of many ideas about what it might contain. They conceived the idea of starting by writing a single chapter of such a book on patterns and tilings. It turned out that 12 chapters were necessary to do justice to the these ideas. This took about 11 years to develop and swelled to about 700 pages of writing, and it was this work that became their book Tilings and Patterns. The originally planned geometry book never got to be written!

There are many aspects of tiling and pattern issues that predate the work of G&S on this topic. However, many of these results are not part of the "standard" topics included in geometry curriculum in America. While many people have noticed with pleasure the multitudinous frieze patterns that they see on buildings, fabrics, and in art, they are unaware of a surprising mathematical result related to these frieze patterns. While one realizes that there are infinitely many different artistic designs that can constitute the "content" of a frieze (ranging from letters of the alphabet, stylized flowers, etc.) there is a mathematical sense in which there are only seven types of such friezes. The 7 types of patterns are shown below (Figure 10).

Examples of 7 types of friezes

Figure 10 (Diagrams illustrating the 7 different kinds of friezes. Image courtesy of Wikipedia.)

Rather amazingly, G&S, by developing the definition of a discrete pattern, were able to breathe fresh life into this rather old topic. By using their "new" notion of a discrete pattern they were able to "refine" the sense in which there are 7 types of friezes into a finer classification under which there are 15 such "discrete frieze patterns."

In Figure 11 below, using a small asymmetric triangle as a "building block" one can see how the 7 frieze patterns above can be refined into 15 patterns as pioneered by the work of G&S. The rows of the diagram show how each of the 7 types of friezes sometimes can be refined from one "frieze type" to several discrete pattern types—the letter labels are one method of giving names to these patterns). In thinking about the way the new system refines the old one, notice that in some of these patterns there is a "motif" in a single row and in some of them they can be thought of as being in two rows. The new approach of G&S involves the interaction between the symmetries of the motif and the symmetries related to the "global" pattern arising from translating along the frieze. A few more details can be found in the discussion further along.

Refined classification of 15 frieze patterns



Figure 11 (15 types of discrete frieze patterns; diagram courtesy of Luke Rawlings.)

The diagram shown in Figure 12 deals with some of the challenges that researchers such as Grünbaum and Shephard who were interested in the classification and enumeration of "symmetric" tilings and patterns face. Interest in symmetry has complicated roots related to work in art and fabrics and also from the science side—the study of minerals and crystals and flowers.

A pattern made up of rows of friezes

Figure 12 (A symmetric part of a wallpaper that extends infinitely in both the horizontal and vertical directions. Image courtesy of Wikipedia.)

What do we see in Figure 12? We see a portion of what is meant to be a part of an infinite object, extending what is there both in the vertical and horizontal directions. We see color and perhaps we are not sure what the foreground and background are. In Figure 13, do we have a white design on a black background or the other way around?

Black and white pattern

Figure 13 (A tiling of a square using black and white regions. It is not clear if the "design" is black on white or white on black. Image courtesy of Wikipedia.)


In Figure 12 it appears that the background might be the "rouge red" but one could perhaps give other interpretations. We see things that seem to be regions where the alternating rows are "separate" bands or friezes. The design that one sees in rows 2 and 4 perhaps remind one of something one might see on a Greek temple. The flower-like pattern of rows 1, 3 and 5 seems to have rotational symmetry as well as mirror or reflection symmetry. Geometers have developed a system of classifying symmetry in the Euclidean plane using distance preserving functions (mappings) which involve translations, rotations, reflections, and glide-reflections. These distance-preserving geometry transformations are known as the isometries. But in addition to such distance-preserving transformations diagrams like the ones in Figure 13, one might have color interchange transformations. There is another interesting difference between the rows that make up this symmetric pattern. The first and second rows both have translational symmetry in the horizontal direction and thus can be viewed as patterns onto themselves as friezes (band, strip) patterns. But the first row can be viewed as having a "discrete" motif which "generates" the pattern, something not true for the 2nd row. While there was a long tradition of looking at friezes and wallpapers which had a periodic structure and classifying them, rather remarkably the idea of looking at "patterns" with a motif like the one in row 1 had never been systematically discussed before Grünbaum and Shephard. Historically rather than looking at motifs, scholars had subdivided the "infinite" design in row 2 by breaking it up into a fundamental region (often there were different choices about how to do this) which was "propagated" via transformations into the periodic frieze or wallpaper.

G&S discovered that whereas there was a long, if not always "accurate" tradition of classifying and thinking about polyhedra, both convex and non-convex polyhedra, the situation for tilings (and the even less studied idea of patterns) was much less developed. There was some work on tilings that were the analogues for tiles of the Platonic Solids (work by Pappus) and Archimedean solids (work by Kepler) but little else. There were questions about the rules that one should allow for a tile. Thus, most examples of tilings looked at regions that were touching edge to edge as the "legal" tiles, but did it make sense to allow a region like Figure 14 as a tile or as a motif for a pattern?

possible tile with two squares joined by a line segment



Figure 14 (Is this "shape" allowed as a tile in a tiling of the plane?)

When one uses tiles to fill the plane, such as the tiling by squares which meet edge to edge shown in Figure 14, one has to think about whether or not the square tile is an "open" set (does not include its boundary points) or a "closed" set (contains its boundary points). For enumerations, note that one can get infinitely many "different tilings" with squares that have tiles that don’t all meet edge to edge by sliding some finite or even an infinite number of columns in Figure 15 half the length of one of the sides of the square up or down. What G&S did was to start from scratch in their joint work to give a coherent and accurate account of the "foundations" of a theory of tiling. They also extended classic enumerations by enumerating how many different "patterns" there could be when the motif used was dots, segments or ellipses. Rather surprisingly this had not been done previously. Along the way they had to invent new words for a variety of concepts that helped organize their new theory.

Tiling of the plane with squares



Figure 15 (One of the three "regular" Euclidean tilings of the plane known from ancient times. Image courtesy of Wikipedia.

Tiling of the plane by regular 3,4, and 6-gons



Figure 16 (A tiling of the plane with regular hexagons, squares and equilateral triangles. Courtesy of Wikipedia.)

While the study of polyhedra has deep roots and multiple "reinventions" of various aspects of the theory, the seemingly neighboring idea of a tiling, while widely present in the art, fabrics and designs of various countries going back thousands of years, had a less obvious footprint in being investigated mathematically. Perhaps this is because mathematical tools to investigate infinite graphs, one way of conceptualizing about tilings, and to discuss symmetry involving something that was "infinite" (the idea of an isometry group) were developed only much later than the tools the Greeks found to study polyhedra. While in modern times symmetry is studied using the tools of graph theory, group theory and the ideas of geometric transformations, in the early study of polyhedra (and tilings) examining the pattern of the polygons surrounding a vertex was the fundamental approach. Thus, even the identity that today is often called Euler’s polyhedral formula, that for a convex bounded polyhedron the number of vertices, faces and edges of the polyhedron are related by
$$V + F – E = 2,$$
which might well have been discovered in ancient times was "discovered" in about 1750 by Leonard Euler. This formula, which involves the 0, 1, and 2- dimensional faces of a 3-dimensional polyhedron can be generalized to $n$ dimensions. G&S were able to find "rules" for fruitful definitions of tiling and pattern and this was helped by their being able to find a tiling version of the $V + F – E = 2$ result. Being able to draw on graph theory and combinatorics was a big factor in their successful leap forward beyond prior work. They also were able to draw insights from the study of things which were "asymmetric," such as fractals.

Another thread tied together by the work of G&S was where the notion of an aperiodic tiling fit in. While tilings that had translational symmetry in two different directions was the major topic that had been looked at by mathematicians and crystallographers, Roger Penrose had made the spectacular observation that there were tiles which enable one to tile the plane but these tiles did not allow a tiling that was periodic—had translational symmetry in two directions. The work of G&S clarified and laid the foundation for more discoveries related to non-periodic and aperiodic tilings. Some confusion exists about the concepts of non-periodic and aperiodic tilings. While the definitions one sees are still in flux, here is the intuitive idea. There may be a non-periodic tiling of the plane with one or more tiles, meaning that the tiling involved does not have translational symmetry but when one has a set of tiles that tile the plane aperiodically, there is no way to use the tiles to get a periodic tiling. Historically, in the attention that the mathematics community gave to infinite tilings (patterns) in the plane there was translational (shift) symmetry in two directions involved. There are tiles which are convex quadrilaterals that can tile the plane periodically (all triangles and quadrilaterals tile the plane) and also with rotational symmetry but do not tile the plane aperiodically.

Tilings and Patterns

For Geoffrey Shephard, MathSciNet informs us that his "Earliest Indexed Publication" was in 1952 and his "Total Publications" were 149 in number. For Grünbaum MathSciNet informs us that his "Earliest Indexed Publication" was in 1955 and his "Total Publications" were 271 in number. Many of these were joint publications, and in fact, individual and joint published works of G&S exceed these numbers. While MathSciNet lists research papers written by both Grünbaum and Shephard, perhaps their most famous collaboration was the book Tilings and Patterns. This book originally appeared in 1987 and was relatively recently reprinted and updated by Dover Publications. Remarkably the book contained many results not previously published in research papers which complement their joint work in scholarly journals. Tilings and Patterns literally rewrote the landscape of the theory of tilings. Grünbaum and Shephard’s innovation was to try to combine the local and global approaches to tilings in the past so that a more comprehensive look at the phenomenon of tilings and patterns was possible. While the word pattern is widely used in mathematics, its use in conjunction with the word tilings in mathematics is rather novel. Yes, patterns appear in many tilings, but by placing the emphasis on a discrete "motif" G&S opened many new doors.

The collaborative work of Branko Grünbaum and Geoffrey Shepherd has catapulted the areas of discrete geometry involving tilings and patterns to a much broader audience and resulted in many new discoveries based on their ideas. More importantly, their collaboration should be an inspiration to the mathematics community that collaboration is exciting and personally rewarding and can result in giant leaps forward for progress in mathematics and its applications.

Dedication

I would like to dedicate this column to the memory of the remarkable geometers Branko Grünbaum and Geoffrey Shephard. It was my very good fortune to have had interactions with them both!

References

Note: No attempt has been made to give a complete set of the joint papers of Grünbaum and Shephard but several particularly important and interesting examples of their collaborative efforts are listed.

  • Brinkmann, G. and P. Goetschalckx, S. Schein, Comparing the constructions of Goldberg, Fuller, Caspar, Klug and Coxeter, and a general approach to local symmetry-preserving operations. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473 (2017), 20170267.
  • Conway, J. and H. Burgiel, C. Goodman-Strauss, The Symmetry of Things, A.K. Peters, Wesley, MA., 2008.
  • Delgado, O. and D. Huson, E. Zamorzaeva, The classification of 2-isohedral tilings of the plane, Geometriae Dedicata 42 (1992) 43-117.
  • Delgado, O. and D. Huson, 4-regular vertex-transitive tilings of E3. Discrete & Computational Geometry, 24 (2000) 279-292.
  • Demaine, E. and J. O’Rourke, Geometric Folding Algorithms, Cambridge University Press, NY, 2007.
    Dress, A., A combinatorial theory of Grünbaum’s new regular polyhedra, Part I: Grünbaum’s new regular polyhedra and their automorphism group, Aequationes Mathematicae. 23 (1981) 252-65.

  • Dress, A., A combinatorial theory of Grünbaum’s new regular polyhedra, Part II: Complete enumeration, Aequationes Mathematicae 29(1985) 222-243.
  • Escher, Maurits C., and D. Schattschneider, Visions of symmetry. Thames & Hudson, 2004.
  • Friedrichs, O. Delgado and D. Huson, Tiling space by platonic solids, I. Discrete & Computational Geometry 21, (1999) 299-315.
  • Grünbaum, B., Convex Polytopes, John Wiley, New York, 1967. (Parts of this book were developed by V. Klee, M. Perles, and G. C. Shephard.)
  • Grünbaum, B., Convex Polytopes, Second Edition, Springer, New York, 2003. (This includes work from the first edition by V. Klee, M. Perles, and G. Shephard and addition input for V. Kaibel, V. Klee and G. Ziegler.)
  • Grünbaum, B. Arrangements and Spreads, American Mathematical Society, for Conference Board of the Mathematical Sciences, Providence, 1972.
  • Grünbaum, B., The angle-side reciprocity of quadrangles. Geombinatorics, 4 (1995) 115-118.
  • Grünbaum, B., Configurations of Points and Lines, American Mathematical Society, Providence, 2009.
  • Grünbaum, B.,Side-angle reciprocity – a survey. Geombinatorics, 2 (2011) 55-62.
  • Grünbaum, B. and G.C. Shephard, The eight-one types of isohedral tilings in the plane, Math. Proc. Cambridge Phil. Soc. 82(1977) 177-196.
  • Grünbaum, B. and G.C. Shephard, Tilings and patterns, Freeman, 1987. (A second updated edition appeared in 2016, published by Dover Press, NY. Errors from the first edition were corrected and notes were added to indicate progress in understanding tilings and patterns.) There also exists a shorter version of the original published by Freeman in 1989, with only the first seven chapters of the original version.)
  • Grünbaum, B. and G.C. Shephard, Interlace patterns in Islamic and Moorish art, Leonardo 25 (1992) 331-339.
  • Huson, D., The generation and classification of tile-k-transitive tilings of the euclidean plane, the sphere and the hyperbolic plane, Geometriae Dedicata 47 (1993) 269-296.
  • McMullen and G.C. Shephard, Convex Polytopes and the Upper Bound Conjecture, London Math. Society, Cambridge U. Press, Cambridge, 1971.
  • O’Rourke, J. How to Fold It, Cambridge University Press, NY 2011.
  • Rawlings, L., Grünbaum and Shephard’s classification of Escher-like patterns with applications to abstract algebra, Doctoral thesis, Mathematics Education, Teachers College, 2016.
  • Roelofs, H. The Discovery of a New Series of Uniform Polyhedra, Doctoral dissertation, 2020.
  • Schattschneider, D., The plane symmetry groups: their recognition and notation. American Mathematical Monthly 85 (1978) 439-450.
  • Schattschneider, D., The mathematical side of MC Escher, Notices of the AMS 57 (2010) 706-718.
  • Shephard, G.C., Convex polytopes with convex, nets, Math. Proc. Camb. Phil. Soc., 78 (1975) 389-403.
  • Shephard, G.C., My work with Branko Grünbaum , Geombinatorics, 9(1999) 42-48. (Note the whole Volume 9, Number 2, October 1999 issue of Geombinatorics is a special issue in honor of the 70th birthday of Branko Grünbaum.)
  • Stevens, P., Handbook of regular patterns: An introduction to symmetry in two dimensions, MIT Press, Cambridge, 1981.
  • Washburn D. and D.W.Crowe, Symmetries of culture: Theory and practice of plane pattern analysis. University of Washington Press, 1988. (Reprinted 2021 by Dover Publications.)
  • Washburn D, and D.W. Crowe, editors, Symmetry comes of age: the role of pattern in culture, University of Washington Press, 2004.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society’s MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

Pseudonyms in Mathematics

Why would there be pseudonyms for the publication of research papers in mathematics? One possible motive might be… that a group of people collaborated on a piece of work and wanted to simplify the multiple authorship to a single name. Another reason appears to be playfulness or whimsy.

Joseph Malkevitch
York College (CUNY)

Introduction

Are you familiar with the novels of Currer Bell or Ellis Bell? Many people who have enjoyed reading Jane Eyre (1847) and Wuthering Heights (1848) are unaware that the authors of these books at the time they were published were known as Currer Bell and Ellis Bell.

In the 19th century there were several examples of ultimately famous women writing under a male pseudonym. Among the most notable were George Eliot as the name for Mary Ann Evans and George Sands as the name for Amantine Lucile Aurore Dupin. (Eliot attended courses on mathematics and physics in London and Geneva and incorporated mathematical themes in her novels.)

Portrait of George Eliot

Figure 1 (George Eliot, aka Mary Ann Evans, as painted by Alexandre-Louis-François d'Albert-Durade. Image courtesy of Wikipedia.)
 

Few who have not studied English literature will recognize the names of Currer Bell, Ellis Bell and Acton Bell as the names under which Charlotte (1816-1855), Emily (1818-1848) and Anne (1820-1849) Brontë published their work in their own times! Another interesting example, this time of a man writing under a pseudonym in the 19th century, was Lewis Carroll, whose true name was C.L. Dodgson.

Lewis Carroll

Figure 2 (C.L. Dodgson, otherwise known as Lewis Carroll, courtesy of Wikipedia.)
 

Dodgson was a distinguished mathematician but not as distinguished as he was to become by being an author! Few people know Dodgson for his mathematics but many have read the book or seen the movie version of Alice in Wonderland! In recent times, Dodgson's mathematical fame has been revived in association with his appealing method of using ranked ballots to decide elections.

While not a pseudonym, the family name that James Joseph Sylvester (1814-1897) was born into was "Joseph," not Sylvester. The Sylvester family practiced Judaism and Sylvester's older brother decided to change the family name from Joseph to Sylvester to avoid some of the anti-semitism that plagued British Jews at the time.

James Sylvester

Figure 3 (James Joseph Sylvester, courtesy of Wikipedia)
 

Sylvester was a student at Cambridge but when it came time to graduate and to get his Master's degree regulations would have required him to sign the "Articles," pledging allegiance to the Church of England, something he refused to do. It was his good fortune that Trinity College in Dublin was willing to grant him his degree based on his work at Cambridge because they were more open minded about religion! Ireland was a country dominated by Catholicism at the time while Britain had an established church because Henry VIII had broken with Catholicism and set in motion years of religious turmoil by bringing a Protestant reform movement to England. However, a big part of his motive was that the Vatican would not allow him to divorce his first wife, Catherine of Aragon, who was Catholic so that he could marry Anne Boleyn, who gave birth to the woman who would become Queen Elizabeth I!

Women who wanted to pursue mathematics, or more generally an education, had limited opportunities in the 19th century. It was not until 1869 that Girton College at Cambridge admitted women and, thus, offered a path for women who wanted to pursue mathematics to study the subject in a university setting. Winifred Edgerton Merrill became the first American woman to earn a PhD in mathematics, which she earned in 1886 from Columbia University. But rather amazingly, the granting of degrees to women by Cambridge was not allowed until 1948. The situation for women and Jews had similarities. Despite his growing reputation as a mathematician, Sylvester was not able to get an appointment at Oxford because of his religion. His famous stays in America were attempts to have his talents recognized by academic institutions but for complex reasons, some of which seem to have been related to his personality, he was unable to get a stable long term position in the United States. Ironically, he returned from America to Britain because he was offered the Savilian Professorship in Geometry at Oxford University, because the rules forbidding Jews to have that position had changed. (For more about Sylvester's career and the careers of prominent women mathematicians such as Emmy Noether and Sofya Kovalevskaya, the first woman to earn a doctorate in mathematics, see the April 2015 Feature Column on Mathematical Careers.)

Sofya Kovalevskaya

Figure 4 (Sofya Kovalevskaya, courtesy of Wikipedia.)
 

Why would there be pseudonyms for the publication of research papers in mathematics? One possible motive might be that a research paper might seem to a community used to a particular person's "impressive" work, to be less impressive and one might want to protect one's reputation by publishing under a pseudonym. Another reason might be that a group of people collaborated on a piece of work and wanted to simplify the multiple authorship to a single name. Another reason appears to be playfulness or whimsy. While there are many pseudonyms that were used for groups of mathematicians, the best known is Bourbaki. Bourbaki represented a group of mathematicians, initially primarily operating out of France, but having members eventually from many countries, to put mathematics on a "sound" foundation rather than look at its separate pieces as the total edifice. Bourbaki stood for the idea of showing with "hindsight" how to structure the vast river of mathematical knowledge in a way that built organically from a well structured foundation. I will not attempt to look at the members of Bourbaki here or its many accomplishments. Many of the members of Bourbaki had distinguished careers as individuals. I will not take on the history and mathematical accomplishments of Bourbaki, not because they are vast, though they are, but in favor of pseudonyms for groups who work in mathematical areas that have good track records with looking at mathematics that can be understood with a relatively limited mathematics background. My goal here is to mention two relatively recent groups of mathematicians who published under an anonymous name. I will say some things about why they might have done this and call attention to some of the research work that as individuals these people accomplished.

So I will look at in turn look at the work of Blanche Descartes and G.W. Peck. Blanche started "her" work earlier that "G.W.," so I will start with her.

Blanche Descartes

What associations do you have with the name Blanche Descartes? Perhaps Blanche Descartes was Rene Descartes's (1596-1650) wife or daughter? In fact Descartes never married but he did have a daughter Francine who died at the age of 5. But seemingly the name Blanche Descartes has no direct connection with Descartes, the great French mathematician and philosopher. Blanche Descartes was a pseudonym initially for joint work by Rowland Brooks, Cedric Smith, Arthur Stone and William Tutte. The four of them met as undergraduate students at Cambridge University in 1936 and were members of the Trinity Mathematical Society. The photo below shows them attending a meeting of the Trinity Mathematical Society, which as you notice, has no female members. Female students were not allowed to study at Trinity College until much later, the first women arriving in 1976!

Trinity Mathematical Society

Figure 5 (The Trinity Mathematical Society, photo courtesy of Wikipedia.)
 

Trinity College at Cambridge, where Isaac Newton had been an undergraduate and later a Fellow, was especially associated with mathematics. The four decided to use the name Blanche Descartes to publish some initial joint work they did. It has been argued that "Blanche" derives from letters involved in their names. Using first letters of Bill (William), Leonard (Brooks middle name), Arthur and Cedric, one gets BLAC and with some "padding" this becomes: BLAnChe. Perhaps Descartes involves a play on the phrase 'carte blanche' and since they all were studying mathematics for different reasons, perhaps a reference to Rene Descartes, who also dabbled in things other than mathematics.

One early question that the four looked at has to do with a problem which has come to be known as "squaring the square." The problem involves taking a square and decomposing (tiling) it into smaller squares of different side lengths. One can also consider the more general question of when a rectangle can be tiled with squares of different lengths. Figure 6 shows an example, discovered by A. Duijvestijn.

A squared square

Figure 6 (A square decomposed into squares of all different sizes. This one has the smallest number of possible squares in any such decomposition. Image courtesy of Wikipedia.)
 

This tantalizing question attracted much interest over the years and has been shown to have unexpected connections to mathematical ideas that seem to have no connection with tilings. Some interest in this problem occurred in the "recreational" mathematics community. It is not exactly clear why Brooks, Smith, Stone and Tutte chose to use a pseudonym but perhaps it might have had to do with their concern that this question was of less mathematical "importance" than topics their teachers at Cambridge considered worth students investing time in investigating. Mathematics is full of examples that were considered recreational at one time but have been shown to be rooted in deeper mathematical ideas. The squared-square problem is an example of such a problem.

For each of the members of Blanche Descartes I will indicate some information about them and try to provide an example of some mathematics associated with them. All of them were to achieve some measure of fame and acclaim under their "real" names, sometimes in limited venues but in Tutte's case on a big stage.

William Tutte (1917-2002)

William Tutte

Figure 7 (Photo of William Tutte. Courtesy of Wikipedia.)
 

Although Tutte was born in England, his academic career was spent largely in Canada at the University of Waterloo. This university has a complex footprint of the presence of mathematics:

  • Department of Applied Mathematics.
  • Department of Combinatorics and Optimization.
  • David R. Cheriton School of Computer Science.
  • Department of Pure Mathematics.
  • Department of Statistics and Actuarial Science.

When Tutte first went to Canada, he did so at the invitation of H.S.M. Coxeter to join the faculty at the University of Toronto. Not long after the University of Waterloo was founded, Tutte moved there and was associated with the Department of Combinatorics and Optimization which at the present time has about 30 members. The reason why his work in England before taking up residency at Waterloo is less well known is that he was part of the team that was assembled in England at Bletchley Park. Even after the war the people who worked at Bletchley Park were not allowed to speak of their work there until quite recently. This team included Alan Turing, who is justly famous for his work on breaking the Enigma machine cipher. However, even after the Enigma ciphers were being read, a code known as Fish, used by the German army and for messages sent by leaders in Berlin to field commanders, had not been broken. Tutte was one of a team that managed to read Fish even though, unlike the case for Enigma, there was no physical machine in the possession of the code breakers to help them with breaking the code. In essence Tutte managed to figure out how the machine used to send messages in Fish worked by reconstructing the exact operation of the machine even without having seen the machine! When this was accomplished, it became possible to decipher Fish messages for the remainder of the war without the Germans realizing that their codes were being read. This work was done before Tutte completed his doctorate.

When WWII ended, Tutte returned as a graduate student to Cambridge in 1945 to work on his doctorate. During this period he produced an example related to the famous four-color theorem which is known today as the Tutte graph in his honor. In this context, a graph is a collection of points (called vertices) and edges, which can be curved or straight, that join up vertices. There are various definitions of graphs but the one preferred by Tutte allows vertices to be joined to themselves (these edges are called loops) and allows pairs of distinct vertices to be joined by more than one edge. We see in Figure 8 on the right the Tutte graph, put together using three copies of the configuration on the left, known as a Tutte triangle. This graph has three edges at every vertex, that is, it is 3-valent or degree 3, is planar (can be drawn in the plane so that edges meet only at vertices) and is three-connected. When a graph has been drawn in the plane so that edges meet only at vertices, the graph is called a plane graph. 3-connected means that for any two vertices $u$ and $v$ in the graph one can find at least 3 paths from $u$ to $v$ that have only the vertices $u$ and $v$ in common. What is special about the Tutte graph is that there is no simple tour of its vertices that visits each vertex once and only once in a simple circuit, a tour usually known as a Hamilton circuit. If it were true that every 3-valent 3-connected graph in the plane had a hamilton circuit there would be a simple proof of the four-color theorem (every graph drawn in the plane can be face colored with 4 or fewer colors). (The coloring rule is that any two faces that share an edge would have to get different colors.)

A Tutte triangle The non-hamiltonian Tutte graph

Figure 8 (A Tutte triangle on the left and three Tutte triangles assembled to form a plane, 3-valent, 3-connected graph with no Hamilton circuit. Images courtesy of Wikipedia.)
 

While the Tutte graph is not the smallest planar, degree 3, 3-connected graph which has no simple closed curve tour of all of its vertices (such a tour is called a Hamilton circuit or HC), it is relatively easy to see why it can't have an HC. This fact follows from that one can show that if an HC visits the vertices of a Tutte triangle then the HC must enter using one of the two edges shown at the bottom and exit the Tutte triangle using the edge at the top. For those interested in applications of mathematics, the problem known as the Traveling Salesperson Problem (TSP) requires finding a minimum cost Hamilton circuit in a graph which has non-zero weights on its edges. Finding routes for school buses, group taxis, or when you run errands involves problems of this kind. Finding solutions to the TSP for large graphs seems to require rapidly growing amounts of computation as the number of sites to be visited (the vertices of the graph) grows.

In addition to his famous example of a graph not having a Hamilton circuit Tutte also showed a very appealing theorem about when a graph must have a Hamilton circuit.:

Theorem (W. T. Tutte).
Every 4-connected plane graph has a hamiltonian circuit.

The 4-connected condition means that given any pair of vertices $u$ and $v$ in the graph there must be at least 4 paths from $u$ to $v$ that have only $u$ and $v$ in common. In particular, this means that the graph must have at least 4 edges at each vertex. Figures show a very regular 4-connected plane graph the graph of the Platonic Solid known as the icosahedron and a much more irregular graph. Can you find a Hamilton circuit in each of these graphs? While there are algorithms (procedures) for finding an HC in a plane 4-connected graph that run relatively fast, the problem of finding an HC in an arbitrary graph is known to be computationally hard.

Graph of the icosahedron

Figure 9 (A 4-connected planar graph. This is the graph of the regular icosahedron. Image courtesy of Wikipedia.)
 

A plane 4-connected graph

Figure 10 (A planar 4-connected graph which is not very symmetric.)
 

Cedric A. B. Smith (1917-2002)

While Smith studied mathematics at Cambridge and published some research work in mathematics, his career path did not involve becoming an academic mathematician associated with a mathematics department. Rather he pursued a career as a statistician and worked at the Galton Laboratory of University College, University of London. Some of Smith's work was related to genomics, helping to locate where particular genes were on a chromosome.

Like Tutte, Smith made an easy-to-state contribution to the theory of Hamilton circuits. Clearly, having conditions that show a family of graphs must have an HC or providing examples of graphs where no HC exists is also intriguing. But it is also natural to ask if there might be families of graphs where graphs might have exactly one HC. Smith was able to provide an answer to this question for the important class of graphs where every vertex has exactly three edges at a vertex.

Theorem.
Every 3-valent cubic graph has a even number of circuits that pass through each vertex once and only once (Hamiltonian circuit).

Because this graph has one Hamilton circuit tour…

A cubic graph with an HC highlighted

Figure 11 (The dark edges show a Hamilton circuit is a 3-valent (cubic) graph.)
 

…by Smith's Theorem it must have another!

Rowland Leonard Brooks (1916-1993)

Rowland Brooks is most well known for a theorem about coloring graphs that is named for him. Let me begin with an application and show how the theorem of Brooks makes it possible to get insight into such situations.

Suppose we have a collection of committees, say, committees of students and faculty at a college. The collection of individuals who are on some committee will be denoted by S. The committee names are a, b, …, h and a table (Figure 12) indicates with an X when a pair of committees has one or more members of S on both committees. It would be nice to be able to schedule the 8 committees into as few hourly time slots as possible so that no two committees that have a common member meet at the same time. Committees with no common members could meet at the same time. A person can't be at the meeting of two committees the person serves on if those committees meet at the same time.

A table of committee conflicts data

Figure 12 (A table where when two committees have one or more people on both committees these committees should not meet at the same time. A conflict is indicated with an X.)
 

We can display the conflict information geometrically using a graph by having a dot for each committee and joining two vertices representing committees with an edge if these committees can't meet at the same time because they have members in common.

A graph coding the previous committee conflict data

Figure 13 (A conflict graph for 8 committees. Committees joined by an edge should have their meetings at different times. The graph can be vertex colored with 4 colors.)
 

The vertex coloring problem for graphs assigns a label to each vertex, called a color, with the requirement that two vertices jointed by an edge get different colors. We could assign a different color to each dot (vertex) in Figure 13, which would mean that we would use 8 time slots for the committee meetings. The minimum number of colors needed to color the vertices of a graph is called the chromatic number of a graph. Brooks was able to find a way to get what is often a good estimate for the chromatic number of a graph.

Brook's Theorem:
If G is a graph which is not a complete graph or a circuit of odd length, then the chromatic number of G is at most (less than or equal to) the degree (valence) equal to the largest degree (valence) that occurs in G.

For a general graph it is a difficult computational problem to determine the chromatic number, but Brook's Theorem often allows one to get a good estimate quickly. In particular, if a graph has a million vertices, no matter how complex the graph, if it has maximum valence 5, it will not require more than 5 colors (though the chromatic number may be less).

Can you find a coloring of the vertices in the graph in Figure 13 that improves over the estimate given by Brook's Theorem?

Arthur Stone (1916-2000)

Arthur Stone eventually made his way to the United States and taught for many years at the University of Rochester. His wife Dorothy (Dorothy Maharam) was also a mathematician and his son David (deceased 2014) and daughter Ellen also became mathematicians.

While Stone contributed to mathematics in a variety of theoretical ways perhaps he is best known for his invention of what are known as flexagons. The hexaflexagon shown in Figure 14 can be folded from the triangles shown in Figure 15.

A hexaflexagon

Figure 14 (An example of a hexaflexagon, image courtesy of Wikipedia.)
 

A template of triangles which fild to a hexaflexagon

Figure 15 (A template for a hexaflexagon, image courtesy of Wikipedia.)
 

While the members of Blanche Descartes published several articles, most of these publications were in fact the work of William Tutte. A more recent example of a group of mathematicians who published together under one name will now be treated.

G.W. Peck

G. W. Peck's publications can be found here. Unlike Blanche Descartes, whose members are now all deceased, of the 6 mathematicians who have sometimes written under the pseudonym of G.W. Peck, three of the six people involved are still alive (2020). What associations do you have with this name? Perhaps you might think of the distinguished actor Gregory Peck, but Eldred Gregory Peck (April 5, 1916 – June 12, 2003), the actor, did not write under the name G.W. Peck. The individuals involved in G.W. Peck's publications were Ronald Graham, Douglas West, George Purdy, Paul Erdős, Fan Chung, and Daniel Kleitman.

Let me make a few brief comments about each of the members of this remarkable collaboration of distinguished mathematicians in turn. As individuals they illustrate the remarkably varied ways that individuals have mathematical careers.

Ron (Ronald) Graham (1935-2020)

Ronald Graham

Figure 16 (A photo of Ronald Graham, courtesy of Wikipedia.)
 

Some people perhaps know Ron Graham best for his juggling and studying mathematical problems associated with juggling. However, before his recent death he was one of America's best known research mathematicians. Some of Graham's fame beyond the mathematics community itself was that Martin Gardner, a prolific popularizer of mathematics, often wrote about ideas which were called to his attention by Ron Graham. But somewhat unusually for mathematicians known for their theoretical work, Ron Graham also had a career as a distinguished applied mathematician. He had a long career as a mathematician at Bell Laboratories where he worked at times under the direction of Henry Pollak, who in addition to his work at Bell Laboratories also was a President of NCTM and MAA. Graham during his career was President of the American Mathematical Society and MAA. He also was head of the Mathematics Section (the position no longer exists) of the New York Academy of Sciences. During his long stay at Bell Laboratories he championed examples of discrete mathematical modeling. This included popularizing the use of graphs and digraphs to solve problems involved in scheduling machines in an efficient manner. He also called attention to the way that problems about packing bins with weights had connections to machine scheduling problems.

Graham published on a vast array of topics ranging from very technical to expository articles. His many contributions to mathematics can be sampled here.

Douglas West (1953- )

Douglas West

Figure 17 (A photo of Douglas West, courtesy of Wikipedia.)
 

In addition to his many research papers, West has published several comprehensive books in the areas of discrete mathematics and combinatorics. He is also noteworthy in maintaining and collecting lists of unsolved problems in the general area of discrete mathematics. In recent years he has helped edited the Problems Section of the American Mathematical Monthly.

George Purdy (1944-2017)

Purdy made many contributions to discrete geometry. He was particularly interested in questions related to arrangements of lines and the Sylvester-Gallai Theorem.

Paul Erdős (1913-1996)

The best known author of this group was Paul Erdős (1913-1996) whose career was marked by not having a specific educational or industrial job. For much of his life Erdős traveled between one location and another to work privately with individuals, and/or give public lectures where he often promoted easy-to-state but typically hard-to-solve problems in geometry, combinatorics and number theory.

Paul Erdos

Figure 18 (A photo of Paul Erdős, courtesy of Wikipedia.)
 

Here is a sample problem in discrete geometry that Paul Erdős called attention to, whose investigation over the years has sprouted many new techniques and ideas. It has also resulted in new questions as some aspect of the initial problem got treated. Suppose that $P$ is a finite set of $n$ distinct points in the plane with the distance between the points being computed using Euclidean distance. One must be careful to specify what distance is to be used because, for example, one could instead compute the result using another distance function, say, taxicab distance. Suppose $D(n)$ denotes the set of numbers one gets for distances that occurs between pairs of points in $P$. Paul Erdős raises questions such as:

  1. What is the largest possible number of elements in $D(n)$?
  2. What is the smallest possible number of elements in $D(n)$?
  3. Can all of the numbers in $D(n)$ be integers?
  4. Can all of the integers in $D(n)$ be perfect squares?

Such problems have come to be known as distinct distance questions. Question (a) is quite easy. However, the question (b) is not fully understood even today. Initially Erdős was concerned with the behavior of the smallest number of values that could occur in D(n) as n got larger and larger. As tools for getting insights into problems has grown as well as interesting examples with particular properties, many new questions have come to be asked. For example. if the points of the original set lie in equal numbers on two disjoint circles what is the smallest number of distinct distances that can occur?

Here is a problem in this spirit to contemplate. In each of Figures 19 and 20 we have a configuration of 20 points, together with some of the line segments that join up these points, when we think of the diagrams as graphs. Figure 19 shows a polyiamond, a configuration of equilateral triangles that meet edge to edge while Figure 20 shows a polyomino, congruent squares which meet edge to edge.

A polyiamond with 20 vertices

Figure 19 (A polyiamond with 20 vertices.)
 

A polyomino with 20 vertices

Figure 20 (A polyomino with 20 vertices)
 

Question: Investigate the number of distinct distances and integer distances that can occur in each of the configurations in Figures 19 and 20. Can you formulate interesting questions to ask about distances based on these two configurations and your thinking about them?

Fan Chung (1949- )

Paul Erdös, Ronald Graham and Fan Chung

Figure 21 (A photo of Ron Graham, Paul Erdős and Fan Chung, photo courtesy of Wikipedia.)
 

Fan Chung is an extremely distinguished mathematician. She was born in Taiwan but did her graduate studies in America, and Herbert Wilf was her doctoral thesis advisor. She was the wife of Ronald Graham, with whom she wrote many joint papers. Like her husband, she worked in both the industrial world and in academia. She worked at Bell Laboratories and at Bellcore after the breakup of the Bell System. Her research covers an unusually broad range of topics, but includes especially important work in number theory, discrete mathematics, and combinatorics. Fan Chung and Ron Graham both made important contributions to Ramsey Theory. Fan Chung still teaches at the University of California, San Diego.

Daniel Kleitman (1934- )

Daniel Kleitman

Figure 22 (A photo of Daniel Kleitman, courtesy of Wikipedia.)
 

The person who perhaps has most often published under the G.W. Peck moniker has been Daniel Kleitman, whose long career has been associated with MIT. Many of his publications are in the area of combinatorics and discrete mathematics, in particular results about partially ordered sets.

Concluding Thoughts

To the extent that there are individuals who can't study or publish mathematics because of discrimination, hopefully we can all work to tear down these barriers. Mathematical progress requires all the help it can get and to deny people the fulfillment that many who get pleasure from doing mathematics have is most unfortunate. While in the past pseudonyms were sometimes chosen to avoid prejudicial treatment, we can hope this will seem less and less necessary in the future.

References

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

  • Appel, K., and W. Haken, J. Koch, Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21 (1977) 429-490.
  • Appel, K. and Haken, W. 1977 Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.
  • Ball, Derek Gordon. Mathematics in George Eliot's Novels. PhD thesis, University of Leicester, 2016.
  • Brooks, R., and C. Smith, A. Stone, W. Tutte, The Dissection of Rectangles into Squares, Duke Mathematical Journal, 7 (1940) 312-40.
  • Chiba, N. and T. Nishizeki, "The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs." Journal of Algorithms 10.2 (1989): 187-211.
  • Chung, Fan RK, Lectures on spectral graph theory, CBMS Lectures, Fresno, 92 (1996): 17-21.
  • Chung, Fan, and R. Graham, Sparse quasi-random graphs, Combinatorica 22 (2002): 217-244.
  • Descartes, Blanche, Network colorings, Math. Gaz. 32 (1948) 67-69.
  • Erdős, .P, and A. H. Stone. On the structure of linear graphs, Bull. Amer. Math. Soc 52.(1946) 1087-1091.
  • Erdős, Paul, and George Purdy. "Some extremal problems in geometry." Discrete Math. 1974.
  • Graham, R., The Combinatorial Mathematics of Scheduling, Scientific American 238 (1978), 124-132.
  • Graham, R., Combinatorial Scheduling Theory, in Mathematics Today: Twelve Informal Essays, ed. L. Steen, Springer-Verlag, N.Y. (1978), 183-211.
  • Henle, M. and B. Hopkins, eds. Martin Gardner in the twenty-first century. Vol. 75. American Mathematical Soc., Providence, 2012.
  • Kleitman, D.. On an extremal property of antichains in partial orders. The LYM property and some of its implications and applications, Combinatorics, 2 (1974) 77-90.
  • Kleitman, Daniel J., and Douglas B. West. "Spanning trees with many leaves." SIAM Journal on Discrete Mathematics 4.1 (1991): 99-106.
  • Purdy, George. "Two results about points, lines and planes." Discrete mathematics 60 (1986): 215-218.
  • Robertson, N. and D. Sanders, P. Seymour, R. Thomas, New Proof of the Four Colour Theorem. Electronic Research Announcement, Amer. Math. Soc. 2, (1996) 17-25.
  • Solymosi, J, and C.. Tóth, Distinct distances in the plane, Discrete & Computational Geometry 25 (2001): 629-634.
  • Smith, C. and S Abbott, The story of Blanche Descartes. Mathematical Gazette (2003) 23-33.
  • Stone, A. H., Paracompactness and product spaces, Bulletin of the American Mathematical Society 54 (1948): 977-982.
  • Szekely, Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997): 353-358.
  • Tutte, W. T., Squaring the Square, Mathematical Games column, ed. M. Gardner, Scientific American, Nov. 1958.
  • West, D., Introduction to Graph Theory. Vol. 2. Upper Saddle River, NJ: Prentice hall, 1996.
AMS Feature Column banner

Remembering Richard Kenneth Guy: Games and Taking on Mountains

This essay is dedicated to the memory of Richard K. Guy (1916-2020) whose life story and accomplishments display a variety of aspects of the complicated landscape of finding fulfilling work on the part of individuals, the concern of society with nourishing those who can produce and use mathematics, and the community of people who have devoted their lives to encourage the flourishing of mathematics.. …

Joseph Malkevitch
York College (CUNY

Introduction

What background is required to do research in mathematics? Who produces new mathematical results and why do such individuals do mathematical research? While mathematics has become a profession and there are individuals who, when asked what they do for a living, respond that they are mathematicians, in the grand scheme of human history of mathematics, its being a profession is of quite recent origin. This essay is dedicated to the memory of Richard K. Guy (1916-2020), whose life story and accomplishments display a variety of aspects of the complicated landscape of finding fulfilling work on the part of individuals, the concern of society with nourishing those who can produce and use mathematics, and the community of people who have devoted their lives to encourage the flourishing of mathematics.

Certainly there are many people who today would say they are “mathematicians” rather than that they teach mathematics, are professors of mathematics or work in industry or government as mathematicians. This group is also notable for having typically earned a doctorate degree in mathematics. Note, however, that many of the individuals who are thought of as great mathematicians of the 19th century and early 20th century who were British or Irish (e.g. Arthur Cayley, James Joseph Sylvester, Augustus de Morgan, William Rowan Hamilton) did not earn doctorate degrees. This was because of the uneven history of where doctorate degrees were awarded. Whereas doctorate degrees were awarded in France, Italy, and Germany as early as the 17th century and even in the United States in late 19th century, well into the 20th century it was common for British mathematicians not to get doctorate degrees. Galileo (1564-1642), though known as a physicist by the public, taught mathematics. And there were early universities in Paris and Bologna where mathematics was part of the curriculum and scholars of mathematics were trained.

However, one can also pursue a “career” involving mathematics if one studies mathematics education, physics, chemistry, economics, biology, computer science, statistics, and a multitude of other “academic” preparations for being employed and one builds on one’s mathematical skills or abilities. I will return to this issue later after taking a look at Richard Guy’s career, noteworthy for the variety of experiences he had in pursuit of his interest and love of mathematics but whose only doctorate was an honorary doctorate. Another thread I will touch on is the view that when mathematics leaps forward it is through the work of relatively young practitioners, and Richard Guy lived and actively worked into old age. He died at 103! Guy was an inspiration for those who love mathematics and are nervous that contributing to mathematics is done only by the relatively young.

Richard Guy–a brief biography

Richard Kenneth Guy was born in England in the town of Nuneaton, which is in the part of the country known as Warwickshire.

Photo of Richard K. Guy

Figure 1 (Photo of Richard Guy by Thane Plambeck, from Palo Alto, CA, courtesy of Wikipedia.)

Eventually he made his way to Cambridge University, whose structure is that one studies at one of various “competing” colleges. In the area of mathematics perhaps the best known of the Cambridge Colleges is Trinity College, partly because this was the college associated with Isaac Newton (1642-1727) but also because such other famous mathematicians as Isaac Barrow (1630-1677), Arthur Cayley (1821-1895), G.H. Hardy (1837-1947), Srinivasa Ramanujan (1887-1920), Bertrand Russell (1892-1970), William Tutte (1917-2002), and William Timothy Gowers. However, Guy went to Caius College, though the “official” name of the college is Gonville and Caius College. For a young country like America it is hard to realize that Gonville and Caius was founded in 1348 (well before Christopher Columbus voyaged to the New World). Some other mathematicians or mathematical physicists who were students at Caius and whose name you might recognize were:

George Green (1793-1841), John Venn (1834-1903), Ronald Fisher (1890-1962), Stephen Hawking (1942-2018)

Photo of Gonville-Caius College at Cambridge

Figure 2 (Photo of Gonville-Caius College at Cambridge, courtesy of Wikipedia.)

John Conway (1937-2020), who died recently was another person well known to the mathematics community who attended Caius College. Conway’s and Richard Guy’s careers crossed many times! Perhaps Guy’s most influential writing was his joint book with Conway and Elwyn Berlekamp, Winning Ways.

Photo of John Conway

Figure 3 (Photo of John Horton Conway.)

Guy served during World War II in the Royal Air Force where he did work related to forecasting the weather–a critical part of the British war effort.

Subsequently, at various times Guy worked as a teacher or took courses at various places. Guy married Nancy Louise Thirian in 1940. She died in 2010. Richard and Louise had three children. His son Michael Guy also did important work in mathematics. Guy relocated from Britain to Singapore in 1950 and taught mathematics at the University of Malaya, where he worked for 10 years. After leaving Singapore he spent time at the new Indian Institute of Technology in Delhi. In 1965, he “settled down” by moving to Canada where he taught in the mathematics department of the University of Calgary. Although he eventually “retired” from the University of Calgary he continued to show up at his office regularly until not long before he died. In Calgary he supervised several doctoral students. The following information is drawn from the Mathematics Genealogy Project

Roger Eggleton, University of Calgary, 1973 Nowakowski, Richard, University of Calgary, 1978 Dan Calistrate, University of Calgary, 1998 Jia Shen, University of Calgary, 2008

In turn Eggleton had at least 8 doctoral students and Nowakowski had at least 10.

While at Calgary, Guy helped organize various mathematics conferences, some of which took place at a location in the mountains not far from Calgary.

 

Photo of Banff Center for the Arts and Creativity

Figure 4 (Photo of the Banff Center for the Arts and Creativity, in Banff, Alberta [Canada], site for some conferences organized by Richard Guy. Photo courtesy of Wikipedia.)

Richard Guy and Louise both enjoyed the exercise and challenge of hiking. Well after many people give up heading out on the trail, he and Louise continued to hike. Guy also continued to hike after his wife died. A point of pride for Guy was that a Canadian Alpine Hut was named for him and Louise. The hut is not open year-round, but in a policy that would have pleased Guy and his wife, “to avoid pressuring the bear habitat, the Guy Hut will be closed between May 1 and November 30 annually.”

Richard Guy eventually got a doctorate degree but it was an honorary degree awarded by the University of Calgary in 1991, relatively late in his long and very productive career as an active mathematician. Much of Guy’s career was in academia but the qualifications for a career in academia vary considerably from one country to another and from one era to another. While most people who are famous for their contributions to mathematics in recent years have earned doctorate degrees, there are some famous examples, including Richard Guy, who found different routes to becoming distinguished contributors to mathematics. Guy, having been born in 1916, presents a relatively common case because of the history of granting the doctorate degree in Great Britain. Let me say something about this situation.

For those attempting to understand the history of mathematics, the development of particular branches of mathematics–geometry, combinatorics, non-associative algebras, partial differential equations, Markov chains, entire functions (a topic in the theory of functions of a complex variable), Banach spaces, etc. a wonderfully useful tool is the previously noted Mathematics Genealogy Project. On this website, searches for British mathematicians yield mathematical ancestors but often the names of the people shown as an ancestor were not a doctoral thesis supervisor but a person who “tutored” or was a primary influence for someone who went on to obtain a reputation in mathematical research but who did not have a doctorate degree. Another historical source of information about individual mathematicians (though not Guy, yet) and various aspects of mathematics is the MacTutor History of Mathematics Archive. Also see this fascinating history of the doctorate in Britain.

Richard Guy’s collaborators

MathsciNet lists a large number of people whom Guy collaborated with as an author. He edited quite a few books as well. As mentioned earlier, his best-known book, Winning Ways, was a joint project with John Horton Conway and Elwyn Berlekamp.

Photo of Elwyn Berlekamp

Figure 5 (Photo of Elwyn Berlekamp, courtesy of Wikipedia.)

 

Photo of John Horton Conway

Figure 6 (Photo of John Conway)

But during his long life, Guy had many collaborators. Some of these were “traditional” academics who taught at colleges and universities but two of his collaborators stand out for having benefited mathematics somewhat differently: Paul Erdős (1913-1996) and Martin Gardner (1914-2010).

Paul Erdős was a mathematical prodigy, born in Hungary. He not only showed talent for mathematics as a youngster, but also skill at developing new mathematical ideas and proving new results while quite young. (Musical prodigies show a split, too: those who at an early age can wow one with how well they play the violin or piano but also prodigies like Mozart and Mendelssohn who at amazingly young ages compose new and beautiful music.) Some prodigies continue to wow with their accomplishments as they age but some die young–Mozart died at 35, Schubert at 31, and Mendelssohn at 38. One can only be sad about the wonderful music they would have created had they lived longer, but we can be thankful for all of the wonderful music they did create.

Paul Erdős did not die young but his career did not follow a usual path. Rather than have a career at one academic institution, he became noted for becoming a traveling ambassador for innovative mathematical questions and ideas, particularly in the areas of number theory, combinatorics, and discrete geometry (including graph theory questions). Erdős’s creativity and brilliance created interest in how closely connected mathematicians were to Erdős via chains of joint publications (books and jointly edited projects do not count). This leads to the concept of Erdős number. Erdős has Erdős number 0. Those who wrote a paper with Erdős have Erdős number 1 and those who wrote a paper with someone who wrote a paper with Erdős have Erdős number 2. Richard Guy’s Erdős number was one, and some might argue that since he wrote 4 papers with Erdős that his Erdős number is 1/4. If you have written a joint paper with a mathematician and are curious to know what your Erdős number is you can find out by using a free “service” of the American Mathematical Society: Find your Erdős number!

Photo of Paul Erdos, Ron Graham and Fan Chung

Figure 7 (Photo of Paul Erdős, Ron Graham (recently deceased) Erdős number 1, and Fan Chung, Ron Graham’s wife–who also has Erdős number 1, courtesy of Wikipedia)

One can compute an Erdős number for people who lived in the distant past. Thus, Carl Gauss has an Erdős number of 4. (Enter names at the link above in the form Euler, Leonard. For this particular name, though, no path can be found!)

Martin Gardner (1914-2010) stands out as perhaps the most unusual promoter of mathematics for the general public, the science community, and research mathematicians in history. Not only did Gardner never earn a doctorate degree in mathematics, he did not earn any degree in mathematics. He did earn a degree in philosophy from the University of Chicago in 1936. Eventually he became involved with writing a mathematical recreations column for Scientific American magazine, and over a period of time these columns were published, anthologized, and augmented to create a constant stream of books that were well-received by the general public. Given the title of the column that Gardner wrote for Scientific American, Mathematical Games, it is not surprising that he drew on the work of Berlekamp, Conway, and Guy. These individuals made suggestions to Gardner for columns to write, and he in turn, when he had ideas for a column/article, often drew on their expertise to “flesh out” his ideas. Over the years, an army of Scientific American readers (including me) were stimulated by Gardner’s columns and books to make contributions to problems that Gardner wrote about or to pursue careers related to mathematics. Readers of Gardner’s books and columns also branched out and learned about mathematical topics that they had not seen in mathematics they had learned in school.

Photo of Martin Gardner

Figure 8 (Photo of Martin Gardner, courtesy of Wikipedia.)

Grundy’s game

It may be helpful to give an example of a combinatorial game that is easy to describe and which is perhaps new to some readers. One of my favorite combinatorial games is known as Grundy’s game, named for Patrick Michael Grundy (1917-1959). Like many combinatorial games it is played using a pile of identical coins, beans, or in Figure 9 line segments. The game is an example of an impartial game, which contrasts with partisan games where each player has his/her own pieces, as in chess or checkers.

Position for Grundy's game

Figure 9 (An initial configuration for Grundy’s game.)

Position for Grundy's game

Figure 10 (One can get to this position in Grundy’s game from the position in Figure 9 by a legal move.)

Grundy’s game works as follows. The game starts with a single pile of stones (here shown as short line segments in a column). The players alternate in making moves. A move consists of taking an existing pile of segments and dividing it into two piles of unequal size. Thus, for the pile in Figure 9, the player making a move from this position could move to a position where there would be one pile of 6 segments and the other of 2 segments. This would be a legal move. A player having to make a move from the position in Figure 10 can NOT make a move based on the pile with two segments, because the only way to divide this pile would create two equal sized piles, which is not allowed. However, there are several moves from this position. Divide the the first pile into piles of size 5 and 1 or of size 4 and 2. The game terminates when a player can’t make a move. John Conway promoted this rule of “normal” play in combinatorial games, namely, “if you can’t move, you lose.” If the termination rule is “if you can’t move, you win,” usually called misère play, then an analysis of optimal play is much harder, for reasons that are clear.

Rather remarkably, whatever the rules of a two-person impartial game, it turns out that the game is equivalent to playing the game of Nim (see below) with a single pile. Charles Bouton in 1902 found a way for any game of Nim, with one or many piles, to determine from the size of these piles whether the player making the next move would win or lose. In the language of combinatorial game theory, any position with legal moves that remain can be classified as being in an N position or a P position. An N position is one in which the next player to play can win with proper perfect play, while a P position is one where the previous player. having had this position, could win with proper perfect play.

Note, however, for a given game, knowing if a position is an N or a P position does not tell a player how to play optimally–that is, what moves to make to guarantee a win no matter what responses the opponent may make, or, if a position is hopeless, what moves to make to force the opponent to make as many moves as possible to win, and perhaps force a mistake to turn a losing position into a win. For a particular “board” of a combinatorial game that has moves that can be made, it can be thought of as either an N position or a P position.

Nim is played starting from a position with one or more piles of identical objects. A move consists of selecting a single pile and removing any number of objects from the pile, including removing all of the objects from the pile. Thus, treating the segments of Figure 9 as a Nim position, one could remove, 1, 2, 3, 4, 5, 6, 7, or 8 segments from the single pile. This position in Figure 9 is an N position. The player who moves from this position can win by removing all 8 segments. For Figure 10 can you see, with more thought, why this is also an N position. Bouton’s solution to checking a Nim position to see its status as an N position or P position involves representing the number of items in each pile as a binary number–binary number notation represents any positive integer using only the symbols 0 and 1. Summarizing what Bouton showed:

a. From a P position, every “move” leads to an N position

b. From an N position, there is some move that leads to a P position

c. P positions have a “value” of 0; N positions have a value that is positive.

The theory that showed all combinatorial two-person impartial games can be shown to have a single Nim value is due independently to the German-born mathematician Roland Percival Sprague (1894-1967) and English mathematician Patrick Michael Grundy (1917-1959). Remarkably, Richard Guy, also independently showed the same result.

Let us come back to Grundy’s game. In light of the discussion above, every initial position of n (positive integer) segments (coins, beans) has a Nim value, that is, a single number that represents the “value” of that position. Suppose one looks at the sequence of Nim values for Grundy’s game starting from a pile of n objects where each computation can take a fair amount of work. Starting with n = 0 this sequence looks like:

0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, …..

Remember that the meaning of a zero is that if it is currently your move, you have lost the game, because you have no move with optimal play by your opponent that will allow you a victory. If the value in the sequence is not zero this means that you have a position that allows you to make a move which will result in a win on the next move or allows you to move to a position from which your opponent cannot win!

What can one say about this sequence? The pattern seems rather irregular and even if you saw a much larger swath of this sequence it would not seem there was a pattern. However, Richard Guy conjectured that this sequence will eventually become “periodic.” This means that after neglecting some long initial piece of the sequence at some point a block of numbers, perhaps large in size, will repeat over and over!

Perhaps the work Guy is best known for is the joint work with Berlekamp and Conway on combinatorial games, which resulted in a book through which all three of these men are known to the public–Winning Ways. Taking off from the many new and old games described in this book there have been hundreds of research papers loosely belonging to combinatorial game theory but reaching into every branch of mathematics. While much of Winning Ways is devoted to discrete mathematics (which includes both finite set ideas as well as those involving discrete infinities), the book also treats topics that lead into complex areas related to “infinitely small” and “infinitely large” numbers.

Eventually John Conway wrote about the remarkable ways that studying combinatorial games of various kinds leads to ideas of numbers that go beyond the integers, rational numbers and real numbers that are the most widely studied discrete infinite and “dense” number systems, for which given any two numbers there is some other number of the system between them. This work of Conway is described in the book Surreal Numbers by Donald Knuth which is aimed at a general audience, and in Conway’s more technical book On Numbers and Games. Guy’s work helped popularize many of Conway’s more technical contributions.

There are two major ways mathematics has contributed to understanding “games.” One strand of game theory concerns conflict situations that arise in various attempts to understand issues related to economics–different companies or countries take actions to get good outcomes for themselves in situations that involve other “players.” The other is combinatorial games like Nim, Grundy’s game, and checkers and chess.

Richard Guy’s mathematics

Richard Guy’s influence as a mathematician comes from a blend of the influence he had through broadcasting the ideas and accomplishments of his collaborators and his role in calling attention to problems which could be understood and attacked with more limited tools than the most abstract parts of mathematics. He did not invent dramatic new tools to attack old problems, or chart out new concepts that would create new fields in mathematics or new avenues for mathematical investigation. He did not get awarded any of the growing number of prizes for dramatic accomplishments in an old field of mathematics (e.g. the work that earned James Maynard the Cole Prize in Number Theory in 2020) or for “lifetime” achievement such as the Abel Prize awarded to Karen Uhlenbeck in 2019–the first woman to win the Abel Prize.

To get an idea of Guy’s work, it helps to look at a sample of the titles of the articles he authored and co-authored. As you can see, they reflect the cheerful and playful aspects of his personality that he showed in his personal interactions with people.

  • All straight lines are parallel
  • The nesting and roosting habits of the laddered parenthesis
  • What drives an aliquot sequence?
  • John Isbell’s game of beanstalk and John Conway’s game of beans-don’t-talk
  • Primes at a glance
  • The second strong law of small numbers
  • Graphs and the strong law of small numbers
  • Nu-configurations in tiling the square
  • The primary pretenders
  • Catwalks, sandsteps and Pascal pyramids
  • The number-pad game
  • Don’t try to solve these problems!
  • Some monoapparitic fourth order linear divisibility sequences
  • Richard Rick’s tricky six puzzle: S5 sits specially in S6
  • A dozen difficult Diophantine dilemmas
  • New pathways in serial isogons

His most important books were:

  • Berlekamp, E. and J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, Two volumes, Academic Press (1982)
  • Berlekamp, E. and J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, Four volumes, AK Peters (2004)
  • Guy, Richard. Unsolved problems in number theory, Springer Science & Business Media, 2004 (with 2546 citations on Google Scholar as of July, 2020)
  • Croft, Hallard T. and Kenneth Falconer, Richard K. Guy,  Unsolved problems in geometry,  Springer Science & Business Media, 2012

These problem books have been reissued at times to update progress on old problems and give new problems. They have resulted in gigantic progress on a wide array of number theory and geometry problems.

Different countries over the years have had varying “success stories” in reaching a general public about the delights of mathematics. In America one of those success stories was Martin Gardner’s contributions mentioned above. In the Soviet Union a different intriguing phenomenon emerged. In America, the typical way one reached students in schools was to provide the students with materials that were not written by especially distinguished research mathematicians but rather by materials that “translated” what researchers had done and or thought about down to the level of the students. But in the Soviet Union MIR Publishers developed a series of books by very distinguished mathematicians and aimed directly for students. These books, originally published in Russian, were eventually made available to an English-speaking audience by a variety of publishers by translating books of these Soviet authors into English. There was the Little Mathematics Library which was marketed through MIR, there was Popular Lectures in Mathematics which were distributed by the University of Chicago, (under an NSF project lead by Izaak Wirszup), there was Topics in Mathematics published by Heath Publishing and another version published via Blaisdell Publishing (which was a division of Random House). Some of the Soviet books appeared in several of these series. While not up-to-date about some of the topics that were treated, to this day these books are remarkable examples of exposition. They are books I keep coming back to and which always reward me by another look. Perhaps my personal favorite is Equivalent and Equideomposable Figures, by Y. G. Boltyanskii. This book is an exposition of the amazing theorem now often called the Bolyai-Gerwien-Wallace Theorem. In brief this theorem says that if one has two plane simple polygons of the same area, one can cut up the first polygon with straight line cuts into a finite number of pieces which can be reassembled to form the second polygon, in the style of a jigsaw puzzle. Figure 11 shows a way to cut a square into four pieces and reassemble the parts into an equilateral triangle of the area of the original square!! Lots of current work is to find the minimal number of pieces needed to carry out dissections between two interesting polygon shapes of the same area.

Diagram illustrating the Bolyai-Gerwien-Wallace Theorem

Figure 11 (A square cut into 4 pieces which have been reassembled to form an equilateral triangle of the same area. Image courtesy of Wikipedia.)

In the mid-1980s, the Consortium for Mathematics and Its Applications (COMAP) approached the National Science Foundation about creating a similar series of books as those pioneered in the Soviet Union. Figure 12 shows the cover of one such book developed and written by Richard Guy, aimed at pre-college students and devoted to combinatorial games. Guy’s book Fair Game was published in 1989. His manuscript was submitted as a handwritten text which had to be retyped prior to publishing!

Cover of Richard Guy's book Fair Game

Figure 12 (Cover of the book Fair Game, by Richard Guy. Image courtesy of the Consortium for Mathematics and its Applications.)

Richard Guy sometimes referred to himself as an “amateur” mathematician.

While he wrote many papers and books, his legacy is not the theorems that he personally proved but his role as someone who loved mathematics and who was a mathematics enthusiast–writing about, teaching about, and doing mathematics. His wonderful promotion of mathematics will live on long after those who knew him personally are gone.

References

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society’s MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

Some books which Richard Guy authored, co-authored or edited:

Guy, R., The Book of Numbers (joint with John Horton Conway), Springer-Verlag, 1996.

Guy, R., Fair Game, Consortium for Mathematics and Its Applications, 1989.

Guy, R.. and R. Woodrow, The Lighter Side of Mathematics, Proc. E. Strens Memorial Conf. on Recr. Math. and its History, Calgary. 1986.

Guy, Richard. Unsolved problems in number theory. Vol. 1. Springer Science & Business Media, 2004.

other references:

Albers, D. and G. Alexanderson (eds.), Fascinating Mathematical People, Princeton U. Press, 2011. (Includes Richard Guy.)

Albert, M. and R. Nowakowski, (eds), Games of No Chance 3, Cambridge U. Press, NY, 2009.

Conway, J., On Numbers and Games, 2nd. edition, AK Peters, Natick, 2001.

Croft, H. and Kenneth Falconer, Richard K. Guy. Unsolved problems in geometry: unsolved problems in intuitive mathematics. Vol. 2. Springer Science & Business Media, 2012.

Erdős, Paul, and Richard K. Guy, Crossing number problems, The American Mathematical Monthly 80 (1973): 52-58.

Guy, R.K. and Smith, C.A., The G-values of various games. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 52, No. 3, pp. 514-526). Cambridge University Press, 1956.

Guy, R. K., & Nowakowski, R. J. (1995). Coin-weighing problems. The American mathematical monthly, 102(2), 164-167.

Nowakowski, R. (ed.), Games of No Chance, Cambridge U. Press, 1996.

Nowakowski, R. (ed)., More Games of No Chance, Cambridge U. Press, 2002.

AMS Feature Column banner

Points, Lines, and Incidences

To honor Mathematics and Statistics Awareness Month, I will treat some remarkable developments concerning a basic intuitive idea in geometry concerning points and lines. …

Joseph Malkevitch
York College (CUNY

Introduction

When people think about mathematics they think of numbers and shapes. Numbers covers the interest of mathematics in arithmetic and algebra. And shape relates to mathematics' concern with geometry. However, in many ways a better way to capture the essence of mathematics is to say that it is concerned with understanding patterns of all kinds, whether they be numerical or geometrical patterns or patterns in more general senses.

To honor Mathematics and Statistics Awareness Month, I will treat some remarkable developments concerning a basic intuitive idea in geometry concerning points and lines. For our discussion I will be concerned with points, lines and segments (portions of lines between two points) that are drawn in the Euclidean plane in contrast to points and lines on another surface such as a sphere or ellipsoid or in the hyperbolic (many parallel lines) or projective planes (no parallel lines). Many of these ideas have ancient roots in many cultures, but often mathematics reinvents itself by trying to understand ideas that at first glance might seem to have been resolved in the distant past.

Configurations of points and lines

Consider the diagram in Figure 1 that shows two triangles being viewed by an eye. While this diagram has infinitely many points on the lines, we will only be interested in the points accentuated with dots. In this diagram there are many segments but some of these lie along the same line. In drawings of this kind we can show only a part of a line. Note that the corresponding vertices of the triangles determine three lines: AA', BB' and CC' that meet at the point called Eye. Note also that we will consider EyeA', EyeA and AA' as three different segments even though EyeA' is made up of two smaller (shorter) segments.

Partial Desargues configuration

Figure 1 (The vertices of two triangles viewed from the point named Eye.)
 

If you count the number of points in Figure 1, there are 7 and the number of lines is 9. Three of the lines have three points on them and the other 6 lines have two points on them. Note that while the segment EyeC and the segment AB meet at a point, we will not be concerned with that point or the one where segment A'B' meets segment CC'. We need to decide how to report the information we see. The segment EyeA' consists of the segments EyeA and AA' which make up the longer segment but the points Eye, A and A' all are points on one line.

The set of labeled points shown in Figure 1 accounts for some two-point lines and some of the points lie on 3-point lines, but note that the diagram does not show all of the lines that the points in the set of points (7 points) might determine. If 7 points were in "general position" they would determine 21 (= (7*6)/2 ) different lines. You are probably aware that any two distinct points in the Euclidean plane determine a unique line. However, if one starts, for example, with 4 points on a line, then any pair of these points determines the same line.

Figure 1 is the starting point for a famous theorem that I will return to in a moment, but to set the stage for what is to come let us also look at the points and lines in Figure 2. This diagram calls attention to 7 points also, but with only 3 lines. One line has 2 points, another 3 points and the third line has 4 points. Five points are shown with only a single line passing through those points and two points have two lines which pass through them. However, perhaps you are wondering if the two "vertical" lines actually intersect (meet) somewhere in the distance. Many people would say the diagram suggests that the lines are parallel, that is, that they do not have a point in common.

Diagram illustrating incidence concept; 7 points, 3 lines
Figure 2 (A collection of 7 points and three lines.)
 

Though in many ways the result I am about to discuss belongs more naturally to projective geometry (where there are no parallel lines, all pairs of distinct lines meet in exactly one point) than Euclidean geometry, it is a theorem as stated for the Euclidean plane.

There is much more that can be said about the diagram that we started with in Figure 1. Figure 3 shows another diagram that helps illustrate the mathematical result involved. The point labeled "Eye" in Figure 1 corresponds to the point labeled O in Figure 2. Furthermore the two triangles in Figure 1 did not overlap but they do in Figure 2. What happens (Figure 3) when we look at the lines determined by the corresponding vertices of the two triangles, the lines determined by AA', by BB' and by CC'? Of course it might be possible that some pair of these three lines would be parallel and would not meet. However, let us assume that in fact every pair of these lines do intersect, and they intersect in the points P, Q and R. (P and Q are shown in Figure 2 but not R.) Can anything be said about this triple of points? Ordinarily if one picks three points at "random," one would not expect them to lie on a line but one would expect them to be the vertices of a triangle. However, the remarkable fact here is that when the two initial triangles have the property that the lines connecting their corresponding vertices meet at a point, the corresponding edges of the triangles (when no pair is parallel) meet at points which lie on a single line!!

Full Desargues configuration

 

Figure 3 (A Desargues configuration but not showing the point where AB and A'B' intersect at R, which would be on the line with P and Q.)
 

This theorem was not noticed by the great Greek geometers but was discovered by Girard Desargues (1591-1661). It is an example of a situation in mathematics where something that one would not expect to happen, as if by magic, does happen. This ability of mathematics to make surprising connections in unexpected situations is part of what attracts so many people to the subject. For those not sure that Figure 3 might just be an accident, you can take a look at another copy of a Desargues configuration (Figure 4) highlighting the two triangles in color and–indicated in red–the point that they are in "perspective" (where the blue lines intersect), and the line that they are in "perspective" from.

Coler coded Desargues configuration
  Figure 4 (Another completed Desargues configuration showing 10 points and lines. Courtesy of Wikipedia.)

 

Here is one formal statement of Desargues's Theorem:

If the corresponding vertices of two distinct triangles in the Euclidean plane ABC and abc pass through a single point O then the corresponding sides of these triangles intersect at points which lie on a single line.

Sometimes this theorem is stated that if two triangles are "in perspective" from a point they are "in perspective" from a line.

Theorems like Desargues's Theorem have come to be known as configuration theorems; there are other theorems of this kind that predate Desargues.

In addition to the "configuration" consisting of points and lines that is represented by the 10 points and 10 lines implicit in Figure 4, there is another amazing configuration theorem which is due to the great mathematician Pappus of Alexandria (lived approximately 290-350).

Pappus configuration

Figure 5 (A diagram illustrating Pappus's Theorem.)
 

Pappus's Theorem can be stated that given six points, A, B, C on one line and a, b, c on another line which intersect (none of the points being where the two lines intersect) (as shown in Figure 5) then the three points where Ab intersects aB, Ac intersects aC and Bc intersects bC are collinear (lie on a single line)!

Whereas Desargues's Theorem can be thought of as 10 points and 10 lines with 3 points on a line and 3 lines passing through a point, the Pappus configuration can be thought of as having 9 points and 9 lines where three points lie on each of the specified lines and triples of lines pass through the specified points.

Pappus's Theorem can be considered as a special case of another remarkable configuration theorem that was discovered by Blaise Pascal (1623-1662), the French philosopher, author and mathematician.

Portrait of Blaise Pascal

Figure 6 (Portrait of Blaise Pascal.)
 

Pappus's Theorem involves 6 points which lie on two lines and the way these points determine lines that create points which lie on a line as well. But since two lines are both equations of degree 1 (equations of the form $ax + by + c = 0$ where $a, b,$ and $c$ are real numbers, with both of $a$ and $b$ not zero), if we multiply these two equations together we get an equation which is of degree two in the variables $x$ and $y$. This would be a quadratic equation in two variables. The "shapes" you are probably most familiar with that satisfy such equations are the conic sections: circles, ellipses, parabolas, and hyperbolas. But two intersecting straight lines or two parallel straight lines can be thought of as "degenerate" conic sections. (A conic section gets its name because it can be thought of as what results from cutting a cone with a plane.) What Pascal realized was that one could generalize Pappus's Theorem to planar conics.

Pascal's Theorem:

Given 6 points which form a hexagon whose vertices lie on a conic section, then the three pairs of opposite sides of this hexagon meet at points which lie on a straight line.

Pascal's Theorem diagram

Figure 7 (A diagram illustrating Pascal's Theorem, involving 6 points inscribed in a conic section, here taken to be an ellipse. Diagram courtesy of Wikipedia.)
 

The rise of interest in configuration theorems such as those of Pappus, Desargues, and Pascal were related to attempts to put an understanding of geometry in a richer context. Attempts to show that Euclid's 5th Postulate, in a modern formulation:

If p is a point not on line l then there is a unique parallel to line l though point P

could be deduced from the other axioms (starting assumptions) were not successful. We know today why they weren't: there are mathematically (logically consistent) geometries where Euclid's 5th postulate fails to hold. Furthermore, people were investigating point/line questions on the sphere, a curved surface rather than a flat one, but where there were "natural" suggestions for what might be "lines" and points on such a surface. In the end, spherical geometry evolved into two different approaches. In the more interesting approach a point was considered to be a pair of points which were at opposite ends of a diameter. It may seem strange to think of two things being identified so that they are considered one, but this point of view is very fruitful because now "two points" determine a unique line, a great circle of the sphere, which is a circle centered at the center of the sphere.

Many people who know some geometry are puzzled by the difference between longitude lines and latitude lines. Longitude lines are great circles which cut through the idealized sphere that represents the Earth at the south and north poles. The circle that is "halfway" between the poles, lying in a plane perpendicular to the line joining the poles, is a great circle too, and it is the equator of the system. But all the other latitude lines that are "parallel" to the equator (in the sense that they don't meet the equator) are not great circles. They are circles which represent the intersection of a plane parallel to the equator, with the sphere.

Incidences

Suppose we are given a "configuration" C of points and lines in the Euclidean plane; we have a finite set P containing $m$ points in the Euclidean plane and a finite set L of $n$ lines which contain some of the points of P. It is possible that the lines of L intersect at points not in P (see Figure 8) and it is possible that L does not contain all of the lines determined by pairs of points in P (Figure 2). One might be interested in counting how many point-line pairs there are in the configuration C. A point-line pair, a point $p$ of set S which is on line $l$ of L is called an incidence. We are not concerned with lengths of segments or with angles between the lines.

The point-line configuration in Figure 8 has 7 straight lines (so set L has 7 elements) and 5 points (so set P has 5 elements). Note that the lines are displayed to suggest they are infinite. The section between two points will be referred to as a segment and when we have in mind the "whole" line that a segment lies in we will call that a line. Some pairs of the points shown do not lie on any line of L. One might consider adding lines between points not already joined, and adding to our configurations points that are obtained from the intersection of such a line with an existing line (assuming that it meets an existing line in a point that is not already in S). However, in what follows we are only concerned with the points and lines in the set of points P given to us and the set of lines L given to us. For Figure 8, of the 5 points (dark dots), one has 2 lines going through it, three points have 3 lines going through them, and one point has 4 lines going through it. For the lines, 6 lines have two points on them and one line has 3 points on it.

Configuration of points and lines, 15 incidences

Figure 8 (An irregular configuration of points and lines starting with a point set P with 5 elements and a line set L with 7 elements.)
 

For practice you may want by direct count to verify that this configuration has 15 point-line incidences and 10 different segments. (The line with three points has 3 segments in all.) You can count the number of points, lines, segments, number of lines with s points and number of points through which t lines pass and incidences you see in Figure 8. You should find 15 incidences, and notice you can count these by concentrating on each line in turn and finding how many points there are on each of the lines or by concentrating on the point and seeing how many lines pass through each of the points! Given the diagram shown in Figure 2 where we have 5 points in the set P and 3 lines in the set L, we can count 9 incidences in this diagram.

Shortly we will discuss a remarkable theorem about counting incidences–the Szemerédi-Trotter Theorem ). But to fully appreciate the circle of ideas involved in this result I will discuss some ideas that seem initially not related to incidences. When most people hear the word graph they think of the graph of a function. When Descartes extended the "synthetic" geometry of Euclid to the analytical geometry of today, it became possible to graph algebraic expressions. Historically this helped with the rapid and fruitful development of the Calculus.

However, there is another more recent use of the word graph. It belongs to the domain of discrete mathematics rather than the domain of continuous mathematics and involves the geometric structures consisting of dots and lines or dots and curves. Graphs of this kind consist of a number of points called vertices (singular vertex) and lines/curves which join up pairs of vertices which are called edges. Figure 9 shows a sample of some graphs.

Three graphs of diffent kinds

Figure 9 (A sample of three different graphs, each with one connected piece.)
 

Each of these three graphs consists of a single piece, and such a graph is called connected–intuitively there is a way of taking any pair of vertices in the graph and getting between them by moving along the edges of the graph. In principle we might have many different lines/curves which connect up a pair of vertices, and we might have vertices that are joined to themselves by a curve (or broken line) but these structures, sometimes called multi-graphs, pseudographs, or graphs with loops and multiple edges will not be considered here. Some graphs have the property that they have been drawn in the plane so that edges meet only at vertices. Such graphs are called plane graphs, and graphs which have the potential to be drawn in the plane so that edges meet only at vertices are known as planar graphs. Figure 10 shows an example of a planar graph on the left and a structurally equivalent graph, an isomorphic graph, on the right; the single crossing has been eliminated.

Planar graph and a plane drawing of this graph

 

Figure 10 (A graph (left) drawn in the plane showing one crossing. This graph is planar because it can be redrawn as shown on the right to get the plane graph with the one crossing eliminated.)
 

While graph theory is a relatively recent subarea of geometry, a relatively recent subarea of graph theory, with mathematical and computer science implications, has been the subject of graph drawing. This domain of ideas concerns questions about the nature of the appearance of different ways a graph might be drawn in the plane.

When a graph is drawn in the plane there may be many different drawings to represent isomorphic copies of the same graph. In particular one might ask for a drawing with the minimum number of crossings for that graph. This number is called the crossing number of the graph. In fact, the crossing number in itself has interesting variants because there can be a difference in the number of crossings when all of the edges are drawn with straight lines versus the number of crossings when the edges are allowed to be curves.

The Szemerédi-Trotter Theorem

A remarkable accomplishment in understanding the behavior of counting the number of incidences for a collection of points and lines was achieved by what has come to be called the Szemerédi-Trotter Theorem. This result is named after William Tom Trotter and Endre Szemerédi.

Photo of Endre Szemerédi Photo of W. T. Trotter

Figure 11 (Photos of Endre Szemerédi and William (Tom) Trotter. Courtesy of Wikipedia and Tom Trotter respectively.)
 

We will first set the stage for the remarkable result of Szemerédi and Trotter, which was proved in 1983.

Szemerédi-Trotter Theorem:

Suppose that we have a collection (set) of points P with m distinct points and a collection of distinct lines L with n lines in the Euclidean plane. As we saw above we will call an incidence a point-line pair (p,l) where p belongs to P and l belongs to L and point p lies on line l. Such pairs are called incidences. What is the maximum number of possible incidences, calculated in terms of the values of m and n? If we denote by I(P,L) the number of incidences for the particular given sets P and L, then we will denote by I(m,n) the largest value of I(P,L) as for any choice of P with m elements and any choice of L with n elements. Notice that in the statement of the theorem below, m and n appear in a symmetrical way. This suggests that perhaps one can get insights into points and lines when we try interchanging their roles. Such a "duality" of points and lines holds fully in projective geometry, where any pair of lines always intersects.

Theorem (Szemerédi-Trotter, 1983): 

$$I(m, n) = O\left(m^{2/3}n^{2/3} + m + n\right)$$

Informally, this theorem gives the order of magnitude that is possible for the largest number of incidences that can occur for a collection of points P with $m$ points and a collection of lines L with $n$ lines.

It is possible to show that this result is "best possible" but for the fact that the exact constant that holds for the expression above is not yet known (see below).

Before looking in more detail about the content of this result here are a few remarks about "big O" notation used in the description of the Szemerédi-Trotter theorem. The notation has a story of its own. It was originated by the German mathematician Edmund Landau (1877-1938) who is most famous as a number theorist.

Photo of Edmund Landau

Figure 12 (Photo of Edmund Landau)
 

In recent times big O notation is often discussed in the context of trying to determine how long it will take to run (how many steps are required) a computer algorithm in terms of some parameter of the size of the problem, typically denoted with the letter $n$. However, Landau was interested in the more general issue of comparing the growth of different functions expressed using the variable, say $n$. While sometimes in the popular press it is stated that some phenomenon is showing exponential growth, to some extent what is meant is that the phenomenon in the short run is growing faster than other functions that people may have studied in a mathematics class, like $n^2$.

The "formal" definition of "$g(x)$ is $O(f(x))$" is that $g$ obeys this property: if $x$ is larger than some fixed integer N, there is a constant C such that:

$$g(x) \leq C(f(x)) \textrm{ for } x \geq N $$

This definition says nothing about how large C or N might be. For some results of this type C and N can be huge and, thus, the result is sometimes not of "practical" computational interest.

The use of big O notation created interest in other ways to notate growth of functions or number of steps in running an algorithm. While notation may not seem an important part of the practice of mathematics, it is part of the craft by which new mathematical ideas are born and new theorems are developed. So you might want to look at the meaning of small o and big omega as notations for grown of functions.

Now that we know the meaning of big O notation we can see that the Szemerédi-Trotter Theorem says that for large enough values of $m$ and $n$, the maximum number of incidences is less than some constant times:

$$m^{2/3}n^{2/3} + m + n.$$

There is another way that the Szemerédi-Trotter Theorem can be stated that gives equivalent information but has a seemingly different flavor. Suppose we are given $m$ points in the plane and a positive integer $i \geq 2$, then the number of lines which contain at least $i$ of these points is given by:

$$O(m^2/i^3 + m/i).$$

In retrospect, it is common that the first proofs of important results are not always as insightful and as "clear" as later proofs. The original approach that Szemerédi and Trotter used to prove their result is not usually discussed because proofs that came after theirs were noticeably simpler. There are two simpler approaches to the proof that are now widely reported as approaches to this theorem. One approach exploited the use of configurations that involved a grid of points, an approach associated with the work of György Elekes(1949-2008), who died sadly at a relatively young age, as well as work due to Laszlo Szekely, which is hinted at below that involves the notion of crossing number.

One tool that has increasingly emerged as useful in discrete geometry in putting to work geometrical insights is graph theory. As we saw, graph theory concerns diagrams such as that in Figure 11.

Kuratowski graphs, contained in any non-planar graph

 

Figure 13 (Two graphs, which require some crossings when drawn in the plane, sometimes called the Kuratowski graphs, that serve as "obstacles" to drawing a graph in the plane. Any graph which can't be drawn in the plane without having edges that cross at points other than vertices must in a certain sense be a "copy" of one of these two graphs (or both) within it.)

 

Photo of K. Kuratowski

Figure 14 Kazimierz Kuratowski (1896-1980)
 

Both of the graphs shown in Figure 13 can be regarded as a collection of points in the Euclidean plane. Note that we could have joined some of the vertices with curves to avoid the crossings that occur in the diagram but we can also interpret this diagram as a "geometric graph" where we have lines which include the points where the lines cross at what are not vertices of the original graph. One approach to connecting graph theory to questions about point and line incidences is forming a graph from the diagram representing a point set P and a line set L by constructing a graph which consists of the vertices that correspond to the points in P and joining two vertices $u$ and $v$ of this graph by edge if there is a line segment in the point/line diagram between $u$ and $v$. This leads to a graph that may be isomorphic to a plane graph, one that can be drawn in the plane without any edges meeting or crossing at points other than vertices, or may be a non-planar graph, but will typically have edges meeting at points which are called crossings–points that are not vertices of the graph involved.

Given a graph, there are many properties about the graph which one can inquire about. Thus, one can ask if a graph is planar, has a simple circuit tour that visits each vertex once and only once in a simple circuit (useful in designing a package delivery routes), has a tour of its edges that visits each edge once and only once (useful in designing snowplowing routes), etc. A natural question to ask is for the different ways to draw a graph in the plane with straight line edges (e.g. the different drawings are isomorphic), what are the smallest number and largest number of crossings of edges that can occur?

Given a graph G, cr(G) is often defined as the minimum number of crossings of edges not at vertices in any drawing of the graph G. Both graphs in Figure 13 can be redrawn with 1 crossing and, thus, have crossing number 1. The first graph shown has 5 crossings in the drawing shown and if edges are not allowed to intersect themselves or cross other edges more than once, this drawing has 5 crossings, which is the largest number of crossings. Depending on what "concepts" one is trying to understand one often puts rules on the allowed drawings. The bottom graph (Figure 13) shows three edges that pass through a single point; for some purposes such a drawing would not be allowed and one is required to use drawings where at most two edges meet at a crossing.

Given a particular graph G, to decide for any integer $c$ if the crossing number $\textrm{cr}(G) \leq c$ is known to be NP-complete. This means that it is very unlikely that there is a polynomial time algorithm for determining the solution to this question. (There are hundreds of NP-complete problems and if any one of them could be solved in polynomial time, then it would be possible to solve them all in polynomial time–no one knows!)

Over many years there has been a progression of results concerning getting bounds on the crossing number of a graph. Using the result known as Euler's Formula that for any planar connected (one piece) graph, V + F – E = 2 where V, F and E denote the number of vertices, faces and edges of the graph. It is not difficult to see that from this result the crossing number of a general graph with V vertices (where V is at least 3) and E edges satisfies $$\textrm{cr}(G) \geq E – 3V + 6.$$

However, making various assumptions about the density of the number of edges (how rich in edges the graph is) of a graph one can get more "interesting" bounds on the crossing number.

Theorem:

$$ \textrm{If } E \geq 4V \textrm{ then cr}(G) \geq (1/64)\left(E^3/V^2\right) $$

Various variants of this result are being explored where the "edge density" is changed, in attempts to understand the value of the constant (above 1/64) in the crossing-number expression. Thinking of a configuration of points and lines in the plane as a graph drawn in the plane with crossings allows one to get the expression for incidences in the Szemerédi-Trotter Theorem.

What else can we say about the crossing number of interesting graphs? One particularly interesting family of graphs is the graphs with $n$ vertices, every pair of vertices being joined by exactly one edge–graphs known as complete graphs. Traditionally this graph is denoted $K_n$.

$K_n$ has $(n)(n-1)/2$ edges since each vertex is joined to the all of the other $n-1$ vertices, and each edge will get counted twice, once at each of its endpoints, which gives the result $(n)(n-1)/2$.

Thus, $\textrm{cr}(K_n) \geq (n)(n-1)/2 – 3n + 6,$ which simplifies to $(n^2/2) – (7/2)n + 6$.

It might seem that it would be easy to find the exact value of the crossing number of $K_n$ which is very symmetrical combinatorially, but perhaps rather surprisingly the exact value of this crossing number for every $n$ is not yet known. It has been conjectured to be Z(n):

$$(1/64)(n)(n-2)^2(n-4), \textrm{ when n is even, and}$$

$$(1/64)(n-1)^2(n-3)^2, \textrm{ when n is odd.}$$

You can check that this formula gives the crossing number of the complete graph with 5 vertices to be 1. Various people (Paul Turán and the recently deceased Richard Guy) have been involved with the "proper" guess for the minimum number of crossings of the different types of "complete" graphs drawn in the plane but the "formulas" above are sometimes associated with the name of the Polish mathematician Kazimierz Zarankiewicz. As is the spirit of mathematics, generalizing interesting ideas and concepts, there are now many kinds of crossing numbers that have been explored.

Photo of K. Zarankiewicz

 

Figure 15 (Kazimierz Zarankiewicz (1902-1959))
 

The Szemerédi-Trotter Theorem initially was concerned with incidences between points and lines. Over a period of time it resulted in new theorems related to incidences between points and pseudolines (lines are to uncooked spaghetti as pseudolines are to cooked spaghetti), points and circles of the same radius, points and circles with different radii, points on parallel lines, etc. In this line of work the result was generalized from points and lines to points and other collections of geometric sets. But if one can discuss points and lines in 2-dimensional space, why not look at points and lines in higher-dimensional spaces, or lines and planes in higher-dimensional spaces? You should not be surprised that all of these have come to be looked at and much more.

While these are seemingly natural extensions of the ideas related to the Szemerédi-Trotter Theorem there is again the element of surprise in mathematics. The Szemerédi-Trotter Theorem seems rooted in combinatorial geometry–counting things–but it also has metrical, distance-related ties. While Paul Erdős played a part in the history of the Szemerédi-Trotter Theorem (not directly discussed above) he also had a part in the this other thread of results. Given a set of points P in the plane, with different conditions on where the points are arranged with respect to each other and perhaps their pattern on lines that pass through the points, one can measure the Euclidean distance (or other distances) between points in the set P. Now one is interested in studying how few or how many distances can occur. There are many papers about counting distinct distances, repeated distances, etc.!

From little acorns great oaks grow. Incidences may seem like an "acorn" compared with other issues in mathematics but it has been an acorn that has grown impressive results. I hope you enjoy Mathematics and Statistics Awareness Month and try your hand at learning and doing some new mathematics.

References

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

Beck, J., On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry, Combinatorica 3 (1983), 281–197.

Brass, P. and W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005.

Clarkson K. and H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990) 99–160.

Dvir, Z., On the size of Kakeya sets in finite fields. J. Amer. Math Soc. 22 (2009) 1093–1097.

Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer- Verlag, Heidelberg (1987)

Elekes, G., On linear combinatorics I, Concurrency—an algebraic approach, Combinatorica 17 (4) (1997), 447–458.

Elekes, G., A combinatorial problem on polynomials, Discrete Comput. Geom. 19 (3) (1998), 383–389.

Elekes, G., Sums versus products in number theory, algebra and Erdős geometry–A survey. in Paul Erdős and his Mathematics II, Bolyai Math. Soc., Stud. 11, Budapest, 241–290 (2002)

Elekes, G., and H. Kaplan, M. Sharir, On lines, joints, and incidences in three dimensions. J. Combinat. Theory, Ser. A. 118 (2011) 962–277

P. Erdős, Problems and results in combinatorial geometry, in Discrete Geometry and Convexity (New York, 1982), vol. 440 of Ann. New York Acad. Sci., 1985, pp. 1–11.

Felsner, S., Geometric Graphs and Arrangements, Vieweg, Wiesbaden, 2004.

Grünbaum, B., Configurations of Points and LInes, Graduate Studies in Mathematics Volume 103, American Mathematical Society, Providence, 2009.

Guth, L. and N. Katz, Algebraic methods in discrete analogs of the Kakeya problem. Advances Math. 225, 2828–2839 (2010)

Guth, L. and N. Katz, On the Erdős distinct distances problem in the plane. Annals Math. 181, 155–190 (2015), and in arXiv:1011.4105.

Kaplan, H., and M. Sharir, E. Shustin, On lines and joints, Discrete Comput. Geom. 44 (2010) 838–843.

Kollar, J., Szemerédi-Trotter-type theorems in dimension 3, Adv. Math. 271 (2015), 30–61.

Matousek, J., Lectures in Discrete Geometry, Springer, New York, 2002.

Pach, J. (ed), Towards a Theory of Geometric Graphs, Contemporary Mathematics 342, American Mathematical Society, Providence, 2004.

Pach, J., and P. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.

Pach, J., and R. Radoicic, G. Tardos, and G. Toth, Improving the Crossing Lemma by ?nding more crossings in sparse graphs, Discrete Comput. Geom. 36 (2006) 527–552.

Pach, J. and M. Sharir, Repeated angles in the plane and related problems, J. Comb. Theory, Ser. A 59 (1992) 12–22.

Pach, J. and M. Sharir, On the number of incidences between points and curves, Combinatorics, Probability and Computing (1998), 121–127.

Pach, J. and M. Sharir, Geometric incidences, pp. 185–224, in Towards a theory of geometric graphs, vol. 342 of Contemporary Mathematics, AMS, Providence, RI, 2004.

Pach, J. and G. Toth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439.

Quilodran, R., The joints problem in Rn . Siam J. Discrete Math. 23 (2010) 2211–2213

Sharir, M. and E. Welzl, Point-line incidences in space. Combinat.
Prob., Comput., 13 (2004) 203–220

Sheffer, A., Distinct Distances: Open Problems and Current Bounds
https://arxiv.org/abs/1406.1949

Solymosi, J., On the number of sums and products, Bulletin of the London Mathematical Society, 37 (2005) 491–494

Solymosi, J. and Tao, T.: An incidence theorem in higher dimensions. Discrete Comput. Geom. 48 (2012) 255–280

Szekely, L., Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997) 353–358.

Szemerédi, E., and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983) 381-392.

Tomassia, R. (ed.), Handbook of Graph Drawing and Visualization, CRC Press, Boca Raton, 2014.

Tomassia, R. and I. Tollis (eds.), Graph Drawing, Lecture Notes in Computer Science 894, Springer, New York, 1995.

Toth, C., The Szemerédi–Trotter theorem in the complex plane, Combinatorica, 35 (2015) 95–126

Zahl, J.. and A Szemerédi–Trotter type theorem in R4, Discrete Comput.
Geom. 54, 513–572 (2015)

AMS Feature Column banner

Joe Malkevitch’s Column Archive

Here are Joe Malkevitch’s older Feature Columns. Joe’s newest columns may be found here.