Банк задач по математике

Задача 8.1.1

Пусть даны $n$ точек на плоскости, не все точки лежат на одной прямой. Тогда найдётся прямая, которая пройдёт ровно через две точки.

?

Примечание.

?

Числом скрещиваний $\mathrm{cr}(\widetilde{G})$ изображения $\widetilde{G}$ графа на плоскости называется число пар таких пересекающихся рёбер, которые не имеют общих вершин.

Числом скрещиваний $\mathrm{cr}(G)$ графа $G$ называется минимальное число скрещиваний среди всех изображений графа на плоскости.

Планарные графы составляют ничтожную долю от всех графов: для планарности в графе должно быть «мало» рёбер, в то время как в «типичном» графе число рёбер квадратично по числу вершин. Поэтому вместо того, чтобы делить мир на чёрное и белое, планарные и непланарные графы, часто хочется классифицировать графы более тонко, по степени их «удалённости от планарных». Соответствующих характеристик непланарности несколько. Одна из главных — это число скрещиваний.

Задача 8.1.2

Докажите, что для любого графа $G$ с $n$ вершинами и $e$ рёбрами (числом скрещиваний $\mathrm{cr}(G)$ графа $G$ называется минимальное число скрещиваний среди всех изображений графа на плоскости, где числом скрещиваний изображения называется число пар таких пересекающихся рёбер, которые не имеют общих вершин) выполнено неравенство $\mathrm{cr}(G) \geq e - 3n$ .

?

Задача 8.1.3

(1)(2)

Дан граф $G$ с $n$ вершинами и $e$ рёбрами (числом скрещиваний $\mathrm{cr}(G)$ графа $G$ называется минимальное число скрещиваний среди всех изображений графа на плоскости, где числом скрещиваний изображения называется число пар таких пересекающихся рёбер, которые не имеют общих вершин).

?

(1)

Если $e \geq 4n$ , то $\mathrm{cr}(G) \geq \dfrac {e^{3}}{64 \cdot n^{2}}$ .

(2)

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

Задача 8.1.4

Пусть $P$ — множество некоторых точек на плоскости, $L$ — множество некоторых прямых на плоскости. Числом инциденций

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

называется количество пар вида (точка на прямой, прямая), где прямая и точка взяты из соответствующих множеств. Обозначим через $I(n, m)$ максимальное число инциденций для всех конфигураций из $n$ различных точек и $m$ различных прямых на плоскости.

Для произвольного $n$ верно неравенство $I(n, n) \geq n^{4/3}/3$ .

?

Задача 8.1.5

(1)(2)(3)

Числом инциденций

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

множества точек $P$ и множества прямых $L$ на плоскости называется количество пар вида (точка на прямой, прямая), где прямая и точка взяты из соответствующих множеств.

Пусть $P$ — множество из $n$ различных точек на плоскости, $L$ — множество из $m$ различных прямых. Пусть $G$ — граф, определяемый следующим образом. Вершины $G$ соответствуют точкам из множества $P$ , а ребро между двумя вершинами $G$ проводится, если и только если две соответствующие точки из множества $P$ лежат на какой-либо прямой из множества $L$ рядом, т.е. не разделены другой точкой из множества $P$ . Таким образом, рёбрам графа $G$ соответствуют отрезки прямых из множества $L$ . Пусть $e$ — число рёбер в графе $G$ .

?

(1)

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

(2)

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

(3)

Теорема Семереди--Троттера. $I(P, L) \leq 4(mn)^{2/3} + m + 4n$ .

Примечание.

?

Из задач 8.1.4 и 8.1.5 (3) следует, что $n^{4/3}/3 \leq I(n, n) \leq 9n^{4/3}$ . Важность этого результата, в частности, в том, что он показывает комбинаторные различия между плоскостью $\mathbb {R}^{2}$ и конечными проективными плоскостями. (См. указание к задаче 5.6.3, а также [J, 12.4].) Для них соответствующая формула выглядела бы как $cn^{3/2}$ . Из этой задачи выросла целая область, которая изучает различные обобщения данного вопроса, например, на случай полиномиальных кривых, пространств бо́льших размерностей и т.п. Кроме того, она тесно связана с задачами о расстояниях, которые мы обсудим ниже, и с вопросами о сложности геометрических конфигураций. Стоит отметить, что исторически первый вопрос в духе вопроса Эрдёша об инциденциях был поставлен Сильвестром ещё в XIX веке (см. задачу 8.1.1). Однако он не получил должного внимания.

Задача 8.1.6

Существует такое число $c$ , что для любых $n$ точек на плоскости верно следующее утверждение. Для $2 \leq k \leq \sqrt{n}$ число прямых, каждая из которых содержит по крайней мере $k$ из этих точек, не превосходит $cn^{2}/k^{3}$ .

?

Задача 8.1.7

Существует такое $c$ , что для любых $n$ точек плоскости количество неупорядоченных пар точек, находящихся на расстоянии $1$ , не превосходит $cn^{4/3}$ .

?

Задачи