О числе множеств, свободных от сумм

• Автор: Омельянов, Кирилл Георгиевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 89 с. : ил.

1 О числе множеств, свободных от сумм (МСС), в Zv

1.1 Основные понятия

1.2 Постановка задачи и классификация МСС

1.3 Вспомогательные утверждения

1.4 Структура максимальных МСС 1-го и 4-го рода

1.5 Нижние оценки числа МСС в Zp

2 О числе МСС в отрезке натуральных чисел [1, п]

2.1 Основные понятия

2.2 О числе МСС в отрезке [(| + е)п, п]

2.3 О числе МСС в отрезке [nг^‘iogn,n]

2.4 О числе независимых множеств в графах Кэли

2.5 Оценки констант Камерона-Эрдеша
А Приложение
А.1 Программа для вычисления нижних
оценок констант Камерона-Эрдеша
Список литературы

Значительное место в математике занимают перечислительные задачи, связанные с проблемами доказательства существования, построения и подсчета числа элементов заданного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, числе n-вершинных графов с определенными свойствами или о числе изомеров химических элементов. В диссертации решаются некоторые перечислительные задачи комбинаторной теории чисел и теории групп. Оценивается число свободных от сумм подмножеств множества {1, ...,п}, то есть подмножеств, в которых не существует решений уравнения хЛ-у — z. Оценивается число свободных от сумм подмножеств в группе Zp и описывается структура максимальных по мощности таких подмножеств. Эти задачи относятся к классу проблем оценки числа объектов с ограничениями на структуру. К таким объектам относятся коды, исправляющие ошибки, антицепи в частичных порядках, независимые множества в графах, слова с запрещенными фрагментами. Особенность работы в том, что для решения теоретико-числовых задач используются методы теории графов.
Множество S целых чисел называется свободным от сумм (МСС), если для любых а,Ь Є S число а + b не принадлежит множеству S. Обозначим через S(m,n) семейство всех подмножеств SC{ieN:w Понятие свободных от сумм множеств ввел, по всей видимости, И. Шур (I. Schur) в 1916 г. для решения задач шифрования. Знаменитая теорема Шура утверждает

невозможность разбиения множества {1,.,п} на фиксированное, не зависящее от п число попарно непересекающихся множеств, свободных от сумм. Дальнейшие исследования множеств, свободных от сумм, были инициированы известной гипотезой Камерона-Эрдеша. В 1988 г. П. Камерон и П. Эрдеш [22] предположили, что
s{n) = 0(2"/2).
Обоснованием для этого предположения служило то, что любое подмножество множества нечетных чисел отрезка [1, те] свободно от сумм, также как и любое подмножество натуральных чисел отрезка [|n/2j + l,n], а число МСС иного вида, по-видимому, относительно мало. П. Камерон и П. Эрдеш доказали, что
s(n/3,n) = 0( 2"/2),
и, кроме того, что существуют константы со и с і, для которых
s(n/3, тг) ~ со2ЇП/,21
при четных п,
s(n/3,n) ~ сДГ”/2!
при нечетных п. Будем называть со и с константами Камерона-Эрдеша.
Н. Алон [21] в 1991 г. и Н. Калкин [23] в 1990 г. независимо доказали, что1
logs(rz) ~ |.
Автор и А. А. Сапоженко [12] в 2002 г. доказали, что для всякого є >
$((1/4 + є)п, п) = 0(2п/2).
Ими же [13] в 2003 г. было доказано, что
s(n3/Vl°g”,п) = 0(2пI2).
Гипотеза Камерона-Эрдеша была доказана независимо А. А. Сапоженко [18] в 2003 г. и Б. Грином [25] в 2004 г. Пусть 51(п) — семейство всех подмножеств множества 'Здесь и далее logm = log2 т.

С2(6) < С3(4),
С2(5) < С(4)С(6),
С2(7) < С2(4)С(6),
и последовательно применяя соответствующие замены, получим граф, содержащий не более одного цикла каждой из длин 3, 5, 6 и 7. Проводя замены, задаваемые соотношениями С(3)<7(5) < С2(4),
С(3)С(6) < С(4)С(5),
<7(3)<7(7) < С(4)С(6),
С(5)С(6) < С(4)С(7),
С(5)С(7) < С3(4),
С(6)С(7) < (72(4)(7(5),
получим граф, содержащий не более одного цикла длины меньшей восьми и отличной от четырех. Проведем замену, задаваемую неравенством (7(3)67(4) < (7(7), если граф содержит цикл длины три. Итак, в результате проведенных преобразований, получен граф Г. Единственность графа, обладающего наибольшим количеством независимых множеств, следует из того, что при преобразовании графа (7 в граф Г обязательно будет использована замена, задаваемая строгим неравенством. □