Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
line in metric space; De Bruijn-Erd\H os theorem
line in metric space; De Bruijn-Erd\H os theorem
Summary:
A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces where each nonzero distance equals $1$ or $2$.
References:
[1] Aboulker, P., Bondy, A., Chen, X., Chiniforooshan, E., Miao, P.: Number of lines in hypergraphs. Discrete Appl. Math. 171 (2014), 137-140. DOI 10.1016/j.dam.2014.02.008 | MR 3190588 | Zbl 1288.05185
[2] Chen, X., Chvátal, V.: Problems related to a De Bruijn-Erdős theorem. Discrete Appl. Math. 156 (2008), 2101-2108. DOI 10.1016/j.dam.2007.05.036 | MR 2437004 | Zbl 1157.05019
[3] Chiniforooshan, E., Chvátal, V.: A De Bruijn-Erdős theorem and metric spaces. Discrete Math. Theor. Comput. Sci. 13 (2011), 67-74. MR 2812604 | Zbl 1283.52022
[4] Bruijn, N. G. De, Erdős, P.: On a combinatorial problem. Proc. Akad. Wet. Amsterdam 51 (1948), 1277-1279. MR 0028289 | Zbl 0032.24405
[5] Erdős, P.: Three point collinearity, Problem 4065. Am. Math. Mon. 50 (1943), 65; Solutions in vol. 51 (1944), 169-171. MR 1525919
Search
Partner of
