Множества, свободные от произведений Петросян Тарон Гайкович

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

Актуальность темы

Теория перечисления, связанная с проблемами существования, построения и подсчета числа элементов заданного множества, обладающих некоторыми свойствами, представляет собой важный раздел дискретной математики К проблемам теории перечисления относятся, например, задачи о числе n-вершинных графов с определенными свойствами, о числе решений задач целочисленного линейного программирования или о числе изомеров химических элементов В диссертации решаются некоторые перечислительные задачи теории конечных групп Основной задачей является оценка числа подмножеств А конечной группы, произведение любых двух элементов которых не принадлежит А Множества, обладающие данным свойством, называются множествами, свободными от произведений (МСП) Помимо основной задачи в диссертации решается задача нахождения размера максимального (по мощности) МСП в конечных группах

Основным методом, используемым в диссертации, является, так называемый, метод контейнеров, разработанный А А Сапоженко Кратко суть метода заключается в следующем Пусть Т и V являются семействами подмножеств множества S Будем говорить, что семейство V покрывает семейство F, если для любого элемента F Є Т существует такой элемент (называемый контейнером) Р Є V, что F С. Р Для семейства объектов, число которых требуется найти, строится некоторое специальное покрывающее семейство контейнеров Число контейнеров в силу их специального построения проще оценивать, чем число исходных объектов С помощью метода контейнеров получены эффективные верхние оценки, а в некоторых случаях и асимптотически неулучшаемые результаты До последнего времени данный метод применялся к задаче оценки числа МСП только в классе конечных абелевых групп В диссертации метод контейнеров применяется для произвольных конечных групп

Начало исследований в области оценки числа множеств, свободных от произведений, было положено в работе П Камерона (Cameron, Р )¹ В ней исследовалась задача нахождения хаусдорфовой размерности семейства всех множеств, свободных от сумм (МСС²), в множестве натуральных чисел Независимо друг от друга Н Калкин (Calkm, N ), Н Алон

^ICameron, Р J , Cyclic automorphisms of a countable graph and random sum-free seb, Graphs Combm , 1 (1985), 129-135

²Когда операция на множестве коммутативна, то подмножества, свободные от произведений, этого множества принято называть множествами свободными от сумм

(Alon, N ), П Эрдеш (Erd6s, Р) и А Гранвиль (Granville, А ) показали, что хаусдорфова размерность семейства всех МСС равна 1/2 Дальнейшие исследования были инициированы совместной работой³ П Эрдеша и П Камерона, в которой найдена асимптотика числа множеств, свободных от сумм, в отрезке натуральных чисел от n/З до п и высказывают гипотезу о том, что число МСС во всем отрезке натуральных чисел [1, п] есть 0(2^п/²) Гипотеза была доказана независимо А А Сапоженко⁴ и Б Грином⁵ (Green, В)

Если абелев случай изучался весьма интенсивно, то работ, изучающих множества, свободные от произведений, в произвольных конечных группах практически нет Для получения асимптотических результатов о числе МСС в конечных абелевых группах существенно использовались результаты теории сложения множеств о структуре и нижних оценках мощности суммы множеств (например, известная теорема Кнезера), которые затем применялись для доказательства расширительности графов Кэли Значительной трудностью, возникающей при переходе к некоммутативным группам, является отсутствие таких же сильных результатов о структуре и мощности суммы множеств, как в абелевом случае Другое затруднение вносят некоммутативность операции в группе и, как следствие, разные размеры произведения (левых или правых) смежных классов Это усложняет доказательство расширительности и построение подходящих графов Кэли В диссертационной работе эти проблемы преодолеваются с помощью детального анализа взаимного расположения левых и правых смежных классов, их произведений, выбора подходящего разбиения группы для построения непересекающихся графов Кэли Преодоление перечисленных выше трудностей делает возможным применение метода контейнеров При доказательстве асимптотики логарифма числа МСП возникает необходимость оценки числа так называемых троек Шура, то есть троек (х, у, z) Є А³, таких, что ху = z Для решения этой задачи используется техника, связанная с преобразованиями Фурье

Задачи о числе и мощности максимального МСП в последние два десятилетия являются предметом активного изучения как за рубежом, так и в России Основной вклад в данную область исследований внесли следующие математики Н Алон, Б Грин, П Камерон, В Лев , Т Лучак, И Ружа, А А Сапоженко, П Эрдеш, X П Яп и другие

³Cameron, Р J, Erd6s, Р , On the number of sets with various properties, Number Theory (Banff, AB, 1988), 61-79, de Gruyter, Berlin, 1990

⁴ А А Сапоженко, Гипотеза Камерона-Эрдеша, Математические вопросы кибернетики Выпуск 13 Изд-во Физматлит 2004

^sGreen, В , The Cameron Erdos Conjecture, Bull London Math Soc 36 (2004), no 6, 769-778

Цель работы

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

Методы исследования

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

Научная новизна

Все результаты диссертации являются новыми и состоят в следующем

1. Найдена асимптотика числа множеств, свободных от произведений, в группах, содержащих хотя бы одну подгруппу индекса 2

2. Установлена асимптотика логарифма числа множеств, свободных от произведений, в конечных группах, таких, что мощность максимального МСП не меньше трети порядка группы

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

4. Найден размер максимального множества, свободного от произведений, в конечных группах, содержащих нормальную подгруппу простого индекса р, р = 2 (mod 3)

Теоретическая и практическая ценность

Работа носит теоретический характер Расширена область применения метода контейнеров на случай некоммутативных групп Полученные при этом методы могут применяться при решении задач перечисления объектов с ограничениями на структуру

Апробация работы

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

на семинаре "Дискретная математика и математическая кибернетика" под руководством В Б Алексеева, А А Сапоженко и С А Ложкина (кафедра математической кибернетики ВМиК МГУ) в марте 2007 г,

на семинаре "Избранные вопросы алгебры" под руководством М В Зайцева, А А Михалева и И А Чубарова (кафедра высшей алгебры механико-математического факультета МГУ) в октябре 2006 г,

на семинаре "Кольца и модули" под руководством В Н Латышева, А В Михалева и В А Артамонова (кафедра высшей алгебры механико-математического факультета МГУ) в 2005 г,

на семинаре "Математические вопросы кибернетики" под руководством О Б Лупанова (механико-математический факультет МГУ) в 2004

г,

на семинаре "Дискретный анализ" под руководством А А Сапо-женко, Н Н Кузюрина и В П Воронина (кафедра математической кибернетики ВМиК МГУ) в 2004-2007 гг,

International Conference KROMSH-2006 The Seventeenth Crimean Autumn Mathematical School-Symposium (Crimea, Laspi-Batihman, Septembe 17-29, 2006)

на XVI Международной школе-семинаре "Синтез и сложность управляющих систем" (Санкт-Петербург, 26-30 июня 2006 г),

на XIV Международной конференции "Проблемы теоретической кибернетики" (Пенза, 23-28 мая 2005 г),

на VIII Международном семинаре "Дискретная математика и ее приложения"(Москва, 2-6 февраля 2004 г),

на VI Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 7-11 декабря 2004 г),

Публикации

Основное содержание диссертации опубликовано в 6 работах [1-6], список которых приведен в конце автореферата Работ, написанных в соавторстве, нет

Структура и объем работы