Bill Kay

Ph.D. Candidate in Mathematics. M.S. in Computer Science.

Emory University.

Research Interests

My research interests lie primarily in the fields of graph theory and combinatorics. Specifically, extremal and probabilistic combinatorics with particular interest in Turán theory, graph coloring, and hypergraph problems. For a detailed description of my current research along with a survey of some of my past results, check out my research statement

Some of my favorite problems

Here's a list of some problems I really like that I am not currently working on. Some of them are problems from my past research, and some are well known conjectures. If you see something here that you want to talk about, feel free to shoot me an e-mail!

  • The Lonely Runners Conjecture. Suppose there are n runners on a (unit distance) circular racetrack whose speeds are all distinct. A runner is said to be lonely at time t if they are distance 1/n away from any other runner (along the track). The question is: is every runner eventually lonely at some point? For an overview of what's known check out the wikipedia page or this great note from Terry Tao.
  • Uniquely Kt-Saturated Graphs . We say a graph G is uniquely Kt-saturated if it contains no copy of Kt, but if you add any missing edge to G there is precisely one copy of Kt. When t = 3, the uniquely Kt-saturated graphs are the stars and the graphs with diameter 2, girth 5 (of which there are 3 or 4, according to the Hoffman-Singleton Theorem). Clearly, any uniquely Kt-saturated graph can be made uniquely Kt+1-saturated by adding a vertex which is adjacent to everything (taking the join with a single vertex). Since the stars provide an infinite collection of uniquely K3-saturated graphs, it follows that there are infinitely many uniquely K4-saturated graphs. In an investigation with Josh Cooper and David Collins, we found several examples of uniquely K4-saturated graphs not obtained in this way (sporadic uniquely K4-saturated graphs). At the same time, Stephen Hartke and Derrick Stolee found these and more examples via orbital branching techniques, along with examples of uniquely Kt-saturated graphs for other values of t. Their write up is the most complete survey of results on uniquely Kt-saturated graphs that I know of. I would like to know a complete characterization of the uniquely K4-saturated graphs.
  • Graham's Tree Reconstruction Conjecture. For the complete problem statement, check out my What's the deal? write up of work on this conjecture. Plainly, I'd love to see this problem completely resolved in either direction.
  • Covering n-Permutations With (n+1)-Permutations. For the complete problem statement, check out my What's the deal? write up of work on this problem. In the first theorem, notice that the upper and lower bounds differ by a logarithmic factor. Can we get rid of that log?
  • Sums of Reciprocals (Erdős). Let S be a subset of the integers. If the sum of the reciprocals of S diverges, must there be arbitrarily long arithmetic progressions in S? As a testament to how tough this problem is, an affirmative answer implies the celebrated Green-Tao Theorem.
  • The Ascending Subgraph Decomposition Conjecture. If G is a graph with n(n+1)/2 edges for some n, there exists a sequence of graphs G1, ... ,G n so that Gi has i edges and is a subgraph of Gi+1. Further, the collection of the Gi partition the edges of G.
  • The Chromatic Number of the Plane ( or the Hadwiger-Nelson Problem). Consider the graph whose vertex set is the plane, and any pair of vertices are adjacent if and only if they are unit distance apart. The Moser Spindle is readily seen to be a unit distance graph with chromatic number 4, while a hexagonal tiling admits a good 7 coloring. Hence, the chromatic number of the plane is between 4 and 7. What is it?
  • The Erdős-Gyárfás Conjecture . This conjecture states that every graph with minimum degree 3 has a cycle whose length is a power of 2. Trying to rig a couterexample to this one is an excellent time sink.
  • The Pythagorean Triples Hypergraph. What is the chromatic number of the 3-uniform hypergraph whose vertex set is the positive integers and a triple is an edge if and only if it is a Pythagorean triple. Is it 2? Is it finite?