On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry (Q789732): Difference between revisions

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 \textit{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.