Неравенство Плюнеке – Ружи
В аддитивной комбинаторике неравенство Плюнеке -Рузсы представляет собой неравенство, которое ограничивает размер различных сумм множества. , учитывая, что существует другой набор так что не намного больше, чем . Несколько более слабая версия этого неравенства была первоначально доказана и опубликована Хельмутом Плюнеке (1970). [ 1 ] Имре Ружа (1989) [ 2 ] позже опубликовал более простое доказательство текущей, более общей версии неравенства. Это неравенство является решающим шагом в доказательстве теоремы Фреймана .
Заявление
[ редактировать ]Следующее обозначение суммы является стандартным в аддитивной комбинаторике. Для подмножеств и абелевой группы и натурального числа , определены следующие:
Набор известен сумма как и .
Неравенство Плюнеке-Рузы
[ редактировать ]Наиболее часто цитируемая версия утверждения неравенства Плюннеке – Ружи следующая. [ 3 ]
Теорема (неравенство Плюнеке-Рузы) — Если и являются конечными подмножествами абелевой группы и является константой, так что , то для всех неотрицательных целых чисел и ,
Это часто используется, когда , и в этом случае константа известна как удвоения константа . В этом случае неравенство Плюнеке – Ружи утверждает, что суммы, сформированные из набора с малой константой удвоения, также должны быть малы.
Неравенство Плюнеке
[ редактировать ]Версия этого неравенства, первоначально доказанная Плюннеке (1970). [ 1 ] немного слабее.
Теорема (неравенство Плюнеке) — Предположим , и являются конечными подмножествами абелевой группы и является константой, так что . Тогда для всех неотрицательных целых чисел ,
Доказательство
[ редактировать ]Неравенство треугольника Ружи
[ редактировать ]Неравенство треугольника Рузсы является важным инструментом, который используется для обобщения неравенства Плюнеке на неравенство Плюнеке – Ружи. Его заявление:
Теорема (неравенство треугольника Рузсы) — Если , , и являются конечными подмножествами группы, то
Доказательство неравенства Плюнеке-Ружсы.
[ редактировать ]Следующее простое доказательство неравенства Плюнеке – Ружи принадлежит Петридису (2014). [ 4 ]
Лемма: Пусть и — конечные подмножества абелевой группы . Если является непустым подмножеством, которое минимизирует значение , то для всех конечных подмножеств ,
Доказательство. Это демонстрируется индукцией по размеру . Для базового случая , Обратите внимание, что это просто перевод для любого , так
Для индуктивного шага предположим, что неравенство выполнено для всех с для некоторого положительного целого числа . Позволять быть подмножеством с , и пусть для некоторых . (В частности, неравенство справедливо для .) Наконец, пусть . Определение подразумевает, что . Таким образом, по определению этих множеств,
Следовательно, учитывая размеры множеств,
Определение подразумевает, что , поэтому по определению , . Таким образом, применяя индуктивную гипотезу о и используя определение ,
Чтобы ограничить правую часть этого неравенства, положим . Предполагать и , то существует такой, что . Таким образом, по определению , так . Следовательно, множества и непересекающиеся. Определения и таким образом подразумевать, что
Опять же по определению , так . Следовательно,
Соединение двух приведенных выше неравенств вместе дает
Это завершает доказательство леммы.
Чтобы доказать неравенство Плюнеке–Рузсы, возьмем и как в утверждении леммы. Прежде всего необходимо показать, что
Это можно доказать методом индукции. В базовом случае определения и подразумеваю, что . Таким образом, определение подразумевает, что . Для индуктивного шага предположим, что это верно для . Применяя лемму с и индуктивная гипотеза дает
На этом индукция завершена. Наконец, неравенство треугольника Рузсы дает
Потому что , должно быть так, что . Поэтому,
Это завершает доказательство неравенства Плюннеке–Ружсы.
Графики Плюннеке
[ редактировать ]И доказательство Плюнеке неравенства Плюнеке, и оригинальное доказательство Ружи неравенства Плюнеке – Ружи используют метод графов Плюнеке. Графы Плюнеке — это способ отразить аддитивную структуру множеств. теоретико-графовым способом [ 5 ] [ 6 ]
Чтобы определить граф Плюнеке, мы сначала определяем коммутативные графы и слоистые графы:
Определение . граф Ориентированный называется полукоммутативным , если всякий раз, когда существуют различные такой, что и находятся края в для каждого , то также существуют различные так что и находятся края в для каждого .
называется коммутативным, если он полукоммутативен и граф, образованный перестановкой всех его ребер, также полукоммутативен.
Определение . — Слоистый граф это (ориентированный) граф. чье множество вершин можно разделить так, чтобы все ребра вошли из к , для некоторых .
Определение . Граф Плюнеке — это многослойный граф, который является коммутативным.
Каноническим примером графа Плюннеке является следующий, который показывает, как структура множеств образуют граф Плюнеке.
Пример . Позволять являются подмножествами абелевой группы. Тогда пусть быть многоуровневым графом, так что каждый слой является копией , так что , , ..., . Создайте преимущество (где и ) всякий раз, когда существует такой, что . (В частности, если , затем по определению, поэтому каждая вершина имеет исходящую степень, равную размеру .) Затем является графом Плюннеке. Например, чтобы проверить это полукоммутативен, если и находятся края в для каждого , затем . Тогда пусть , так что и . Таким образом, является полукоммутативным. Аналогично можно проверить, что граф, образованный перестановкой всех ребер также полукоммутативен, поэтому является графом Плюннеке.
В графе Плюннеке образ множества в , написано , определяется как множество вершин в до которого можно добраться по пути, начинающемуся из некоторой вершины в . В частности, в приведенном выше примере это просто .
Коэффициент увеличения между и , обозначенный , затем определяется как минимальный коэффициент, на который изображение набора должно превышать размер исходного набора. Формально,
Теорема Плюнеке представляет собой следующее утверждение о графах Плюнеке.
Теорема (теорема Плюннеке) — Пусть быть графом Плюнеке. Затем, уменьшается в .
Доказательство теоремы Плюннеке включает в себя технику, известную как «трюк с тензорным произведением», в дополнение к применению теоремы Менгера . [ 5 ]
Неравенство Плюнеке-Ружсы является довольно прямым следствием теоремы Плюнеке и неравенства треугольника Ружи. Применяя теорему Плюнеке к графику, приведенному в примере, при и , получается, что если , то существует так что . Применяя этот результат еще раз с помощью вместо , существует так что . Тогда по неравенству треугольника Ружи (на ),
тем самым доказывая неравенство Плюнеке – Ружи.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Плюннеке, Хельмут (1970). «Теоретико-числовое приложение теории графов». Журнал чистой и прикладной математики . 243 : 171–183. дои : 10.1515/crll.1970.243.171 .
- ^ Ружа, Имре (1989). «Применение теории графов к аддитивной теории чисел». Сайентия, серия А. 3 : 97–109.
- ^ Кандела, Пабло; Гонсалес-Санчес, Диего; де Ротон, Энн (2019). «Неравенство Плюннеке-Рузсы в компактных абелевых группах». Иберо-американский математический журнал . 35 (7): 2169–2186. arXiv : 1712.07615 . дои : 10.4171/rmi/1116 .
- ^ Петридис, Гиоргис (2014). «Неравенство Плюннеке – Ружи: обзор». Комбинаторная и аддитивная теория чисел . Спрингерские труды по математике и статистике. Том. 101. С. 229–241. дои : 10.1007/978-1-4939-1601-6_16 . ISBN 978-1-4939-1600-9 .
- ^ Перейти обратно: а б Тао, Т.; Ву, В. (2006). Аддитивная комбинаторика . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-85386-6 .
- ^ Ружа И., Суммы и структура (PDF) .