Math Problems Vault

Problem 8.1.1

Let $n$ points be given in the plane, not all of them lying on one line. Then there is a line that passes through exactly two of the points.

?

Problem 8.1.2

Prove that for every graph $G$ with $n$ vertices and $e$ edges (the crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of crossings over all drawings of the graph in the plane, where the number of crossings of a drawing is the number of pairs of intersecting edges that have no common vertices) the inequality $\mathrm{cr}(G) \geq e - 3n$ holds.

?

Problem 8.1.3

(1)(2)

Given a graph $G$ with $n$ vertices and $e$ edges (the crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of crossings over all drawings of the graph in the plane, where the number of crossings of a drawing is the number of pairs of intersecting edges that have no common vertices).

?

(1)

If $e \geq 4n$ , then $\mathrm{cr}(G) \geq \dfrac {e^{3}}{64 \cdot n^{2}}$ .

(2)

$\mathrm{cr}(G) \geq \dfrac {e^{3}}{64 \cdot n^{2}} - n$ .

Problem 8.1.4

Let $P$ be a set of points in the plane and $L$ a set of lines in the plane. The number of incidences

I(P, L) := \left|\left\{ (p, l) \in P \times L : p \in l\right\} \right|

is the number of pairs of the form (point on a line, line), where the line and the point are taken from the respective sets. Denote by $I(n, m)$ the maximum number of incidences over all configurations of $n$ distinct points and $m$ distinct lines in the plane.

For arbitrary $n$ the inequality $I(n, n) \geq n^{4/3}/3$ holds.

?

Problem 8.1.5

(1)(2)(3)

The number of incidences

I(P, L) := \left|\left\{ (p, l) \in P \times L : p \in l\right\} \right|

of a set of points $P$ and a set of lines $L$ in the plane is the number of pairs of the form (point on a line, line), where the line and the point are taken from the respective sets.

Let $P$ be a set of $n$ distinct points in the plane and $L$ a set of $m$ distinct lines. Let $G$ be the graph defined as follows. The vertices of $G$ correspond to the points of the set $P$ , and an edge between two vertices of $G$ is drawn if and only if the two corresponding points of the set $P$ lie next to each other on some line of the set $L$ , i.e., are not separated by another point of the set $P$ . Thus the edges of the graph $G$ correspond to segments of lines from the set $L$ . Let $e$ be the number of edges in the graph $G$ . The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of crossings over all drawings of the graph in the plane, where the number of crossings of a drawing is the number of pairs of intersecting edges that have no common vertices.

?

(1)

$\mathrm{cr}(G) \leq m^{2}$ .

(2)

$e \geq I(P, L) - m$ .

(3)

The Szemerédi--Trotter theorem. $I(P, L) \leq 4(mn)^{2/3} + m + 4n$ .

Remark.

?

It follows from Problems 8.1.4 and 8.1.5 (3) that $n^{4/3}/3 \leq I(n, n) \leq 9n^{4/3}$ . The importance of this result lies, in particular, in the fact that it shows the combinatorial differences between the plane $\mathbb {R}^{2}$ and finite projective planes. (See the hint to Problem 5.6.3, and also [J, 12.4].) For them the corresponding formula would look like $cn^{3/2}$ . A whole field has grown out of this problem, studying various generalizations of this question, for example, to the case of polynomial curves, spaces of higher dimensions, etc. Moreover, it is closely related to problems on distances, which we discuss below, and to questions on the complexity of geometric configurations. It is worth noting that historically the first question in the spirit of Erdős's question on incidences was posed by Sylvester as early as the 19th century (see Problem 8.1.1). However, it did not receive due attention.

Problem 8.1.6

There exists a number $c$ such that for any $n$ points in the plane the following statement holds. For $2 \leq k \leq \sqrt{n}$ the number of lines each of which contains at least $k$ of these points does not exceed $cn^{2}/k^{3}$ .

?

Problem 8.1.7

There exists $c$ such that for any $n$ points of the plane the number of unordered pairs of points at distance $1$ does not exceed $cn^{4/3}$ .

?