Title:

# On a Generalization of the de Bruijn-Erdos Theorem

Supko, Cathryn (2014) On a Generalization of the de Bruijn-Erdos Theorem. Masters thesis, Concordia University.

 Preview
Text (application/pdf)
CathrynSupko6472621MastersThesis.pdf - Accepted Version
257kB

## 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 an $\Omega (\sqrt{n})$ lower bound on the number of distinct lines in all metric spaces without a universal line.

Divisions: Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering Thesis (Masters) Supko, Cathryn Concordia University M. Comp. Sc. Computer Science 4 July 2014 Chvatal, Vasek 979069 CATHRYN SUPKO 07 Nov 2014 17:04 18 Jan 2018 17:48
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page