Множества, свободные от произведений

• Автор: Петросян, Тарон Гайкович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 52 с.

Введение

I Число множеств, свободных от произведений, в группах, содержащих подгруппу индекса 2
§ 1 Основные понятия и вспомогательные утверждения
§ 2 Асимптотика числа МОП в группах, содержащих подгруппу индекса
II Верхняя оценка числа МСП в одном классе групп
§ 1 Вспомогательные утверждения
§ 2 Число МСП в группах, не содержащих подгрупп индекса 2
III Асимптотика логарифма числа МСП в конечных группах
§ 1 Асимптотика логарифма числа МСП
§ 1.1 Вспомогательные утверждения
§ 1.2 Основная лемма
§ 1.3 Асимптотика
§ 2 Размер максимального МСП в одном классе групп
Список литературы
Теория перечисления, связанная с проблемами существования, построения и подсчета числа элементов заданного множества, обладающих некоторыми свойствами, представляет собой важный раздел дискретной математики. К проблемам теории перечисления относятся, например, задачи о числе n-вершинпых неизоморфиых графов с определенными свойствами, числе решений задач целочисленного линейного программирования или о числе изомеров химических элементов. Традиционным и широко используемым методом решения подобных задач является классический метод производящих функций, связанный с использованием перечислительных теорем Пойя, де Брейна и Робинсона. Однако метод производящих функций требует существования разрешимых рекуррентных соотношений, что пс всегда выполняется.
В теории перечисления достаточно часто возникают задачи оценки числа объектов с некоторыми запретами или ограничениями. Такими являются, например, задачи о числе связных подмножеств, с заданной мощностью границы, в графах, числе антицепей в унимодальных частично упорядоченных множествах, числе независимых множеств в регулярных графах и о числе множеств, свободных от сумм, в конечных абелевых группах. Как правило для таких задач не удается найти разрешимых рекуррентных соотношений. В связи с этим для решения этих задач A.A. Саиожеико разработал метод контейнеров. Сущность данного метода состоит в том, что исходное семейство, мощность которого мы пытаемся найти, покрывается некоторым другим семейством множеств (контейнеров). Данный метод позволяет не только получать эффективные верхние оценки, но и в некоторых случаях асимптотические равенства. В частности, методом контейнеров получены асимптотика числа множеств, свободных от сумм (МСС), в начальном отрезке натуральных чисел (гипотеза Камерона-Эрдеша) и асимптотика числа МСС в конечных абелевых группах четного порядка.
Основной задачей диссертации является оценка числа множеств, свободных от произведений (МСП), в произвольных конечных группах. Для получения асимптотических результатов о числе МСС в конечных абелевых группах существенно использовались результаты теории сложения множеств о структуре и нижних оценках мощности суммы множеств (например, известная теорема Кнезера), которые затем применялись для

доказательства расширительиости графов Кэли. Значительной трудностью, возникающей при переходе к произвольным конечным группам, является отсутствие таких же сильных результатов о структуре и мощности суммы множеств, как в абелевом случае. Нскоммутативпость операции в группе и, как следствие, разные размеры произведения (левых или правых) смежных классов усложняют построение подходящих регулярных подграфов Кэли. В диссертационной работе эти трудности преодолеваются с помощью детального анализа взаимного расположения левых и правых смежных классов, их произведений, выбора подходящего разбиения группы для построения нспересекающихся графов Кэли, сохраняющих свойство регулярности. Таким образом становится возможным применение метода контейнеров. При доказательстве асимптотики логарифма числа МСП используются техника, связанная с преобразованиями Фурье.
В диссертации получена асимптотика числа МСП и размер максимального МСП в некоторых классах конечных групп, асимптотика логарифма числа МСП в конечных группах, при некоторых ограничениях на размер максимального МСП, оценка числа МСП в конечных группах, в которых индекс нормальной подгруппы является простым числом, большим чем 2.
История вопроса
Понятие множества, свободного от сумм (МСС), было введено Шуром в 1916 году для решения задач шифрования. Множество А называется множеством, свободных от сумм (МСС), если нет троек (x,y,z) £ А3, удовлетворяющих уравнению х + у = z. Шур [30] показал, что невозможно разбить начальный отрезок натуральных чисел на конечное число МСС.
Исследовались две естественные перечислительные задачи:
1) нахождение размера максимального МСС,
2) оценка числа всех МСС.
В [17, 1985] П. Камерон оценивал хаусдорфову размерность семейства всех МСС в множестве натуральных чисел и предположил, что она равна 1/2. Финитизацией данной проблемы стал вопрос о числе МСС в начальном отрезке натуральных чисел. Начало исследований в этом направлении было положено совместной работой П. Эрдеша (Erdos Р.) и П. Камерона (Cameron Р.) [18], в которой высказана гипотеза о том, что мощность семейства всех МСС |SF([l,n])| в отрезке натуральных чисел [1, п] есть 0(2"/2).
Н. Калкин (Calkin N.) [16,1990], независимо, П. Эрдеш (Erdos Р.) и А.

Литература
[1] Э.Б. Винберг, Курс алгебры. - М.: Изд-во "Факториал", 1999.
[2] Г.П. Гаврилов, A.A. Сапоженко, Задачи и упражнения, по дискретной математике. - 3-є изд. - М.: Изд-во "Физматлит", 2004.
[3] А.И. Кострикин, Введение в алгебру. - М.: Изд-во "Наука", 1977.
[4] Т.Г. Петросян, Число множеств, свободных от произведений, VIII Международный семинар "Дискретная математика и ее приложения". - М.: Изд-во механико-математического факультета МГУ, 2004, стр. 358-361.
[5] Т.Г. Петросян, Множества, свободные от произведений, в группах, VI Международная конференция "Дискретные модели в теории управляющих систем". - М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2004, стр. 204-206.
[6] Т.Г. Петросян, О числе мноэ/сеств, свободных от произведений, в группах четного порядка, Дискретная математика, 17 (2005), No. 1, 89-101.
[7] Т.Г. Петросян. О мнооісествах, свободных от произведений, Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики". - М.: Изд-во механико-математического факультета МГУ, 2005, стр. 120.
[8] Т.Г. Петросян, Размер максимального множества, свободного от произведений, в группах порядка pq, Материалы Международной школы-семинара "Синтез и сложность управляющих систем" (Санкт-Петербург, июнь 2006). - М.: Изд-во механико-математического факультета МГУ, 2006, стр. 85-88.
[9] Т.Г. Петросян, О верхней оценке числа мнооісеств, свободных от произведений, Дискретная математика, 19 (2007), No. 1, стр. 76-88.