De Bruijn–Erdős-type theorems for graphs and posets

Pierre Aboulker, Guillaume Lagarde, David Malec, Abhishek Methuku, Casey Tompkins

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva


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.

Idioma originalInglés
Páginas (desde-hasta)995-999
Número de páginas5
PublicaciónDiscrete Mathematics
EstadoPublicada - 1 may 2017
Publicado de forma externa

Áreas temáticas de ASJC Scopus

  • Ciencia computacional teórica
  • Matemáticas discretas y combinatorias


Profundice en los temas de investigación de 'De Bruijn–Erdős-type theorems for graphs and posets'. En conjunto forman una huella única.

Citar esto