SAMPLE PROBLEMS AND PROBLEM AREAS worked on by participants in previous REU's at Auburn (1999, 2000, and 2005), with remarks on problems remaining

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 are sets of t vertices in the graph no two of which are adjacent.  (Such sets of mutually non-adjacent vertices are said to be independent.) The graph is (t,r)-regular if for every such set of t vertices, their open neighbor set (the union of the sets of vertices adjacent to the different vertices in the given 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. (To form the join of two graphs, put in all the edges between disjoint copies of the graphs.) The resulting graph is (t, q + t(p-1))-regular.
     One of the best results in the study of (t,r)-regular graphs is the following theorem of Ralph Faudree and Debra Knisley: Given r, for all n sufficiently large--say, n at least as large as some integer N(2,r)--the only (2,r)-regular graphs on n vertices are of the form described in the paragraph above, with suitable choices of p and q (allowed to be 0, by the way). The original proof of this beautiful result does not give nice estimates of the smallest value of N(2,r).  Evan Morgan, a participant in our 2000 REU, found a different proof, longer but somehow more reasonable, which eventually led to very nice estimates: roughly, for r > 2, r^2 > N(2,r) > (r^2)/16.
     In 2005 some of our participants took a shot at finding N(2,r) exactly, and all of the (2,r)-regular graphs of order less than N(2,r), for small values of r.  They made it through r = 4, and there the matter rests.
     There is a "for all n sufficiently large" structure theorem for (t,r)-regular graphs, for t > 2, which is similar to the Faudree-Knisley theorem, but not quite as simple.  Good estimates of the smallest N(t,r) in that theorem remain to be investigated.  Also, it would be nice to know what all of the (t,r)-regular graphs are for t = 3,4, and small values of
r.

    A graph is uniformly (t,r)-regular if the open neighbor set of any set of t of the vertices of the graph has cardinality r.  In this definition, t is not required to be less than or equal to the vertex independence number, and the sets that we are looking at the open neighbor sets of are not required to be independent. (However, t can be no greater than the number of vertices of the graph.)  The property of (t,r)-regularity is much more widely encountered than is uniform (t,r)-regularity, and, indeed, until recently it was an open problem of great interest to classify the uniformly (t,r)-regular graphs, for t > 1 and various r.  There are some easy ways to come by such graphs--for instance, take any graph with edges, let t be the number of vertices, and let r be the number of non-isolated vertices.  And there are other "trivial" ways to come by graphs with the property.
   In the spring of 2005 a satisfactory characterization of all uniformly (2,r)-regular graphs (which include some non-trivial cases) was achieved by Khodkar, Leach, and Robinson.  In the summer of 2005 two of our REUparticipants, Kevin Lin and Caleb Petrie, had a go at the case t = 3,and by the end of the program, after a lot of strenuous and ingenious scrambling around the problem, were pretty well convinced that there were no non-trivially uniformly (3,r)-regular graphs, but their admirable compilation of partial results did not add up to a proof.  However, their efforts did stimulate further attacks on the problem and very recently, in October, 2005, it was proven that there are no non-trivially uniformly (t,r)-regular graphs for any r and any t > 2. (Kevin and Caleb achieved co-authorship on the paper containing this lovely theorem, by the way.)

   Here is a property that turns out to be almost the same as uniform (2,r)-regularity:  A graph is k-friendly iff any two distinct vertices in it have exactly k common neighbors (i.e., the intersection of their open neighbor sets has cardinality k). It is a nice warm-up exercise to describe the 0-friendly graphs; a famous result from the late '60's, the Friendship Theorem, describes all the 1-friendly graphs.  In our 2005 REU, Kelly Bragan got interested in the question of whether or not there are any k-friendly graphs for k > 1, other than the complete graph on k + 2 vertices. In joint work with an Auburn faculty member, she found all the 2-friendly graphs (there are only 3 of them), and went on to characterize,
in joint work with two faculty members, k-friendliness for all k > 1 in terms of another well known graph property, strong regularity.

   REU participants at Auburn have also been interested in other topics in graph theory, including the "coloring number", Grundy coloring, the circular chromatic number, and various fractional parameters.

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 2 elements, and the problem has been the object of study and attack ever since.
   Auburn REU participants Jennifer Clem (1999), and Stacy McClanahan and Janet Trimm (2000) had considerable success in a number of special cases, most notably when S has 3 elements.

Euclidean Coloring Problems

    In our 1999 REU, Arthur Szlam discovered a theorem that still ranks as our best so far from an REU participant (in the opinion of the person who is writing this, anyway).  We won't bother you with the theorem statement, but here are a couple of easy consequences that we are pretty sure were unknown previously: Let E be either the Euclidean plane or the set of rational points in (coordinatized) 4-dimensional Euclidean space. In any 2-coloring of E, say with red and blue, with the property that no two blue points are a distance 1 apart, the set of red points must contain translates of every 3-point subset of E.
 
    Arthur's original theorem was generalized beyond recognition by himself and two Auburn faculty, and one of the generalized forms came in handy in our 2005 REU. Emma Friedman became interested in the problem of coloring the integers 1,...,N with as few colors as necessary so that no 3-term arithmetic progression in that block of integers is monochromatic. Certainly the number of colors required is no greater than that required
to forbid monochromatic "cyclic" 3-term  arithmetic progressions, i.e. {k, k+d, k+2d} in which the addition is mod N, and it turns out that Szlam's theorem provides a nifty way to get an upper bound on that number.  Emma did tremendous work on these problems for N < 26, and will become a co-author of a paper on the topic as soon as her faculty
collaborator does his part.
 
    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 (or from 3 to 2, if x is increasing)?  In the case of rectangles, there was also some success in finding where f(x) jumped from 3 to 4. There are a lot of unanswered questions on this topic.

   The kth Babai number of a metric space X is the smallest positive integer m, if any, such that for any set of k or fewer distances (positive real numbers, that is), X can be colored with m colors so that no two points of X the distance between which belongs to the set are the same color.  It has recently been shown that the kth Babai number of the real
line, and of the integers, with the usual notion of distance, is k + 1.  In our 2005 REU Albert Lee made some progress toward determining the first Babai number of the set of integer points in n-dimensional Euclidean space, and there may be a paper in progress, if some more results can be obtained. There are a truckload of wide open problems concerning the Babai numbers of various interesting subsets of the finite dimensional Euclidean spaces.
         
   In the 2000 REU Aaron Bohannon and Elizabeth Thomas, working with an  Auburn faculty member, contributed to the following result: for any 2 sets of 3 points in the plane, except possibly in the case where both sets are collinear and on parallel lines, there is a 2-coloring of the plane (in fact, a very special 2-coloring, outside of the possibly exceptional cases, a "slab" or "interval strip" coloring) such that no translate of either of the two sets is monochromatic.  The exceptional case remains unresolved; the question in that case  is equivalent to the following, which seems very doable, but has resisted attack so far:  Is it the case that for any 4 positive integers a, b, c, and d, there is a 2-coloring of
the set of integers such that for every integer x, neither of the sets {x, x+a, x+a+b}, {x, x+c, x+c+d} is monochromatic?

n-ary Huffman Sequences

   An n-ary Huffman sequence of length m is the sequence of code word lengths, in non-decreasing order, of a prefix-free sequence of code words, over an n-letter code alphabet, obtained by some instance of Huffman's algorithm applied to some probability distribution over an m-letter source alphabet. There is a good algorithm for generating all possible n-ary Huffman sequences of length m, given n, m > 1, yet there do not seem to be any good estimates on how many of them there are.  In our 2005 REU Ryan Citko and Jeffrey Scott had a go at this problem, and did not succeed, but came up with several interesting observations and conjectures that will certainly be of use in the future.

Miscellaneous

   REU participants at Auburn have also done good and useful work on

(i) finding Groebner bases of ideals in polynomial rings;

(ii) probabilistic finite state automata;

(iii) problems in the theory of combinatorial designs (e.g., trying to
decompose the complete tripartite graph with 10 vertices per part into the
union of edge-disjoint 5-cycles);

and a wide variety of puzzles and problems, some open, posed from time to
time by faculty and graduate students at Auburn, or visiting Auburn during
the REU program.