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.
Áreas temáticas de ASJC Scopus
- Ciencia computacional teórica
- Matemáticas discretas y combinatorias