Examinando por Autor "Tompkins, Casey"

Mostrando 1 - 1 de 1
  • No hay miniatura disponible
    Ítem
    De Bruijn–Erdős-type theorems for graphs and posets
    (Elsevier B.V., 2017-05) Aboulker, Pierre; Lagarde, Guillaume; Malec, David; Methuku, Abhishek; Tompkins, Casey
    A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for posets, where lines are defined using the natural betweenness relation in posets. More precisely, we obtain a bound on the number of lines depending on the height of the poset. The extremal configurations are also determined. Finally, we introduce a new notion of lines in graphs and show that our result for posets can be extended to this setting. © 2017 Elsevier B.V.