Неравенство Брегмана – Минца

В дискретной математике, Брегман– Неравенство Минца, или теорема Брегмана, позволяет оценить перманент двоичной матрицы с помощью сумм по строкам или столбцам. Неравенство было предположено в 1963 г. и впервые доказано в 1973 г. Львом М. Брегманом. Дальнейшие доказательства, основанные на энтропии, были даны Александром Шрайвером и Джайкумаром Радхакришнаном. Неравенство Брегмана – Минца используется, например, в теории графов для получения верхней границы количества точных соответствий в двудольном графе.

• 1 Оператор
• 2 Приложение
• 3 Связанные операторы
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

Перманент квадратной двоичной матрицы $A\; =\; (aij)\; \{\backslash \; displaystyle\; A\; =\; (a\_\; \{ij\})\}$размера $n\; \{\backslash \; displaystyle\; n\}$с суммами строк $ri\; =\; ai\; 1\; +\; \cdots \; +\; ain\; \{\backslash \; displaystyle\; r\_\; \{i\}\; =\; a\_\; \{i1\}\; +\; \backslash \; cdots\; +\; a\_\; \{in\}\}$для $i\; =\; 1,\dots ,\; n\; \{\backslash \; displaystyle\; i\; =\; 1,\; \backslash \; ldots,\; n\}$можно оценить как

$на\; A\; \le \; \prod \; i\; =\; 1\; n\; (ri!)\; 1\; /\; ri.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{per\}\; A\; \backslash \; leq\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; (r\_\; \{i\}!)\; ^\; \{1\; /\; r\_\; \{i\}\}.\}$

Следовательно, перманент ограничен произведение средних геометрических чисел от $1\; \{\backslash \; displaystyle\; 1\}$до $ri\; \{\backslash \; displaystyle\; r\_\; \{i\}\}$для $i\; =\; 1,\dots ,\; n\; \{\backslash \; displaystyle\; i\; =\; 1,\; \backslash \; ldots,\; n\}$. Равенство сохраняется, если матрица является блочно-диагональной матрицей, состоящей из матриц единиц, или является результатом перестановок строк и / или столбцов такой блочно-диагональной матрицы. Поскольку перманент инвариантен относительно транспонирования, неравенство также выполняется для сумм столбцов матрицы соответственно.

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

Между квадратной двоичной матрицей $A\; \{\backslash \; displaystyle\; A\}$<94 существует взаимно однозначное соответствие.>размера $n\; \{\backslash \; displaystyle\; n\}$и простой двудольный граф $G\; =\; (V\; \cup \; \dot{}\; W,\; E)\; \{\backslash \; displaystyle\; G\; =\; (V\; \backslash ,\; \{\backslash \; dot\; \{\backslash \; cup\}\}\; \backslash ,\; W,\; E)\}$с разделами одинакового размера $V\; =\; \{v\; 1,\dots ,\; vn\}\; \{\backslash \; displaystyle\; V\; =\; \backslash \; \{v\_\; \{1\},\; \backslash \; ldots,\; v\_\; \{n\}\; \backslash \}\}$и $W\; =\; \{w\; 1,\dots ,\; wn\}\; \{\backslash \; displaystyle\; W\; =\; \backslash \; \{w\_\; \{1\},\; \backslash \; ldots,\; w\_\; \{n\}\; \backslash \}\}$, взяв

$aij\; =\; 1\; \iff \; \{vi,\; wj\}\; \in \; E.\; \{\backslash \; displaystyle\; a\_\; \{ij\}\; =\; 1\; \backslash \; Leftrightarrow\; \backslash \; \{v\_\; \{i\},\; w\_\; \{j\}\; \backslash \}\; \backslash \; in\; E.\}$

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

$a\; 1\; \sigma \; (1)\; \cdots \; an\; \sigma \; (n)\; =\; 1\; \{\backslash \; displaystyle\; a\_\; \{1\; \backslash \; sigma\; (1)\}\; \backslash \; cdots\; a\_\; \{n\; \backslash \; sigma\; (n)\}\; =\; 1\}$

соответствует идеальному совпадению $\{\{v\; 1,\; w\; \sigma \; (1)\},\dots ,\; \{vn,\; w\; \sigma \; (n)\}\; \}\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; \{v\_\; \{1\},\; w\; \_\; \{\backslash \; sigma\; (1)\}\; \backslash \},\; \backslash \; ldots,\; \backslash \; \{v\_\; \{n\},\; w\; \_\; \{\backslash \; sigma\; (n)\}\; \backslash \}\; \backslash \}\}$из $G\; \{\backslash \; displaystyle\; G\}$. Следовательно, если $M\; (G)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{M\}\}\; (G)\}$обозначает набор точных соответствий $G\; \{\backslash \; displaystyle\; G\}$,

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

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

$|\; M\; (G)\; |\; \le \; \prod \; я\; знак\; равно\; 1\; N\; (d\; (vi)!)\; 1\; /\; d\; (vi),\; \{\backslash \; displaystyle\; |\; \{\backslash \; mathcal\; \{M\}\}\; (G)\; |\; \backslash \; leq\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; (\; d\; (v\_\; \{i\})!)\; ^\; \{1\; /\; d\; (v\_\; \{i\})\},\}$

где $d\; (vi)\; \{\backslash \; displaystyle\; d\; (v\_\; \{i\})\}$- градус вершины $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$. Из-за симметрии соответствующая оценка также верна для $d\; (wi)\; \{\backslash \; displaystyle\; d\; (w\_\; \{i\})\}$вместо $d\; (vi)\; \{\backslash \; displaystyle\; d\; (v\_\; \{\; i\})\}$. Таким образом, количество возможных точных совпадений в двудольном графе с разделами равного размера можно оценить с помощью степеней вершин любого из двух разделов.

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

$на\; \; A\; \le \; \prod \; i\; =\; 1\; nri\; +\; 1\; 2,\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{per\}\; A\; \backslash \; leq\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{\backslash \; frac\; \{r\_\; \{i\}\; +1\}\; \{2\}\},\}$

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

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

Тем самым достигается максимум для блочно-диагональной матрицы, чья диагональные блоки - это квадратные матрицы блоков размера $k\; \{\backslash \; displaystyle\; k\}$. Соответствующее утверждение для случая, когда $k\; \{\backslash \; displaystyle\; k\}$не является делителем $n\; \{\backslash \; displaystyle\; n\}$, является открытой математической проблемой.

• Вычисление постоянного

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