Перманенты многомерных матриц в задачах дискретной математики Тараненко Анна Александровна

Содержание к диссертации

Введение

1. Свойства, примеры и некоторые применения перманента много мерных матриц 23

1.1. Простейшие свойства перманентов многомерных матриц 23

1.2. Примеры 26

1.3. Применение перманента для подсчета числа комбинаторных объектов 28

2. Полистохастические матрицы и классические теоремы для двумерных матриц 35

2.1. Положительность перманента и теорема Биркгофа 35

2.2. Экстремумы перманента полистохастических матриц 38

3. Верхние оценки перманента многомерных матриц 45

3.1. Оценка перманента полистохастических матриц 45

3.1.1. Свойства функций Р ( ) и fn(l) 46

3.1.2. Дифференциальное неравенство на функцию Р ( ) 48

3.1.3. Асимптотическая верхняя оценка перманента 51

3.2. Оценки перманента многомерных (ОД)-матриц 59

4. 1- Факторы и 1-факторизации гиперграфов 67

4.1. Оценка числа 1-факторов в гиперграфе 67

4.2. Оценка числа 1-факторизаций полного гиперграфа 81

5. Квазигруппы, латинские квадраты и гиперкубы 86

5.1. Трансверсали в латинских квадратах и гиперкубах 86

5.1.1. Подсчет числа трансверсалей с помощью многомерного перманента 86

5.1.2. Оценки числа трансверсалей 87

5.1.3. Трансверсали в некоторых латинских гиперкубах

5.2. Трансверсали в квазигруппах 91

5.2.1. Трансверсали в полностью разделимых квазигруппах 98

5.2.2. Трансверсали в полулинейных квазигруппах 101

5.2.3. Трансверсали в гг-арных квазигруппах порядка 4 Ill

5.2.3. Трансверсали в итерированных группах Ъ\ и Z4 116

Заключение 122

Литература

• Применение перманента для подсчета числа комбинаторных объектов
• Экстремумы перманента полистохастических матриц
• Факторы и 1-факторизации гиперграфов
• Трансверсали в полностью разделимых квазигруппах

Введение к работе

Актуальность темы. Предметом исследования данной работы являются перманенты многомерных матриц. Актуальность выбранной темы исследования обусловлена ее потенциальными приложениями ко многим задачам перечислительной комбинаторики и дискретной математики.

Введем необходимые определения и обозначения.

Пусть n, d Є N и пусть I^d_n = {(«1,..., otd) ' сц Є {1,..., п}} - множество индексов. d-Мерной матрицей А порядка п будем называть массив чисел (a_a)_ald, а_а Є R.

Для к Є {О,... , d] к-мерной гранью матрицы А называется /с-мерная подматрица матрицы А, полученная фиксацией значений d — к координат, в то время как остальные к координат пробегают все п значений, {d — 1)-Мерную грань (і-мерной матрицы назовем гипергранью.

Обозначим через D{A) множество всех диагоналей (і-мерной матрицы А порядка п:

D(A) = { (а\...,а^п)\а^г Є I^d_n)\/i ^ j p(aⁱ,a^j) = d } ,

где р - расстояние Хэмминга (число позиций, в которых два вектора различаются).

Перманентом многомерной матрицы А называется величина

pGD(A) а&Р

Определим различные классы многомерных матриц.

Матрицы, у которых все элементы равны нулю или единице будем называть (ОД)-матрицами. Диагональная матрица - это (ОД)-матрица, у которой индексы единичных элементов образуют диагональ. Матрица А называется неотрицательной, если а_а > 0 для всех а Є 1%.

С помощью перманентов неотрицательных многомерных матриц специального вида можно посчитать число таких комбинаторных объектов, как 1-факторы в d-дольных d-униформных гиперграфах¹, совершенные коды и замощения графов², А-дизайны и Н-дизайны³.

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

¹Dow, S. J. Permanents of d-dimensional matrices / S. J. Dow, P. M. Gibson // Linear Algebra Appl. — 1987. - Vol. 90. - P. 133-145.

²Августинович, С. В. Многомерные перманенты в задачах перечисления / С. В. Августинович // Дискрет, анализ и исслед. операций. — 2008. — Т. 15, № 5. — С. 3-5.

³Potapov, V. N. On the multidimensional permanent and

d-Мерным МДР-кодом порядка п и с расстоянием к называется такой набор из n^d~^k+l элементов <і-мерной матрицы порядка п, что расстояние Хэмминга между индексами различных элементов не меньше к.

d-Мерный латинский гиперкуб Q порядка п есть <і-мерная матрица порядка п, элементы которой принимают п различных значений, и все значения в любой одномерной грани которой различны. Двумерный латинский гиперкуб называется латинским квадратом. Трансверсалъ латинского гиперкуба - это диагональ, содержащая все п различных значений. Число трансверсалей в гиперкубе Q будем обозначать как T(Q).

Следующий способ связать многомерный перманент с числом трансверсалей в латинском гиперкубе описан еще в 1968 году В. Б. Юркатом и X. Дж. Райзером⁴.

Каждому (і-мерному латинскому гиперкубу Q сопоставим {d + 1)-мерную (ОД)-матрицу А того же порядка по следующему правилу: элемент гиперкуба q_a равен і тогда и только тогда, когда элемент матрицы а_а^ равен единице. Несложно видеть, что перманент такой матрицы А равен числу трансверсалей в гиперкубе Q, а сама матрица А является полистохастической матрицей. В дальнейшем полистохастические d-мерные (0,1)-матрицы порядка п для краткости называются d-мерными МДР-кодами порядка п.

Обозначим через Q^ d-мериъш латинский гиперкуб порядка п такой,

d+i что q_ai,...,a_d = ctd+i тогда и только тогда, когда ^ oti = 0 mod п. Соответ-

г=\

ствующий гиперкубу Q_n {d+ 1)-мерный МДР-код порядкап, для которого

d+i элемент т_а равен единице тогда и только тогда, когда ^ oti = 0 mod п,

г=\

обозначим как М.^¹.

Латинские квадраты и гиперкубы, а также их трансверсали являются предметом исследования в работах Я. М. Уонлесса и Б. Д. Маккая^{5 6}, Р. Глебова и 3. Лурии⁷ и других авторов.

Пусть Ytq есть множество {0,..., q — 1} . m-Арная квазигруппа порядка q - это алгебраическая система, состоящая из множества S и т-арной операции / : S —> T,_q такой, что уравнение Хо = f(x\,..., x_m) имеет единственное решение относительно любой переменной при произвольной фиксации значений всех остальных m переменных. В дальнейшем мы отождествляем квазигруппу с ее т-арной операцией /. Таблица Кэли любой т-арной квазигруппы порядка q является m-мерным латинским гиперку-

⁴Jurkat, W. В. Extremal configurations and decomposition theorems / W. B. Jurkat, H. J. Ryser // J. Algebra. - 1968. - Vol. 8. - P. 194-222.

⁵Wanless, I. M. Transversals in latin squares: a survey / I. M. Wanless // Surveys in Combinatorics 2011, London Math. Soc. Lecture Note Ser. 392. — Cambridge: Cambridge University Press. — 2011. — P. 403-437.

⁶McKay, B. D. A census of small latin hypercubes / B. D. McKay, I. M. Wanless // SIAM J. Discrete Math. - 2008. - Vol. 22. - P. 719-736.

⁷Glebov, R. On the maximum number of Latin transversals / R. Glebov, Z. Luria // J. Combin. Theory Ser. A. - 2016. - Vol. 141. - P. 136-146.

бом того же порядка и наоборот.

Трансверсалью в т-арной квазигруппе / порядка q называется множество {ск*}^_₁ векторов а^г = (а^г₀,а\, ? aln)i al ^ ^qi ^такое> ^{чт0 а}о = f(a\,...,a^l_m) для всех і Є {1,... ,q} и а\ = а³_к для всех г ^ j и к Є {О,..., т}. Обозначим через Т(/) число трансверсалей в квазигруппе /.

Заметим, что между трансверсалями в квазигруппе и в латинском гиперкубе, который представляет собой таблицу Кэли этой квазигруппы, естественным образом устанавливается взаимно однозначное соответствие, поэтому все вопросы о трансверсалях в латинских гиперкубах можно переформулировать для квазигрупп и наоборот. Кроме того, график любой т-арной квазигруппы есть некоторый (т + 1)-мерный МДР-код того же порядка, поэтому подсчет числа трансверсалей в т-арной квазигруппе эквивалентен вычислению перманента некоторой полистохастической (0,1)-матрицы.

m-Арные квазигруппы / и д порядка q изотопны, если для некоторого набора из т + 1 перестановки а і Є S_q, і = 0,..., m выполняется

/(жі,..., х_т) = o-Q¹ (д((Ті(хі),..., (J_m(x_m))).

m-Арная квазигруппа / порядка q является суперпозицией (т — к)-арной квазигруппы h и (& + 1)-арной квазигруппы д_: если существует такая перестановка а Є S_m+i, что для всех хо, , х_т Є T,_q верно

/(ж_Ь...,Ж_т) = Хо ^р(ж_ст(0),Ж_ст(і),...,Ж_ст(А;)) = /і(ж_ст(А;₊і),...,Ж_ст(_т)).

т-Арная квазигруппа / при т > 3 называется полностью разделимой, если она является суперпозицией полностью разделимых квазигрупп h\ и /і2, арность каждой из которых не меньше 2. Все бинарные квазигруппы также считаются полностью разделимыми.

Одним из наиболее простых примеров полностью разделимых квазигрупп является т-арная итерированная группа Ъ_ч:

«/ v 1 ? ' ' ' ' '*^jrn) "^0 ^<^^> ^0 ~г **Ч ~г ~г Х_т U, Х{ t iLiqi

где + означает групповую операцию в Ъ_я. Таблица Кэли этой квазигруппы есть в точности латинский гиперкуб Q, а ее график - это МДР-код М.⁺¹.

Приведем также некоторые определения из теории гиперграфов.

Пара Н = (X, W) называется гиперграфом с множеством вершин X и множеством гиперребер W, где каждое гиперребро w Є W есть некоторое подмножество вершин X. Гиперграф Н называется d-униформным, если каждое его гиперребро состоит ровно из d вершин.

Обозначим через H^d_n полный d-униформный гиперграф на п вершинах, то есть гиперграф, множество гиперребер которого состоит из всех (i-элементных подмножеств вершин.

Будем говорить, что гиперграф Н имеет 1-фактор, если он содержит непересекающийся по вершинам набор гиперребер, покрывающий все

множество вершин. Гиперграф Н называется 1-факторизуемым, если он может быть представлен в виде непересекающегося по гиперребрам объединения 1-факторов. Обозначим через <р(Н) число 1-факторов в гиперграфе Н. 1-Факторы в гиперграфах являются естественным обобщением понятия совершенного паросочетания в графах.

Как и для графов, так и для униформных гиперграфов сложно найти необходимые и достаточные условия существования в них 1-факторов. Проблема существования 1-факторов в гиперграфах рассматривается, например, в работах^{8 9 10}.

Гиперграф Н называется простым, если он не содержит кратных гиперребер. Матрицей смежности А(Н) простого <і-униформного гиперграфа Н на п вершинах назовем такую <і-мерную (ОД)-матрицу порядка п, что ее элемент <2a_b...,a_d равен единице тогда и только тогда, когда множество вершин {«і,..., ad} является гиперребром гиперграфа Н. Данное определение матрицы смежности гиперграфа обобщает понятие матрицы смежности графа.

Гиперграф Н = (X, W) называется d-долъным, если множество его вершин может быть разделено на такие d подмножеств (долей), что каждое гиперребро содержит ровно по одной вершине из каждого подмножества. Очевидно, что любой d-дольный гиперграф является <і-униформньім.

Пусть Н - <і-дольньій гиперграф с долями мощности п. Матрицей смежности долей А(Н) гиперграфа Н назовем такую <і-мерную матрицу порядка п, что ее элемент a_au„_nad равен кратности гиперребра (а\,..., ad) в гиперграфе Н, где а{ - вершина из доли с номером і. Таким образом, между неотрицательными целочисленными <і-мерньіми матрицами и d-дольными сбалансированными гиперграфами есть взаимно однозначное соответствие, и, как несложно видеть, перманент матрицы смежности долей А(Н) равен числу 1-факторов в гиперграфе Н. Данное соответствие было описано С. Дж. Доу и П. М. Гибсоном¹¹.

Считается, что понятие перманента двумерных матриц ввел в 1812 году О. Л. Копій¹², а значит, история перманентов насчитывает уже более двухсот лет. Свойства перманентов хорошо изучены, и для них обнаружены разнообразные применения в теории графов, в теории комбинаторных структур, и даже в физике. Наиболее известно использование перманента для подсчета числа совершенных паросочетаний в двудольном графе.

⁸Lo, A. Perfect matchings in 3-partite 3-uniform hypergraphs / A. Lo, K. Markstrom // J. Combin. Theory Ser. A. - 2014. - Vol. 127. - P. 22-57.

⁹R6dl, V. Perfect matchings in large uniform hypergraphs with large minimum collective degree / V. Rodl, A. Ruciriski, E. Szemeredi // J. Combin. Theory Ser. A. - 2009. - Vol. 116. - P. 613-636.

¹⁰Treglown, A. Exact minimum degree thresholds for perfect matchings in uniform hypergraphs / A. Treglown, Yi. Zhao // J. Combin. Theory Ser. A. - 2012. - Vol. 119. - P. 1500-1522.

¹¹Dow, S. J. Permanents of d-dimensional matrices / S. J. Dow, P. M. Gibson // Linear Algebra Appl. — 1987. - Vol. 90. - P. 133-145.

¹²Cauchy, A.-L. Memoire sur les fonctions qui ne peuvent obtenir que deux valeurs egales et de signes contraires par suite des transpositions operees entre les variables qu'elles renferment / A.-L. Cauchy // J. Ec. Polyt. - 1812. - Vol. 10, Cah. 17. - P. 29-112.

Исследованию перманентов посвящено множество работ, причем в значительной их части рассматриваются перманенты дважды стохастических матриц. Максимально полное для своего времени описание свойств перманента приведено в книге¹³ X. Минка 1982 года.

На перманенты двумерных матриц получено множество нижних и верхних оценок. Для (ОД)-матриц наиболее известна верхняя оценка перманента на основе числа единиц в строках матрицы, которая изначально была высказана в качестве гипотезы¹⁴ X. Минком, а первое ее доказательство было найдено Л. М. Брэгманом¹⁵.

Положительность перманента двумерных неотрицательных матриц несложно проверяется с помощью критерия Кёнига-Фробениуса, который утверждает, что перманент неотрицательной матрицы порядка п положителен тогда и только тогда, когда сумма размеров любой ее нулевой подматрицы не превосходит п.

Одним из простых следствий этого критерия является тот факт, что перманент неотрицательной матрицы, у которой суммы элементов в любой строке и любом столбце совпадают, всегда положителен. Наилучшая нижняя оценка для перманента таких матриц с целыми элементами получена А. Схрейвером¹⁶.

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

Рассмотрим задачу определения минимума и максимума перманента на множестве дважды стохастических матриц. Несложно понять, что максимальное значение, равное единице, перманент принимает на диагональной матрице. Гипотеза о том, что минимум перманента дважды стохастических матриц достигается на равномерной матрице, была высказана Б. Л. ван дер Варденом в 1926 году, а доказана лишь в 1980 году независимо Г. П. Егорычевым¹⁷ и Д. И. Фаликманом¹⁸.

Одно из первых обобщений перманента на многомерный случай было предложено А. Кэли в 1849 году¹⁹. Затем перманент многомерной матрицы

¹³Минк, X. Перманенты / X. Минк. - М.: Мир, 1982. - 213 с.

¹⁴Minc, Н. Upper bound for permanents of (0,l)-matrices / H. Mine // Bull. Amer. Math. Soc. — 1963.

- Vol. 69. - P. 789-791.

¹⁵Брэгман, Л. M. Некоторые свойства неотрицательных матриц и их перманентов / Л. М. Брэгман // Докл. АН СССР. - 1973. - Т. 211, № 1. - С. 27-30.

¹⁶Schrijver, A. Counting 1-factors in regular bipartite graphs / A. Schrijver // J. Combin. Theory Ser. B.

- 1998. - Vol. 72, No. 1. - P. 122-135.

¹⁷Егорычев, Г. П. Решение проблемы Ван дер Вардена для перманентов / Г. П. Егорычев // Сиб. мат. журнал. - 1981. - Т. 22, № 6. - С. 65-71.

¹⁸Фаликман, Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы / Д. И. Фаликман // Матем. заметки. - 1981. - Т. 29, № 6. - С. 931-938.

¹⁹Cayley, A. On the theory of determinants / A. Cayley // Trans. Cambridge. Philos. Soc. — 1849. —

и его свойства были упомянуты Т. Мюиром , в работе которого многомерный перманент возникает как одно из обобщений детерминанта.

До последнего времени работы С. Дж. Доу и П. М. Гибсона, опубликованные в 1980-е годы, были единственными работами, в которых многомерный перманент являлся основным объектом исследования. В этих работах приведены доказательства некоторых простых, но важных свойств перманентов многомерных матриц.

Существует несколько возможных обобщений двумерного перманента на многомерный случай. Основное отличие между ними состоит в различных определениях диагонали.

Пусть А - (і-мерная матрица порядка п. Определим г-диагональ матрицы А как множество индексов элементов МДР-кода с расстоянием г и обозначим через D_r{A) множество всех r-диагоналей матрицы А. г-Перманентом матрицы А назовем величину

РЄГ_ГЛ = ^2 П^аа

pGD_r(A) аЄр

При г = d имеем определение перманента, принятое за основное в этой работе. Как известно, только МДР-коды с расстояниями 2nd существуют в любой (і-мерной матрице. Поэтому случай г = 2, как и г = d, достоин особого внимания. Кроме того, для 2-перманента также можно найти приложения в задачах перечисления. Например, так как число (d— 1)-мерных латинских гиперкубов порядка п равно 2-перманенту единичной (і-мерной матрицы порядка п, то с помощью оценки 2-перманента такой матрицы Н. Линиал и 3. Лурия²¹ получили верхнюю оценку на число латинских гиперкубов.

В пользу выбора <і-перманента как основного обобщения двумерного перманента говорит тот факт, что r-перманент любой (і-мерной матрицы А порядка п равен <і-перманенту подходящей многомерной матрицы. Впервые такая конструкция была описана С. Дж. Доу и П. М. Гибсоном²², и с ее помощью они получили верхнюю оценку 2-перманента²³.

Целью данной работы является изучение свойств перманента многомерных матриц и поиск возможностей для его применения к оценке и подсчету числа различных комбинаторных структур. По-видимому, множество возможных приложений многомерных перманентов существенно богаче, чем множество приложений перманентов двумерных матриц. Много-

Vol. 8. - Р. 75-88.

²⁰Muir, Т. A treatis on the theory of determinants / T. Muir. — London: Macmillan and Co., 1882. — 774 p.

²¹Linial, N. An upper bound on the number of high-dimensional permutations / N. Linial, Z. Luria // Combinatorica. - 2014. - Vol. 34, No. 4. - P. 471-486.

²²Dow, S. J. Permanents of d-dimensional matrices / S. J. Dow, P. M. Gibson // Linear Algebra Appl. — 1987. - Vol. 90. - P. 133-145.

²³Dow, S. J. An upper bound for the permanent of a 3-dimensional (0,l)-matrix / S. J. Dow, P. M. Gibson // Proc. Amer. Math. Soc. - 1987. - Vol. 99, No. 1. - P. 29-34.

мерные перманенты тесно связаны с такими объектами, как трансверсали в латинских гиперкубах, 1-факторы в гиперграфах, замощения транзитивных графов, МДР-коды и комбинаторные дизайны. Многие результаты относительно данных объектов, можно переформулировать в терминах перманентов многомерных матриц, а многомерные перманенты в свою очередь могут помочь в решении некоторых проблем для таких объектов. Как и в случае двумерных матриц, многомерные перманенты находят свое применение в физике для описания взаимодействий элементарных частиц²⁴.

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

Научная новизна и значимость. Работа носит теоретический характер. Все результаты, представленные в диссертации, являются новыми и снабжены полными доказательствами. Полученная в данной работе верхняя оценка на число трансверсалей в латинских квадратах и гиперкубах существенно улучшает ранее известные оценки и является асимптотически точной, а для полного униформного гиперграфа найдена первая нетривиальная оценка числа его 1-факторизаций. Результаты о трансверсалях в квазигруппах порядка 4 дают новое подтверждение гипотезы Я. М. Уон-лесса о существовании трансверсалей в латинских гиперкубах.

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

Методы исследования. В диссертации используются методы дискретного и математического анализа, комбинаторные и алгебраические методы, методы теории графов и гиперграфов.

Основные результаты диссертации.

1. Доказана асимптотически точная с ростом порядка верхняя оценка

²⁴Tichy, М. С. Partially distinguishable Boson-Sampling and the multi-dimensional permanent / M. С Tichy // Physical Review A. - 2015. - Vol. 91, No. 2. - 022316.

перманента полистохастических матриц, из которой в качестве следствия получена асимптотически неулучшаемая верхняя оценка числа трансвер-салей в латинских квадратах и гиперкубах.

1. Получено обобщение верхней оценки числа 1-факторов графа через перманент его матрицы смежности на случай униформных гиперграфов. Доказана верхняя оценка на число 1-факторизаций полного dуниформного гиперграфа.

2. Найдена нижняя оценка числа трансверсалей в полностью разделимых квазигруппах нечетной арности. Доказано, что на множестве n арных квазигрупп порядка 4 только квазигруппы, изотопные итерированной группе Z4 четной арности, не содержат трансверсалей. Для итерированных групп Z4 и 1^2 произвольной арности вычислено количество трансверсалей.

Публикации. Результаты, полученные в данной диссертации, опубликованы в 14 работах, из которых 6 работ издано в журналах из списка ВАК, а 8 работ - в трудах и тезисах конференций.

Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

IX Молодежная научная школа по дискретной математике и ее приложениям. (Москва, 2013).

Moscow Workshop on Combinatorics and Number Theory. (Москва, 2014).

European Conference on Combinatorics, Graph Theory and Applications 2015. (Берген, Норвегия, 2015).

39th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. (Брисбен, Австралия, 2015).

7th European Congress of Mathematics (Берлин, Германия, 2016).

International Conference and PhD-Master Summer School on Graphs and Groups, Spectra and Symmetries. (Новосибирск, 2016).

Семинар по теории кодирования Института проблем передачи информации им. А. А. Харкевича РАН. (2014).

Общеинститутский семинар Института математики им. С. Л. Соболева СО РАН. (2016).

Семинары «Теория кодирования» и «Дискретный анализ» Института математики им. С. Л. Соболева СО РАН и кафедры теоретической кибернетики НГУ. (2013-2017).

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Объем диссертации составляет 130 страниц. Список литературы содержит 66 наименований.

Применение перманента для подсчета числа комбинаторных объектов

Проблемам существования систем Штейнера с заданными параметрами и оценки их числа посвящено немало работ. Например, верхняя оценка на число троек Штейнера доказана в работе [32], а асимптотика числа систем Штейнера для любых допустимых наборов параметров анонсирована в [30].

Рассмотрим граф G(V, Е) такой, что все его максимальные клики име ют мощность d. Набор максимальных клик назовем совершенным кликосоче танием, если объединение этих клик однократно покрывает все вершины гра фа. Обозначим через PCM(G) число совершенных кликосочетаний в графе G. Построим по графу G d-униформный гиперграф HPCM(G) такой, что верши ны этого гиперграфа являются вершинами графа G, а гиперребра HPCM(G) соответствуют максимальным кликам в графе G. Легко видеть, что число 1 факторов в гиперграфе Hpcu{G) равно числу совершенных кликосочетаний в графе G: 4 (HPCM(G)) = PCM(G). 3. Следующая конструкция была предложена СВ. Августиновичем в ра боте [1].

Пусть G(V, Е) - регулярный граф. Обозначим через Aut((7) группу автоморфизмов графа G (группу отображений вершин графа на себя, сохраняющих смежность). Граф G называется транзитивным если группа Aiit(G) транзитивно действует на множестве его вершин, то есть если для любых и, v Є V существует автоморфизм а Є Aut((7) такой, что и = a(v).

Выберем некоторое подмножество S мощности d вершин регулярного транзитивного графа G и назовем его плиткой. Набор автоморфизмов { 2i}f=1 называется замощением графа G плиткой S, если (ii(S) П CLJ(S) = 0 для всех і j j, и для каждой вершины v Є V существует такой автоморфизм а , что v при зо надлежит tti(S). Обозначим через T(G,S) число замощений графа G плиткой S.

Построим і-униформньій гиперграф HT(G,S): вершинами которого являются все вершины графа G, а каждое гиперребро есть множество вершин a(S) для некоторого автоморфизма а Є Aut((7). Если гиперграф HT(G} S) является (і-дольным (то есть если его вершины можно разбить на d групп мощности п так, чтобы пересечение всех a(S) с любой из этих групп было не пусто), то для него можно построить матрицу смежности долей AT(G, S): которая будет иметь размерность d и порядок п, и перманент которой совпадет с числом замощений графа G плиткой S: peTAT(G,S) = T(G,S). Большинство перечисленных далее конструкций являются частными случаями данной.

Замощением конечной абелевой группы (R, +) называется такая пара подмножеств (плиток) S и Т, что S + Т = R и \S\\Т\ = \R\. Обозначим через s мощность плитки S: а через GT(R, S) число замощений группы R плиткой S. Рассмотрим гиперграф HGT(R, S), множеством вершин которого является множество всех элементов группы Л, а гиперребра есть множества вида х — S для некоторого элемента х Є R. Заметим, что число гиперребер в этом гиперграфе равно числу его вершин и что он является s-униформным и s-регулярным. Если в группе R существует хотя бы одно замощение (S, Т) плиткой S: то гиперграф HQT(R., S) будет s-дольным, причем в качестве долей можно взять множества s + T, s Є S. Любому замощению группы R плиткой S можно поставить в соответствие как 1-фактор в HGT(R, S): так и трансверсаль. Таким образом, число замощений группы R равно и перманенту матрицы смежности долей AQT{R-, S) размерности s и порядка -R/s, и перманенту матрицы смежности 1-факторов AGT(R, S) той же размерности и того же порядка: GT{R, S) = регЛст(Л, S) = perAGT{R, S). 5. Пусть JJI есть булев гиперкуб размерности п. Совершенным кодом С в гиперкубе Z называется такое подмножество, что любой шар единичного радиуса в Z содержит ровно один элемент из С.

Несложно видеть, что мощность каждого совершенного кода С равна N = —т. Совершенные коды существуют только в булевых гиперкубах Щ с п = 2т — 1, причем любой такой гиперкуб можно разбить на D = п + 1 непересекающихся совершенных кодов. Обозначим через РС(п) число совершенных кодов в гиперкубе Щ.

Заметим, что граф кратчайших расстояний в гиперкубе Z будет транзитивным графом, в качестве плитки в нем мы рассмотрим шар единичного радиуса и построим D-униформный гиперграф Нрс(п): число 1-факторов в котором будет равно числу замощений булева куба шарами единичного радиуса. Так как гиперкуб Ъ\ разбивается на совершенные коды, то гиперграф Нрс(п) будет D-дольным, а если в качестве автоморфизмов Ky6aZ мы будем рассматривать только сдвиги на ненулевой вектор, то Нрс(п) будет простым. Матрица смежности долей гиперграфа Нрс(п) является D-мерной (ОД)-матрицей поряд-ка N = —j, и число всех совершенных кодов в булевом гиперкубе Z совпадает с ее перманентом: ретАрс(п) = РС(п).

Обозначим через Z n-мерный гиперкуб порядка q, а через MDS(n} q} d) количество МДР-кодов с расстоянием d в Z . .

Построим гиперграф HMDS{ I q,d): вершинами которого являются все (d— 1)-мерные грани в гиперкубе Z" а любое гиперребро есть такой набор различных D = Cdn l (d — 1)-мерных граней, что в их пересечении лежит ровно один элемент гиперкуба Z"\ Полученный гиперграф является простым и D-дольным, где в качестве долей можно взять все (d— 1)-мерные грани одного направления.

Экстремумы перманента полистохастических матриц

Если в этих рассуждениях грани Ір являются одномерными, то матрицы Аа двумерны, и их перманенты можно оценить с помощью теоремы Брэгмана. Поэтому верно следующее утверждение.

Утверждение 7. Пусть А - d-мерная (0,1)-матрица порядка п, 1р - одномерные грани матрицы А некоторого направления, гр - сумма элементов в грани 1р. Построим (d— 1)-мерную матрицу В порядка п с элементами Ьр = г#!1/Г/3. Тогда ретА ретВ.

Если в каждой гиперграни матрицы В мы заменим все элементы на максимальный в гиперграни и воспользуемся линейностью перманента, то в правой части неравенства утверждения 7 возникнет перманент некоторой (d — 1)-мерной (ОД)-матрицы. Для оценки этого перманента можно снова применить утверждение 7, что даст следующий результат.

Теорема 21. Пусть А - d-мерная (О,1)-матрица порядка п. Выберем в матрице А систему 01,... ,0 -1 вложенных направлений граней: вектор Ok задает направление к-мерных граней, и вектор 0&-i получается из вектора Ok заменой одного нуля на единицу (на каждом шаге одна из переменных координат становится фиксированной). Считаем, что гиперграни направления Od-i пронумерованы числами от 1 до п. Предположим, что для 1 к d — 1 все единичные элементы к-мерных граней направления Ok, лежащих в г-ой гиперграни, можно покрыть s k (к — \)-мерными гранями направления Оk-i- Тогда d—l п perA Hl[sbk\l/s k. к=\ г=1 Равенство в этом неравенстве будет достигаться, например, на блочно-диагональных матрицах. В то же время оценка сильно зависит от расположения единиц в гранях матрицы и часто не точна.

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

Пусть HLS(TI) - гиперграф, вершинами которого являются вершины куба Z , а гиперребра соответствуют МДР-кодам с расстоянием 2 в Z , и пусть Abs(n) - матрица смежности долей этого гиперграфа. Как было показано ранее, размерность и порядок матрицы ALS(TI) равны п, и ее перманент совпадает с числом латинских квадратов порядка п. Для краткости обозначим это число через LS(n).

Заметим, что для любого 2 к d — 1 для покрытия всех единиц в к-мерных гранях матрицы ALS(TI) необходимо не более к — 1 штук (к — 1)-мерных граней, а любая одномерная грань матрицы ALS(TI) содержит не более одной единицы. По теореме 21 п— 1 п п LS(n) = n\peiALS(n) п\ Y[ П к]1/к = П к]П/кі к=\ г=1 к=\ что совпадает с классической верхней оценкой числа латинских квадратов. Можно также доказать, что гипотеза 5 выполняется асимптотически для матриц с достаточно большим числом единиц в гипергранях.

Обозначим через Ad(n,r) множество всех d-мерных (0,1)-матриц порядка п, у которых количество единиц в і-ой гиперграни не превосходит Г{{п), и введем функцию F(x) = \х\\1 х . Тогда Гі{п)\ -j-jr І при п — оо. п , max регЛ n!d"V(n) П W AeAd(n,r) х4- \ П 1=1

Доказательство. Докажем теорему индукцией по размерности матрицы. Базой индукции является случай d = 2, который легко проверяется с помощью теоремы 1.

Предположим, что для размерности d—1 теорема верна и докажем теорему для размерности d. Пусть А - произвольная матрица из Ad(n,r). Тогда г-ая гипергрань некоторого направления матрицы Л содержит не более Г І{ГІ) единиц.

Зафиксируем такое направление одномерных граней, что все грани 1р этого направления целиком лежат в выбранных гипергранях, и предположим, что в грани 1/з содержится sp единиц. Рассмотрим (d — 1)-мерную матрицу В с элементами Ьр = spl1 . Из утверждения 7 имеем, что ретА ретВ. Обозначим f(x) = х\1 х. Используя известные оценки факториала, для функции f(x) можно получить следующие неравенства: (2тгх)1/2ххе-1 f(x) е1/хх1+1/2хе-\ Обозначим правую часть этого неравенства функцией д(х). Можно проверить, что д(х) - вогнутая функция.

Факторы и 1-факторизации гиперграфов

Перед первым этапом выберем вершину у\ для подмножества Y\_, которая покроет некоторую фиксированную вершину х\ Є X. Заметим, что выбрать такую вершину у\ можно тремя способами.

Предложим, что после к-ото этапа мы имеем Y{ = { yj,... , угШi}, і Є {1, 2,3}, где mi + vfi i + Шз 2k + 1, и ни одна из вершин х Є X не смежна в точности двум вершинам из Y\ U У? U У3. Так как граф связен, то существует вершина х Є X, которая покрыта ровно одной вершиной из УЇ UI2UI3. Без ограничения общности можно считать, что х смежна некоторой вершине из Y\. Тогда число способов выбрать вершины у2 для множества І2 и у3 для множества Уз, покрывающие вершину ж , равно двум. Если существует, например, вершина х \ которая смежна некоторым вершинам у{ Є Y\ и у\ 2 и не смежна всем вершинам из Уз, то последняя вершина, покрывающая ж" находится однозначно и добавляется во множество Уз. Продолжаем этот процесс до тех пор, пока каждая вершина х Є X не станет смежной трем, одной или ни одной вершинам из Yi U У2 U У3 Заметим, что самая последняя вершина в построении множеств УЇ, У? и Уз определяется однозначно. Так как на каждом этапе мощность Y\ U У? U Уз возрастает не менее чем на 2, то общее количество этапов не превосходит — 1. Следовательно, число правильных разбиений доли Y Т(В) 3-2n 2 1. Для оценки величины Р{В) используем теорему Схрейвера (теорему 3) и учтем, что перманент матрицы, две диагонали которой заполнены единицами, не меньше 2: Р(В) 2 ()". Таким образом, Т(В) 3n+1 Зп _ 1 Р(В) 23-/2+2 72" = м(п?з)" Как было отмечено ранее, из леммы 7 следует утверждение 8, а значит, можно считать доказательство теоремы 24 завершенным.

Для і-дольньіх гиперграфов несложно доказать другую оценку числа 1-факторов. Но при большом числе вершин в гиперграфе она будет хуже оценки из теоремы 24.

Пусть LS(n) есть число всех латинских квадратов порядка п, а через QS(n) обозначим число всех латинских квадратов, у которых один из столбцов (например, первый) фиксирован. Несложно видеть, что LS(n) = QS(n)n\.

Сначала докажем небольшую вспомогательную лемму: Лемма 8. Пусть U(d) - d-мерная (0,1)-матрица порядка d такая, что ее элемент иа = 1 тогда и только тогда, когда все компоненты а\}... , а различны. Тогда перманент матрицы U(d) равен числу латинских квадратов с фиксированным заполнением одного из столбцов: peril = QS{d). Доказательство. Пусть набор индексов (а1,..., ad) формирует единичную диа гональ в матрице U(s). Составим таблицу Т размера dxdc элементами tij = аг-. В любой строке Т все элементы различны, так как индекс аг соответствует еди ничному элементу матрицы U(d). В любом столбце таблицы Т значения эле ментов также различны, так как индексы (а1,..., а ) формируют диагональ, а значит, ни на какой позиции в них не могут оказаться два одинаковых элемента. Следовательно, таблица Т является латинским квадратом порядка d. По любому латинскому квадрату порядка d аналогичным образом строится еди ничная диагональ в матрице U(d). Заметим, что любая перестановка строк квадрата Т не меняет диагональ, которой соответствует этот квадрат. Поэтому перманент U равен числу латинских квадратов с фиксированным заполнением одного из столбцов. Докажем с помощью этой леммы оценку на число 1-факторов в /с-сбалан-сированном (і-дольном гиперграфе:

Доказательство. Занумеруем доли гиперграфа Н от 1 до d. Так как гиперграф Н - і-дольньій, то его матрицу смежности А{Н) можно разбить на блоки vp порядка к: где (3 = (/Зі,..., (3d) и (ЗІ Є {1,..., d}, такие, что элемент аа попадает в блок V/з тогда и только тогда, когда вершина с номером oti принадлежит Д-ой доли гиперграфа Н. Заметим, что единицы матрицы А{Н) могут содержаться только в таких блоках vp: что все значения /Зі,..., (3d различны. Поэтому семерная (ОД)-матрица порядка d: элемент которой равен единице тогда и только тогда, когда блок vp содержит единицы, совпадает с матрицей U(d).

Рассмотрим произвольный 1-фактор в гиперграфе Н. Заметим, что гиперребра этого 1-фактора можно ориентировать так, чтобы все соответствующие этой ориентации элементы А{Н) сформировали частичную диагональ длины к, целиком лежащую в некотором блоке vp. Если / Є $(Н) есть набор из d 1-факторов гиперграфа Н и (/З1,..., (3 ) - единичная диагональ в матрице U(d), то можно ориентировать правильно гиперребра і-ого 1-фактора / так, чтобы соответствующие им элементы А{Н) сформировали частичную единичную диагональ, лежащую в блоке Vpi. Объединение всех элементов, соответствующих гиперребрам /, даст единичную диагональ в А{Н). Таким образом, число правильных ориентации фиксированного набора / из d 1-факторов не меньше перманента матрицы U(d).

Трансверсали в полностью разделимых квазигруппах

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

Доказательство. 1. По лемме 15 любая полулинейная квазигруппа нечетной арности п содержит 8n_1 трансверсалей, порожденных сдвоенными четверками. Также напомним, что по лемме 16 для стандартной полулинейной квазигруппы, определенной булевой функцией Л, типичная четверка (z1, z2, z3, zA) соответствует трансверсалям квазигруппы тогда и только тогда, когда X(zl) 0 Х(72) 0 Ар) 0 А(?) = 0.

Из леммы 11 получаем, что любая п-арная Z2,-линейная квазигруппа изо 120 топна стандартной полулинейной квазигруппе /Z2, заданной с помощью тождественно нулевой булевой функции \j2. Следовательно, для любой типичной четверки (V, z2, z3, z4) сумма X (zl) ф\ (г2) ф\ (г:і) фА22(г4) равна нулю, а значит, каждая типичная четверка порождает трансверсали в квазигруппе / .

Далее, по лемме 10 любая n-арная Z4-линейная квазигруппа изотопна стандартной полулинейной квазигруппе /z4, заданной такой булевой функцией Az4, что Xz4(z) = 0, если вес z сравним с 0 или 3 по модулю 4, и Xz4(z) = 1, если вес z сравним с 1 или 2 по модулю 4.

Рассмотрим типичную четверку (z1, z2, z3, zA) в (п + 1)-мерном булевом гиперкубе. По определению каждый вектор z имеет четный вес и w{zl) +w{z2) + w{zi) + w{zA) = 2n + 2 = 0 mod 4. Тогда число векторов z\ вес которых сравним с 2 по модулю 4, четно, а значит, четное число векторов zi имеют вес сравнимый с 1 или 2 по модулю 4. Отсюда Az4P) Є Az4p) 0 AZ4p) 0 AZ4p) = 0, и каждая типичная четверка порождает трансверсали в квазигруппе/ . Из леммы 16 имеем, что любая типичная четверка соответствует ровно 2 . 4П_1 трансверсалям в квазигруппах /Z2 и /z4- Таким образом, T{hi) = T(fZ4) = 2 r-lW(n) + 8й"1 = = — Г-1 (бп - 3 2n) + 8n_1 = - 24n_1 + 5 8n"2. 2. Если n четно, то трансверсалям полулинейных квазигрупп могут соответствовать только типичные четверки.

Как и раньше, n-арные Ж -линейные квазигруппы изотопны стандартной полулинейной квазигруппе /Z2, определенной с помощью тождественно нулевой булевой функции, и все типичные четверки порождают ровно 2 4П_1 трансвер-салей в квазигруппе fj2. Поэтому T(f) = 2 4n-lW(n) = — 4 1 (6n - 2n) = - 24n": - 8n"2.

Так как в квазигруппах f%4 нечетной арности и в квазигруппах fjp. любая типичная четверка дает трансверсали, то эти квазигруппы содержит максимальное число трансверсалей среди всех полулинейных квазигрупп. По лемме 17, если для некоторой булевой функции А и для каждой типичной четверки (z1, z2, z3, zA) выполнено X(zl) A(z2) ф A(z3) 0 A(z4) = 0, то для любой двумерной грани Р n-мерного булева гиперкуба имеем, что сумма X(z) сравнима Z&P либо с 0, либо с 1 по модулю 2 для нечетного п и сравнима с 0 по модулю 2 для четного п. Из леммы 11 следует, что такие булевы функции могут определять только Z4-линейные и Zr -линейные квазигруппы.

Заметим, что тривиальная верхняя оценка на число трансверсалей в п-арных квазигруппах порядка 4 есть 4!n_1 = 24n_1, и что число трансверсалей в Zr -линейных и Z HHeftHbix квазигруппах довольно близко к данной оценке. Поэтому можно предположить, что верна

Линейные квазигруппы нечетной арности и Щ-линейные квазигруппы имеют максимальное число трансверсалей во множестве всех п-арных квазигрупп порядка 4.

Численные данные, полученные при помощи [38], подтверждают эту гипотезу для всех п 5. Перечислим основные результаты данной работы:

1. Доказана асимптотически точная с ростом порядка верхняя оценка перманента полистохастических матриц, из которой в качестве следствия получена асимптотически неулучшаемая верхняя оценка числа трансверсалей в латинских квадратах и гиперкубах.

2. Получено обобщение верхней оценки числа 1-факторов графа через перманент его матрицы смежности на случай униформных гиперграфов. Доказана верхняя оценка на число 1-факторизаций полного dуниформного гиперграфа.

3. Найдена нижняя оценка числа трансверсалей в полностью разделимых квазигруппах нечетной арности. Доказано, что на множестве n-арных квазигрупп порядка 4 только квазигруппы, изотопные итерированной группе Z4 четной арности, не содержат трансверсалей. Для итерированных групп Z4 и Z произвольной арности вычислено количество трансверсалей.