ПЕРМАНЕНТЫ

Х.Минк ПЕРМАНЕНТЫ В книге известного американского математика X. Минка впервые дано достаточно полное изложение теории перманентов — развивающейся области комбинаторной математики. Приводится обзор результатов, связанных с приложениями перманентов к решению теоретико-вероятностных, комбинаторных и физических задач. Включены упражнения, дополняющие излагаемый материал. Для специалистов, использующих комбинаторику в практической деятельности, для студентов, изучающих эту область. ОГЛАВЛЕНИЕ Предисловие редактора перевода 5 От редактора Энциклопедии 7 Предисловие редактора серии 8 Предисловие автора 11 Глава 1. Теория перманентов в ее историческом развитии 13 1.1. Введение 13 1.2. Основоположники: Бине и Коши 14 1.3. Продолжатели: Борхарт, Кэли и Мастер из Эдинбурга — сэр Томас 17 Мюир 1.4. Ренессанс теории перманентов: теорема Мюирхеда, проблема Пойа, 20 неравенство Шура и гипотеза Ван дер Вардена 1.5. Новая эра: Марвин Маркус и К° 24 Задачи 26 Глава 2. Свойства перманентов 28 2.1. Элементарные свойства 28 2.2. Функция перманента как скалярное произведение 32 Задачи 39 Глава 3. (0,1)-матрицы 40 3.1. Матрицы инцидентности 40 3.2. Теоремы Фробениуса и Кёнига 42 3.3. Структура квадратных (0, 1) -матриц 45 3.4. (0, 1) -циркулянты 55 Задачи 59 Глава 4. Нижние границы для перманентов 62 4.1. Теорема Маршалла Холла 62 4,2. (0, 1) -матрицы 64 4.3. Вполне неразложимые (0, 1) -матрицы 68 4.4. Неотрицательные матрицы 72 4.5. Положительно полуопределенные эрмитовы матрицы 76 Задачи 80 Глава 5. Гипотеза Ван дер Вардена 83 5.1. Теория Маркуса — Ньюмена 83

5.2. Свойства минимизирующих матриц 5.3. Некоторые частные результаты. Теорема Фридленда 5.4. Гипотеза Маркуса и Минка 5.5. Нижние границы для перманентов дважды стохастических матриц Задачи Глава 6. Верхние границы для перманентов 6.1. От Мюира к Юркату и Райзер 6.2. (0, 1)-матрицы 6.3, Неотрицательные матрицы 6.4. Комплексные матрицы Задачи Глава 7. Вычисление перманентов 7.1. Метод Бине — Минка 7.2. Метод Райзера 7.3. Сравнение методов вычисления Задачи Глава 8. Еще о перманентах 8. 1 Другие результаты 8.2. О применениях перманентов 8.3. Гипотезы и нерешенные проблемы — «урожай» 1965 г. 8.4. Гипотезы и нерешенные проблемы — новый список Задачи Список литературы Послесловие

91 95 100 104 108 110 110 113 116 119 122 124 124 127 129 131 133 133 139 151 157 162 164 210