Неравенство пересекающихся чисел

В математике отрисовки графика, неравенства пересекающихся чисел или лемма о пересечении дает нижнюю границу на минимальное количество пересечений данного графа как функцию количества ребер и вершин графа график. В нем говорится, что для графов, в которых число ребер e значительно больше числа вершин n, число пересечений по крайней мере пропорционально e / n.

Он имеет приложения в СБИС и комбинаторная геометрия, и был независимо открыт Аджтаи, Хватал, новорожденный, и Семереди и Лейтон.

• 1 Заявление и история
• 2 Приложения
• 3 Доказательство
• 4 Варианты
• 5 Ссылки

Неравенство числа пересечений утверждает, что для неориентированного простого графа G с n вершинами и e ребрами, такими, что e>7n, число пересечений cr ( G) подчиняется неравенству

$cr\; \; (G)\; \ge \; e\; 3\; 29\; n\; 2.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cr\}\; (G)\; \backslash \; geq\; \{\backslash \; frac\; \{e\; ^\; \{3\}\}\; \{29n\; ^\; \{2\}\}\}.\}$

Константа 29 является наиболее известной на сегодняшний день и связана с Акерман. Более ранние результаты с более слабыми константами см. В Pach Tóth (1997) и Pach et al. (2006). Константу 7 можно уменьшить до 4, но за счет замены 29 худшей константой 64.

Важно различать число пересечений cr (G) и парное число пересечений-cr (ГРАММ). Как отмечено Pach Tóth (2000), число парных пересечений $pair-cr\; (G)\; \le \; cr\; (G)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{pair-cr\}\}\; (G)\; \backslash \; leq\; \{\backslash \; text\; \{cr\}\}\; (G)\}$относится к минимальному количеству пар ребер, каждая из которых определяет одно пересечение, тогда как число пересечений просто относится к минимальному количеству пересечений. (Это различие необходимо, поскольку некоторые авторы предполагают, что на правильном рисунке никакие две кромки не пересекаются более одного раза.)

Мотивация Лейтона к изучению числа пересечений заключалась в применении к СБИС проектирование в теоретической информатике.

Позже Секели (1997) понял, что это неравенство дает очень простые доказательства некоторых важных теорем в геометрии инцидентности. Например, теорема Семереди – Троттера, верхняя граница количества инцидентов, которые возможны между заданным количеством точек и прямых на плоскости, следует путем построения графа, вершины которого точки, а ребра - отрезки прямых между точками инцидента. Если бы инцидентностей было больше, чем граница Семереди – Троттера, этот граф обязательно имел бы больше пересечений, чем общее количество пар прямых, что невозможно. Неравенство также может быть использовано для доказательства теоремы Бека о том, что если конечный набор точек не имеет линейного числа коллинеарных точек, то он определяет квадратичное количество различных прямых. Точно так же Тамал Дей использовал его для доказательства верхних оценок на геометрических k-множеств.

Сначала мы дадим предварительную оценку: для любого графа G с n вершинами и e рёбер, имеем

$cr\; \; (G)\; \ge \; e\; -\; 3\; n.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cr\}\; (G)\; \backslash \; geq\; e-3n.\}$

Чтобы доказать это, рассмотрим диаграмму G, которая имеет ровно cr (G) пересечений. Каждое из этих пересечений можно удалить, удалив ребро из G. Таким образом, мы можем найти граф с не менее чем e - cr (G) ребрами и n вершинами без пересечений, и, таким образом, это плоский граф. Но тогда из формулы Эйлера должно быть e - cr (G) ≤ 3n, и утверждение следует. (На самом деле e - cr (G) ≤ 3n - 6 при n ≥ 3).

Чтобы получить фактическое неравенство числа пересечений, мы теперь используем вероятностный аргумент . Мы позволяем выбрать параметр 0 < p < 1 be a вероятность позже и строим случайный подграф H графа G, позволяя каждой вершине G лежать в H независимо с вероятностью p и допуская ребро G лежит в H тогда и только тогда, когда его две вершины были выбраны лежащими в H. Пусть e H, n H и cr H обозначают количество ребра, вершины и пересечения H соответственно. Поскольку H является подграфом G, диаграмма G содержит диаграмму H. По предварительному неравенству числа пересечений

$cr\; H\; \ge \; e\; H\; -\; 3\; n\; H.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cr\}\; \_\; \{H\}\; \backslash \; geq\; e\_\; \{H\}\; -3n\_\; \{H\}.\}$

Принимая ожидания, получаем

$E\; [cr\; H]\; \ge \; E\; [e\; H]\; -\; 3\; E\; [n\; H].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{E\}\; [\backslash \; operatorname\; \{cr\}\; \_\; \{H\}]\; \backslash \; geq\; \backslash \; mathbf\; \{E\}\; [e\_\; \{H\}]\; -\; 3\; \backslash \; mathbf\; \{E\}\; [n\_\; \{H\}].\}$

Поскольку каждая из n вершин в G имела вероятность p оказаться в H, мы имеем E[nH] = pn. Точно так же каждое из ребер в G имеет вероятность p остаться в H, поскольку обе конечные точки должны оставаться в H, поэтому E[eH] = pe. Наконец, каждый перекресток на диаграмме G имеет вероятность p остаться в H, так как каждый перекресток включает четыре вершины. Чтобы убедиться в этом, рассмотрим диаграмму группы G с пересечениями cr (G). Мы можем считать, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, иначе мы могли бы поменять местами пересекающиеся части двух ребер и уменьшить количество пересечений на единицу. Таким образом, каждый перекресток на этой диаграмме включает четыре различных вершины G. Следовательно, E [cr H ] = pcr (G), и мы имеем

$p\; 4\; cr\; \; (G)\; \ge \; p\; 2\; e\; -\; 3\; пн.\; \{\backslash \; displaystyle\; p\; ^\; \{4\}\; \backslash \; operatorname\; \{cr\}\; (G)\; \backslash \; geq\; p\; ^\; \{2\}\; e-3pn.\}$

Теперь, если мы установим p = 4n / e < 1 (since we assumed that e>4n), мы получим после некоторого алгебра

$cr\; \; (G)\; \ge \; e\; 3\; 64\; n\; 2.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cr\}\; (G)\; \backslash \; geq\; \{\backslash \; frac\; \{e\; ^\; \{3\}\}\; \{64n\; ^\; \{2\}\}\}.\}$

Небольшое уточнение этого аргумента позволяет заменить 64 на 33,75 для e>7.5n.

Для графиков с обхватом больше 2r и e ≥ 4n, Pach, Spencer Tóth (2000) продемонстрировали улучшение этого неравенства до

$cr\; \; (G)\; \ge \; crer\; +\; 2\; nr\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cr\}\; (G)\; \backslash \; geq\; c\_\; \{r\}\; \{\backslash \; frac\; \{e\; ^\; \{r\; +\; 2\}\}\; \{n\; ^\; \{r\; +\; 1\}\}\}.\}$

Адипрасито показал обобщение на более высокие измерения: если $\Delta \; \{\backslash \; displaystyle\; \backslash \; Delta\}$является симплициальным комплексом, который кусочно-линейно отображается в $R\; 2\; d\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{R\}\; ^\; \{2d\; \}\}$, и он имеет $fd\; (\Delta )\; d\; \{\backslash \; displaystyle\; f\_\; \{d\}\; (\backslash \; Delta)\; \backslash \; \backslash \; d\}$-мерные грани и $fd\; -\; 1\; (\Delta )\; (d\; -\; 1)\; \{\backslash \; displaystyle\; f\_\; \{d-1\}\; (\backslash \; Delta)\; \backslash \; \backslash \; (d-1)\}$-мерные грани такие, что $fd\; (\Delta )>(\; d\; +\; 3)\; fd\; -\; 1\; (\Delta )\; \{\backslash \; displaystyle\; f\_\; \{d\}\; (\backslash \; Delta)>(d\; +\; 3)\; f\_\; \{d-1\}\; (\backslash \; Delta)\}$, то количество попарно пересекающихся $d\; \{\backslash \; displaystyle\; d\}$-мерных граней не менее

$fdd\; +\; 2\; (\Delta )\; (d\; +\; 3)\; d\; +\; 2\; fd\; -\; 1\; d\; +\; 1\; (\Delta ).\; \{\backslash \; Displaystyle\; \{\backslash \; frac\; \{f\_\; \{d\}\; ^\; \{d\; +\; 2\}\; (\backslash \; Delta)\}\; \{(d\; +\; 3)\; ^\; \{d\; +\; 2\}\; f\_\; \{d-1\}\; ^\; \{d\; +\; 1\}\; (\; \backslash \; Delta)\}\}.\}$