Login | Register

On a Generalization of the de Bruijn-Erdos Theorem


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.

Text (application/pdf)
CathrynSupko6472621MastersThesis.pdf - Accepted Version
Available under License Spectrum Terms of Access.


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
Item Type:Thesis (Masters)
Authors:Supko, Cathryn
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:4 July 2014
Thesis Supervisor(s):Chvatal, Vasek
ID Code:979069
Deposited On:07 Nov 2014 17:04
Last Modified: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

Downloads per month over past year

Back to top Back to top