Master thesis defense: Cathryn Supko

Speaker: Cathryn Supko

Supervisor: Dr. V. Chvatal
Examining Committee: Drs. T. Fevens, B. Jaumard,, V. Haarslev (Chair)
Title: On a Generalization of the de Bruijn-Erdos
Theorem Date: Friday, July 4, 2014
Time: 10:00
Place: EV 3.309 

Abstract

The de Bruijn-Erdos Theorem from combinatorial geometry states that every set of n noncollinear points in the plane determine at least n distinct lines. Chen and Chvatal conjecture that this theorem can be generalized from the Euclidean metric to all finite metric spaces with appropriately defined lines. The purpose of this document is to survey the evidence given thus far in support of the Chen-Chvatal Conjecture. In particular, it will include recent work which provides a n1/2/2 lower bound on the number of distinct lines in all metric spaces without a universal line.