150. Linear programming bounds for problems in discrete geometry
Invited abstract in session TA-1: Plenary II, stream Plenaries.
Thursday, 9:00 - 10:00Room: C V VI
Authors (first author is the speaker)
| 1. | Mate Matolcsi
|
| Budapest University of Technology and Economics |
Abstract
Let us colour the points of the plane in such a way that the endpoints of any segment of length 1 have different colours. The least number of colours needed is called the chromatic number of the unit distance graph of the plane, and determining this number is the famous Hadwiger-Nelson problem. A linear relaxation of the problem arises if we allow "fractional colourings". In this talk we will review some recent results concerning the fractional chromatic number of the plane, and the density of subsets avoiding the unit distance. In all results the theoretical considerations yield linear programs, whose solution gives bounds on the relevant quantities. A computer search is then utilized to select the best possible parameters of the linear program to obtain the sharpest possible bounds.
Keywords
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers