Number of lines in hypergraphs

Abstract

Chen and Chvátal introduced the notion of lines in hypergraphs; they proved that every 3-uniform hypergraph with $n$ vertices either has a line that consists of all $n$ vertices or else has at least ${\log }_{2}n$ distinct lines. We improve this lower bound by a factor of $2-o(1)$.

References in corpus (1)

• Towards a de Bruijn-Erd\H os theorem in the $L_1$-metric

Cited by in corpus (1)

• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs