Booth Id:
MATH043T
Category:
Mathematics
Year:
2017
Finalist Names:
Lee, Thomas
Li, Stephanie
Abstract:
The chromatic number of the n-dimensional Euclidean space is the minimum number of colors with which the entire space can be colored so that every two points one unit apart have different colors.
A unit-distance graph in n dimensions is a graph whose vertices are points in the n-dimensional space and whose edges are pairs of points unit-distance apart. Clearly, the chromatic number of an n-dimensional space is at least as large as the chromatic number of some finite unit-distance graph. The chromatic number is greater than or equal to n+1, since every two vertices of an n-dimensional regular simplex of unit side-length require different colors. The spindle construction, ascribed to Moser and Moser for n = 2 and Raiskii for n > 3, uses regular simplices to demonstrate that the chromatic number is greater than or equal to n + 2.
In 2002, Nechushtan proved that the chromatic number in 3 dimensions is greater than or equal to 6 and claimed that his proof can be used to construct a unit-distance graph which requires six colors and has no more than 400 vertices.
By rotating and transforming Nechushtan’s basic unit-distance graph with chromatic number 5, we construct an explicit unit-distance graph in 3 dimensions with chromatic number 6 that has only 79 vertices and 250 edges. Our methods can be applied to certain 2-deficient, x-chromatic unit-distance graphs in order to construct graphs with chromatic number x+ 1.
Awards Won:
Fourth Award of $500