Неравенство Брегмана – Минка - Bregman–Minc inequality

В дискретная математика, то Неравенство Брегмана – Минка, или же Теорема Брегмана, позволяет оценить постоянный из двоичная матрица через суммы строк или столбцов. Неравенство было предположено в 1963 г. Хенрик Минц и впервые доказано в 1973 г. Лев М. Брегман.[1][2] Дальше энтропия -основанные доказательства были даны Александр Шрайвер и Джайкумар Радхакришнан.[3][4] Неравенство Брегмана – Минца используется, например, в теория графов для получения оценок сверху количества идеальное соответствие в двудольный граф.

Заявление

Перманент квадратной двоичной матрицы размера с суммой строк за можно оценить по

Следовательно, перманент ограничен произведением геометрические средства номеров из к за . Равенство выполняется, если матрица блочно-диагональная матрица состоящий из матрицы единиц или является результатом перестановок строк и / или столбцов такой блочно-диагональной матрицы. Поскольку перманент инвариантен относительно транспозиция, неравенство выполняется и для столбцовых сумм матрицы соответственно.[5][6]

Заявление

Бинарная матрица и соответствующий двудольный граф с возможным идеальным совпадением отмечены красным. Согласно неравенству Брегмана – Минца, на этом графе не более 18 точных паросочетаний.

Между квадратной двоичной матрицей существует взаимно однозначное соответствие размера и просто двудольный граф с равными размерами перегородки и принимая

Таким образом, каждый ненулевой элемент матрицы определяет край в графике наоборот. Идеальное сочетание в это выбор ребра, так что каждый вершина графа является концом одного из этих ребер. Каждое ненулевое слагаемое перманента удовлетворение

соответствует идеальному совпадению из . Следовательно, если обозначает множество совершенных совпадений ,

держит. Неравенство Брегмана – Минца теперь дает оценку

куда это степень вершины . В силу симметрии соответствующая оценка верна и для вместо . Таким образом, количество возможных совершенных паросочетаний в двудольном графе с разделами одинакового размера можно оценить через степени вершин любого из двух разделов.[7]

Связанные заявления

С использованием неравенство средних арифметических и геометрических, из неравенства Брегмана – Минца прямо следует более слабая оценка

что было доказано Хенриком Минком еще в 1963 году. Еще одно прямое следствие неравенства Брегмана – Минца - это доказательство следующей гипотезы Герберт Райзер с 1960. Пусть на делитель и разреши обозначают набор квадратных двоичных матриц размера с суммами строк и столбцов, равными , тогда

Тем самым достигается максимум для блочно-диагональной матрицы, диагональные блоки которой являются квадратными матрицами размера . Соответствующее утверждение для случая, когда не является делителем это открытая математическая проблема.[5][6]

Смотрите также

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

  1. ^ Хенрик Минц (1963), "Верхние оценки перманентов (0,1) -матриц", Бык. Амер. Математика. Soc., 69: 789–791, Дои:10.1090 / с0002-9904-1963-11031-9
  2. ^ Лев Брегман (1973), «Некоторые свойства неотрицательных матриц и их перманенты», Советская математика. Докл., 14: 945–949
  3. ^ Александр Шрайвер (1978), «Краткое доказательство гипотезы Минца», J. Combin. Теория Сер. А, 25: 80–83, Дои:10.1016/0097-3165(78)90036-5
  4. ^ Джайкумар Радхакришнан (1997), "Энтропийное доказательство теоремы Брегмана", J. Combin. Теория Сер. А, 77: 161–164, Дои:10.1006 / jcta.1996.2727
  5. ^ а б Хенрик Минк (1984), Перманенты, Энциклопедия математики и ее приложений, 6, Cambridge University Press, стр. 107–109.
  6. ^ а б Владимир Сачков (1996), Комбинаторные методы в дискретной математике, Cambridge University Press, стр. 95–97.
  7. ^ Мартин Айгнер, Гюнтер М. Циглер (2015), Das Buch der Beweise (4-е изд.), Springer, стр. 285–292.

внешняя ссылка