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

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

Заявление

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщение

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

Характеристики подобных проблем

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

Ссылки

• Гейл, Д. (1957). «Теорема о потоках в сетях» . Пасифик Дж. Математика . 7 (2): 1073–1082. дои : 10.2140/pjm.1957.7.1073 .
• Райзер, HJ (1957). «Комбинаторные свойства матриц нулей и единиц» . Может. Дж. Математика . 9 : 371–377. дои : 10.4153/cjm-1957-044-3 . S2CID   120496629 .
• Райзер, HJ (1963). Комбинаторная математика . Джон Уайли и сыновья .
• Бруальди, Р. ; Райзер, HJ (1991). Комбинаторная теория матриц . Нью-Йорк: Издательство Кембриджского университета . ISBN  9780521322652 .
• Форд (младший), ЛР ; Фулкерсон, Д.Р. (1962). Потоки в сетях . Принстон. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Краузе, Манфред (1996), «Простое доказательство теоремы Гейла-Райзера», American Mathematical Monthly , 103 (4): 335–337, doi : 10.2307/2975191 , JSTOR   2975191
• Бергер, Аннабель (2013), «Заметки о характеристиках последовательностей орграфов», Discrete Mathematics , 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 .