Теорема Гейла – Райзера - Gale–Ryser theorem

В Теорема Гейла – Райзера это результат теория графов и комбинаторная теория матриц, две ветви комбинаторика. Он предоставляет один из двух известных подходов к решению проблема двусторонней реализации, т.е. дает необходимое и достаточное условие для двух конечные последовательности из натуральные числа быть последовательность степеней маркированного просто двудольный граф; последовательность, удовлетворяющая этим условиям, называется «биграфической». Это аналог Теорема Эрдеша – Галлаи для простых графиков. Теорема была опубликована в 1957 г. Х. Дж. Райзер а также Дэвид Гейл.

утверждение

Пара последовательностей неотрицательных целые числа ${ Displaystyle (а_ {1}, ldots, а_ {п})}$ и ${ displaystyle (b_ {1}, ldots, b_ {n})}$ с участием ${ Displaystyle а_ {1} geq cdots geq а_ {п}}$ является биграфическим тогда и только тогда, когда ${ displaystyle sum _ {i = 1} ^ {n} a_ {i} = sum _ {i = 1} ^ {n} b_ {i}}$ и для ${ displaystyle k}$ такой, что ${ Displaystyle 1 Leq К Leq N}$:

${ displaystyle sum _ {i = 1} ^ {k} a_ {i} leq sum _ {i = 1} ^ {n} min (b_ {i}, k).}$

Замечание

Иногда эту теорему формулируют с дополнительным ограничением ${ Displaystyle b_ {1} geq cdots geq b_ {п}}$. Это условие не обязательно, потому что метки вершин одного раздельный набор в двудольный граф можно переключать произвольно.В 1962 году Форд и Фулкерсон ^[1] дал иную, но эквивалентную формулировку теоремы.

Другие обозначения

Теорема также может быть сформулирована в терминах нуля или единицы. матрицы. Связь можно увидеть, если понять, что каждый двудольный граф имеет матрица двойственности где суммы столбцов и суммы строк соответствуют ${ Displaystyle (а_ {1}, ldots, а_ {п})}$ и ${ displaystyle (b_ {1}, ldots, b_ {n})}$. Каждую последовательность также можно рассматривать как раздел того же числа ${ Displaystyle м = сумма _ {я = 1} ^ {п} а_ {я}}$. Получается, что раздел ${ Displaystyle (а_ {1} ^ {*}, ldots, а_ {п} ^ {*})}$ где ${ displaystyle a_ {k} ^ {*}: = | {b_ {i} | b_ {i} geq k } |}$ это сопряженное разделение из ${ displaystyle (b_ {1}, ldots, b_ {n})}$. Сопряженное разбиение может быть определено Диаграмма Феррерса. Более того, есть связь с соотношением мажоризация. Рассмотрим последовательности ${ Displaystyle (а_ {1}, ldots, а_ {п})}$, ${ displaystyle (b_ {1}, ldots, b_ {n})}$ и ${ Displaystyle (а_ {1} ^ {*}, ldots, а_ {п} ^ {*})}$ так как ${ displaystyle n}$-мерные векторы ${ displaystyle a}$, ${ displaystyle b}$ и ${ displaystyle a ^ {*}}$. поскольку ${ displaystyle sum _ {i = 1} ^ {k} a_ {i} ^ {*} = sum _ {i = 1} ^ {n} min (b_ {i}, k)}$, приведенная выше теорема утверждает, что пара неотрицательных целочисленных последовательностей a и b с невозрастанием a является биграфической тогда и только тогда, когда сопряженное разбиение ${ displaystyle a ^ {*}}$ из ${ displaystyle b}$ мажоритарный ${ displaystyle a}$. Третья формулировка представляет собой последовательность степеней простых ориентированные графы максимум с одним петля на вершина. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа. Когда бывают пары неотрицательных целые числа ${ displaystyle ((a_ {1}, b_ {1}), ..., (a_ {n}, b_ {n}))}$ то степень -превосходить пары помеченных ориентированный граф не более одного цикла на вершину? Теорема легко адаптируется к этой формулировке, поскольку особого порядка b не существует.

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

Доказательство состоит из двух частей: необходимость условия и его достаточность. Мы наметим доказательство обеих частей на языке матриц. Чтобы убедиться, что условие теоремы необходимо, рассмотрим матрицу смежности биграфической реализации со строковыми суммами ${ displaystyle (b_ {1}, ldots, b_ {n})}$ и суммы столбцов ${ Displaystyle (а_ {1}, ldots, а_ {п})}$, и сдвинуть все единицы в матрице влево. Суммы строк остаются, а суммы столбцов теперь ${ displaystyle a ^ {*}}$. Операция сдвига всех единиц влево увеличивает разделение в порядке мажорирования, и поэтому ${ displaystyle a ^ {*}}$ мажоритарный ${ displaystyle a}$.

Первоначальное доказательство достаточности условия было довольно сложным. Краузе (1996) дал простое алгоритмическое доказательство. Идея состоит в том, чтобы начать с Диаграмма Феррерса из ${ displaystyle b}$ и сдвигайте единицы вправо, пока суммы столбцов не станут ${ displaystyle a}$. Алгоритм работает не более ${ displaystyle n}$ шаги, на каждом из которых одна запись перемещается вправо.

Более сильная версия

Бергер доказал^[2] что достаточно рассмотреть те ${ displaystyle k}$th неравенства такие, что ${ Displaystyle 1 Leq к <п}$ с участием ${ displaystyle a_ {k}> a_ {k + 1}}$ и равенство для ${ Displaystyle к = п}$.

Обобщение

Пара конечных последовательностей неотрицательных целые числа ${ displaystyle a}$ и ${ displaystyle b}$ с невозрастанием ${ displaystyle a}$ является биграфическим тогда и только тогда, когда ${ displaystyle sum _ {i = 1} ^ {n} a_ {i} = sum _ {i = 1} ^ {n} b_ {i}}$ и существует последовательность ${ displaystyle c}$ так что пара ${ displaystyle c, b}$ биграфичен и ${ displaystyle c}$ мажоритарный ${ displaystyle a}$.^[3] Более того, в ^[4] также доказано, что пара ${ displaystyle a}$ и ${ displaystyle b}$ имеет больше биграфических реализаций, чем пара ${ displaystyle c}$ и ${ displaystyle b}$. Это приводит к тому, что регулярные последовательности иметь для фиксированного количества вершины и края наибольшее количество биграфических реализаций, если n делит m. Они противоположные последовательности из пороговые последовательности только с одной уникальной биграфической реализацией, известной как график пороговых значений. Minconvex последовательности обобщите эту концепцию, если n не делит m.

Характеристики схожих проблем

Подобные теоремы описывают последовательности степеней простых графов и простых ориентированных графов. Первая проблема характеризуется Теорема Эрдеша – Галлаи. Последний случай характеризуется Теорема Фулкерсона – Чена – Ансти.

Заметки

использованная литература

• Гейл, Д. (1957). «Теорема о потоках в сетях». Pacific J. Math. 7 (2): 1073–1082. Дои:10.2140 / pjm.1957.7.1073.
• Райзер, Х. Дж. (1957). «Комбинаторные свойства матриц нулей и единиц». Мочь. J. Math. 9: 371–377. Дои:10.4153 / cjm-1957-044-3.
• Райзер, Х. Дж. (1963). Комбинаторная математика. Джон Уайли и сыновья.
• Бруальди, Р.; Райзер, Х. Дж. (1991). Комбинаторная матричная теория. Нью-Йорк: Издательство Кембриджского университета.
• Форд (младший), Л.; Фулкерсон, Д. (1962). Потоки в сетях. Принстон.CS1 maint: ref = harv (ссылка на сайт)
• Краузе, Манфред (1996), "Простое доказательство теоремы Гейла – Райзера", Американский математический ежемесячный журнал, 103 (4): 335–337, Дои:10.2307/2975191, JSTOR  2975191
• Бергер, Аннабелл (2013), "Заметка о характеристике последовательностей орграфов", Дискретная математика, 314: 38–41, arXiv:1112.1215, Дои:10.1016 / j.disc.2013.09.010.
• Бергер, Аннабель (2018), «Мажоризация и количество двудольных графов для заданных степеней вершин», Сделки по комбинаторике, 1: 19–30, Дои:10.22108 / toc.2017.21469.