Here is a problem I composed, which recently appeared on the Colorado Mathematical Olympiad.
If one wishes to color the integers so that every two integers that differ by a factorial get different colors, what is the fewest number of colors necessary?
I might describe a solution, as well as some related history, in a future post. But for now I’ll just say that Adam Hesterberg solved this problem at Canada/USA Mathcamp a few summers ago, claiming the $20 prize I offered almost as soon as I offered it. At the time, I suspected but still did not know the exact answer.
Although the wording of the problem strongly suggests that the answer is finite, I don’t think that this is entirely obvious.
Along those lines, here is another infinite graph with finite chromatic number.
If one wishes to color the points of the Euclidean plane so that every two points at distance one get different colors, what is the fewest number of colors necessary?
This is one of my favorite unsolved math problems, just for being geometrically appealing and apparently intractably hard. After fifty years of many people thinking about it, all that is known is that the answer is 4, 5, 6, or 7. Recent work of Shelah and Soifer suggests that the exact answer may depend on the choice of set theoretic axioms.
This inspired the following related question.
If one wishes to color the points of the Euclidean plane so that every two points at factorial distance get different colors, do finitely many colors suffice?
More generally, if 
mathematical musings 
We (Jack D’Aurizio and Maurizio Monge from the University
of Pisa, Italy) are proud to announce a solution:
the chromatic number of the graph G, whose nodes
are the integers, in which
(a-b)=n! -> a and b have different colors,
is -exactly- 4; details can be found in the PDF file.
We have an additional question: is it possible to color
the integers with a finite number of colors, in order that
two integers that differs by a positive square have
different colors?
Jack and Maurizio, I’d like to see your solution. Is the PDF file posted anywhere?
Also, I like this question about squares…
The link http://poisson.dm.unipi.it/~daurizio/4Colors.pdf on Jack’s name is probably what he’s referring to, however the server poisson.dm.unipi.it seems to be down at the moment.
The PDF is there; we’ve got some server issues, now it should be fine.
Recently (2003) Bergelson has proved that, in the quadratic case, a finite amount of colors is not sufficient: http://www.math.ohio-state.edu/~vitaly/vbkatsiveli20march03.pdf
His techniques deeply rely on the theory of ultrafilters and ergodic, measure-preserving systems; however, we suspect that a simpler proof (maybe using the Mycielski construction and the fact that the squares are an additive base of order 4) is possible.
After a full immersion in the bibliography, we have an alternative proof that the chromatic number of the graph G over the integers, where
(ab) belongs to E(G) |b-a| is a positive square
is unbounded. Suppose that X(G)=k, then call
C_1, … , C_k
the chromatic components.
First step: without loss of generality, we can assume
that every C_i is infinite and syndetic.
Proof: shifts and compactness. If C_1 has unbounded gaps,
for every M there exist a coloring of [1,…,M]
requiring only (k-1) colors, so X(G)=k-1,
contradiction.
Second step: Lovasz conjecture is true. Sarkozy proved
(http://www.renyi.hu/~p_erdos/1978-19a.pdf) through the
Hardy-Littlewood circle method, that, if A is a subset
of [1,..,N] such that (A-A) does not contain the square
of a positive integer, then the asymptotic density of A
satisfy:
alpha(N) = O( (log N)^(-1/3) (log log N)^(2/3) ) = o(1)
So, for every infinite and syndetic C, there is a
positive integer m with the property that
m^2 belongs to (C-C).