Теорема Каратеодори (выпуклая оболочка)
Теорема Каратеодори — теорема выпуклой геометрии . В нем говорится, что если точка лежит в выпуклой оболочке из набора , затем лежит в каком-то -мерный симплекс с вершинами в . Эквивалентно, можно записать как выпуклую комбинацию не более чем указывает на . Кроме того, можно записать как выпуклую комбинацию не более чем крайние точки в , так как неэкстремальные точки можно удалить из без изменения состава в выпуклой оболочке.
Эквивалентная теорема для конических комбинаций утверждает, что если точка лежит в коническом корпусе из набора , затем можно записать как коническую комбинацию не более указывает на . [ 1 ] : 257
Две другие теоремы Хелли и Радона тесно связаны с теоремой Каратеодори: последняя теорема может быть использована для доказательства первых теорем и наоборот. [ 2 ]
Результат назван в честь Константина Каратеодори , доказавшего теорему в 1911 году для случая, когда компактен . [ 3 ] В 1914 году Эрнст Стейниц расширил теорему Каратеодори для произвольных множеств. [ 4 ]
Пример
[ редактировать ]
Теорема Каратеодори в двух измерениях утверждает, что мы можем построить треугольник, состоящий из точек из P , который заключает в себе любую точку выпуклой оболочки P .
Например, пусть P = {(0,0), (0,1), (1,0), (1,1)}. Выпуклая оболочка этого множества представляет собой квадрат. Пусть x = (1/4, 1/4) в выпуклой оболочке P . Затем мы можем построить набор {(0,0),(0,1),(1,0)} = P ′, выпуклая оболочка которого является треугольником и заключает в себе x.
Доказательство
[ редактировать ]Примечание. Мы будем использовать только тот факт, что является упорядоченным полем , поэтому теорема и доказательство работают, даже если заменяется любым полем , вместе с общим заказом.
Сначала формально сформулируем теорему Каратеодори: [ 5 ]
Теорема Каратеодори — Если , затем представляет собой неотрицательную сумму не более точки .
Если , затем является выпуклой суммой не более точки .
Суть теоремы Каратеодори заключается в конечном случае. Такое сведение к конечному случаю возможно, поскольку – множество конечной выпуклой комбинации элементов ( выпуклой оболочки подробности см. на странице ).
Лемма — Если затем , существует такой, что , и самое большее из них ненулевые.
Благодаря лемме теорема Каратеодори представляет собой простое расширение:
Для любого , представлять для некоторых , затем , и мы воспользуемся леммой.
Вторая часть [ нужны разъяснения ] сводится к первой части путем «поднятия одного измерения» - распространенный прием, используемый для сведения аффинной геометрии к линейной алгебре и сведения выпуклых тел к выпуклым конусам.
Явно, пусть , затем определите с подмножеством . Это вызывает встраивание в .
Любой , по первой части, имеет «приподнятое» представление где максимум из ненулевые. То есть, , и , что завершает доказательство.
Это тривиально, когда . Если мы сможем доказать это всем , то по индукции мы доказали это для всех . Таким образом, остается доказать это для . Это докажем индукцией по .
Базовый случай: , тривиально.
Индукционный корпус. Представлять . Если некоторые , то доказательство закончено. Итак, предположим, что все
Если линейно зависима, то мы можем использовать индукцию по ее линейной оболочке, чтобы исключить один ненулевой член в , и тем самым устранить его в также.
В противном случае существует , такой, что . Тогда мы можем интерполировать полный интервал представлений:
Если для всех , затем установите . В противном случае, пусть быть самым маленьким такой, что один из . Тогда мы получим выпуклое представление с ненулевые члены.
Альтернативные доказательства используют теорему Хелли или теорему Перрона-Фробениуса . [ 6 ] [ 7 ]
Варианты
[ редактировать ]Номер Каратеодори
[ редактировать ]Для любого непустого , определите его число Каратеодори как наименьшее целое число , такой, что для любого , существует представление в виде выпуклой суммы до элементы в .
Теорема Каратеодори просто утверждает, что любое непустое подмножество есть номер Каратеодори . Эта верхняя граница не обязательно достигается. Например, единичная сфера в имеет число Каратеодори, равное 2, поскольку любая точка внутри сферы представляет собой выпуклую сумму двух точек на сфере.
С дополнительными предположениями о , верхние границы строго ниже, чем можно получить. [ 8 ]
Безразмерный вариант
[ редактировать ]Недавно Адипрасито, Барани, Мустафа и Терпаи доказали вариант теоремы Каратеодори, не зависящий от размерности пространства. [ 9 ]
Красочная теорема Каратеодори
[ редактировать ]Пусть X 1 , ..., X d +1 — множества из R д и пусть x — точка, содержащаяся в пересечении выпуклых оболочек всех этих d +1 множеств.
Тогда существует множество T = { x 1 , ..., x d +1 }, где x 1 ∈ X 1 , ..., x d +1 ∈ X d +1 , такое, что выпуклая оболочка T содержит точка х . [ 10 ]
Если рассматривать множества X 1 , ..., X d +1 как разные цвета, то множество T состоит из точек всех цветов, отсюда и слово «красочный» в названии теоремы. [ 11 ] Множество T также называют радужным симплексом , поскольку это d -мерный симплекс , в котором каждый угол имеет свой цвет. [ 12 ]
У этой теоремы есть вариант, в котором выпуклая оболочка заменяется конической оболочкой . [ 10 ] : Thm.2.2 Пусть X 1 , ..., X d — множества из R д и пусть x — точка, содержащаяся в пересечении конических оболочек всех этих d множеств. Тогда существует множество T = { x 1 , ..., x d где x 1 ∈ X 1 , ..., x d ∈ X d , такое, что коническая оболочка T } , содержит точку x . [ 10 ]
Мустафа и Рэй распространили эту красочную теорему на перенос точек на выпуклые тела. [ 12 ]
Вычислительная задача поиска красочного множества лежит на пересечении классов сложности PPAD и PLS . [ 13 ]
См. также
[ редактировать ]- Лемма Шепли – Фолкмана.
- Теорема Хелли
- Теорема Кирхбергера
- N-мерный многогранник
- Теорема Радона и ее обобщение Теорема Тверберга
- Теорема Крейна – Милмана
- Теория Шоке
Примечания
[ редактировать ]- ^ Ловас, Ласло ; Пламмер, доктор медицины (1986). Теория соответствия . Анналы дискретной математики. Том. 29. Северная Голландия. ISBN 0-444-87916-1 . МР 0859549 .
- ^ Данцер, Л.; Грюнбаум, Б .; Клее, В. (1963). «Теорема Хелли и ее родственники». Выпуклость . Учеб. Симп. Чистая математика. Том. 7. Американское математическое общество . стр. 101–179. См., в частности, стр. 109.
- ^ Каратеодори, К. (1911). «Об области изменения констант Фурье положительных гармонических функций» . Rendiconti del Circolo Matematico di Palermo (1884–1940) (на немецком языке). 32 (1): 193–217 [см. стр. 200 внизу]. дои : 10.1007/BF03014795 . S2CID 120032616 .
- ^ Стейниц, Эрнст (1913). «Условно сходящиеся ряды и выпуклые системы». Дж. Рейн Анжью. Математика . 1913 (143): 128–175. дои : 10.1515/crll.1913.143.128 . S2CID 120411668 .
- ^ Леонард, И. Эд; Льюис, Дж. Э. (2016). «3.3 Выпуклые оболочки». Геометрия выпуклых множеств . Хобокен, Нью-Джерси: Уайли Блэквелл. ISBN 978-1-119-02266-4 .
- ^ Эгглстон, Х.Г. (1958). Выпуклость . Издательство Кембриджского университета. дои : 10.1017/cbo9780511566172 . ISBN 9780511566172 . См. стр. 40–41.
- ^ Насоди, Мартон; Полянский, Александр (2021). «Перрон и Фробениус встречают Каратеодори». Электронный журнал комбинаторики . 28 (3). arXiv : 1901.00540 . дои : 10.37236/9996 . S2CID 119656227 .
- ^ Барань, Имре; Карасев, Роман (20 июля 2012 г.). «Заметки о числе Каратеодори». Дискретная и вычислительная геометрия . 48 (3): 783–792. arXiv : 1112.5942 . дои : 10.1007/s00454-012-9439-z . ISSN 0179-5376 . S2CID 9090617 .
- ^ Адипрасито, Карим; Барань, Имре; Мустафа, Набиль Х.; Терпаи, Тамаш (28 августа 2019 г.). «Теоремы Каратеодори, Хелли и Тверберга без размерности». arXiv : 1806.08725 [ math.MG ].
- ^ Jump up to: а б с Барань, Имре (1 января 1982 г.). «Обобщение теоремы Каратеодори» . Дискретная математика . 40 (2–3): 141–152. дои : 10.1016/0012-365X(82)90115-7 . ISSN 0012-365X .
- ^ Монтехано, Луи; Фабила, Руй; Брачо, Хавьер; Барани, Имре; Ароча, Джордж Л. (1 сентября 2009 г.). «Очень красочные теоремы » Дискретная и вычислительная геометрия . 42 (2): 142–154. дои : 10.1007/s00454-009-9180-4 . ISSN 1432-0444 .
- ^ Jump up to: а б Мустафа, Набиль Х.; Рэй, Саураб (6 апреля 2016 г.). «Оптимальное обобщение теоремы Красочного Каратеодори» . Дискретная математика . 339 (4): 1300–1305. дои : 10.1016/j.disc.2015.11.019 . ISSN 0012-365X .
- ^ Менье, Фредерик; Мюльцер, Вольфганг; Саррабезолль, Полина; Стейн, Янник (01 января 2017 г.), «Радуга в конце линии? Формулировка PPAD красочной теоремы Каратеодори с приложениями», Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2017 г. , Материалы , Общество промышленной и прикладной математики, стр. 1342–1351, arXiv : 1608.01921 , doi : 10.1137/1.9781611974782.87 , ISBN 978-1-61197-478-2 , S2CID 5784949
Дальнейшее чтение
[ редактировать ]- Экхофф, Дж. (1993). «Теоремы типа Хелли, Радона и Каратеодори». Справочник по выпуклой геометрии . Том. А, Б. Амстердам: Северная Голландия. стр. 389–448.
- Мустафа, Набиль; Менье, Фредерик; Гоаок, Ксавьер; Де Лоэра, Хесус (2019). «Дискретные, но вездесущие теоремы Каратеодори, Хелли, Спернера, Такера и Тверберга». Бюллетень Американского математического общества . 56 (3): 415–511. arXiv : 1706.05975 . дои : 10.1090/bull/1653 . ISSN 0273-0979 . S2CID 32071768 .
Внешние ссылки
[ редактировать ]- Краткое изложение теоремы в терминах выпуклых оболочек (на PlanetMath )