Codes with bounded distances, and their applications to distance graphs

In Coding Theory, the maximum size of binary codes of length n with minimum distance d is a well studied problem. In this talk, we study binary codes when there is a restriction on maximum distance as well. Various upper bounds including an exponential upper bound have been established using a result of Kabanjanskii--Levenstein and Jung's theorem in Combinatorial Geometry. We show applications of these coding theoretic results to the lower bound on chromatic number of the n-dimensional integer grid. This is motivated by Hadwiger--Nelson problem that asks for the minimum number of colors needed to color the real plane such that any two points at distance 1 are forbidden to receive the same color. The best known lower and upper bounds are 4 and 7, with no improvement in the last 50 years.

This is a joint work with S. Anderson and H. Maharaj.

Event Topic

Discrete Applied Math Seminar