Теорема Эрдеша – Галлаи

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

Заявление

Последовательность неотрицательных целых чисел $d_{1}\geq \cdots \geq d_{n}$ можно представить как последовательность степеней конечного простого графа на n вершинах тогда и только тогда, когда $d_{1}+\cdots +d_{n}$ четный и

\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)

держится для каждого $k$ в $1\leq k\leq n$ .

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

Нетрудно показать, что условия теоремы Эрдеша–Галлаи необходимы для того, чтобы последовательность чисел была графической. Требование четности суммы степеней — это лемма о рукопожатии , уже использованная Эйлером в его статье 1736 года о мостах Кенигсберга . Неравенство между суммой $k$ наибольших степеней, а сумму оставшихся степеней можно определить двойным подсчетом : в левой части указано количество смежностей ребер и вершин среди $k$ вершин высшей степени, каждая такая смежность должна находиться либо на ребре с одной или двумя конечными точками высокой степени, $k(k-1)$ Член справа дает максимально возможное количество смежностей ребра и вершины, в которых обе конечные точки имеют высокую степень, а оставшийся член справа сверху ограничивает количество ребер, которые имеют ровно одну конечную точку высокой степени. Таким образом, более сложная часть доказательства состоит в том, чтобы показать, что для любой последовательности чисел, удовлетворяющей этим условиям, существует граф, для которого она является последовательностью степеней.

Первоначальное доказательство Эрдеша и Галлаи (1960) было длинным и сложным. Чоудум (1986) цитирует более короткое доказательство Клода Бержа , основанное на идеях сетевого потока . Вместо этого Чоудум приводит доказательство посредством математической индукции суммы степеней: он позволяет $t$ быть первым индексом числа в последовательности, для которой $d_{t}>d_{t+1}$ (или предпоследнее число, если все равны), использует анализ случаев, чтобы показать, что последовательность, образованная вычитанием единицы из $d_{t}$ и из последнего числа в последовательности (и удаления последнего числа, если это вычитание приводит к тому, что оно становится нулевым) снова является графическим и образует график, представляющий исходную последовательность, путем добавления ребра между двумя позициями, из которых одно было вычтено.

Трипати, Венугопалан и Уэст (2010) рассматривают последовательность «субреализаций», графов, степени которых ограничены сверху заданной последовательностью степеней. Они показывают, что если G — подреализация, а i — наименьший индекс вершины в G , степень которой не равна d _i , то G можно модифицировать таким образом, чтобы создать другую подреализацию, увеличивая степень вершины i без изменение степеней более ранних вершин последовательности. Повторные шаги такого типа должны в конечном итоге привести к реализации заданной последовательности, доказывая теорему.

Связь с целочисленными разделами

Айгнер и Триш (1994) описывают тесную связь между теоремой Эрдеша-Галлаи и теорией целочисленных разбиений . Позволять $m=\sum d_{i}$ ; то отсортированные целочисленные последовательности суммируются до $m$ можно интерпретировать как разделы $m$ . При мажорировании своих префиксных сумм разбиения образуют решетку , в которой минимальное изменение между отдельным разбиением и другим разбиением, стоящим ниже по порядку разбиения, состоит в вычитании единицы из одного из чисел. $d_{i}$ и добавить его к числу $d_{j}$ это меньше как минимум на два ( $d_{j}$ может быть нулевым). Как показывают Айгнер и Триш, эта операция сохраняет свойство графичности, поэтому для доказательства теоремы Эрдеша–Галлаи достаточно охарактеризовать графические последовательности, максимальные в этом порядке мажорации. Они дают такую характеристику в терминах диаграмм Феррера соответствующих разбиений и показывают, что она эквивалентна теореме Эрдеша – Галлаи.

Графические последовательности для других типов графиков

Подобные теоремы описывают последовательности степеней простых ориентированных графов, простых ориентированных графов с петлями и простых двудольных графов ( Бергер 2012 ). Первая проблема характеризуется теоремой Фулкерсона–Чена–Ансти . Последние два случая, которые эквивалентны, характеризуются теоремой Гейла–Райзера .

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

Трипати и Виджай (2003) доказали, что достаточно рассмотреть $k$ неравенство такое, что $1\leq k<n$ с $d_{k}>d_{k+1}$ и для $k=n$ . Баррус и др. (2012) ограничивают набор неравенств для графиков противоположной тяги. Если четная положительная последовательность $d$ не имеет повторяющихся записей, кроме максимального и минимального (и длина превышает самую большую запись), то достаточно проверить только $l$ неравенство, где $l=\max\{k\mid d_{k}\geq k\}$ .

Обобщение

Конечные последовательности неотрицательных целых чисел $(d_{1},\cdots ,d_{n})$ с $d_{1}\geq \cdots \geq d_{n}$ является графическим, если $\sum _{i=1}^{n}d_{i}$ четно и существует последовательность $(c_{1},\cdots ,c_{n})$ это графическое изображение и мажорирует $(d_{1},\cdots ,d_{n})$ . Этот результат был получен Айгнером и Тришем (1994) . Махадев и Пелед (1995) заново изобрели ее и дали более прямое доказательство.