An Improvement of the Lower Bound on the Minimum Number of ≤k-Edges

Abstract

In this paper, we improve the lower bound on the minimum number of $\le k$-edges in sets of n points in general position in the plane when k is close to $\frac{n}{2}$. As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph $K_n$ for some values of n.

1. Introduction

The search for lower bounds for the minimum number of $\le k$-edges in sets of n points of the plane for $n \ge 2$$k+2$ ($e_{ \le k}\left(n\right)$) is an important task in Combinatorial Geometry, due to its relation with the rectilinear crossing number problem. The most well-known case of the rectilinear crossing number problem aims to find the number $\overline{cr}\left(P\right)$ of crossings in a complete graph with a set of vertices P consisting of n points in the plane (in general position) and edges represented by segments and the minimum number of crossings over P, $\overline{cr}\left(n\right)$ (see the definitions below). The idea of determining $\overline{cr}\left(n\right)$ for each n was firstly considered by Erdös and Guy (see [1,2]). Determining $\overline{cr}\left(n\right)$ is equivalent to finding the minimum number of convex quadrilaterals defined by n points in the plane. These kinds of problems belong to classical combinatorial geometry problems (Erdös-Szekeres problems). The study of $\overline{cr}\left(n\right)$ is also interesting from the point of view of Geometric Probability. It is connected with the Sylvester Four-Point Problem, in which Sylvester studies the probability of four random points in the plane forming a convex quadrilateral.

Nowadays, finding the value of $\overline{cr}\left(n\right)$ continues to be a challenging open problem. The exact value of $\overline{cr}\left(n\right)$ is known for $n \le 27$ and $n=30$. The search of lower and upper asymptotic bounds of $\overline{cr}\left(n\right)$ constitutes a relevant task due to its connection with the problem of finding the value of the Sylvester Four-Point Constant $q_{*}$. In order to define properly $q_{*}$, it is necessary to consider a convex open set R in the plane with finite area. Let $q\left(R\right)$ be the probability that four points chosen randomly from R define a convex quadrilateral. Whence, $q_{*}$ is defined as the infimum of $q\left(R\right)$ taken over all open sets R.

In particular, the connection between $q_{*}$ and $\overline{cr}\left(n\right)$ is given by the following expression:

$${\displaystyle q_{*}=\underset{n\to \infty }{lim}\frac{\overline{cr}\left(n\right)}{\left(\genfrac{}{}{0pt}{}{n}{4}\right)}}$$

For more details, see [3].

The rigorous definitions of the above-presented concepts are the following:

Definition 1.

Given a finite set of points in general position in the plane P, assume that we join each pair of points of P with a straight line segment. The rectilinear crossing number of P ($\overline{cr}\left(P\right)$ ) is the number of intersections out of the vertices of said segments. The rectilinear crossing number of n ( $\overline{cr}\left(n\right)$) is the minimum of $\overline{cr}\left(P\right)$ over all the sets P with n points.

Definition 2.

Given a set of points in general position, $A=\left\{p_1,...,p_n\right\}$ and an integer number k such that $0 \le k \le \frac{n-2}{2}$, a k-edge of A is a line R that joins two points of A and leaves exactly k points of A in one of the open half-planes (it is named the k-half plane of R).

Definition 3.

Given a set of points in general position, $A=\left\{p_1,...,p_n\right\}$, a $\le k$-edge of A is an i-edge of A with $i \le k$.

Notation 1.

We call $e_k\left(P\right)$ the number of $k-$edges of the set P and $e_k\left(n\right)$ the maximum number of $e_k\left(P\right)$ over all the sets P with n points.

The relation between the number of $\le k$-edges of P and $\overline{cr}\left(P\right)$ is given by the expression:

$$\overline{cr}\left(P\right)=\sum _{k=0}^{⌊\frac{n-2}{2}⌋-2}\left(n-2k-3\right)e_{ \le k}\left(P\right)-\frac{3}{4}\left(\begin{array}{c}n\\ 3\end{array}\right)+\left(1+{\left(-1\right)}^{n+1}\right)\frac{1}{8}\left(\begin{array}{c}n\\ 2\end{array}\right),$$

(1)

where $e_{ \le k}\left(P\right)$ is the number of $\le k$-edges of the set P with $\left|P\right|=n$ (see [4,5]). This implies that

$$\overline{cr}\left(n\right) \ge \sum _{k=0}^{⌊\frac{n-2}{2}⌋-2}\left(n-2k-3\right)e_{ \le k}\left(n\right)-\frac{3}{4}\left(\begin{array}{c}n\\ 3\end{array}\right)+\left(1+{\left(-1\right)}^{n+1}\right)\frac{1}{8}\left(\begin{array}{c}n\\ 2\end{array}\right).$$

(2)

This way, improvements of the lower bound of $e_{ \le k}\left(n\right)$ for $k \le ⌊\frac{n-2}{2}⌋-2$ yield an improvement of the lower bound of the rectilinear crossing number of n. The exact value of $e_{ \le k}\left(n\right)$ is known for $k<⌈\frac{4n-11}{9}⌉$ (see [4,6,7]). For $k \ge ⌈\frac{4n-11}{9}⌉$, the current best lower bound of $e_{ \le k}\left(n\right)$ is $e_{ \le k}\left(n\right) \ge u_k$ for the sequence $u_k$ defined in [6].

Taking into account the asymptotic equivalence of $u_k$, we have

$$e_{ \le k}\left(n\right) \ge \left(\begin{array}{c}n\\ 2\end{array}\right)-\frac{1}{9}\sqrt{\frac{n-2k-2}{n}}\left(5n^2+19n+31\right).$$

(3)

For k close to $⌊\frac{n-2}{2}⌋-2$, namely $k=⌊\frac{n-t}{2}⌋$ for some fixed constant t, the bound (3) gives

$$e_{ \le k}\left(n\right) \ge \left(\begin{array}{c}n\\ 2\end{array}\right)-O\left(n^{\frac{3}{2}}\right).$$

(4)

For these values of k, if we define P as a set for which $e_{ \le k}\left(n\right)$ is attained and $e_s\left(P\right)$ as the number of s-edges of P (see the definitions below), then we have that the identity: $e_{ \le k}\left(n\right)=\left(\begin{array}{c}n\\ 2\end{array}\right)-\left(e_{k+1}\left(P\right)+...+e_{⌊\frac{n-2}{2}⌋}\left(P\right)\right)$ together with the current best upper bound of $e_s\left(P\right)$ (due to Dey, see [8]) yield a lower bound that is asymptotically better than (4). More precisely, in [8] was shown the existence of a constant $C \le 6.48$ such that

$$e_s\left(P\right) \le Cn{\left(s+1\right)}^{\frac{1}{3}},$$

(5)

for $s<\frac{n-2}{2}$ and

$$e_s\left(P\right) \le Cn{\left(\frac{n-1}{2}\right)}^{\frac{1}{3}},$$

(6)

for $s=\frac{n-2}{2}$.To do this, Dey in [8] applied the crossing lemma and the following values for $E(<=s)\left(n\right)$, the maximum number of $(<=s)$-edges due to [9]

$$E(<=s)\left(n\right)=s(k+1)\mathrm{for}s<(n-2)/2,E(<=(n-2)/2)\left(n\right)=n(n-1)/2.$$

The best values for C are $C={\left(\frac{\mathrm{31,827}}{2^{10}}\right)}^{\frac{1}{3}}$ for $s<\frac{n-2}{2}$ and $C={\left(\frac{\mathrm{31,827}}{2^{12}}\right)}^{\frac{1}{3}}$ for $s=\frac{n-2}{2}$, for n an even number, if $e_s\left(P\right) \ge \frac{103n}{6}$, (see [10,11]). Notice that this condition is satisfied for large n and s close to $\frac{n}{2}$ due to the best lower bound of $e_s\left(n\right)$. As an example, for $s=\frac{n-3}{2}$ we have the upper bound (5) for $n \ge 327$ and, for $s=\frac{n-5}{2}$, we have the upper bound (5) for $n \ge 329$.

This gives:

$$e_{ \le k}\left(n\right) \ge \left(\begin{array}{c}n\\ 2\end{array}\right)-Cn\sum _{i=k+1}^{⌊\frac{n-2}{2}⌋}{(i+1)}^{\frac{1}{3}},$$

(7)

for n an odd number and

$$e_{ \le k}\left(n\right) \ge \left(\begin{array}{c}n\\ 2\end{array}\right)-\left(Cn\sum _{i=k+1}^{\frac{n-4}{2}}{(i+1)}^{\frac{1}{3}}+Cn{\left(\frac{n-1}{2}\right)}^{\frac{1}{3}}\right),$$

(8)

for n an even number. In this paper we improve in, at most, $⌊\frac{t}{4}⌋$ the bounds (7) and (8) for $k=⌊\frac{n-t}{2}⌋$ and some big values of n. In this way, we achieve the best lower bound of $e_{ \le k}\left(n\right)$ for these values of k and n. As a consequence, we improve the lower bound of the rectilinear crossing number of $K_n$.

The outline of the rest of the paper is as follows: In Section 2 we give the improvement of the lower bound of $e_{ \le k}\left(n\right)$, $k=⌊\frac{n-t}{2}⌋$, for the cases $t=7$ (n is an odd number) and $t=8$ (n is an even number). In Section 3, we generalize the achieved results in Section 2, and in Section 4 we give some concluding remarks.

2. The Improvement of the Lower Bound

In order to get the improvement of the lower bound of $e_{ \le k}\left(n\right)$, we need the following lemma:

Lemma 1.

Let k and n be positive integers, and let P be a set of n points in general position in the plane. If $k<⌊\frac{n-2}{2}⌋$, then

$$e_k\left(n-1\right) \ge \frac{n-k-2}{n}{e}_k\left(P\right) + \frac{k + 1}{n}{e}_{k + 1}\left(P\right).$$

(9)

Proof. 

Each $\left(k+1\right)$-edge of P leaves $k+1$ points of P in its $\left(k+1\right)$-half plane, and each k-edge of P leaves $n-k-2$ points of P in one of its half-planes. Therefore, the total number of points of P in these planes, allowing repetitions, is

$$\left(n-k-2\right)e_k\left(P\right) + \left(k + 1\right)e_{k + 1}\left(P\right),$$

(10)

and then there is a point of P, say $p_n$, that belongs to s half-planes with

$$s \ge \frac{n-k-2}{n}{e}_k\left(P\right) + \frac{k + 1}{n}{e}_{k + 1}\left(P\right).$$

(11)

If we remove $p_n$, then we obtain a set $Q=\left\{p_1,...,p_{n-1}\right\}$ such that the $\left(k+1\right)$-edges of P corresponding to the s half-planes are now k-edges of Q, because they have $\left(k+1\right)-1=k$ points of Q in one of the open half-planes.

Moreover, the k-edges of P corresponding to the s half-planes are now k-edges of Q because they still have k points of Q in one of the open half-planes. Therefore, we have that

$$e_k\left(n-1\right) \ge e_k\left(Q\right) \ge s \ge \frac{n-k-2}{n}{e}_k\left(P\right) + \frac{k + 1}{n}{e}_{k + 1}\left(P\right)$$

(12)

as desired. □

Corollary 1.

Let k and n be positive integers, and let P be a set of n points in general position in the plane. If $k<⌊\frac{n-2}{2}⌋$, then

$$min\left\{e_k\left(P\right),e_{k+1}\left(P\right)\right\} \le ⌊\frac{n}{n-1}{e}_k\left(n-1\right)⌋.$$

(13)

Proof. 

Applying Lemma 1, we obtain

$$e_k\left(n-1\right) \ge \frac{n-k-2}{n}{e}_k\left(P\right) + \frac{k+1}{n}{e}_{k+1}\left(P\right) \ge \frac{n-1}{n}min\left\{e_k\left(P\right),e_{k+1}\left(P\right)\right\}.$$

(14)

This implies the desired result. □

Corollary 2.

Let k and n be positive integers, and let P be a set of n points in general position in the plane. If $k<⌊\frac{n-2}{2}⌋$, then

$$min\left\{e_k\left(P\right),e_{k+1}\left(P\right)\right\} \le ⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{10}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(k+1\right)}^{\frac{1}{3}}⌋⌋.$$

(15)

Proof. 

The result follows from Corollary 1 and inequality (5). □

Remark 1.

For fixed k and some values of $n,$ the bound in Corollary 2 may improve by one the following upper bound of $min\left\{e_k\left(P\right),e_{k+1}\left(P\right)\right\}$ derived from (5)

$$\begin{array}{c}min\left\{e_k\left(P\right),e_{k+1}\left(P\right)\right\} \le min\left\{⌊{\left(\frac{\mathrm{31,827}}{2^{10}}\right)}^{\frac{1}{3}}n{\left(k+1\right)}^{\frac{1}{3}}⌋,⌊{\left(\frac{\mathrm{31,827}}{2^{10}}\right)}^{\frac{1}{3}}n{\left(k+2\right)}^{\frac{1}{3}}⌋\right\}=\hfill \\ \hfill ⌊{\left(\frac{\mathrm{31,827}}{2^{10}}\right)}^{\frac{1}{3}}n{\left(k+1\right)}^{\frac{1}{3}}⌋.\end{array}$$

(16)

We will apply this improvement to shift the lower bound on the number of $\le k$-edges for sets with n points in the cases $k=\frac{n-7}{2}$ and $k=\frac{n-8}{2}$ for some values of n.

Corollary 3.

Let $n \ge 7$ be an odd integer, and let $k:=(n-7)/2$. Then

$$e_{ \le k}\left(n\right) \ge \frac{n^2-n}{2}-⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-3\right)}^{\frac{1}{3}}⌋⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋.$$

(17)

Proof. 

Let P be a set of n points in general position attaining $e_{ \le k}\left(n\right)$. From (7), it follows that

$$\begin{array}{c}{e}_{ \le k}\left(n\right)=\frac{n^2-n}{2}-e_{\frac{n-5}{2}}\left(P\right)-e_{\frac{n-3}{2}}\left(P\right)=\frac{n^2-n}{2}-min\left\{e_{\frac{n-5}{2}}\left(P\right),e_{\frac{n-3}{2}}\left(P\right)\right\}\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-max\left\{e_{\frac{n-5}{2}}\left(P\right),e_{\frac{n-3}{2}}\left(P\right)\right\}.\end{array}$$

(18)

Thus, we obtain the desired result by applying Corollary 2 to $k=\frac{n-5}{2}$ and the following upper bound of $max\left\{e_{\frac{n-5}{2}}\left(P\right),e_{\frac{n-3}{2}}\left(P\right)\right\}$ derived from (5)

$$\begin{array}{c}max\left\{e_{\frac{n-5}{2}}\left(P\right),e_{\frac{n-3}{2}}\left(P\right)\right\} \le max\left\{⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-3\right)}^{\frac{1}{3}}⌋,⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋\right\}=\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋.\end{array}$$

(19)

□

Remark 2.

Comparing with the upper bound of $u_{\frac{n-7}{2}}$ included in Lemma 1 of [6], we obtain that for $n \ge$ 33,623, the lower bound:

$$e_{ \le \frac{n-7}{2}}\left(n\right) \ge \frac{n^2-n}{2}-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-3\right)}^{\frac{1}{3}}⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋$$

(20)

is better than the lower bound for $e_{ \le \frac{n-7}{2}}\left(n\right)$ of [6]. For these values of n, the lower bound (17) sometimes improves (20) by one and is the best current lower bound of $e_{ \le \frac{n-7}{2}}\left(n\right)$. As an example, we get the improvement for the following odd values of n:

33,627, 33,629, 33,637, 33,639, 33,641, 33,647, 33,649, 33,651, 33,653, 33,661, 33663, 33,665, 33,667, 33,677, 33,679, 33,681, 33,683, 33,685, 33,687, 33,713, 33,715, 33,717, 33,719, 33,721, 33,723.

Remark 3.

Plugging (17) in (2), we obtain an improvement of 4 for the lower bound of $\overline{cr}\left(n\right)$ for the aforementioned odd values of n in the range $\left[33623,33723\right]$ because the coefficient of $e_{ \le \frac{n-7}{2}}\left(n\right)$ in (2) is 4.

Corollary 4.

Let $n \ge 8$ be an even integer, and let $k:=(n-8)/2$. Then

$$\begin{array}{c}{e}_{ \le k}\left(n\right) \ge \frac{n^2-n}{2}-⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-4\right)}^{\frac{1}{3}}⌋⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋-\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{13}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋.\end{array}$$

(21)

Proof. 

Let P be a set of n points in general position attaining $e_{ \le k}\left(n\right)$. From (8), it follows that

$$e_{ \le k}\left(n\right)=\frac{n^2-n}{2}-min\left\{e_{\frac{n-6}{2}}\left(P\right),e_{\frac{n-4}{2}}\left(P\right)\right\}-max\left\{e_{\frac{n-6}{2}}\left(P\right),e_{\frac{n-4}{2}}\left(P\right)\right\}-e_{\frac{n-2}{2}}\left(P\right).$$

(22)

Then we obtain the desired result by applying Corollary 2 to $k=\frac{n-6}{2}$, (6) and the following upper bound of $max\left\{e_{\frac{n-6}{2}}\left(P\right),e_{\frac{n-4}{2}}\left(P\right)\right\}$ derived from (5):

$$\begin{array}{c}max\left\{e_{\frac{n-6}{2}}\left(P\right),e_{\frac{n-4}{2}}\left(P\right)\right\} \le max\left\{⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-4\right)}^{\frac{1}{3}}⌋,⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋\right\}=\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋.\end{array}$$

(23)

□

Remark 4.

Comparing with the upper bound of $u_{\frac{n-8}{2}}$ included in Lemma 1 of [6], we obtain that for $n \ge$ 63,370, the lower bound

$$\begin{array}{c}{e}_{ \le \frac{n-8}{2}}\left(n\right) \ge \frac{n^2-n}{2}-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-4\right)}^{\frac{1}{3}}⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋-\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{13}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋\end{array}$$

(24)

is better than the lower bound for $e_{ \le \frac{n-8}{2}}\left(n\right)$ of [6]. For these values of n, the lower bound included in Corollary 4 sometimes improves (24) by one, and then it is the best current lower bound of $e_{ \le \frac{n-8}{2}}\left(n\right)$. As an example, we get the improvement for the following values of n:

63,374, 63,380, 63,386, 63,392, 63,398, 63,404, 63,408, 63,410, 63,414, 63,416, 63420, 63,426, 63,430, 63,436, 63,440, 63,446, 63,450, 63,454, 63,456, 63,460, 63,464, 63,468.

Remark 5.

Plugging the lower bound included in Corollary 4 in (2), we obtain an improvement of 5 for the lower bound of $\overline{cr}\left(n\right)$ for the aforementioned values of n in the range $\left[\mathrm{63,370},\mathrm{63,470}\right]$ because the coefficient of $e_{ \le \frac{n-8}{2}}\left(n\right)$ in (2) is 5.

3. Generalization

We can apply Corollary 2 to improve the lower bound of $e_{ \le \frac{n-t}{2}}\left(n\right)$ in at most $⌊\frac{t}{4}⌋$ for fixed t, $n>t$, n and t with the same parity, by a generalization of the Corollaries 3 and 4.

Proposition 1.

It is satisfied that

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right) \ge \frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-7}{4}}(⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-\left(4s+3\right)\right)}^{\frac{1}{3}}⌋⌋+\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n+2-\left(4s+3\right)\right)}^{\frac{1}{3}}⌋)\end{array}$$

(25)

for odd n, $t\equiv 3\left(4\right)$, $t \ge 7$,

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right) \ge \frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-5}{4}}(⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-\left(4s+1\right)\right)}^{\frac{1}{3}}⌋⌋+\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n+2-\left(4s+1\right)\right)}^{\frac{1}{3}}⌋)-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋\end{array}$$

(26)

for odd n, $t\equiv 1\left(4\right)$, $t \ge 5$,

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right) \ge \frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-4}{4}}(⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-4s\right)}^{\frac{1}{3}}⌋⌋+\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n+2-4s\right)}^{\frac{1}{3}}⌋)-⌊{\left(\frac{\mathrm{31,827}}{2^{13}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋\end{array}$$

(27)

for even n, $t\equiv 0\left(4\right)$, $t \ge 4$ and

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right) \ge \frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-6}{4}}(⌊\frac{n}{n-1}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}\left(n-1\right){\left(n-(4s+2)\right)}^{\frac{1}{3}}⌋⌋+\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n+2-(4s+2)\right)}^{\frac{1}{3}}⌋)-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{13}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋\end{array}$$

(28)

for even n, $t\equiv 2\left(4\right)$, $t \ge 6$.

Proof. 

Assume that P is a set in which $e_{ \le \frac{n-t}{2}}\left(n\right)$ is attained. For odd n, $t\equiv 3\left(4\right)$, $t \ge 7$ we have that:

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right)=\frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-7}{4}}\left(e_{\frac{n-\left(4s+3\right)}{2}}\left(P\right)+e_{\frac{n-2-\left(4s+3\right)}{2}}\left(P\right)\right)=\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{n^2-n}{2}-\sum _{s=0}^{\frac{t-7}{4}}\left(min\left\{e_{\frac{n-\left(4s+3\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+3\right)}{2}}\left(P\right)\right\}+max\left\{e_{\frac{n-\left(4s+3\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+3\right)}{2}}\left(P\right)\right\}\right).\end{array}$$

(29)

For odd n, $t\equiv 1\left(4\right)$,$t \ge 5$ we have that:

$$\begin{array}{cc}& e_{ \le \frac{n-t}{2}}\left(n\right)=\frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-5}{4}}\left(e_{\frac{n-\left(4s+1\right)}{2}}\left(P\right)+e_{\frac{n-2-\left(4s+1\right)}{2}}\left(P\right)\right)-e_{\frac{n-3}{2}}\left(P\right)=\hfill \\ & \frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-5}{4}}\left(min\left\{e_{\frac{n-\left(4s+1\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+1\right)}{2}}\left(P\right)\right\}+max\left\{e_{\frac{n-\left(4s+1\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+1\right)}{2}}\left(P\right)\right\}\right)-e_{\frac{n-3}{2}}\left(P\right).\hfill \end{array}$$

(30)

For even n, $t\equiv 0\left(4\right)$, $t \ge 4$ we have that:

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right)=\frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-4}{4}}\left(e_{\frac{n-4s}{2}}\left(P\right)+e_{\frac{n-2-4s}{2}}\left(P\right)\right)-e_{\frac{n-2}{2}}\left(P\right)=\hfill \\ \hfill \frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-4}{4}}\left(min\left\{e_{\frac{n-4s}{2}}\left(P\right),e_{\frac{n-2-4s}{2}}\left(P\right)\right\}+max\left\{e_{\frac{n-4s}{2}}\left(P\right),e_{\frac{n-2-4s}{2}}\left(P\right)\right\}\right)-e_{\frac{n-2}{2}}\left(P\right).\end{array}$$

(31)

For even n, $t\equiv 2\left(4\right)$, $t \ge 6$ we have that:

$$\begin{array}{c}{e}_{ \le \frac{n-t}{2}}\left(n\right)=\frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-6}{4}}\left(e_{\frac{n-\left(4s+2\right)}{2}}\left(P\right)+e_{\frac{n-2-\left(4s+2\right)}{2}}\left(P\right)\right)-e_{\frac{n-4}{2}}\left(P\right)-e_{\frac{n-2}{2}}\left(P\right)=\hfill \\ \frac{n^2-n}{2}-\sum _{s=1}^{\frac{t-6}{4}}\left(min\left\{e_{\frac{n-\left(4s+2\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+2\right)}{2}}\left(P\right)\right\}+max\left\{e_{\frac{n-\left(4s+2\right)}{2}}\left(P\right),e_{\frac{n-2-\left(4s+2\right)}{2}}\left(P\right)\right\}\right)\\ \hfill -e_{\frac{n-4}{2}}\left(P\right)-e_{\frac{n-2}{2}}\left(P\right).\end{array}$$

(32)

Then we have the desired results by applying the bound of Corollary 2, (5), and (6). □

Remark 6.

As an example, for $t=11\equiv 3\left(4\right)$ and n an odd number, we obtain that for $n \ge$ 122,487, the lower bound

$$\begin{array}{c}{e}_{ \le \frac{n-11}{2}}\left(n\right) \ge \frac{n^2-n}{2}-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-3\right)}^{\frac{1}{3}}⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-1\right)}^{\frac{1}{3}}⌋-\hfill \\ \hfill ⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-7\right)}^{\frac{1}{3}}⌋-⌊{\left(\frac{\mathrm{31,827}}{2^{11}}\right)}^{\frac{1}{3}}n{\left(n-5\right)}^{\frac{1}{3}}⌋\end{array}$$

(33)

is better than the lower bound for $e_{ \le \frac{n-11}{2}}\left(n\right)$ of [6]. For these values of n, the lower bound included in Proposition 1 sometimes improves (33) by two, and then it is the best current lower bound of $e_{ \le \frac{n-11}{2}}\left(n\right)$. As a matter of fact, we get the improvement for every odd value of n in the range $\left[\mathrm{122,487},\mathrm{122,587}\right]$ except for the following values: 122,533, 122,547, 122,577, 122,583.

4. Conclusions

We have improved the current lower bound on the maximum number of $\le k$-edges for planar sets of n points when k is close to $\frac{n}{2}$ for some values of n. To do this, we have applied an upper bound of $min\left\{e_k\left(P\right),e_{k-1}\left(P\right)\right\}$ that is a function of $e_k\left(n-1\right)$, where $e_s\left(P\right)$ is the number of s-edges of a set P of n points, and $e_k\left(n-1\right)$ is the maximum number of k-edges over all the sets Q with $n-1$ points. This sometimes improves by one the upper bound of $min\left\{e_k\left(P\right),e_{k-1}\left(P\right)\right\}$ due to Dey (see [8]).

As a consequence, we have shifted the lower bound of the rectilinear crossing number of n points in the plane for some large values of n. This reduces the gap with the current best upper bound for these values of n, closing in the exact value of $\overline{cr}\left(n\right)$.

An open problem is to determine whether these improvements are attained for infinite values of n. In order to do this, it is enough to prove that, for k close to $\frac{n}{2}$ and, for infinite values of n, the bound of expression (15) improves by one unit the bound of (16).