Теорема Кирхбергера
Теорема Кирхбергера — теорема дискретной геометрии о линейной разделимости . Двумерная версия теоремы утверждает, что если конечное множество красных и синих точек на евклидовой плоскости обладает свойством, заключающимся в том, что для каждых четырех точек существует линия, разделяющая красную и синюю точки внутри этих четырех, то существует существует единственная линия, отделяющая все красные точки от всех синих точек. Дональд Уотсон формулирует этот результат более красочно, используя аналогию с фермерским двором:
Если овцы и козы пасутся в поле и на каждые четыре животных существует линия, отделяющая овец от коз, то такая линия существует для всех животных. [ 1 ]
В более общем смысле, для конечного числа красных и синих точек в -мерное евклидово пространство , если красная и синяя точки в каждом подмножестве точек линейно разделимы, то все красные точки и все синие точки линейно разделимы. Другой эквивалентный способ формулировки результата состоит в том, что если выпуклые оболочки конечного числа красных и синих точек имеют непустое пересечение, то существует подмножество точки, для которых также пересекаются выпуклые оболочки красных и синих точек в подмножествах. [ 2 ] [ 3 ]
История и доказательства
[ редактировать ]Теорема названа в честь немецкого математика Пауля Кирхбергера, студента Давида Гильберта в Геттингенском университете , который доказал ее в своей диссертации 1902 года. [ 4 ] и опубликовал его в 1903 году в «Математических анналах» , [ 5 ] в качестве вспомогательной теоремы использовал при анализе аппроксимации Чебышева . В отчете Гильберта о диссертации говорится, что некоторые из вспомогательных теорем Кирхбергера в этой части его диссертации были известны Герману Минковскому , но неопубликованы; неясно, применимо ли это утверждение к результату, ныне известному как теорема Кирхбергера. [ 6 ]
Со времени работы Кирхбергера были опубликованы и другие доказательства теоремы Кирхбергера, в том числе простые доказательства, основанные на теореме Хелли о пересечении выпуклых множеств , [ 7 ] на основе теоремы Каратеодори о принадлежности к выпуклым оболочкам , [ 2 ] или основано на принципах, связанных с теоремой Радона о пересечении выпуклых оболочек. [ 3 ] Однако теорема Хелли, теорема Каратеодори и теорема Радона появились позже теоремы Кирхбергера.
Обобщения и связанные с ними результаты
[ редактировать ]Усиленная версия теоремы Кирхбергера фиксирует одну из заданных точек и рассматривает только подмножества точки, включающие фиксированную точку. Если красные и синие точки в каждом из этих подмножеств линейно разделимы, то все красные и все синие точки линейно разделимы. [ 1 ] Теорема также верна, если красные и синие точки образуют компакты , которые не обязательно конечны. [ 3 ]
Используя стереографическую проекцию , теорему Кирхбергера можно использовать для доказательства аналогичного результата для круговой или сферической разделимости: если каждые пять точек из конечного числа красных и синих точек на плоскости могут иметь красные и синие точки, разделенные кругом, или каждые точки в более высоких измерениях могут иметь красные и синие точки, разделенные гиперсферой , тогда все красные и синие точки могут быть разделены таким же образом. [ 8 ]
См. также
[ редактировать ]- Теорема о разделении гиперплоскостей , теорема о том, что непересекающиеся компактные выпуклые множества линейно отделимы.
Ссылки
[ редактировать ]- ^ Jump up to: а б Уотсон, Дональд (1973), «Уточнение теорем Кирхбергера и Каратеодори», Австралийское математическое общество , 15 (2): 190–192, doi : 10.1017/S1446788700012957 , MR 0333980
- ^ Jump up to: а б Шимрат, Моше (1955), «Простое доказательство теоремы П. Кирхбергера» , Pacific Journal of Mathematics , 5 (3): 361–362, doi : 10.2140/pjm.1955.5.361 , MR 0071796
- ^ Jump up to: а б с Вебстер, Р.Дж. (1983), «Еще одно простое доказательство теоремы Кирхбергера», Журнал математического анализа и приложений , 92 (1): 299–300, doi : 10.1016/0022-247X(83)90286-X , MR 0694178
- ^ Пол Кирхбергер в проекте «Математическая генеалогия»
- ^ Кирхбергер, Пауль (1903), «О методах аппроксимации Чебышева» , Mathematical Annals , 57 (4): 509–540, doi : 10.1007/BF01445182 , MR 1511222 , S2CID 120774553
- ^ Стеффенс, Карл-Георг, «4.3 Тезис Кирхбергера», История теории приближения: от Эйлера до Бернштейна , Бостон: Биркхойзер, стр. 135–137, doi : 10.1007/0-8176-4475-x_4 , MR 2190312
- ^ Радемахер, Ганс ; Шенберг, И.Дж. (1950), «Теоремы Хелли о выпуклых областях и задача аппроксимации Чебышева», Canadian Journal of Mathematics , 2 : 245–256, doi : 10.4153/cjm-1950-022-8 , MR 0035044
- ^ Лэй, SR (1971), «О разделении сферическими поверхностями», American Mathematical Monthly , 78 (10): 1112–1113, doi : 10.2307/2316320 , JSTOR 2316320 , MR 0300201
Дальнейшее чтение
[ редактировать ]- Бергольд, Хелена; Фельснер, Стефан; Шойхер, Манфред; Шредер, Феликс; Штайнер, Рафаэль (2020), «Топологические рисунки соответствуют классическим теоремам выпуклой геометрии», Труды 28-го Международного симпозиума по рисованию графов и визуализации сетей , arXiv : 2005.12568
- Кордовил, Рауль (1982), «О теореме разделения ориентированных матроидов трех порядков», Discrete Mathematics , 40 (2–3): 163–169, doi : 10.1016/0012-365X(82)90117-0 , MR 0676722
- Хоул, Майкл Э. (1991), «Теоремы о существовании разделяющих поверхностей», Discrete & Computational Geometry , 6 (1): 49–56, doi : 10.1007/BF02574673 , MR 1073072 , S2CID 1992810
- Ланги, Жолт; Насоди, Мартон (2008), «Теоремы типа Кирхбергера для разделения выпуклыми областями», Periodica Mathematica Hungarica , 57 (2): 185–196, doi : 10.1007/s10998-008-8185-6 , MR 2469604 , S2CID 15506550
- Нетребин, АГ; Шашкин, Ю. А. (1985), "Теоремы типа Кирхбергера и Каратеодори в обобщенных выпуклых пространствах", Доклады АН СССР , 283 (5): 1085–1088, МР 0802134
- Ренни, Британская Колумбия (1970), «Теорема, подобная теореме Кирхбергера», Журнал Лондонского математического общества , вторая серия, 2 : 40–44, doi : 10.1112/jlms/s2-2.1.40 , MR 0250192