Presentation Title

The Chromatic Number of Prime Distance Graphs

Faculty Mentor

Daphne Liu

Start Date

18-11-2017 1:45 PM

End Date

18-11-2017 2:00 PM

Location

9-285

Session

Physical Sciences 2

Type of Presentation

Oral Talk

Subject Area

physical_mathematical_sciences

Abstract

The chromatic number of distance graphs is problem proposed by Paul Erdős. The problem is a simplification of the chromatic number of the plane, but as time went by the problem proved to be just as complex as the problem from which it is derived. The original problem asks what is a minimal number of colors needed to color the xy-plane so that no two points, distance 1 apart, share a color. The simplification asks to consider the same proposition but just on the x-axis. To prevent triviality, Erdős proposed a distance graph. A distance graph is a graph that is built on the integers with a distance set where two integers are adjacent if their separation is in the distance set. We are interested in distance sets that consist of prime numbers. The chromatic number of distance graphs was eventually shown to be bounded by the lonely runner conjecture. The lonely runner conjecture asks us to consider n runners on a circular track. Each runner runs at a constant speed. The conjecture states that there will be a time where one runner becomes lonely, that is all the other runners are at least 1/n apart. We can determine exactly how far the other runners are using the kappa value of that runner. If we fix a runner with speed 0, then that kappa value of 0 can be used to bound the chromatic number of a distance graph. The lonely runner conjecture has only been proven for up to 6 runners, this means that we can bound the chromatic number for distance graphs whose distance set consist of five numbers. We have shown some partial results for the distance set {2, 3, 7, x, y} and generalizations of our results.

Summary of research results to be presented

We have completely solved the chromatic number for G(Z, {2,3,7,11,x}) for all x. Our remaining results focus the distance graph G(Z, {2,3,7,x,y}). Using the kappa value, we have proven that if x and y are both congruent to 2,3,7,8,13,14,18,19 (mod 21) OR 2,3,5,6 (mod 9) then the chromatic number is 3.

This document is currently not available here.

Share

COinS
 
Nov 18th, 1:45 PM Nov 18th, 2:00 PM

The Chromatic Number of Prime Distance Graphs

9-285

The chromatic number of distance graphs is problem proposed by Paul Erdős. The problem is a simplification of the chromatic number of the plane, but as time went by the problem proved to be just as complex as the problem from which it is derived. The original problem asks what is a minimal number of colors needed to color the xy-plane so that no two points, distance 1 apart, share a color. The simplification asks to consider the same proposition but just on the x-axis. To prevent triviality, Erdős proposed a distance graph. A distance graph is a graph that is built on the integers with a distance set where two integers are adjacent if their separation is in the distance set. We are interested in distance sets that consist of prime numbers. The chromatic number of distance graphs was eventually shown to be bounded by the lonely runner conjecture. The lonely runner conjecture asks us to consider n runners on a circular track. Each runner runs at a constant speed. The conjecture states that there will be a time where one runner becomes lonely, that is all the other runners are at least 1/n apart. We can determine exactly how far the other runners are using the kappa value of that runner. If we fix a runner with speed 0, then that kappa value of 0 can be used to bound the chromatic number of a distance graph. The lonely runner conjecture has only been proven for up to 6 runners, this means that we can bound the chromatic number for distance graphs whose distance set consist of five numbers. We have shown some partial results for the distance set {2, 3, 7, x, y} and generalizations of our results.