×

On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry. (English) Zbl 0533.52004

Let \(T^*(S,k)\) denote the number of straight lines containing at least k but less than 2k points of a given set S of noncollinear points in the Euclidean plane and \(t(n,k)=\max_{| S| =n}T^*(S,k).\) The author proves the following estimate: \(t^*(n,k)\leq c\cdot n^ 2/k^{2+\delta}\) with \(\delta =1/20\) for all \(2\leq k\leq(2n)^{1/2}\), where c denotes an absolute constant. Using this result the author deduces the following two theorems: Theorem 1. Let \(L_ 1,L_ 2,...,L_ t\) denote all possible connecting lines of the n-element coplanar point-set S. If \(\max_{1\leq i\leq t}| L_ i\cap S| =n- x\) (x, 0\(\leq x\leq n-2\) is arbitrary), then \(c_ 1\cdot x\cdot n<t\leq x(n-x)+(^ n\!_ 2)+1\leq 1+x\cdot n\). This theorem settles a conjecture of P. Erdős [Ann. Mat. Pura Appl., IV. Ser. 103, 99-108 (1975; Zbl 0303.52006), and Combinatorica 1, 25-42 (1981; Zbl 0486.05001)] in the affirmative sense. Theorem 2. For any point \(P\in S\) let f(S,P) denote the number of connecting lines through P and denote also by \(f(n)=\min_{| S| =n}\max_{P\in S}f(S,P)\). Then \(f(n)>c_ 2\cdot n\). Similar results are also given for other classes of curves such as unit circles and horocycles.
Reviewer: H.Kramer

MSC:

52A37 Other problems of combinatorial convexity
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Beck andJ. Spencer, Unit distances, submitted toJournal of Combinatorial Theory, Series A (1982) · Zbl 0551.05005
[2] H. S. M. Coxeter,Introduction to geometry, John Wiley and Sons, New York, 1961. · Zbl 0095.34502
[3] G. A. Dirac, Collinearity properties of sets of points,Quart. J. Math. 2 (1951) 221–227. · Zbl 0043.14602 · doi:10.1093/qmath/2.1.221
[4] P. Erdos, On some problems of elementary and combiratorial geometry,Annali di Mat. Pura et Applicata, Ser. IV. 103 (1975) 99–108. · Zbl 0303.52006 · doi:10.1007/BF02414146
[5] P. Erdos, Some applications of graph theory and combinatorial methods to number theory and geometry,Colloquia Math. Soc. János Bolyai, Algebraic methods in graph theory, Szeged (Hungary) (1978) 137–148.
[6] P. Erdos, On the combinatorial problems which I would most like to see solved,Combinatorica 1 (1981) 25–42. · Zbl 0486.05001 · doi:10.1007/BF02579174
[7] B. Grünbaum,Arrangements and spreads, Regional Conference Series in Mathematics 10, Amer. Math. Soc., 1972.
[8] E. Jucovič, Problem 24,Combinatorial structures and their applications, Gordon and Breach, New York, 1970.
[9] L. M. Kelly andW. Moser, On the number of ordinary lines determined byn points,Canad. J. Math. 10 (1958) 210–219. · Zbl 0081.15103 · doi:10.4153/CJM-1958-024-6
[10] W. Moser,Research problems in discrete geometry, Mimeograph notes, 1981. · Zbl 0528.52001
[11] T. S. Motzkin, The lines and planes connecting the points of a finite set,Trans. Amer. Math. Soc. 70 (1951) 451–464. · Zbl 0043.14603 · doi:10.1090/S0002-9947-1951-0041447-9
[12] E. Szemerédi andW. T. Trotter, Extremal problems in discrete geometry,Combinatorica 3 (3–4) (1983) 381–392. · Zbl 0541.05012 · doi:10.1007/BF02579194
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.