De Bruijn–Erdős-type theorems for graphs and posets
No hay miniatura disponible
Archivos
Fecha
2017-05
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Elsevier B.V.
Nombre de Curso
Licencia CC
ATRIBUCIÓN-NOCOMERCIAL-SINDERIVADAS 4.0 INTERNACIONAL
CC BY-NC-ND 4.0
Deed
Licencia CC
https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
Resumen
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.
Notas
Indexación: Scopus
Palabras clave
Betweenness, De Bruijn–Erdős theorem, Lines
Citación
Discrete Mathematics Volume 340, Issue 5, Pages 995 - 9991 May 2017
DOI
10.1016/j.disc.2017.01.012