row1
Worked on by participants in Auburn Math REUs: 1999, 2000, 2005-2008, and 2010-2023.
Coloring problems, Euclidean and otherwise
In 1999 Arthur Szlam produced, at the end of the 8-week program, the following theorem (stated here in slightly more generality than the original): Suppose that A is a subset of n-dimensional real space, closed under vector addition. Suppose that A can be colored with 2 colors, say red and blue, so that no two blue points in A are a distance d apart, and, for some k-element subset K of A, no translate of K in A is all red. Then A can be colored with k colors so that no two points in A that are d apart are the same color.
This theorem has obvious connections with the famous problem of determining the “chromatic number” of n-dimensional real space - the smallest number of colors necessary to color n-dimensional real space so that no two points a distance 1, say, from each other are the same color. For instance, from the well-known fact that in the case n = 2 the chromatic number is at least 4, from Szlam’s lemma we deduce that for every coloring of the plane with red and blue so that no two blue points are a distance 1 from each other, the red set must contain translates of every 3-point set in the plane. (This is a result of Erdos, Graham, Montgomery, Rothschild, Spencer, and Straus from 1975—their proof is very different.)
The connection between Szlam’s lemma and certain Euclidean coloring problems leads to quite a few problems that are approachable—and if we replace Euclidean distance by an arbitrary translation-invariant metric, Szlam’s lemma still holds, and we get a basket of new results and new problems. But there is far more than that to work on; perhaps because the proof of Szlam’s lemma is so easy, it generalizes to a veritable method for getting upper bounds on the chromatic numbers of exotic hypergraphs, in some cases. We’ll not go into what the “chromatic number” of a “hypergraph” is, but here is an instance of an application of Szlam’s lemma, generalized, to a situation involving chromatic numbers of famous exotic hypergraphs. Suppose k > 2 and r > 1 are integers. The van der Waerden number W(k,r) is the smallest positive integer N such that for every coloring of {1,…,N} (or of any block of N consecutive integers) with r colors, there must be a monochromatic k-term arithmetic progression in there somewhere.
Our REU was brought to consider these difficult numbers by the efforts of Emma Friedman, a 2005 participant, who essentially worked out what W(3,2) and W(3,3) were, during the program. Of course, these values were old news in the lofty world of van der Waerden numbers, but Emma’s efforts, plus the fact that during the 2008 program we saw how to bring a generalization of Arthur Szlam’s idea to bear on the study of the W(k,r), caused a return to the subject, summer after summer, with some evolution of our ideas, until in 2008 Jeffrey Burkert saw how to apply an appropriate version of Szlam’s lemma to obtain, after some trouble, a brand new lower bound on the W(k,r). Perhaps more important than the result itself are interesting questions that arise from the method. There is a lot to work on here.
In 2021 Alan Li proved a surprising generalization of Szlam’s Lemma. I won’t give the generalization here, but here is one of its possible applications: Suppose that the (Euclidean) plane can be colored with 4 colors, red, blue, green, and yellow, so that some distance is forbidden for blue, green, and yellow, and there is some two point set in the plane no translate of which is all red. Then the chromatic number of the plane is no greater than 6.
The application of Szlam’s method to questions about the van der Waerden numbers W(k,r) involves what we call the cyclic van der Waerden numbers, which have to do with coloring the ring of integers modulo n so that no k-term “cyclic” arithmetic progression in that ring is monochromatic. (Definitions omitted.) In 2011 Daniel Grier made the surprising discovery that the set of positive integers n such that the integers modulo n can be 2-colored so that no 3-term cyclic arithmetic progression is monochromatic is {2,3,4,6,8}. What’s surprising are the gaps.
No one has yet tried to apply Li’s generalization of Szlam’s Lemma to the study of the cyclic van der Waerden numbers. We just can’t find the time in our busy schedules!
More Euclidean Coloring Problems
Let U be any non-empty subset of any Euclidean space, and consider the integer-valued function f defined on the positive real numbers by f(x) = the smallest number of colors needed to color U so that no two points a distance x apart are the same color.
It is easy to see that if U is convex, or even starlike, then f is non-increasing. Three REU participants, Roberto Rubalcaba (1999), Aaron Bohannon (2000), and Jeremy Lanig (2000) contributed results to a paper, co-authored with a faculty member, mainly about the question: if U is a planar disk or a rectangle, at what value of x does the value of f jump from 2 to 3, as x decreases? In the case of rectangles, there was also some success in finding where f(x) jumped from 3 to 4. In the case of a closed disc, we believed that the jump from 3 to 4 occurred at x = radius of the disk times the square root of 3, but could not prove it. A 2008 participant, Kit Maier, has settled this question beyond the shadow of a doubt. There is still work to be done in this area, however.
In 2006 Andrew Schneider and Michael Tiemeyer, working with one of the program directors, were co-authors of a paper in which it was shown that for any distance d the rational points in 3-dimensional real space can be colored with 4 colors so that no two points a distance d apart are the same color. (The paper appeared in Geombinatorics in 2007.) This theorem was an existence result, and the proof was not at all constructive. In 2008 Jeffrey Burkert gave explicit 4 colorings of the integer points in 3- and in 4- dimensional real space “forbidding the distance d”, for all possible d. (His paper also appeared in Geombinatorics.) Work on coloring the rational or integer points in Euclidean spaces has been greatly discouraged by the success of an Auburn Ph.D. in settling a great many questions—but there are still some elderly open problems to have a go at, and the recent new results raise new questions.
The Frobenius Problem
For any set S of positive integers with greatest common divisor 1, every positive integer from some point on is representable as a non-negative integer combination of elements of S. The Frobenius problem is to determine what that point is, as a function of the elements of S. Frobenius completely solved the problem in the special case where S has only 2 elements, and the problem has been the subject of study and attack ever since.
Auburn REU participants Jennifer Clem (1999), Stacy McClanahan and Janet Trimm (2000), and Jonathan Waite (2008) had considerable success in a number of special cases, most notably when S has 3 elements.
In 2008 Kit Maier and Jordan Paschke obtained the first results for what eventually became a paper on Frobenius problems in the Gaussian integers. The paper, joint with two faculty members, appeared in Geombinatorics in January, 2011. In 2011 Nicole Looper extracted from that paper a general form for Frobenius problems in arbitrary commutative rings with unit, and obtained some interesting results in the cases when the ring is a quadratic extension of the integers. (The Gaussian integers constitute such a ring.) A joint paper co-authored by Nicole and one of the project directors appeared in Geombinatorics. Quite hefty papers on Frobenius problems in different rings were produced by REUers in 2012, 2015, 2020, and 2021. All but one have appeared in refereed journals, and the remaining one has been accepted for publication.
Number Theory, other than Frobenius problems
In 2006 Jeff Ward introduced us to the abundancy index: If n is a positive integer, I(n) is the sum of the positive divisors of n (including n itself), divided by n. For example, I(10) = 9/5. A good deal, but not too much, has been discovered about the abundancy index over the last 70 years or so, and several in the program, including one of the program directors, had an enjoyable time in 2006 resurrecting and rediscovering a fair amount of it. Jeff eventually wrote an interesting paper, which appeared in 2008, in which he showed that if n is a positive integer other than 10 such that I(n) = 9/5 (it is not known if there is any such n), then n is a square with at least 6 distinct prime divisors, the smallest being 5; there is some more in the theorem about the form of the other prime divisors, and the powers to which they occur in the factorization of n. The program director who participated in the study of the abundancy index believes that Jeff’s methods can be pushed further. In 2011 Kim Allen had a go at this pushing, and made a lot of progress, but didn’t succeed in changing that “6” to a “7”. In 2012 Tim Lai and the interested program director got within shouting distance of Kim’s goal; we had only to check something or other for all primes less than 20,000. But the summer ended, neither of us knew how to compute, and there the matter stands.
In 2007 Jeff’s brother Matt wrote a nice paper about the abundancy index in the Gaussian integers.
In 2010 Mike Laughlin asked a series of questions that led to the following conjecture: for any positive integers k and r, there is a (smallest) integer N(k,r) such that all integers no less than N(k,r) can be written as the sum of r or more kth powers of distinct positive integers. It is easy to see that N(1,r) = r(r + 1)/2, for all r. Mike is the co-author with a faculty member of a paper, which appeared in 2011, in which it is shown that N(2,1) = N(2,2) = N(2,3) = 129. A number of other seizable problems are suggested in this paper.
But the main problem, the conjecture about the existence of the N(k,r), was settled in the affirmative in 2011 by Nicole Looper and Nathan Saritzky. Their joint paper appeared in 2016.
Our involvement with Euclidean coloring problems led us to a different genre of number theory questions, on which our REUers produced notable results in 2013, 2015, and 2017. For one instance: for which integers b, c, satisfying 0 < b < c, can the set of integers be colored with 2 colors so that no translate {a, a + b, a + c} of {0, b, c}is monochromatic? Good results, yes, but the question is not completely answered.
Graph Theory
Suppose that t and r are positive integers, and that a graph has vertex independence number at least t. This means that there is at least one set of t vertices in the graph no two of which are adjacent. (Such a set of vertices is said to be independent.) The graph is (t,r)-regular if for every such set of t vertices, their open neighbor set (the set of vertices with at least one neighbor in the set) has cardinality r.
For examples, take t or more disjoint complete graphs on p vertices, and take the join of their union with a complete graph on q vertices. (The join of two graphs is formed by putting in all the possible simple edges between two disjoint copies of the graphs.) The resulting graph is (t, q + t(p – 1))- regular.
A theorem due to Ralph Faudree and Debra Knisley (not REU participants!) says that for each r there is a (smallest) integer N(2,r) such that for all n from N(2,r) on, all (2,r)- regular graphs on n vertices must have the form of the graphs constructed by the instructions in the preceding paragraph (in which, by the way, q can be 0). The original proof of this beautiful result does not give nice estimates of N(2,r). Evan Morgan, a 2000 participant, found a different proof, longer but somehow more reasonable, which eventually led to nice estimates: for r > 2, (r^2)/16 < N(2,r) < r^2. The evidence so far suggests that N(2,r) is close to the upper bound, in this inequality.
In 2005 some of our participants helped out by trying to find all possible (2,r)-regular graphs for small values of r. It’s not so easy! After the program, one of the participants, Kelly Bragan, worked out all of the (2,3)-regular graphs with a classmate at Birmingham Southern, and they wrote a paper about it. Besides the graphs of the Faudree-Knisley form, there were 19 “sporadic” (2,3)-regular graphs. This work established beyond the shadow of a doubt that N(2,3) = 8.
There is a “for all n sufficiently large” structure theorem for (t,r)- regular graphs with t > 2 which is similar to the Faudree-Knisley theorem, but not quite as simple. Some time ago a (then) graduate student at the University of South Carolina, Melanie Laffin, worked on (3,r)-regular graphs for small values of r, but there is still a lot to be done.
If the edges of a graph are colored, a subgraph of the graph is said to be “rainbow” in the coloring if no color is repeated on the edges of the subgraph. It is well known that it is possible to color the edges of the complete graph on n vertices with n – 1 colors so that no cycle subgraph is rainbow, but that if n or more colors are used, there must be a rainbow 3-cycle somewhere in the graph. In 2007 participants Adam Gouge, Laura Nunley, and Luke Paben looked at edge colorings of complete graphs that forbid rainbow colorings and produced, with 2 faculty co-authors, a paper (which appeared in 2010) that contained some nice results: the different such colorings with n – 1 colors are in natural correspondence to the full binary trees with n leafs; there is such a coloring with t colors such that the different colors are used as equally often as possible if and only if t is no greater than (n + 1)/2; and a couple of others requiring definitions that will not be given here. There are still open problems to look at in this connection.
We could go on and on! But we’ll save a few surprises for the program.
