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