Обобщение теоремы Н. Алона о честном делении отрезка
|
1 Введение 2
1.1 Теоремы Тверберга 2
1.2 Теорема Алона и ее обобщения 4
2 Основные результаты 5
2.1 Цветная теорема о честном делении 5
2.2 Сбалансированная цветная теорема о честном делении (s=r) 7
2.3 Сбалансированная цветная теорема о честном делении (общий случай) 9
2.4 Вторая цветная теорема о честном делении (с маленькими цветными классами) 10
3 Сравнения результатов 11
3.1 Из сбалансированной теоремы следует цветная теорема (s=r) 12
3.2 Из сбалансированной теоремы следует цветная теорема (общий случай) 12
4 Заключение 13
Список литературы 14
1.1 Теоремы Тверберга 2
1.2 Теорема Алона и ее обобщения 4
2 Основные результаты 5
2.1 Цветная теорема о честном делении 5
2.2 Сбалансированная цветная теорема о честном делении (s=r) 7
2.3 Сбалансированная цветная теорема о честном делении (общий случай) 9
2.4 Вторая цветная теорема о честном делении (с маленькими цветными классами) 10
3 Сравнения результатов 11
3.1 Из сбалансированной теоремы следует цветная теорема (s=r) 12
3.2 Из сбалансированной теоремы следует цветная теорема (общий случай) 12
4 Заключение 13
Список литературы 14
Некоторые важные результаты в комбинаторике, дискретной геометрии и теоретической информатике были доказаны с помощью различных методов алгебраической топологии. В течение последних десятилетий топологические методы в комбинаторике стали использоваться чаще и более продуманно.
Например, для некоторых задач результат может быть выведен из несуществования определенного отображения между двумя топологическими пространствами. Существует несколько стандартных подходов к доказательству несуществования такого отображения, которые опираются на топологические свойства пространств.
В данной работе применяются подобные методы для доказательства следствий из одной из базовых теорем топологической комбинаторики.
1.1 Теоремы Тверберга
Рассмотрим несколько теорем типа Тверберга. Это целое семейство результатов про разделение конечного множества точек с некоторыми свойствами в Rd. Первая теорема - теорема Радона [1].
Теорема 1.1. Для всякого множества X С Rd, |X| = d + 2. Тогда существует разделение X на два множества X = X1 U X2, такие что conv(X1) П conv(X2) = 0.
Заметим, что уже при |X| = d +1 утверждение теоремы не будет выполняться, так как в качетсве X можно рассмотреть вершины стандартного симплекса размерности d.
Одна важнейших теорем - классическая теорема Тверберга [2]. Теорема Радона является предшественником этого результата и частным случаем при r = 2. Теперь в множестве больше элементов и, соотвественно, количество классов увеличивается. Теорема 1.2. Для всякого множества S С Rd, |S| = (r — 1)(d + 1) + 1, где r > 1. Существует разбиение множества S на r попарно непересекающихся множеств S = S1 U ... U Sr, т.ч.
conv(S1) П ... П conv(Sr) = 0.
Этот результат может быть легко переформулирован в терминах аффинных отображений. Множество точек X можно воспринимать как образ вершин стандартного симплекса соответствующей размерности N = (r — 1)(d +1) при некотором аффинном отображении. Тогда теорему 1.2 можно записать следующим образом.
Теорема 1.3. Для любого аффинного f : XN —! Rd, где N = (r — 1)(d + 1) найдутся r непересекающихся граней XN: Д1,..., Дг, таких что
f (Д1) П ... П f (Дг ) = 0.
В такой формулировке теорема более полезна. Из нее легче получать некоторые следствия и обобщения. Например, можно рассматривать не только аффинные отображения. Следующий результат известен как топологическая теорема Тверберга [3]. Теперь рассматривается любое непрерывное отображение, но так же теперь r должно быть степенью простого числа. Это условие существенно, так как иначе утверждение неверно при достаточно больших d [4].
Теорема 1.4. Пусть r = pv - степень простого числа, d > 1. Для любого непрерывного отображения
f ■ д(г-1)С+1) ! Rd
найдутся непересекающиеся грани A(r-1)(d+1) ■ Д1,... Д,., такие что
f (Д1) ... f (Дг ) = 0.
Следующая серия теорем типа Тверберга получена с помощью добавления раскраски симплекса. Предположим, все вершины покрашены в несколько цветов, у каждой - свой цвет. Назовем грань симплекса радужной, если все ее вершины имеют разные цвета. К предыдущим утверждениям добавляется условие на непересекающиеся грани: теперь каждая из них должна быть радужной. Размерность симплекса, количество и размеры цветовых классов могут меняться, давая разные обобщения и следствия.
Цветная теорема Тверберга [5] описывает случай, когда размерность симплекса такая же, как в топологической теореме, а вершины раскрашены в d + 2 цвета.
Теорема 1.5. Пусть r > 2 - простое число, d > 1, N = (r — 1)(d +1).
Д N - N—мерный стандартный симплекс с раскраской его вершин (множество V) в d + 2 цвета: V = C0 U... Cd U Cd+1, такие что |Ci| = r — 1 для 0 < i < d, |Cd+1| = 1. Тогда для любого непрерывного отображения
f ■ Д N ! Rd
найдутся r непересекающихся радужных граней Д1,..., Дг симплекса ДN, удовлетворяющих
f (Д1) ... f (Дг ) = 0.
Заметим, что топологическая теорема Тверберга не следует из цветной. Действительно, в теореме 1.5 условие на r сильнее, оно обязано быть простым числом.
Следующая теорема - сбалансированная цветная теорема Тверберга [6]. Можно уменьшить количество цветов и добавить условие сбалансированности, которое ограничивает размерности радужных симплексов. Но тогда количество вершин придется увеличить.
Теорема 1.6. Пусть r = pv - степень некоторого простого числа, d > 1. Пусть k > 0 и 0 < s < r удовлетворяют условию
r(k — 1) + s = (r — 1)d, , или, более точно,
k = (r — 1)d/r], s = (r — 1)d — r(k — 1).
Пусть m = (2r — 1)(k + 1), Д[m] - стандартный симплекс размерности m — 1 с m вершинами, которые раскрашены в k + 1 цветов: [m] = C1 U ... U Ck+1 и |СД = 2r — 1 для любого i, 1 < i < k + 1. Тогда для любого непрерывного отображения
f ■ Д[т] -! Rd
найдутся r радужных граней Д[т] ■ Д1,..., Дг, удовлетворяющих
f (Д1) ... f (Дг) = 0 и для которых верно
dim(Ai) = |Дг | — 1 < k для 1 < i < s и dim(Ai) < k — 1 для s < i < r.
Несмотря на то, что последние две теоремы - родственные, ни одна из них не следует из другой, так как размерности симплексов различаются.
В следующей версии цветной теоремы [6] размерность снова (r — 1)(d +1). В теореме 1.5 количество вершин одного цвета было не более r — 1 для всех цветов кроме одного. Теперь классы уменьшаются: максимальное количество вершин одного цвета r++1. Следовательно, и количество цветов увеличится, что делает формулировку чуть слабее. Но этот результат доказан для большего класса возможных r - для степеней простых чисел.
Теорема 1.7. Пусть r = pv - степень простого числа, d > 1, N = (r — 1)(d + 1). Пусть AN - симплекс размерности N с заданной раскраской множества вершин V в t цветов:
V = C1 и... и Ct;
где |Сг| < q = :'21 для любого i, 1 < i < t. Тогда для любого непрерывного отображения f : AN —! Rd найдутся r непересекающихся граней A1,... Ar симплекса AN, таких что
f (Ai) ... f (Ar ) = ?.
Все эти теоремы связаны и похожими подходами к доказательству. Можно рассматривать конфигурационное пространство наборов из r непересекающихся радужных граней исходного симплекса. На эти симплексы можно так же добавлять условия на размерность, чтобы доказывать теорему 1.6. По данному отображению f строится соответствующее отображение из конфигурационного пространства. Далее доказательство опирается на топологические свойства конфигурационных пространств. Подобные рассуждения и приемы можно применить и при доказательстве других фактов.
1.2 Теорема Алона и ее обобщения
Посмотрим теперь на теорему Алона о честном делении - один из самых известных ранних результатов топологической комбинаторики [7]. Будем интерпретировать единичный отрезок [0,1] и n вероятностных мер на нем как ожерелье c n драгоценными камнями. Пусть ожерелье было украдено r ворами. Теперь их цель - разрезать его на несколько кусочков и распределить между собой, так чтобы каждому досталась равная доля от всех драгоценных камней. Теорема Алона оценивает количество разрезов, которое необходимо при этом сделать.
Теорема 1.8. Пусть Ц1,Ц2,..., Цп - набор из n (абсолютно) непрерывных вероятностных мер на отрезке [0,1]. Пусть r > 2 и N = (r — 1)n. Тогда существует разбиение отрезка [0,1] на N + 1 интервал 11,12,..., IN+1 и функция
f : {1, 2,...,N + 1}-^{1, 2,...,r},
такие что для каждой меры цг, 1 < i < n, и для любого j 2 {1,2,..., r}
Е Ц‘(1Р> = 1
Теорема Алона дает лучшую оценку. Действительно, если носители мер - попарно непересекающиеся отрезки, то менее d(r — 1) разрезов сделать не получится.
Этот результат имеет различные вариации, которые получаются с помощью добавления дополнительных условий и ограничений на то, как кусочки ожерелья распределяются между ворами. Например, можно рассмотреть разделение без зависти, где каждый вор имеет личные предпочтения, которые должны учитываться. После того, как все интервалы распределены, ни один из воров не должен завидовать своим товарищам. В статье Йойич-Панина-Живалевич ([10]) показано, что добавление индивидуальных предпочтений схоже с добавлением еще одной меры.
В этой работе изучается другой вариант дополнительных условий. На интервалах можно определить раскраску и добавить требование о том, что каждый вор должен получать радужный набор кусочков.
Целью этой работы является изучить цветные версии теоремы Алона, получить аналоги цветных теорем Тверберга и сравнить полученные утверждения.
Например, для некоторых задач результат может быть выведен из несуществования определенного отображения между двумя топологическими пространствами. Существует несколько стандартных подходов к доказательству несуществования такого отображения, которые опираются на топологические свойства пространств.
В данной работе применяются подобные методы для доказательства следствий из одной из базовых теорем топологической комбинаторики.
1.1 Теоремы Тверберга
Рассмотрим несколько теорем типа Тверберга. Это целое семейство результатов про разделение конечного множества точек с некоторыми свойствами в Rd. Первая теорема - теорема Радона [1].
Теорема 1.1. Для всякого множества X С Rd, |X| = d + 2. Тогда существует разделение X на два множества X = X1 U X2, такие что conv(X1) П conv(X2) = 0.
Заметим, что уже при |X| = d +1 утверждение теоремы не будет выполняться, так как в качетсве X можно рассмотреть вершины стандартного симплекса размерности d.
Одна важнейших теорем - классическая теорема Тверберга [2]. Теорема Радона является предшественником этого результата и частным случаем при r = 2. Теперь в множестве больше элементов и, соотвественно, количество классов увеличивается. Теорема 1.2. Для всякого множества S С Rd, |S| = (r — 1)(d + 1) + 1, где r > 1. Существует разбиение множества S на r попарно непересекающихся множеств S = S1 U ... U Sr, т.ч.
conv(S1) П ... П conv(Sr) = 0.
Этот результат может быть легко переформулирован в терминах аффинных отображений. Множество точек X можно воспринимать как образ вершин стандартного симплекса соответствующей размерности N = (r — 1)(d +1) при некотором аффинном отображении. Тогда теорему 1.2 можно записать следующим образом.
Теорема 1.3. Для любого аффинного f : XN —! Rd, где N = (r — 1)(d + 1) найдутся r непересекающихся граней XN: Д1,..., Дг, таких что
f (Д1) П ... П f (Дг ) = 0.
В такой формулировке теорема более полезна. Из нее легче получать некоторые следствия и обобщения. Например, можно рассматривать не только аффинные отображения. Следующий результат известен как топологическая теорема Тверберга [3]. Теперь рассматривается любое непрерывное отображение, но так же теперь r должно быть степенью простого числа. Это условие существенно, так как иначе утверждение неверно при достаточно больших d [4].
Теорема 1.4. Пусть r = pv - степень простого числа, d > 1. Для любого непрерывного отображения
f ■ д(г-1)С+1) ! Rd
найдутся непересекающиеся грани A(r-1)(d+1) ■ Д1,... Д,., такие что
f (Д1) ... f (Дг ) = 0.
Следующая серия теорем типа Тверберга получена с помощью добавления раскраски симплекса. Предположим, все вершины покрашены в несколько цветов, у каждой - свой цвет. Назовем грань симплекса радужной, если все ее вершины имеют разные цвета. К предыдущим утверждениям добавляется условие на непересекающиеся грани: теперь каждая из них должна быть радужной. Размерность симплекса, количество и размеры цветовых классов могут меняться, давая разные обобщения и следствия.
Цветная теорема Тверберга [5] описывает случай, когда размерность симплекса такая же, как в топологической теореме, а вершины раскрашены в d + 2 цвета.
Теорема 1.5. Пусть r > 2 - простое число, d > 1, N = (r — 1)(d +1).
Д N - N—мерный стандартный симплекс с раскраской его вершин (множество V) в d + 2 цвета: V = C0 U... Cd U Cd+1, такие что |Ci| = r — 1 для 0 < i < d, |Cd+1| = 1. Тогда для любого непрерывного отображения
f ■ Д N ! Rd
найдутся r непересекающихся радужных граней Д1,..., Дг симплекса ДN, удовлетворяющих
f (Д1) ... f (Дг ) = 0.
Заметим, что топологическая теорема Тверберга не следует из цветной. Действительно, в теореме 1.5 условие на r сильнее, оно обязано быть простым числом.
Следующая теорема - сбалансированная цветная теорема Тверберга [6]. Можно уменьшить количество цветов и добавить условие сбалансированности, которое ограничивает размерности радужных симплексов. Но тогда количество вершин придется увеличить.
Теорема 1.6. Пусть r = pv - степень некоторого простого числа, d > 1. Пусть k > 0 и 0 < s < r удовлетворяют условию
r(k — 1) + s = (r — 1)d, , или, более точно,
k = (r — 1)d/r], s = (r — 1)d — r(k — 1).
Пусть m = (2r — 1)(k + 1), Д[m] - стандартный симплекс размерности m — 1 с m вершинами, которые раскрашены в k + 1 цветов: [m] = C1 U ... U Ck+1 и |СД = 2r — 1 для любого i, 1 < i < k + 1. Тогда для любого непрерывного отображения
f ■ Д[т] -! Rd
найдутся r радужных граней Д[т] ■ Д1,..., Дг, удовлетворяющих
f (Д1) ... f (Дг) = 0 и для которых верно
dim(Ai) = |Дг | — 1 < k для 1 < i < s и dim(Ai) < k — 1 для s < i < r.
Несмотря на то, что последние две теоремы - родственные, ни одна из них не следует из другой, так как размерности симплексов различаются.
В следующей версии цветной теоремы [6] размерность снова (r — 1)(d +1). В теореме 1.5 количество вершин одного цвета было не более r — 1 для всех цветов кроме одного. Теперь классы уменьшаются: максимальное количество вершин одного цвета r++1. Следовательно, и количество цветов увеличится, что делает формулировку чуть слабее. Но этот результат доказан для большего класса возможных r - для степеней простых чисел.
Теорема 1.7. Пусть r = pv - степень простого числа, d > 1, N = (r — 1)(d + 1). Пусть AN - симплекс размерности N с заданной раскраской множества вершин V в t цветов:
V = C1 и... и Ct;
где |Сг| < q = :'21 для любого i, 1 < i < t. Тогда для любого непрерывного отображения f : AN —! Rd найдутся r непересекающихся граней A1,... Ar симплекса AN, таких что
f (Ai) ... f (Ar ) = ?.
Все эти теоремы связаны и похожими подходами к доказательству. Можно рассматривать конфигурационное пространство наборов из r непересекающихся радужных граней исходного симплекса. На эти симплексы можно так же добавлять условия на размерность, чтобы доказывать теорему 1.6. По данному отображению f строится соответствующее отображение из конфигурационного пространства. Далее доказательство опирается на топологические свойства конфигурационных пространств. Подобные рассуждения и приемы можно применить и при доказательстве других фактов.
1.2 Теорема Алона и ее обобщения
Посмотрим теперь на теорему Алона о честном делении - один из самых известных ранних результатов топологической комбинаторики [7]. Будем интерпретировать единичный отрезок [0,1] и n вероятностных мер на нем как ожерелье c n драгоценными камнями. Пусть ожерелье было украдено r ворами. Теперь их цель - разрезать его на несколько кусочков и распределить между собой, так чтобы каждому досталась равная доля от всех драгоценных камней. Теорема Алона оценивает количество разрезов, которое необходимо при этом сделать.
Теорема 1.8. Пусть Ц1,Ц2,..., Цп - набор из n (абсолютно) непрерывных вероятностных мер на отрезке [0,1]. Пусть r > 2 и N = (r — 1)n. Тогда существует разбиение отрезка [0,1] на N + 1 интервал 11,12,..., IN+1 и функция
f : {1, 2,...,N + 1}-^{1, 2,...,r},
такие что для каждой меры цг, 1 < i < n, и для любого j 2 {1,2,..., r}
Е Ц‘(1Р> = 1
Теорема Алона дает лучшую оценку. Действительно, если носители мер - попарно непересекающиеся отрезки, то менее d(r — 1) разрезов сделать не получится.
Этот результат имеет различные вариации, которые получаются с помощью добавления дополнительных условий и ограничений на то, как кусочки ожерелья распределяются между ворами. Например, можно рассмотреть разделение без зависти, где каждый вор имеет личные предпочтения, которые должны учитываться. После того, как все интервалы распределены, ни один из воров не должен завидовать своим товарищам. В статье Йойич-Панина-Живалевич ([10]) показано, что добавление индивидуальных предпочтений схоже с добавлением еще одной меры.
В этой работе изучается другой вариант дополнительных условий. На интервалах можно определить раскраску и добавить требование о том, что каждый вор должен получать радужный набор кусочков.
Целью этой работы является изучить цветные версии теоремы Алона, получить аналоги цветных теорем Тверберга и сравнить полученные утверждения.
В работе представлены цветные версии теоремы Алона о честном делении и показаны их сравнения. Благодаря особенностям задачи о делении, цветные теоремы о делении отрезка оказываются сильнее, чем аналогичные цветные теоремы Тверберга. Это так, потому что в доказательстве можно использовать большее число интервалов, но после этого вырожденные кусочки можно игнорировать. Это обстоятельство было открыто в Йойич-Панина-Живалевич [10].
