Article ID Journal Published Year Pages File Type
419303 Discrete Applied Mathematics 2015 12 Pages PDF
Abstract

In trying to generalize the classic Sylvester–Gallai theorem and De Bruijn–Erdős theorem in plane geometry, lines and closure lines were previously defined for metric spaces and hypergraphs. Both definitions do not obey the geometric intuition in the sense that two lines (closure lines) may intersect at more than one point, and one line (closure line) might be the proper subset of another. In this work, we study the systems where one or both of the configurations are forbidden. We note that when any two lines intersect in at most one point, the two classic theorems extend in any metric space. We study the metric spaces induced by simple graphs where no line is a proper subset of another, and show that the least number of lines for such a graph with nn vertices is between the order of n4/3n4/3 and n4/3ln2/3nn4/3ln2/3n.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,