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

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

Заявление

Перманент квадратной двоичной матрицы ${\displaystyle A=(a_{ij})}$ размера ${\displaystyle n}$ с суммой строк ${\displaystyle r_{i}=a_{i1}+\cdots +a_{in}}$ за ${\displaystyle i=1,\ldots ,n}$ можно оценить по

${\displaystyle \operatorname {per} A\leq \prod _{i=1}^{n}(r_{i}!)^{1/r_{i}}.}$

Следовательно, перманент ограничен произведением геометрические средства номеров из ${\displaystyle 1}$ к ${\displaystyle r_{i}}$ за ${\displaystyle i=1,\ldots ,n}$. Равенство выполняется, если матрица блочно-диагональная матрица состоящий из матрицы единиц или является результатом перестановок строк и / или столбцов такой блочно-диагональной матрицы. Поскольку перманент инвариантен относительно транспозиция, неравенство выполняется и для столбцовых сумм матрицы соответственно.^[5][6]

Заявление

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

Между квадратной двоичной матрицей существует взаимно однозначное соответствие ${\displaystyle A}$ размера ${\displaystyle n}$ и просто двудольный граф ${\displaystyle G=(V\,{\dot {\cup }}\,W,E)}$ с равными размерами перегородки ${\displaystyle V=\{v_{1},\ldots ,v_{n}\}}$ и ${\displaystyle W=\{w_{1},\ldots ,w_{n}\}}$ принимая

${\displaystyle a_{ij}=1\Leftrightarrow \{v_{i},w_{j}\}\in E.}$

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

${\displaystyle a_{1\sigma (1)}\cdots a_{n\sigma (n)}=1}$

соответствует идеальному совпадению ${\displaystyle \{\{v_{1},w_{\sigma (1)}\},\ldots ,\{v_{n},w_{\sigma (n)}\}\}}$ из ${\displaystyle G}$. Следовательно, если ${\displaystyle {\mathcal {M}}(G)}$ обозначает множество совершенных совпадений ${\displaystyle G}$,

${\displaystyle |{\mathcal {M}}(G)|=\operatorname {per} A}$

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

${\displaystyle |{\mathcal {M}}(G)|\leq \prod _{i=1}^{n}(d(v_{i})!)^{1/d(v_{i})},}$

куда ${\displaystyle d(v_{i})}$ это степень вершины ${\displaystyle v_{i}}$. В силу симметрии соответствующая оценка верна и для ${\displaystyle d(w_{i})}$ вместо ${\displaystyle d(v_{i})}$. Таким образом, количество возможных совершенных паросочетаний в двудольном графе с разделами одинакового размера можно оценить через степени вершин любого из двух разделов.^[7]

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

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

${\displaystyle \operatorname {per} A\leq \prod _{i=1}^{n}{\frac {r_{i}+1}{2}},}$

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

${\displaystyle \max _{A\in \Lambda _{kn}}\operatorname {per} A=(k!)^{n/k}.}$

Тем самым достигается максимум для блочно-диагональной матрицы, диагональные блоки которой являются квадратными матрицами размера ${\displaystyle k}$. Соответствующее утверждение для случая, когда ${\displaystyle k}$ не является делителем ${\displaystyle n}$ это открытая математическая проблема.^[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.

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

• Робин Уитти. «Теорема Брегмана» (PDF; 274 КБ). Теорема дня. Получено 19 октября 2015.