Volume 3, Issue 1, April 2019, Pages: 60-69
V. Yegnanarayanan
Department of Mathematics, School of Arts, Science and Humanities, SASTRA Deemed to be University, Thanjavur-613401, Tamilnadu, India
Some problems become very popular and demand rapt attention while others just collect dust on the shelf.
Big Conferences like this are a nice breeding ground for advertising or publicizing both old and new problems. Consider
for example the famous unit-distance problem. This problem asks for the smallest number of colors needed to color the
points of the plane R2 so that points unit distance apart have distinct colors. This problem was attributed to atleast
five different mathematicians in a variety of combinations. Edward Nelson, Hugo Hadwiger, Paul Erdos, Martin Gardner
and Leo Moser. It is now known as Hadwiger-Nelson problem (HNP). The problem was actually formulated by Edward
Nelson in 1950 when he was a graduate student at the University of Chicago. Nelson called it the alternative four-color
problem as it dealt with the plane and four colors. He proved that atleast four colors are needed. John Isbell upon
learning about the problem from Nelson, proved in 1951 that the unit distance graph is 7-colorable. This problem might
be a typical candidate for a famous problem. It is simple enough for high school student to understand, it is easy to
describe and looks deceptively easy to solve. After all, all one needs is to construct a finite set of points in the plane that
requires more than 4-colors or prove that any set of points is 4-colorable. As a matter of fact, while hundreds of papers
dedicated to variations of this problem have been published, no progress has been made on the actual chromatic number
of the unit distance graph since its inception. In this paper this problem is discussed further. Its variations, enormity,
challenges, bottleneck and road ahead are quite mind-boggling. However, upon reading this one gets clarity regarding
the role of several pure mathematics concepts emanating from set theory, algebra, analysis, topology and number theory.
The author of this paper was fascinated very much and is completely engrossed with this problem since 2010. The
following are some of his results in this topic.
Given a subset D in Z , an integer distance graph is a graph G(Z; D) with Z as vertex set and with an edge
joining two vertices u and v iff ju − vj 2 D. The author considered the problem of determining χ(G(Z; D)) when D
is either a) a set of (n + 1) positive integers for which the nth power of the last is the sum of the nth powers of the
previous terms or b) a set of Pythagorean quadruples or c) a set of Pythagorean n-tuples or d) a set of square distances
or e) a set of abundant numbers or deficient numbers or Carmichael numbers or f) a set of polytope numbers or g) a
set of happy numbers or lucky numbers or h) a set of Lucas numbers or i) a set of Ulam numbers or j) a set of weird
numbers. In addition, he also found some useful upper and lower bounds for general cases too technical to mention here
[14]
Graphs, chromatic number, plane-coloring problem
1. Alexander Soifer. Chromatic number of the plane and is relatives I. The problems its history, Geocombinatorics 2003; 12(3): 131-148.
2. Bernays BP. A system of axiomatic set theory III. J. Symbolic Logic 1942; 7: 65-89.
3. de Bruijn NG, Erdos P. A color problem for infinite graphs and a problem in the theory of relations. Proceedings Series A. 54(5) and Indag. Math. 1951; 13(5).
4. Eggleton RB, Erdos P, Skilton DK. Coloring the real line. J. Combinatorial Theory, Ser. B 1985; 39: 86-100, to erratum 1986; 41: 139.
5. Eric Moorhouse G. On the chromatic numbers of planes, Preliminary Draft. revised, 3 March 2010, Source : Google.
6. Falconer KJ. The realization of distance in measurable subsets covering in Rn . J. Combin Theory Ser. A 1981; 31(2): 181-189.
7. Gardner M. Mathematical Games. Scientific Amer. 1960; 203(4): 180.
8. Hugo Hadwiger, Hans Debrunner. Combinatorial geometry in the plane. Holt, Rinehart and Winston, Newyork, 1964.
9. Jech JTJ. The axiom of choice. North Holland, Amsterdam, 1973.
10. Piepmeyer L. The maximum number of odd integral distances between points in the plane. Discrete Comput Geometry 1996; 16: 113-115.
11. Rado R. Axiomatic treatment of rank in infinite sets. Canad. J. Math. 1949; 1: 337-343.
12. Raigorodskij AM. Borsuk’s problem and ch no.s of some metric spaces. Russ Math Surv 2001; 56(1): 103-139.
13. Solovay RM. A model of set theory in which every set of reals is Lebeque measurable. Ann. of Math. (Ser. 2) 1970; 92: 1-56.
14. Yegnananarayanan V. Chromatic number of graphs with special distance sets I. Algebra and Discrete Mathematics 2014; 17(1): 135-160.
15. Zermelo E. Beweiss class jede Menge wohlgeordrnet. Warden Kann Math. Ann. 1904; 59: 514-516.
