Теория Рамсея с нулевой суммой

В математике теория Рамсея с нулевой суммой или теория нулевой суммы — это раздел комбинаторики . Он занимается задачами следующего рода: дана комбинаторная структура, элементам которой присвоены разные веса (обычно элементы из абелевой группы $A$ ), ищутся условия, гарантирующие существование некоторой подструктуры, сумма весов ее элементов равна нулю (в $A$ ). Он сочетает в себе инструменты теории чисел , алгебры , линейной алгебры , теории графов , дискретного анализа и других разделов математики.

Классическим результатом в этой области является теорема 1961 года Пола Эрдеша , Авраама Гинзбурга и Авраама Зива : ^{[ 1 ]} для любого $2m-1$ элементы $\mathbb {Z} _{m}$ , существует подмножество размера $m$ это в сумме равняется нулю. ^{[ 2 ]} (Эта граница является точной, поскольку последовательность $m-1$ нули и $m-1$ они не могут иметь никакого подмножества размера $m$ суммирование до нуля. ^{[ 2 ]}) Известны доказательства этого результата с использованием теоремы Коши-Дэвенпорта , малой теоремы Ферма или теоремы Шевалле-Ворнинга . ^{[ 2 ]}

можно определить Обобщая этот результат, для любой абелевой группы G минимальную величину $EGZ(G)$ элементов G таких, что должна существовать подпоследовательность $o(G)$ элементы (где $o(G)$ — порядок группы), который в сумме равен нулю. Известно, что $EGZ(G)\leq 2o(G)-1$ , и что эта оценка является строгой тогда и только тогда, когда $G=\mathbb {Z} _{m}$ . ^{[ 2 ]}

См. также

Проблема с нулевой суммой

Ссылки

^ Эрдеш, Пол; Гинзбург А.; Зив, А. (1961). «Теорема аддитивной теории чисел». Бык. Рез. Совет Израиля . 10F : 41–43. Збл 0063.00009 .
^ Jump up to: ^а ^б ^с ^д «Теорема Эрдеша-Гинзбурга-Зива — Математическая энциклопедия» . энциклопедияofmath.org . Проверено 22 мая 2023 г.

Дальнейшее чтение

Задачи с нулевой суммой - Опрос (журнальная статья в открытом доступе)
Теория Рамсея с нулевой суммой: графики, последовательности и многое другое (домашняя страница семинара)
Арье Бялостоцкий , « Деревья с нулевой суммой: обзор результатов и открытых проблем » Н. В. Зауэр (ред.) Р. Е. Вудро (ред.) Б. Сэндс (ред.), Конечная и бесконечная комбинаторика в множествах и логике , Nato ASI Ser. , Клювер Акад. Опубл. (1993) стр. 19–29.
Ю. Каро, « Задачи с нулевой суммой: обзор » Дискретная математика. , 152 (1996), стр. 93–113.

Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Эрдеш, Пол; Гинзбург А.; Зив, А. (1961). «Теорема аддитивной теории чисел». Бык. Рез. Совет Израиля . 10F : 41–43. Збл 0063.00009 .

[:0-2] Jump up to: ^а ^б ^с ^д «Теорема Эрдеша-Гинзбурга-Зива — Математическая энциклопедия» . энциклопедияofmath.org . Проверено 22 мая 2023 г.

[ 1 ]

[ 2 ]