Теорема Гейла–Райзера

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

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

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

Иногда эта теорема формулируется с дополнительным ограничением . Это условие не является необходимым, поскольку метки вершин одного долевого множества в двудольном графе можно переставлять произвольно.${\displaystyle b_{1}\geq \cdots \geq b_{n}}$

В 1962 году Форд и Фулкерсон ^[1] дали иную, но эквивалентную формулировку теоремы.

Теорему можно также сформулировать в терминах матриц нуль-единица . Связь можно увидеть, если понять, что каждый двудольный граф имеет матрицу бисмежности , где суммы столбцов и суммы строк соответствуют и . ${\displaystyle (a_{1},\ldots ,a_{n})}$${\displaystyle (b_{1},\ldots ,b_{n})}$

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

Третья формулировка в терминах степенных последовательностей простых ориентированных графов с не более чем одной петлей на вершину . В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа. Когда пары неотрицательных целых чисел являются парами входящей и исходящей степеней маркированного ориентированного графа с не более чем одной петлей на вершину? Теорему можно легко адаптировать к этой формулировке, поскольку не существует специального порядка b.${\displaystyle ((a_{1},b_{1}),...,(a_{n},b_{n}))}$

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

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

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

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

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

• Гейл, Д. (1957). «Теорема о потоках в сетях». Pacific J. Math . 7 (2): 1073– 1082. doi : 10.2140/pjm.1957.7.1073 .
• Райзер, Х. Дж. (1957). «Комбинаторные свойства матриц из нулей и единиц». Can. J. Math . 9 : 371– 377. doi : 10.4153/cjm-1957-044-3 . S2CID  120496629.
• Райзер, Х. Дж. (1963). Комбинаторная математика . John Wiley & Sons .
• Brualdi, R. ; Ryser, HJ (1991). Комбинаторная теория матриц . Нью-Йорк: Cambridge University Press . ISBN 9780521322652.
• Форд (младший), Л.Р .; Фулкерсон, Д.Р. (1962). Потоки в сетях . Принстон.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Краузе, Манфред (1996), «Простое доказательство теоремы Гейла–Райзера», American Mathematical Monthly , 103 (4): 335– 337, doi :10.2307/2975191, JSTOR  2975191
• Бергер, Аннабелл (2013), «Заметка о характеристике последовательностей орграфов», Дискретная математика , 314 : 38–41 , arXiv : 1112.1215 , doi : 10.1016/j.disc.2013.09.010, S2CID  119170629.
• Бергер, Аннабелл (2018), «Мажоризация и число двудольных графов для заданных степеней вершин», Труды по комбинаторике , 1 : 19–30 , doi :10.22108/toc.2017.21469.