Пересечение числового неравенства - Crossing number inequality

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

Он имеет приложения в СБИС дизайн и комбинаторная геометрия, и был открыт независимо Аджтай, Chvátal, Новорожденный и Семереди^[1]и по Leighton.^[2]

Заявление и история

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

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

Постоянная 29 является наиболее известным на сегодняшний день и принадлежит Акерману.^[3]Более ранние результаты с более слабыми константами см. Пах и Тот (1997) и Pach et al. (2006).^[4][5]Постоянная 7 может быть понижен до 4, но за счет замены 29 с худшей константой 64.

Важно различать номер пересечения cr (г) и число попарного пересечения пара-cr (г). Как отмечает Пах и Тот (2000), число попарного пересечения ${ Displaystyle { текст {пара-cr}} (G) leq { text {cr}} (G)}$ относится к минимальному количеству пар ребер, каждое из которых определяет одно пересечение, тогда как число пересечений просто означает минимальное количество пересечений. (Это различие необходимо, поскольку некоторые авторы предполагают, что на правильном рисунке никакие два края не пересекаются более одного раза.)^[6]

Приложения

Мотивация Лейтон к изучению чисел скрещивания заключалась в том, что СБИС дизайн в теоретической информатике.^[2]

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

Доказательство

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

${ displaystyle operatorname {cr} (G) geq e-3n.}$

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

Чтобы получить фактическое неравенство числа пересечений, мы теперь используем вероятностный аргумент. Пусть 0 < п < 1 быть вероятность параметр, который будет выбран позже, и построить случайный подграф ЧАС из г позволяя каждой вершине г лежать в ЧАС независимо с вероятностью п, и позволяя край г лежать в ЧАС тогда и только тогда, когда две его вершины были выбраны лежащими в ЧАС. Позволять е_ЧАС, п_ЧАС и cr_ЧАС обозначим количество ребер, вершин и пересечений ЧАСсоответственно. поскольку ЧАС является подграфом г, диаграмма г содержит схему ЧАС. По предварительному неравенству числа пересечений имеем

${ displaystyle operatorname {cr} _ {H} geq e_ {H} -3n_ {H}.}$

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

${ displaystyle mathbf {E} [ operatorname {cr} _ {H}] geq mathbf {E} [e_ {H}] - 3 mathbf {E} [n_ {H}].}$

Поскольку каждый из п вершины в г имел вероятность п быть в ЧАС, у нас есть E[п_ЧАС] = пн. Аналогично каждое ребро в г имеет вероятность п² остаться в ЧАС поскольку обе конечные точки должны оставаться в ЧАС, следовательно E[е_ЧАС] = п²е. Наконец, каждое пересечение на диаграмме г имеет вероятность п⁴ остаться в ЧАС, так как каждый перекресток включает четыре вершины. Чтобы увидеть это, рассмотрим схему г с cr (г) переходы. Мы можем считать, что любые два ребра в этой диаграмме с общей вершиной не пересекаются, иначе мы могли бы поменять местами пересекающиеся части двух ребер и уменьшить число пересечений на единицу. Таким образом, каждый перекресток на этой диаграмме включает четыре различных вершины г. Следовательно, E[cr_ЧАС] = п⁴cr (г) и у нас есть

${ displaystyle p ^ {4} operatorname {cr} (G) geq p ^ {2} e-3pn.}$

Теперь, если мы установим п = 4п/е < 1 (поскольку мы предположили, что е > 4п), после некоторой алгебры получаем

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

Небольшое уточнение этого аргумента позволяет заменить 64 к 33.75 за е > 7.5п.^[3]

Вариации

Для графиков с обхват больше, чем 2р и е ≥ 4п, Пах, Спенсер и Тот (2000) продемонстрировали улучшение этого неравенства до^[9]

${ displaystyle operatorname {cr} (G) geq c_ {r} { frac {e ^ {r + 2}} {n ^ {r + 1}}}.}$

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

${ Displaystyle { гидроразрыва {f_ {d} ^ {d + 2} ( Delta)} {(d + 3) ^ {d + 2} f_ {d-1} ^ {d + 1} ( Delta) }}.}$

Рекомендации