ОТЗЫВ

официального оппонента на диссертацию Тараненко Анны Александровны «Перманенты многомерных матриц в задачах дискретной математики» представленную на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 – «Дискретная математика и математическая кибернетика».

Комбинаторика как наука прошла долгий путь. Началом этого пути можно считать задачи комбинаторного характера, появляющиеся в переписке Б. Паскаля и П. Ферма, которые их современниками рассматривались, скорее, как математические головоломки, но при этом заложили фундамент теории вероятностей. На современной нам точке этого пути комбинаторика – это дисциплина, вбирающая в себя широчайший спектр математических методов и имеющая не менее широкий спектр теоретических и практических приложений (от сложностных аспектов теории алгоритмов до моделей социальных и компьютерных сетей).

Есть в комбинаторике объекты, в отношении которых появляющиеся новые подходы и методы порождают больше вопросов, чем закрывают. К таковым, думается, смело можно отнести понятие перманента. Даже в простейшем двумерном случае и даже для простейшего класса матриц перманент уже ведет себя совершенно непредсказуемо в сравнении с ближайшим своим «концептуальным соседом» – определителем: если определитель над некоторыми полями (в частности, над конечными или над полем рациональных чисел) тривиальным образом вычисляется за полиномиальное время, то задача вычисления перманента целочисленной 0-1-матрицы уже вычислительно трудна. Более того, она настолько обща, что снабжение полиномиальной детерминированной машины Тьюринга оракулом, вычисляющим значение перманента, дает вычислительную модель, справляющуюся с любой задачей из полиномиальной иерархии (это содержание известной теоремы С. Тоды, доказанной в 1991 году). Известны и другие задачи, касающиеся перманента, решение которых в свое время воспринималось как крупные математические результаты. В этой связи нельзя не упомянуть гипотезу Ван дер Вардена, доказанную и . Одной из вех теории сложности алгоритмов было введение Л. Дж. Вэлиантом понятий класса #P и #P-полных задач. Тот факт, что пересчетный вариант задачи о булевой выполнимости – #P-полная задача, был ожидаем, но вот полученный Вэлиантом результат о #P-полноте задачи вычисления перманента целочисленной 0-1-матрицы, несомненно, удивителен и является одной из жемчужин теории вычислительной сложности.

НЕ нашли? Не то? Что вы ищете?

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

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

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

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

Введение содержит основные определения и используемые далее обозначения, краткий (но, тем не менее, весьма емкий) исторический обзор, а также описание структуры работы и перечень основных полученных автором результатов.

В первой главе доказаны некоторые базовые свойства перманентов многомерных матриц. Особый интерес в данной главе представляет параграф 1.3, в котором приведены 10 примеров классов комбинаторных объектов, число которых выражается посредством многомерного перманента (системы Штейнера, различные варианты задачи о замощении, совершенные коды, МДР-коды, латинские квадраты, прямоугольники и гиперкубы, специальные виды комбинаторных дизайнов и разбиений множеств).

Вторая глава посвящена исследованию тонких отличий между двумерным и многомерным случаями. В частности, хорошо известно, что перманент любой дважды стохастической матрицы положителен, но при этом существуют полистохастические матрицы с нулевым перманентом. Все известные примеры такого типа строятся для матриц нечетной размерности. Соответственно, возникает гипотеза (недоказанная на настоящий момент) о положительности перманента полистохастической матрицы в случае четной размерности.  Продвинуться в решении этого (и некоторых близких по смыслу вопросов, описанных в этой же главе диссертации) можно за счет исследования экстремумов перманента полистохастической матрицы. Было бы заманчиво предположить, что для полистохастических матриц будет выполнен «аналог» гипотезы Ван дер Вардена, и минимальное значение перманента будет достигнуто на равномерной матрице. Основной результат второй главы диссертации опровергает это предположение. В частности, из теоремы 17 вытекает, что в случае нечетного на равномерной матрице достигается локальный максимум перманента по всем полистохастическим матрицам размерности . Для четного предлагается специальная конструкция полистохастической мерной матрицы, перманент которой асимптотически (с ростом порядка) меньше перманента равномерной матрицы. Данные результаты полностью опровергают гипотезы, выдвинутые ранее в работе С. Доу и П. Гибсона.

Третья глава диссертации является центральной. Именно в ней приведено детальное доказательство основного результата работы – асимптотической оценки максимума перманента полистохастической матрицы (теорема 19 в тексте работы). Соответствующее доказательство технически весьма сложно и занимает около 15 страниц (включая доказательства многочисленных вспомогательных утверждений). Помимо данного результата в третьей главе приведены оценки перманента многомерных матриц.

Четвертая и пятая главы посвящены использованию многомерных перманентов для оценивания количества комбинаторных объектов различной природы. В частности, в главе 4 построены оценки числа 1-факторов в гиперграфе, а также числа 1-факторизаций полного гиперграфа. Главу 5 можно рассматривать как развернутое исследование проблемы подсчета числа трансверсалей в  латинских квадратах гиперкубах и квазигруппах.

Приведем дополнительные комментарии по содержанию диссертации. Нельзя не отметить, что некоторые результаты работы получили живой отклик научного сообщества, занимающегося близкими проблемами (что, конечно же, нечасто бывает с результатами кандидатских диссертаций). В первую очередь, сказанное касается теоремы 19 (асимптотическая верхняя оценка перманента полистохастической матрицы) и ее следствий. Так, из данной теоремы следует верхняя оценка на число трансверсалей в латинских квадратах, и этот результат лежит в русле проблемы, вызывающей в последние годы живейший интерес в среде специалистов по комбинаторике. Особая ценность теоремы 19 в данном контексте заключается в том, что вытекающая из нее асимптотическая верхняя оценка на число трансверсалей в латинских квадратах является неулучшаемой. Это следует из опубликованной в прошлом году работы Р. Глебова и З. Лурии.

По тексту диссертации можно сделать несколько замечаний.


Как уже было отмечено выше, #P-полнота проблемы вычисления перманента двумерной целочисленной 0-1-матрицы является одним из фундаментальных результатов теории сложности алгоритмов. Соответственно, чуть-чуть более детальное касание данного факта и ссылка на работу Л. Вэлианта, в которой он был установлен, дополнительно бы подчеркнули актуальность и значимость представленных в диссертации результатов. В работе Р. Глебова и З. Лурии приведена ссылка на теорему 19, а также альтернативное доказательство верхней оценки числа трансверсалей в латинских гиперкубах. С одной стороны, данный результат выглядит менее общим, чем теорема 19. С другой, в работе Р. Глебова и З. Лурии используется т. н. «энтропийный подход», который, по утверждению авторов, позволяет строить более простые доказательства. Комментарии по этому поводу в диссертации были бы нелишними. Глава 5 явным образом распадается на две части. В первой приводится ряд выражений и оценок, в которых фигурирует перманент. Вторая же часть данной главы (начиная с раздела 5.2) содержит массу результатов, касающихся подсчета трансверсалей в квазигруппах, а также различных структурных свойств квазигрупп, однако перманенты для получения данных результатов не используются.

Ниже приведены замечания редакционного характера.


Обозначение «», используемое на стр. 59, несколько сбивает с толку, поскольку – это мерная матрица порядка , все элементы которой равны , а под понимается мерная матрица порядка , все элементы которой равны . Нумерация результатов, фигурирующая в описании структуры работы (Введение), представляется не вполне удачной – номера основных результатов не совпадают с фактическими их номерами в тексте диссертации. Можно было бы решить данную проблему дополнительными комментариями, например, «Теорема 9 (теорема 19 в главе 3)». На стр. 41 (нижняя часть) в формуле суммирования пропущены индексы: написано вместо .

Перечисленные замечания не носят принципиальный характер и, конечно же, не перевешивают достоинств диссертации. Из текста диссертации виден, без преувеличения, огромный объем проделанной работы. Уровень математических построений, используемых автором, оставляет очень сильное положительное впечатление. Все основные результаты диссертации строго и скрупулезно доказаны. Несмотря на некоторые, довольно трудные моменты, видно желание автора сделать доказательства как можно более понятными – для этой цели используются многочисленные вспомогательные утверждения.

Полученные в диссертации результаты, безусловно, находятся в тренде исследований по данному направлению, которые проводятся в ведущих мировых центрах. Из явно значимых результатов следует отметить аналитический метод построения асимптотической оценки максимума перманента полистохастических матриц и ряд следствий теоремы 19 (в первую очередь, конечно же, неулучшаемую верхнюю оценку на число трансверсалей в латинских квадратах и гиперкубах).

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

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

Не вызывает вопросов актуальность выбранной темы исследования и соответствие работы паспорту специальности 01.01.09 в пункте 1: «Дискретная математика». Диссертационная работа имеет важное теоретическое значение и соответствует требованиям, изложенным в Положении о присуждении ученых степеней, утвержденном Постановлением Правительства Российской Федерации от 01.01.01 г. (в действующей редакции). Автореферат правильно и полно отражает содержание диссертации.

Резюмируя все вышесказанное, считаю, что диссертация «Перманенты многомерных матриц в задачах дискретной математики» является законченной научно-квалификационной работой, в которой получены важные теоретически результаты по использованию перманентов многомерных матриц для оценивания числа комбинаторных объектов разнообразной природы. Диссертация удовлетворяет требованиям, предъявляемым к диссертациям на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 – «Дискретная математика и математическая кибернетика», а ее автор, Анна Александровна Тараненко заслуживает присуждения указанной степени.

Заведующий лабораторией,

кандидат технических наук, доцент                                                

04.05.2017

ФГБУН «Институт динамики систем и

теории управления им.

СО РАН», зав. лабораторий дискретного

анализа и прикладной логики,

к. т.н., доцент.

Адрес: 664033, Иркутск,

тел.: +7 (3952) 42-71-00

e-mail: *****@***ru