Ronald Graham received his PhD in combinatorial number theory in 1962, and took a position at Bell Labs where he worked for 37 years. Bell Labs gave its people great freedom in their research, and Graham’s interests were very wide. Over the course of his long career, Graham has made many significant contributions and often found himself working on important problems. His friendship with the brilliant Hungarian mathematician Paul Erdős also provided an important service to mathematics.
Erdős received a postdoctoral position in England in 1934 and, sensing the climate for Jews in Europe, remained in England and the United States until after the war. In the mid-1950s, the Hungarian government wanted him to return to Hungary and offered a unique inducement: Erdős could become a nonresident while retaining his Hungarian citizenship. This would allow him to come and go whenever he pleased and to have a foreign bank account. He could stay in Hungary as long as he liked, but he would lose his privileges if he lingered for more than half of any calendar year. Erdős accepted this arrangement, in part because his mother, with whom he was very close, lived in Budapest and, like almost all Hungarians, was not allowed to leave the country.
Although Erdős was able to spend almost six months a year in Budapest, he was still officially a resident of Israel, and was thus compelled to travel for the remainder of each year. His solution to this problem was to visit mathematicians all over the world. Graham and his wife Fan Chung played a crucial role in helping Erdős maintain this odd peripatetic lifestyle for many years. Graham also popularized, and I think invented, the idea of the Erdős number. Those who wrote a joint paper with Erdős have an Erdős number of 1, those writing a paper with someone with an Erdős number, k, and those whose Erdős number is not k or less, have an Erdős number of k + 1. I believe that Graham may also have been responsible for the Erdős–Bacon number, which is the sum of a given Erdős number and a similar one for the actor Kevin Bacon. He also created the pen name G. W. Peck, whose letters include the initials of the authors of a paper: G for Graham, E for Erdős, and several other mathematicians. This raised the potential for imaginary and complex Erdős numbers.
The breakup of AT&T led to the decline of theoretical research at Bell Labs. In 1999, Graham moved to the University of California at San Diego as a distinguished professor. He has served the mathematics community as the president of the American Mathematical Society, and he has won many honors and awards. Over the course of his career, he has published more than 300 mathematical papers and several books.
Connections in Discrete Mathematics contains 20 papers honoring Graham on his eightieth birthday. Many of the authors are distinguished, and, together with the editors, they have taken pains to make their papers accessible.
Three Appetizers
In his contribution, Persi Diaconis describes certain results about the Fibonacci numbers—a numerical sequence such that the first two numbers are 1, and each succeeding number is the sum of the previous two. Thus they begin as: 1, 1, 2, 3, 5, 8, 13. If we look at the remainders of these numbers, upon dividing them by any prime number p, the results are periodic. What is the period as a function of p? Many deep questions with a similar flavor are discussed in this paper.
Neil Sloane’s essay is devoted to cellular automata. A grid somewhat like a spreadsheet is given, and rules defined that determine the neighborhood of each cell. There are many possible rules. The numeral 1 is inscribed on some square. That done, another rule specifies what happens stepwise to a given cell as a function of the sum of the entries of its neighbors. Suppose that a cell’s neighbors are the eight cells with which it shares at least one boundary point. Proceeding in steps, the automaton assigns 1 to each cell if the sum of the entries in its neighborhood is odd, and otherwise 0. What happens after n such steps? How many cells then have the value 1? This is an easy problem for very small n, but a hard problem for larger values. This automaton is known as Fredkin’s replicator.
Andrew Odlyzko’s paper is devoted to polynomials of degree n whose coefficients are 0, 1, or –1, and whose magnitude is as constant as possible when evaluated on the unit circle of the complex plane. The paper contains various results and a number of conjectures about such polynomials.
One Main Course
Peter Frankl and Andrey Kupavskii have contributed an essay that we now describe in more detail. Much more detail. The binomial coefficient (n, k) counts the number of different ways of choosing k elements from n elements: (n, k) = n!/(k!(n – k)!). Suppose that we have two collections of sets, A and B, both of whose members are k-element subsets of a total of n elements, where every member of A has at least one element in common with each member of B, and n is at least 2k.
Frankl and Kupavskii provide a novel proof of an old result: the product of the sizes of A and B is at most the square of (n – 1, k – 1). Their purpose is to suggest that the same approach may provide a short proof when the members of B each have j elements and j is less than k. With n values of at least 2k, the bound is (n – 1, k – 1)(n – 1, j – 1). The previous known proof of this statement is quite long and opaque.
I will describe an argument that when fleshed out verifies their suggestion, and comprises a proof of the important case in which n, k, and j approach infinity. Suppose we number our n elements and to every set Q assign the binary number whose rth digit is 1 when the rth element is in Q. The weight of Q is the sum of the digits of this number. Frankl and Kupavskii’s argument is based on the observation that, without loss of generality, we may assume that the members of A and of B are both assigned the largest numbers of weights k and j respectively. Both A and B can then be completely described by specifying the minimum assigned number among their members. The smaller that minimum, the larger the collection. Every possible prefix for the minimum number for B implies a bound on its size and on the size of A. We want to find the values of j and k for which the product of these bounds is greatest and show that this product is no greater than (n – 1, k – 1)(n – 1, j – 1) for each of our prefixes.
When the first 5 digits of B’s minimum number are 01011 or greater, the values of j and k that produce maximum sizes are both n/2, which means that the j = k result described by Frankl and Kupavskii leads to the more general claim for such prefixes.
To prove the more general result, we need only handle prefixes for the B collection that are 01010 or less. Fortunately, we can do so by looking only at such B prefixes of weight at most 2. The more interesting cases are those for which that prefix begins as 01 with the second 1 in the (s – 1)st digit, the shortest of which is 01010.
Every 0 in a prefix of a minimum number for a collection implies that the sets whose numbers agree with it in all more significant digits and disagree in that digit are in the collection, while every 1 implies that those sets are not in the collection. The number 0101 is larger than 0100 followed by all 1’s. Thus collections with that prefix are at most (n – 1, j – 1) + (n – 3, j – 2) + (n – 4, j – 2) in size. Those that start as 1 are counted by the first term, as 011 by the second, and as 0101 by the third.
The complement d of the minimum number set b in B is the largest set that does not share an element with b, so that no set whose number is smaller than d can be in A. This implies that the minimum number for A must have a prefix of at least 10101. The upper bound on the size of A imposed by the smaller number 10100 followed by all 1s is derived from its three 0s, and is (n – 2, k – 2) + (n – 4, k – 3) + (n – 5, k – 3).
For s of at least 4, the corresponding size bounds are (n – 1, j – 1) + (n – 2, j – 1) – (n – s, j – 1) and (n – 2, k – 2) + (n – 1 – s, k – 1 – s). The maximum size of the k terms occurs when 2k = n. Its ratio to (n – 1, k – 1) is easily obtained. The similar j terms achieve their maximum when j < n/2.
It is easiest to visualize the bound by examining the case when n is so large compared to s that (n – k)/n and (n – k – s)/n are almost the same. The ratios of binomial coefficients obtained by dividing the bounds by (n – 1, k – 1)(n – 1, k – 1) then become a simple polynomial Z in the variable x, with x = (n – j)/n, namely, Z = (1 + x – xs)(2–1 + 2–s+1). We must prove that Z is no greater than 1 for x values between 0.5 and 1.
The maximum of this polynomial occurs where its derivative is 0. This occurs when xss–1 is 1/s, and the upper bound is 1 + xs (1 – 1/s)(1 + 22–s)/2. 1/s is always less than 1/e for s values of at least 3, while (1 – 1/s)s–1 is greater than 1/e. If we increase this upper bound by replacing xs by (1 – 1/s), the ratio product is, at most, (1 + (1 – 1/s)2)(1 + 22–s)/2, which is less than 1 for all s values of at least 4. For s = 3, the relevant ratios are 13/9 and 11/16, whose product is also less than 1.
The finite n cases work out the same way. By its structure, the ratio of j terms is at most 2, which means that the product of the ratios is less than 1 unless the k ratio is at least ½. That only happens when n is at least 2s–2 which for large s is much larger than s. Evaluating the bounds requires more work with finite n than is shown above, but not much more.
We must also address the prefixes of B’s minimum number whose first two digits are 00. These are much easier to handle and we need only consider prefixes of 000, 0011, 00101, 001001, and 001000 for B. For the prefix 000 with first 1 in the tth place, the B ratio (prefix bound divided by (n – 1, j – 1)) consists of t terms and is therefore less than t, while the A ratio is at most 2–t+2, and the products are always less than 1 for all n. The other four cases are not much harder and we leave proof of this claim as an exercise.
There are two other cases that need be handled, namely when the minimum number for B is 0, and when it is 01. In the first, A is empty so that the size product is 0. In the case of 01, the A minimum number must be greater than the complement of 01 followed by all 0, and so has size at most (n – 2, n/2 – 1). The B ratio is 1 + 1 while the A ratio is ½(n – 2)/(n – 1), and the product is less than 1.
Frankl and Kupavskii’s intuition about this problem was correct. The prefix argument given above handles all cases for which their argument does not apply.
The argument here is based on the observation, attributed by Frankl and Kupavskii to Anthony Hilton, that largest size A’s and B’s can always be found that both consist of sets with largest assigned numbers having weights k and j respectively. This statement is really the same thing as a classical result in this field. Consider a collection C whose members all have size n – j. The down-shadow of C of any size q consists of all q-element sets that are contained in one or more members of C. There is always a collection C of any size X whose members have size n – j such that its down-shadow is as small as possible and consists of the smallest numbered sets having weight n – j. We have used this claim because the down-shadow of the complements of the members of B of size k are the size k sets which cannot be in A. Minimizing the down-shadow of B is exactly what is needed to maximize the size of A. That the smallest numbered sets do the minimizing means that their complements in B are largest sets. The sets omitted by smallest numbered sets are smallest numbered sets, so A consists of the other sets of size k, which are then the largest numbered ones.
You can observe from these remarks that proof of the k > j result involves concepts that appear at first glance to have nothing to do with the problem. Yet such ideas form a kind of scaffolding that allows for the construction of this proof. This scaffolding is what makes possible the relatively short proof of the result described above. Verifying that the proof is correct involves checking all its details carefully. Finding the proof is a much more difficult problem because it requires first finding the right scaffolding, which Frankl and Kupavskii did, and a priori there is no straight path leading to such things. The difference between finding and checking a proof is analogous to the difference between NP and P in computer science.
The other chapters of Connections in Discrete Mathematics cover a wide variety of subjects, and many mention open problems. Adrian Bolt, Steve Butler, and Espen Hovland contribute a paper about Apollonian ring packings. Elsewhere, there is a short piece entitled “Pick’s Theorem and Sums of Lattice Points” by Karl Levy and Mervyn Nathanson. Several chapters touch on juggling—a particular passion of Graham’s—notably a contribution by Erik and Martin Demaine, in which they offer two new mathematical typefaces based on juggling trajectories and card shuffling patterns. Graham is a coauthor of two papers, a chapter with his wife Fan, “The Digraph Drop Polynomial,” and a paper coauthored with Joe Buhler, Anthony Gamst, and Alfred Hales, “Explicit Error Bounds for Lattice Edgeworth Expansions.”
Examining the many results, concepts, and open problems discussed in Connections in Discrete Mathematics is a bit like listening to a lecture by Erdős. There is so much to see that it becomes hard to focus on one thing. The best approach to this volume might be to consider one small issue at a time, as we have attempted to do here.
