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

2015/01/27 by Pierre Aboulker, Guillaume Lagarde, Aboulker, Pierre +7
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1501.06681

openalex publication_date 2015/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 graphs. Restricting our attention to comparability graphs, we obtain a version of the De Bruijn-Erdős theorem for partially ordered sets (posets). Moreover, in this case, we have an improved bound on the number of lines depending on the height of the poset. The extremal configurations are also determined.

Related

• Graphs with no induced house nor induced hole have the de\n Bruijn-Erd Hos property
• Towards a de Bruijn-Erd\H os theorem in the L₁-metric
• Graph metric with no proper inclusion between lines
• Combining the theorems of Turán and de Bruijn-Erd\H os
• The de Bruijn-Erdös theorem in incidence geometry via Ph. Hall's marriage theorem