Теорема Каратеодори - это теорема выпуклой геометрии . Он утверждает, что если точка x из R d лежит в выпуклой оболочке множества P , то x может быть записано как выпуклая комбинация не более чем d + 1 точки в P. А именно, существует подмножество P ′ множества P, состоящее из из d + 1 или меньше точек таких, что x лежит в выпуклой оболочке P ′. Эквивалентно, x лежит в r - симплексе с вершинами в P , где. Наималейший г , что делает последнее утверждение действительно для каждого х в выпуклой оболочке P определяются как число Каратеодорьте из P . В зависимости от свойств P могут быть получены более низкие оценки, чем те, которые дает теорема Каратеодори. [1] Обратите внимание, что P не обязательно должно быть выпуклым. Следствием этого является то, что P ′ всегда может быть экстремальным в P , поскольку неэкстремальные точки могут быть удалены из P без изменения принадлежности x к выпуклой оболочке.
Подобные теоремы Хелли и Радона тесно связаны с теоремой Каратеодори: последняя теорема может использоваться для доказательства первых теорем и наоборот. [2]
Результат назван в честь Константина Каратеодори , который доказал теорему в 1907 году для случая, когда P компактно. [3] В 1914 году Эрнст Стейниц расширил теорему Каратеодори для любых множеств P в R d . [4]
Пример
Рассмотрим множество P = {(0,0), (0,1), (1,0), (1,1)}, которое является подмножеством R 2 . Выпуклая оболочка этого множества - квадрат. Рассмотрим теперь точку х = (1/4, 1/4), который находится в выпуклой оболочке P . Затем мы можем построить набор {(0,0), (0,1), (1,0)} = P ′, выпуклая оболочка которого представляет собой треугольник и охватывает x , и, таким образом, теорема работает для этого случая, с тех пор | P ′ | = 3. Это может помочь визуализировать теорему КАРАТЕОДОРИ в 2 -х измерениях, как говорят , что мы можем построить треугольник , состоящий из точек из Р , покрывающей любую точку P .
Доказательство
Пусть й точка в выпуклой оболочке P . Тогда x - выпуклая комбинация конечного числа точек в P :
где каждый x j принадлежит P , каждый λ j (wlog) положителен и.
Предположим, что k > d + 1 (иначе доказывать нечего). Тогда векторы х 2 - х 1 , ..., х к - х 1 являются линейно зависимыми ,
так что существуют вещественные скаляры μ 2 , ..., μ k , не все нулевые, такие, что
Если μ 1 определяется как
тогда
и не все μ j равны нулю. Следовательно, хотя бы одно μ j > 0. Тогда
для любого действительного α . В частности, равенство будет выполняться, если α определяется как
Обратите внимание, что α > 0, и для любого j от 1 до k ,
В частности, λ i - αμ i = 0 по определению α . Следовательно,
где каждый неотрицательно, их сумма равна единице, и, кроме того, . Другими словами, х представляется в виде выпуклой комбинации в большинстве K -1 точек P . Этот процесс можно повторять до тех пор й не представлен в виде выпуклой комбинации в большинстве д + 1 точек в P .
Альтернативные доказательства используют теорему Хелли или теорему Перрона – Фробениуса . [5] [6]
Варианты
Теорема Каратеодори для конической оболочки
Если точка x из R d лежит в конической оболочке множества P , то x можно записать как коническую комбинацию не более чем d точек в P. А именно, существует подмножество P ′ множества P, состоящее из d или меньшего количества точек , такая, что x лежит в конической оболочке P ′. [7] : 257 Доказательство аналогично исходной теореме; разница в том, что в d- мерном пространстве максимальный размер линейно-независимого множества равен d , а максимальный размер аффинно-независимого множества равен d +1. [8]
Безразмерный вариант
Недавно Адипрасито, Барани, Мустафа и Терпай доказали вариант теоремы Каратеодори, не зависящий от размерности пространства. [9]
Красочная теорема Каратеодори
Пусть X 1 , ..., X d + 1 - множества в R d, и пусть x - точка, содержащаяся в пересечении выпуклых оболочек всех этих d +1 множеств.
Тогда существует множество T = { x 1 , ..., x d + 1 }, где x 1 ∈ X 1 , ..., x d + 1 ∈ X d + 1 , такое, что выпуклая оболочка T содержит точка x . [10]
Если рассматривать множества X 1 , ..., X d + 1 как разные цвета, то множество T состоит из точек всех цветов, отсюда и «красочный» в названии теоремы. [11] Множество T также называют радужным симплексом , поскольку это d -мерный симплекс, в котором каждый угол имеет свой цвет. [12]
В этой теореме есть вариант, в котором выпуклая оболочка заменяется конической . [10] : Теорема.2.2. Пусть X 1 , ..., X d - множества в R d, и пусть x - точка, содержащаяся в пересечении конических оболочек всех этих d множеств. Тогда существует множество Т = { х 1 , ..., х д }, где х 1 ∈ X 1 , ..., х D + 1 ∈ X d + 1 , таким образом, что коническая оболочка из Т содержит точку х . [10]
Мустафа и Рэй распространили эту красочную теорему с точек на выпуклые тела. [12]
Смотрите также
Заметки
- ^ Bárány, Имре; Карасев, Роман (2012-07-20). «Заметки о числе Каратеодори». Дискретная и вычислительная геометрия . 48 (3): 783–792. arXiv : 1112.5942 . DOI : 10.1007 / s00454-012-9439-z . ISSN 0179-5376 . S2CID 9090617 .
- ^ Danzer, L .; Грюнбаум, Б .; Клее, В. (1963). «Теорема Хелли и ее родственники». Выпуклость . Proc. Symp. Чистая математика. 7 . Американское математическое общество . С. 101–179. См., В частности, стр.109.
- ^ Каратеодори, К. (1907). "Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen" . Mathematische Annalen (на немецком языке). 64 (1): 95–115. DOI : 10.1007 / BF01449883 . ISSN 0025-5831 . Руководство по ремонту 1511425 . S2CID 116695038 .
- ^ Стейниц, Эрнст (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Математика . 1913 (143): 128–175. DOI : 10,1515 / crll.1913.143.128 . S2CID 120411668 .
- ^ Эгглстон, HG (1958). Выпуклость . Издательство Кембриджского университета. DOI : 10,1017 / cbo9780511566172 . ISBN 9780511566172. См. Страницы 40–41.
- ^ Насоди, Мартон; Полянский, Александр (2019). «Перрон и Фробениус встречаются с Каратеодори». arXiv : 1901.00540 [ math.MG ].
- ^ Ловас, Ласло ; Пламмер, Мэриленд (1986). Теория соответствия . Анналы дискретной математики. 29 . Северная Голландия. ISBN 0-444-87916-1. Руководство по ремонту 0859549 .
- ^ «Выпуклая геометрия - теорема Каратеодори для векторов в конусе» . Обмен математическими стеками . Проверено 22 июля 2020 .
- ^ Адипрасито, Карим; Барани, Имре; Mustafa, Nabil H .; Терпай, Тамаш (28 августа 2019 г.). «Теоремы Каратеодори, Хелли и Тверберга без размерности». arXiv : 1806.08725 [ math.MG ].
- ^ а б в Барани, Имре (1 января 1982 г.). «Обобщение теоремы Каратеодори». Дискретная математика . 40 (2–3): 141–152. DOI : 10.1016 / 0012-365X (82) 90115-7 . ISSN 0012-365X .
- ^ Монтехано, Луис; Фабила, Руй; Брачо, Хавьер; Барани, Имре; Ароча, Хорхе Л. (2009-09-01). «Очень красочные теоремы» . Дискретная и вычислительная геометрия . 42 (2): 142–154. DOI : 10.1007 / s00454-009-9180-4 . ISSN 1432-0444 .
- ^ а б Mustafa, Nabil H .; Рэй, Саураб (2016-04-06). «Оптимальное обобщение Красочной теоремы Каратеодори» . Дискретная математика . 339 (4): 1300–1305. DOI : 10.1016 / j.disc.2015.11.019 . ISSN 0012-365X .
дальнейшее чтение
- Экхофф, Дж. (1993). «Теоремы типа Хелли, Радона и Каратеодори». Справочник по выпуклой геометрии . А, В . Амстердам: Северная Голландия. С. 389–448.
- Мустафа, Набиль; Менье, Фредерик; Гоаок, Ксавьер; Де Лоэра, Хесус (2019). «Дискретные, но вездесущие теоремы Каратеодори, Хелли, Спернера, Такера и Тверберга». Бюллетень Американского математического общества . 56 (3): 415–511. arXiv : 1706.05975 . DOI : 10,1090 / бык / 1653 . ISSN 0273-0979 . S2CID 32071768 .
Внешние ссылки
- Краткая формулировка теоремы в терминах выпуклых оболочек (в PlanetMath )