Теоремы типа Хелли для трансверсалей семейств множеств и их приложения

ВВЕДЕНИЕ
Одной из классических тем комбинаторной и выпуклой геометрии являются исследования по проблеме существования m-мерной плоскости, пересекающей все множества некоторого семейства выпуклых множеств в
Эта плоскость называется т-трансверсалью семейства. Знаменитая теорема Хелли (E. Helly) [1] дает критерий существования О-трансверсали, т.е. общей точки семейства выпуклых множеств. В обшем виде задача о нахождении условий существования m-трансверсали впервые была сформулирована в работе P. Vincensini [2], где поставлена следующая задача
Vincensini’s Problem. Существует ли для 0 < тп < п такое число г = г(п,7м), что для любого (достаточно большого) семейства'Р выпуклых множеств в IR”, если любые г его членов имеют гп-трансверсаль. то и все семейство V имеет тп -трансверсаль.
В той же статье приведен ошибочный результат, что /*(2,1) < б. Л.А. Сантало (L.A. Santalö) [3] (см. также [4], с. 23) показа!, что без дополнительных предположений г(п, т) = оо при п > 2. Позже Хадвигер и Дебруннер (H. Hadwiger, H. Debrunner) [4] показали, что r(n,m) = ос даже для семейств попарно непересекающихся выпуклых множеств в Rn. В дальнейшем этой тематике было посвящено много работ, относящихся, в основном, к случаям m = п — 1, m = 1, а также п = 2. Имеющиеся здесь результаты частично отражены в следующих книгах [4, 5, 6. 7, 8]. В литературе существует много примеров, показывающих, что условия, гарантирующие существование m-трансверсали, являются весьма ограничительными даже в случае п = 2 (см., например, [4, о, 6, 7, 8]).
Центральный результат работы — это теорема 1.2.2 [9, 10, 11, 12]. Условия этой теоремы — комбинаторно-геометрические, однако ее утверждение имеет отношение и к топологии. В частности, ее следствиями являются с одной стороны теорема Хелли, а с другой стороны — теорема о покрытии сферы Борсука Люстернпка - Шнирельмана, а значит,
2
и эквивалентная ей теорема об антиподах Борсука - Улама (К. Borsuk.
S. Ulam) [13, 14].
В дальнейшем, при ссылках на некоторые классические результаты, во введении будут цитироваться не оригинальные работы, а обзоры [5, 6]. Основная цель настоящей работы — изучение различных трансверсалей семейств множеств.
В главе I (§1 - §7) приводятся различные теоремы о трансверсалях и вводится обобщенная выпуклость.
В §1 доказывается важная топологическая лемма [10, 12], являющаяся основной в доказательстве теоремы 1.2.2 и приводятся ее непосредственные следствия.
Лемма 1.1.1. Бати si,..., sm — сечения вещественного или комплексного канонического расслоения 7£_т+1 над вещественным или комплексным многообразием Грассмана GJJ,. то существует такое (n—m+l)-мерное подпространство L (вещественное или комплексное), что si(L) = ••• =
sm(L).
Доказательство этой леммы основано на применении характеристических классов Штифеля Уитни и Чжэня (лемма верна и для кватернион-ных грассмановых многообразий, о грассмановых многообразиях и характеристических классах см. в [15]). Позже эта лемма (в 1990 г.) независимо и другим способом была также доказана R .Т. Zivaljevic и S.T. Vrecica в [16], которые использовывали работу E. Fadell и S. Husseini [17].
Приведем теперь пример непосредственного приложения леммы. Обозначим через Кп — множество всех непустых компактных выпуклых множеств в IR” с топологией, индуцированной метрикой Хаусдорфа. Вектор-нозначным функционалом будем называть такое полунепрерывное снизу многозначное отображение р : Кп —> М" (С”), что p(V) € Кп и лежит в аффинной оболочке aff V множества V (см., например, [18, 19]). Например, таковы отображения, ставящие в соответствие выпуклому компакту множество центров его вписанных или описанных шаров в банаховой метрике, барицентр, точку Штейнера, центр минимального эллипсоида и т.д.
Следующая теорема [12] легко вытекает из предыдущей леммы и является усилением известной теоремы о центре тяжести сечения выпуклого тела (см., например, [20], с. 229).
Теорема 1.1.2. Если х внутренняя точка выпуклого п-мерного компакта V С R" (С"), то для любого набора векторнозначных функци-
3
/
о налов (pi,... ,pw) : Кп т ш (соответственно С" 771) существует
такая (п - т)-мерная плоскость тг Э х, что р\(V П 7г) = • • • = р1П(V Птг) = х.
Аналогичные результаты были получены для проекции на подпространство и для семейства выпуклых множеств [12].
В §2 формулируется и доказывается основная теорема 1.2.2 о транс-версалях [9, 10, 11, 12]. Заметим, что вопрос о связи между строением грассмановых многообразий G’rln и существованием общих трансвер сален был поставлен в книге [5], с. 61, и основной результат §2 это, по-видимому, первый результат на эту тему. Позже близкие теоремы о трансверсалях, используя топологические соображения получили .J.E.Goodman, R.Pollack, R.Wenger (см. [21, 22]).
Множество V С Rn (Са) назовем к-квазиеыпукльш, если его образ при любом линейном (аффинном) отображении / : Rn (О*) —> Ш.к (Cfc) выпукл или, что эквивалентно, если его ортогональная проекция L(V) на любое мерное подпространство L (вещественное или комплексное) выпуклое множество.
Очевидно, что если множество п-кваэивыпукло, то оно — выпукло. Также ясно, что если множество выпукло, то оно и fc-квазивыпукло для всех к. Но обратное неверно. Например, если V граница выпуклого множества в Rn, то ясно, что V — (гг — 1)-кваэивыпукло. Или, если, в качестве более общего примера, взять множество Nk(F), которое является объединением к-мерных граней ограниченного выпуклого многогранника F (к-мерный остов F). Другой пример невыпуклого, но квазивыпуклого множества, дает так называемое "ожерелье Антуана" (см. [23]). Это множество даже является вполне несвязным, но 1-кваэивыпуклым. Н литературе 1-квазивыпуклые множества также называются выпукло-связными (см. [5], с. 38).
Будем говорить, ЧТО семейство множеств Р имеет СВОЙСТВО П* ИЛИ, Р € Нк если любые < к множеств семейства Р имеют непустое пересечение и свойством И (Р € П), если пересечение всего семейства непусто.
Сформулируем основной результат параграфа. Пусть {Pi} i<i<m<n набор таких семейств (n—m+1)-квазивыпуклых замкнутых подмножестве IRn или С”, что в любом семействе есть компакты И |Р;| > п — т + 2 для всех ц 1 < г < т.
Теорема 1.2.2. Если Pi £ П„_т+2 длявсехг, 1 < i < m, то семейство Р — UI=i Р* имеет (m — 1 )-траисверсаль.
Ясно, что при m = I теорема 1.2.2 в точности совпадает с теоремой
4
Хелли. В §‘2 приведен и другой вариант этой теоремы и получены также обобщения этой теоремы на случай флагов (определение флага см. в [24]).
Для формулировки обобщения теорем 1.2.2, 1.2.3 на случай флагов аналогично возьмем набор семейств {Р,}ккто подмножеств для которого существует такое разбиение (/1, /2,..., 1к) множества индексов Гп = {1,2,..., т}, что |/у | = ту, ту < п — 1, тх < т2 < • • • < Шк 3> 1 < 3 < к и семейства Р, для всех г, I £ /у, состоят из (п — пу )-квазивыпуклых множеств, где
Теорема 1.2.4. Если для любого 1 < j < к и любого і £ /у семейство Р, £ Пп_Пі+і, то существует такой флаг F £ F(n,R”) (F(n, С"), что для любого j плоскость 7гу является nj-трансверсалью семейства Pj =
и?=1и,е/,р-- 1 < І < ^
В §3 показано, как из теоремы 1.2.2 выводится теорема 1.3.1, следствиями которой являются теорема Борсука - Люстерника - Шнирель-мана (при к = 2 и m = 0) и теорема о покрытии S. Stahl [25] (при к = 2/ и
Множество V С 1КП назовем односторонним, если V содержится в открытом полупространстве с граничной гиперплоскостью, проходящей через 0, и всесторонним в противном случае. Назовем т-мерной подефе-рой пересечение (т + 1)-мерного подпространства со сферой.
Теорема 1.3.1 [0, 10, 12]. Если каждая т-мерпая подефера пересекает не менее к множеств семейства Р — {К}, 1 < г < к+п — т — 2, к+п > т — 1, состоящего из замкнутых (открытых) множеств, которые лежат на сфере З**-1, то одно из множеств семейства Р содержит всестороннее множество из т 4- 2 точек.
Показано, что при гп = п теорема 1.2.2 и теорема Борсука - Люстерника Шиирельмана эквивалентны.
В §4 понятие трансверсали обобщается так, что это обощение включает, как частный случай семейство поверхностей, задаваемых множествами нулей произвольных функций, и доказываются некоторые несложные результаты об этих трансверсалях, необходимые ниже, а также иллюстрируются и мотивируются вводимые понятия. Нижеследующие определения даны в [12, 26, 27].
m — 0).
5
Пусть У — множество, F — поле, L — линейное TV-мерное пространство, состоящее из Р-значных функций на У, L* — сопряженное к L пространство. Отображение vi : V L*, определенное для всех / G L, х G У, формулой (с/Л.т), /) = f(x) назовем отображением Веронезе для L.
В §4 будем полагать, что F = & или С, У = R" (соответственно С’1). Пусть в L содержите я функция е, тождественно равная 1, и пусть L таково, что для всех компактных (замкнутых) У Ç R” множество со(v/ДУ)) компактно (соответственно замкнуто). (Ясно, что если в L все функции непрерывны, то последнее верно). Для / € I и Л' С L положим
EU) = {* € V : /(*) = 0}, Я(А') = f| Я(/) = П я (Я,
/€* /GlinA-
и Р(/) = {яг G Rn : /(ж) > 0}, Р(/) = {х G Rn : /(*) > 0} для L = R.
Если / —линейная функция на R", то Р(/), Р(/) и #(/) — открытое и замкнутое полупространства и гиперплоскость, соответственно. Таким образом, множества Р(/), P(f) п Н({) — это аналоги открытого и замкнутого полупространства и гиперплоскости.
Обозначим через con V коническую оболочку множества V. через со У выпуклую оболочку множества У, через V — замыкание У.
Будем говорить, что функция / € L разделяет множество У Ç Rn (соответственно С”), если О G со/(У), и, что функция / G L разделяет множества V\, Vo в Rn, если \\ С Р(}) и V2 Ç Р( —/). Множества V\, У> в этом случае назовем L- отделимыми.
Подпространство Lq С L назовем (т, Ь)-трансв ер солью семейства Р, если / разделяет множество У для всех / Е Lo? У G Pu diin Lq = N — m — 1.
Семейство множеств Р в R" (Сп) назовем L-неразделимым, если у него есть (0, £)-трансверсаль. В противном случае, Р назовем L-раз делимым. Семейство множеств Р в R" назовем вполне L-разделимым, если для всех подсемейств Р' С Р множества UvgP' ^ 11 LVgp\p' ^ — L-отделимы.
Если Рд — пространство полиномиальных функций степени < И на R” (Сп), то dim PJ = (п^ )> множество H(f) — это алгебраическая гиперповерхность, а при d = l — гиперплоскость. Классическое определение отображения Веронезе дается для пространства L = РЦ (см. [28]). Если Sn — пространство вещественных функций на. R" с базисом /0 = 1, /; = л:,;, L < г < п, /п+1 = «!+••• + то множество #(/) — это сфера или гиперплоскость, а /с-мерные подпространства L С S(En) называются (п — к — 1)-мерными обобщенными сферами (см. [’29]).
6
Следующие факты показывают [12, 26, 27], что понятие (т, £)-транс-вор с а ли есть обобщение понятия т-трансверсали, Р-неразделимость является обобщением свойства семейства иметь общую точку, и указывают связь между существованием трансверсали и отделимостью множеств:
(1) Множества У\, 1'2 1-отделимы тогда и только тогда, когда множества и Ь1(У2) Р^-1-отделимы;
(2) Если семейство множеств Р обладает свойством П, то оно Р-неразделимо;
(3) Семейство Р замкнутых выпуклых множеств в Мп или в С” имеет (ш, Р1п)-трансверсаль тогда и только тогда, когда у семейства Р существует ш-трансверсаль;
(4) Семейство множеств Р в I" (‘С71) имеет (га, Р)-трансверсаль тогда и только тогда, когда семейство г\&(Р) = {<;/,(!') : V Е Р} имеет (га, Р{* ~1)-трансверсаль или, что эквивалентно, когда семейство соиь(Р) = {со1>^(1/Г) : V Е Р\ имеет га-трансверсаль;
В §5 доказаны теоремы о существовании обобщенных трансверсалей и далее в нем пространства функций Ь такие же, что и в §4.
Будем говорить, что семейство множеств Р имеет свойство П*(£) {Р Е Щ(Р)), если все подсемейства Р из < к множеств £-неразделимы.
Множество V С X" (С”) назовем (к, Ь)-квазивыпуклым9 если для всех /1, • • •> Л ^ Ь множество ..., ЛОО) С Е* (С*) выпукло.
Легко видеть, что (к, Р”)-квазивыпуклость совпадает с А-квазивыпук-лостью, а множество V С М'1 (Сп) — (к, Р)-квазивыпукло тогда и только тогда, когда множество ^(К) — А-квазивыпукло.
Также показано, что семейство из т компактных множеств в М” имеет (га, Т)-трансверсаль тогда и только тогда, когда оно не вполне Т.-раз делимо (это утверждение является обобщением результата из [21]).
Главным результатом этого параграфа является следующая
Теорема 1.5.1 [12, 26, 27]. Пусть Р,, 1 < I < га < N — 1, такие семейства замкнутых множеств Км (С'1), что каждое Р; или содержит компакт, или конечно, и Р; Е Плг-т+1(£) Для всех *• Тогда семейство Р = и^1 Р имеет (тп — 1, Ь)-трансверсаль тг; если, кроме того, семейства Р± состоят из (Лг — т,Ь)-квазивыпуклых множеств, то V р) II(тг) ф Ф для всех V Е Р.
В приложениях иногда полезны теоремы о трансверсалях, определяемых семействами функций, не образующими линейного пространства.
7
Рассмотрим множество X и такую функцию
/ = f(a, х) : Rn+I х X —> R, а Є R’!+\ ж Є X,
что для некоторого фиксированного m Є и всех ^ Є IR, имеем,
f(ta,x) = t2m+1/(a,i), а Є Rn+\ ж Є X.
В частности, имеем, f(a.x) = —f(—a,x). Таким образом семейство функций {/(а,#)}, а Є Rn+1, параметризовано множеством параметров Rn+I.
Бели L — линейное вещественное Л -мерное пространство функций на Rn, то можно считать, что L является множеством параметров МЛ\ множество X = R”, а отображение / = f{a,x) : L xWl —> R, а Є L, x E R'* задается равенством / = Да,.г) = а(х) = (vl(®)»°)
Подобно предыдущему, будем говорить, что функция } разделяет подмножество V С X при данном «о? если /(ao,£i)/(ao,Х2) < 0 для некоторых хі, Х2 Є V. Функция / разделяет Vj, Vj СХ, если существует такой параметр ао, что /(а0, г) < 0 для всех т € V\ и f(a0ix) > 0 для всех ж € V2. Если такого параметра ао не существует, будем говорить, что множества Vi, V*j являются J-неразделимыми. Очевидно, что если \\ П V2 Ф 0, то они — /-неразделимы.
Положим Л/00 = {а Є R?,+ 1 : f(a>x) >0, х Є V С X) С R”+1. Множество УСА" назовем f-компактным, если множество К /(V) — открытое. Если X — топологическое пространство, а / — непрерывное отображение, то легко видеть, что любой компакт V С X является /-компактом.
Теорема 1.5.6 [12]. Пусть Р\,..., Рп семейства /-компактных подмножеств X и во всех Pi любые два. множества /-неразделимы, то существует такой параметр а0 € Rn+1, что / = /(ciq,x) разделяет все множества семейства Р = иГ=і Pi-
Следствие 1.5.7. Если в R" даны m(n -1- 1) — 1 семейств выпуклых компактов и все семейства имеют свойство П2, то найдутся гп гиперплоскостей. объединение которых пересекает все множества всех семейств.
Заметим, что прямо из теоремы 1.2.2 существование m гиперплоскостей, объединение которых пересекает все множества семейства Р, следует только при меньшем числе семейств = гпп.
В конце параграфа приводится одна простая теорема о трансверса-лях [30], в доказательстве которой используется теорема Лере (J. Leray) о нерве ([31], см. также [5], с. 55).
8
В §6 приводятся обобщения теорем Хадвигера - Дебруннера о транс-версали. Условия существования трансверсали в §6 являются обобщением условий в теореме о трансверсалях Хадвигера Дебруннера (см. [4] стр. 06, а также см. [5] стр. 04). Будем полагать, что все семейства множеств, которые рассматриваются в §6 состоят из выпуклых компактов в К"'*.
Семейство множеств Р в назовем равномерно ограниченным, если диаметры всех множеств семейства имеют верхнюю грань.
Будем говорить, что семейство Р в Мп неограничено в направлении у 6 если существует такая последовательность векторов
Семейство множеств Р в К" назовем /-неограниченным (или Р € Р/), 1 < I < П, если существуют / линейно независимых векторов У\,У2, • • ■ У1 С 5Д_1, в направлении которых Р неограничено. Легко видеть, что Р Е В у эквивалентно неограниченности ЬТ(Р) и Р е В/ эквивалентно тому, что рецессивный конус сои Сг(Р) имеет размерность > / (см. главу 2 §1). Если на семейство множеств не наложено никаких условий типа ограниченности или неограниченности, то будем считать, что семейство является 0-неограниченным.
Теперь приведем обобщение теоремы Хадвигера - Дебруннера.
Теорема 1.6.3 [26, 30. 32]. Пусть дан набор неотрицательных целых чисел I = £3™! /;, и такой набор {Р,}, 1 < г < тп < п, равномерно ограниченных и /,-неограниченных семейств множеств в что
|Р* | > п — тп + 2 + /,•. Если для всех г и для любого такого <5, С Р = что \Qif\Pj\ = Ь при г Ф 3 и \QiC\Pi\ = Ь + 11 — А: + 2 существует I-трансверсаль, то существует (га — 1 + 1)-трансверсаль у семейства. Р.
Теорема Хадвигера - Дебруннера получается из теоремы 1.6.3 при т = 1 и / = 1, при тп = 1 и / = 0 из теоремы 1.6.6 получается теорема Хелли, а при / = 0 — теорема 1.2.2.
Рассмотрим тп точек {д?! - а*2- • • •, хт } в общем положении в С Ел+/ и т попарно ортогональных подпространств и ортогональных подпространств ЬууЬъ. ..уЬт размерности ... ,/„,, соответственно. Пусть Р*у 1 £ / < ш, — семейство всех одноточечных подмножеств плоскости а?,- + Ьгу тогда семейства Р,-, 1 < г < т, удовлетворяют условиям теоремы 1.0.2 и очевидно, что размерность трансверсапи га—1+/ нельзя уменьшить.
В §6 также приводится обобщение другого результата Хадвигера -Дебруннера о трансверсали (см. [4], с. 59, [5], с. 48).
9
Для семейства множеств Р точечной к-трансверсалью называется такое множество lT, \U\ < к, что U OV ф 0 для всех V Є Р (см., например, [4, 5] или [33]). Положим Р Є П(т,А*), если любые < т множеств из Р имеют точечную А>трансверсаль, и Р Є П(А-), если семейство Р имеет точечную Av трансвер саль. Обозначим t(P) = inf к, где Р Є П(Лг).
Хадвигеру и Дебруннеру принадлежат следующие определения [4, 5]. Семейство Q множеств обладает (р, <у)-свойством (Q Є Пь</), если из каждых р множеств семейства найдутся q с непустым пересечением. Пусть
М(р, q; Р) = sup t(Q).
qcp, Qeпр.,
Для семейства всех выпуклых компактов Р в ЭР, положим М (р, q: Р) = М(р, г/; п). Хадвигер и Дебруннер [4, о] доказані, что если
її
n+l<q<p< п _ ^ (q - 1), то М (р, q\ п) = р - q + 1.
Недавно, И. Алон и Д. К лейтман (N. Alon, D.J. Kleitman) [34] показали, что если /г 4-1 < q < р, то М (р, q\ ri) < ос для всех р, <у, п £ N.
Следующий результат является обобщением результатов Хадвигера -Дебруннера и Алона - Клейтмана при / = 0 на случай т-трансвсрсалей.
Теорема 1.6.4 [26, 30. 32]. Если Р такое равномерно ограниченное и I-неограниченное семейство выпуклых компактов в ЕХ что среди каждых (р —1)(/ 4- 1} 4- 1 множеств семейства найдутся 1{р — 1) 4- q, имеющих 1-трапсвсрсаль, n — I + 1 < q < р, то существует такое семейство {тг,}^/ параллельных l-мерных плоскостей, что V П Ut'e/ 7Г' ^ ® ^ля всех У € Р и |/| < М(р, су; п — /).
Условие, что среди каждых (р — 1)(/ 4-1) 4- 1 множеств семейства найдутся 1(р — 1)4- q, имеющих /-трансвсрсаль, нельзя заменить на более слабое условие, что среди каждых (р — 1) (/ 4-1) множеств семейства найдутся 1{р — 1) 4- q — 1, имеющих /-транс вер сачь.
В некоторых случаях теорему 1.6.4, используя результаты из [153], можно уточнить.
Теорема 1.6.5. Существует такая функция <p(q,n — I), что если Р такое равномерно ограниченное и /-неограниченное семейство выпуклых компактов в Rn, что среди каждых (р — 1)(/ 4-1) 4- 1 множеств семейства найдутся 1(р — 1) 4- q, имеющих 1-трансвсрсальу п — / 4-1 < q < р < 4>{q, n — I) п и нет совпадающих проекции множеств из Р на любую (іі — I)-мерную
10
плоскость, то можно так удалить р — q множеств из Р, что семейство, которое осталось, будет иметь I-трансверсаль.
В §7 приводятся обобщения классических теорем Грюнбаума и Шни-рельмана - Сантало (см. [5], с. 62 - 63) о трансверсали.
Теорема 1.7.1 [26]. Пусть R = {тг,}»е/ семейство в JRr* (С”) различных параллельных (п — т)-мерных плоскостей и Rrt(C" ) = aflf U>,_/ 77і> а Р = {К’}*€/ таі<ОЄ семейство выпуклых компактов, ЧТО V{ С 7Гі для всех
і є і.
lorда, если для всех подсемейств Q С Р, |Q| < (n — m)(m + 1) H- 1 существует m - трансв ер саль, то она существует у всего семеііства. Р.
Теорема Грюнбаума и Шнирельмана - Сантало (см. [5], с. 63) следует из теоремы 1.7.1 при m = 1 и m = п — 1, соответственно. Эта теорема является некоторым ответом на вопрос из [6], с. 414, об обобщении теоремы Грюнбаума - Шнирельмана - Сантало при 1 < ш < n — 1.
Следующий результат получается прямо из теоремы 1/2.2.
Теорема 1.7.2. Пусть R = {я\},-€/ такое семейство в Rn (С") различных параллельных (гг ~ т)-мерных плоскостей, что К" (С") = aff Uiç/ кі 11 Pj = {Vji}i<zr, 1 < j < k < n — m, такие семейства выпуклых компактов, что Vji С 7Гі для всех г € I и 1 < j < к.
Тогда, если для любого подсемейства Q Ç Pj, |Q| < (n — m)(m 4-1) — к + 2 u всех j, 1 < j < к, существует m-трансверсаль, то существует (к—I)-мернаяплоскость 11 в пространстве £(Lq , Lq) такая, что для любого Vji, і Є I и j, 1 < j < к существует такое / € П, что f(x) € Vj,, х Є Lq.
Легко видеть, что л і П U/єн / — (& “ 1)-мерная плоскость для всех
і. Поэтому, если к > n — m — теорема тривиальна. Также легко видеть, что 7г; П (J/еП gr / — алгебраическая (к + m — 1)-мерная поверхность в IR".
В конце параграфа приводится аналоги этих результатов для обобщенных трансворсалей.
Глава II (§1 - §6) посвящена геометрическим приложениям теоремы
1.2,2. Так как из теоремы 1.2.2 следуют теорема Хелли и теорема Борсука - Улама, то ее можно применять в тех же случаях, что и эти теоремы. Она позволяет как бы ’’интерполировать’' результаты в том смысле, что если какая-то теорема доказывается с помощью теоремы Хелли, а похожая теорема с помощью теоремы Борсука - Улама, то можно получить и теоремы, ”промежуточные” между этими двумя. Будет дан пример такого результата. Будут также приведены результаты, которые получаются
11
из теоремы 1.2.2 путем “экстраполяции" классических следствий теоремы Хеллп (подобные результаты, доказываемые с помощью теоремы Борсука - Улама, не были ранее отмечены).
В параграфе §1 приводятся обобщения и уточнения классических теорем об отделимости выпуклых множеств и Хелли (см. [5, 35]). Следующий результат — основной в §1 и включает в себя, как теорему Хеллп так и теорему об отделимости выпуклых множеств. Его доказательство основано на теореме 1.2.2.
Теорема 2.1.4 [12, 26]. Если для семейства Р выпуклых компактов в Е”. имеем, Р ( II, то существует такое Ро = {К'}і<г<* С Р. 2 < К «. +1. и такое семейство замкнутых полупространств Я = {М,-}і<і<* £ П. что
где — (к — 1 )-мерный открытый симплекс, а Ее Ст”_к+].
Бели семейство Р состоит из двух элементов, то получаем из теоремы
2.1.4 теорему об отделимости выпуклых множеств.
Если для семейства Р = {Уі}ієі выпуклых компактных множеств в Е/? существует такое семейство замкнутых полупространств Я = { А/, } /, что У{ С Мі и Я £ П, то семейство Р называется отделимым по Гейлу
Из теоремы 2.1.4 сразу следуют результаты В. Кли (V. Klee) (см. [5], с. 47), Ф. Леви (F.W. Levi) (см. [5], с. 50) и М. Брин (М. Breen) [37], а если еще применить теорему 1.2.2. то эти результаты можно и "проэкс-траполировать”. Приведем для примера обобщение результата М.Брин [37], который в свою очередь обобщает теорему Хелли.
Бели и и V — точки множества V С Мп, то выражение ”и видна из v в множестве V” означает, что отрезок [«, v] С V. Множество называется звездным, если в V есть точка, из которой видны все остальные.
Для формулировки теоремы рассмотрим т таких семейств Р,-, что каждое состоит из (п — т + 1)-квазивыпуклых компактов, лежащих в Rrl или Сп и |Pt| > п — m 4- 2, 1 < г < т, т < п. Тогда верна
Теорема 2.1.6 [26]. Если для всех L Є , для всех г я для всех
подсемейств S С Pi, |5| < п — m + 2 множество L(V$) = Uves L(V), — звездно, то семейство Р = Ufej ft имеет (m — 1)-трансверсоль.
Аналогично, используя теорему 2.1.4 и результаты ігз §4 главы I легко доказать следующее ее обобщение.
к
(D. Gale) (см. [36]).
12
Теорема 2.1.8 [10, 12. 26]. Семейство компактов Р в R" L-раз делимо тогда и только тогда, когда существуют такие множества V* Є Р и функции fi € L, что Vi С P{fi) и IXі P(fi) = 0, 1 < г < m < N.
Результаты §2 имеет в основном вспомогательный характер. В нем приводятся обобщения и уточнения классических теорем Каратеодори (С. Carat heo dory), Кирхбергера (P. Kirchberger) (см. [5], с. 34) и Р. Радо (К. Rado) [38], а также теоремы Д. Уотсона (D. Watson) [39]. Приведем основной результат параграфа в наиболее общей форме .
Теорема 2.2.8 [10, 12, 26, 27, 40]. Если Р = {VJ}i<*<fc — L-неразделимое. семейство компактов в К”, то существует такое L-неразделимое семейство конечных подмножеств fV/}i<i<fc, ЧТО V( С Vi и Хд=1 \у;\ < (k-l)N + l.
Если положить L = S{EU), то в качестве следствия из теоремы 2.2.8 получаем результат S.R. Lay из [41] об отделимости сферами.
Следствие 2.2.10. Пусть в К" даны два конечных множества V\ и Vo- Если для любых таких непустых V/ С \\ и У£ С V2, что \V{\ + |V.[| < п 4- 3, существует такая сфера, что одно из множеств {, Vo} лежит внутри сферы, а другое снаружи, то существует такая сфера, что одно из множеств {\\, V2} лежит внутри сферы, а другое снаружи.
В §3 приведены различные варианты теоремы Хелли для некомпактных множеств. Известно, что теорема Хелли, неверна для произвольного бесконечного семейства выпуклых множеств. В §3 даны необходимые и достаточные условия непустоты пересечения бесконечного семейства замкнутых выпуклых множеств [42]. Из результатов параграфа следует известная теорема П. Рокафеллара (Р.Т. Rockafeilar) [35, с. 207 - 210].
В §4 приведены различные обобщения теоремы классической теоремы о трансверсалях, полученной А. Хорном (A. Horn) и В. Клн (см. [5], с. 46), где этот результат назван единственным по настоящему содержательным обобщением теоремы Хелли, связанным с существованием общих транс-версалей. Эта теорема является весьма частным случаем теоремы 1.2.2. Основным результат этого параграфа является следующая теорема.
Теорема 2.4.1 [12. 2G, 27]. Если в каждом семействе {Р,}к,<л-, к < m < п, (п — гп + 1 )-квазивыпуклых компактов в Rn (С") любые < n — m + 2 множеств Р{' -неразделимы, то:
(1) каждая (т - к — 1)-мерная плоскость в Еп (Сп) принадлежит (m — 1)-трансверсалп семейства Р = |J*=i Р%1
13
(2) для всех (т — к — I)-мерных подпространств L в IRn (Cu) существует [m — 1 )-трансвсрсаль семейства Р = U£Li Pit параллельная L.
Следствие 2.4.2. Для целых 0 < m < п и такого семейства Р, что оно состоит из (п—гп-\-\)-квазивыпук.пых компактов в Rn и |Р| > n — m+1, следующие три утверждения эквивалентны:
(1) каждые n — m + 1 множеств семейства Р Р{1 -неразделимы;
(2) любая (m — I)-мерная плоскость в Шп лежит в некоторой m - трансверса-ли семейства Р;
(3) для всех m-мерных подпространств L в R” существует m-транс всрсаль семейства Р параллельная L.
Этот результат обобщает теорему Хорна - Кли на квазивыпуклые множества, а следующий обобщает эту теорему для (m, £)-трансверсалей.
Пусть L — линейное N-мерное пространство функций на К", которое содержит константы и образ любого компактного множества при отображении Веронезе является компактом.
Теорема 2.4.3. Для целых га, 0 < m < N — 1 и семейства Р, \Р\ > I = N — m, компактов в Шп. следующие три утверждения эквивалентны:
(1) каждые I множеств семейства Р L-неразделимы;
(2) каждое l-мерное подпространство в L лежит в (т. Ь)-трансверсалп семейства Р;
(3) каждое такое I-мерное подпространство Lq С L, что е Є L0, содержит (т, Ь)-трансверсаль семейства Р.
В §5 приводится пример ’’интерполяции” двух результатов с помощью теоремы 1.2.2 и в качестве примера рассматриваются ряд задач, группирующихся вокруг ”теоремы о бутерброде” Улама - Штейнгауза (H. Steinhaus) и теоремы о делении мер Неймана (В.II. Neumann) - Радо (см. [43, с. 22) и [5, с. 31) ). В доказательстве первой теоремы применяется теорема Борсука - Улама, а второй — теорема Хелли.
Задачам на деление множеств и мер в Шп одной или несколькими гиперплоскостями и связанным с ними задачам о мерах симметрии выпуклых тел посвящено много работ различных авторов (см., например, обзор [43]).
Если Р(Ь) — такое аддитивное семейство множеств в R", что Р{{) Є P(L) для всех / Є L, то зарядом. // на семействе Р{Ь) назовем полуад-дитивную и монотонную функцию множеств, определенную на P(L), т.е. p(V U W) < /і(V) + p(W) для VyW Є P(L) и p(V) < p(W) для V Ç W. Легко привести примеры зарядов, беря различные меры или емкости или, что менее традиционно. — ранговую функцию матроида.
14
Заряд р назовем (/?, L)-ограниченным, R > О, если для всех таких / € L, что p(P(f)) < существует такое множество А'(/) Ç Р(—/), что
t>j,(Â"(/)) ограничено и ^‘(Р(/;)) < ^ для всех таких }' Е L, что P(f) П А(/) = 0. Легко видеть, что если V имеет конечную меру Лебега или заряд сосредоточен на ограниченном множестве, то равенство =
mes(P{f)C\V) определяет заряд, являющийся (R, 1)-ограниченным для всех R относительно Р'\
Сформулированные ниже результаты, для ограниченных измеримых по Лебегу множеств и L = Р", одновременно получили R.T. Zivaljevic и S.T. Vrecica в [16].
Теоремы 2.5.1, 2.5.9 [44, 45, 46]. Если даны к зарядов /і;, определенных на аддитивных семействах множеств РДР"), 1 < і < к < п% и (п —к + 2)-ограниченных, то существует такая (к — 1)-мерная плоскость 7г, что для всех таких f Є Р", что Р(/) Э 7г, и для всех і верно неравенство
1М(Р(Л) > -~ТГ. 1 < i<k:
п — к + 2
Если даны к зарядов ц,, определенных на аддитивных семействах множеств Pi{L), 1 < і < к < N — 1, и (N — к + 1 )-ограниченных относительно L, то существует (N — к)-мерное подпространство Ьц С L, е £ Lq, а для всех f Е L и с> 0 верно неравенство
МР(/ + с))> 1 <* <*•
Из теоремы 2.5.1 следует при к = 1 результат Неймана - Радо, а при к = п и для непрерывных и аддитивных зарядов — ” теорема о бутерброде”. Многочисленные следствия теоремы 2.5.1 приведены в [46], где, в частности, обобщаются результаты из [47, 48]. Подобный же результат был получен для разбиения заряда полным флагом [46].
В §6 приведены некоторые примеры ” экстраполяции” с помощью теоремы 1.2.2. классических следствий теоремы Хелли. Следующий результат ”экстраполирует” теоремы P.Vincensini и В.Кли (см. [5], с. 25) и совпадает с ними при m = 1.
Для их формулировки рассмотрим выпуклый компакт Vq Е R" и га семейств Р\,...,РГП выпуклых множеств в R". Пусть все множества семейств Р\,..., Рт — компактны (или все семейства Р\,..., Р7П — конечны). Предположим также, что т < п и \Р;\ > п — т + 2, 1 < і < га; тогда верна
15
Теорема 2.6.1 [46]. Если в любом семействе Р; для всех подсемейств Q £= \Q\ < ” ” m + 2, существует такое х Є М", что xq + Vq: (1) пе-
ресекает все множества семейства Q; (2) или покрывает все множества семейства Q; (3) или содержится во всех множествах семейства Q, то существует такая (гп — Ї)-мерная плоскость тг, что для всех V Є Р = Ui=i имеем: (1) (Vo + *) П V' ф 0; (2) (JVeP V С (V0 + л-); (3) Vo + * С V для некоторого X Єя.
Приводимый ниже результаты обобщает классическую теорему Мин-ковского (Н. Minkovski) - Радона (J. Radon) о мерах симметрии, которые рассмотрели случай m = 1 (см., например, [5], с. 30 или [43], с. 30).
Теорема 2.6.3(12, 26]. Если Vi,..., Vm, m < n, — выпуклые компакты в Rn, то существует такая (m — 1)-мерная плоскость тг и точка z Є л1-, что для каждой, проходящей через z хорды [и у v] множествах 1 (Vi), имеем,
Ik ~ wll ^ n — m +1
Це - н|| — n — m + 2 ’
Известно, что для любой хорды [u,t>], проходящей через центр тяжести л выпуклого компакта V, верно неравенство \\z — u||/||u — и\\ < n/(n + l). Таким образом, теорема 2.6.3 следует также из теоремы 1.1.2.
Приведем данеє обобщение классической теоремы М.А. Красносельского о звездных множествах (см., например, [5], стр. 27).
Теорема 2.6.5 [12, 26]. Пусть V],...,Vm, m < л. — бесконечные компакты в!" и для всех г, 1 < г < ш, и всех V С V). |1'| < n — m + 2, существует точка ху Є Vi, из которой видны все точки V. Тогда существует такая (m— 1)-мерная плоскость тг, что множество (JI=i ^ ‘— звездно относительно 7Г.
Глава III (§1 - §6) посвящена приложениям теоремы Хелли, которые концентрируются вокруг теоремы Г. Юнга (H.W. Jung).
В §1 изучается следующий вопрос: при каких метрических условиях произвольные непустые множества V и W (не обязательно выпуклые) в метрическом векторном пространстве L над полем Ш являются /•'"-отделимыми. Легко видеть, что если расстояние между V и W велико по сравнению с их диаметрами, то их можно отделить гиперплоскостью. Какое соотношение между диаметрами Г, IV и расстоянием между ними гарантирует отделимость?
16
Вопрос об отделимости имеет важное значение в различных областях математики, например, в выпуклой геометрии и выпуклом анализе [35], в теории приближения функций [49] и в теории распознавания образов. В частности, следствием результатов параграфа будет классическая теорема Г. Юнга в евклидовом пространстве (см. [5], с. 29).
Пусть д(х,у) — билинейная форма в £, d2(x,y) — д(х — у, х — у) и
dl(V,W)= т{ d2(x,y), bl(V,W)= sup <P(x,y), iSV.yeH" J xev.yew
_ J SUPх,у€У,хфу^2(х,у), \V\ > 2,
s I d2g(V) = 0, \V\ = 1,
c2/y\ f 'm^r-v€V,x&yid (x.y), |V| > 2,
' I *j|(V) = 0, \v\ = 1,
S2g(W, V) = sup inf d2(x, y), D](Wi V) = mn.x{Sg(W, V)J](V, W)},
d(di,d2,k,l) = ^ di -I—d-2
и
d(dl,d‘2, п) = шах d(d^,d2,k,n+ 2 — к).
1<&<п+1
Если £ — евклидово пространство, то dg(V) — диаметр, а <5д(У) -минидиаметр множества V (см. [50]); 50(\¥,У) — уклонение множества V от множества И7, а £^(И7, V) — хаусдорфово расстояние между множествами IV и V (см., например. [43]).
Теорема 3.1.2, 3.1.3, 3.1.4 [26, 51, 52]. ЕслиУ, V/ С £ и: (1 )<Рд{У) > 0, <§(№))>(), (2)<Рд(У,\У) > k(d2(У) + d2(W)), то со V П со IV = 0
Если сНш £ = п и для любых х 6 V и у Е И7 верно неравенство (1) и неравенство (3) д?(х,у) > d{d2{V), о^(И7), п), то со V П со И7 = 0 .
Если V п IV - компакты, то их можно отделить.
Если V и И7 С Еп> то их можно отделить и верно неравенство
(4) ^(со V,со IV) > \У) - d(d2g(V),d2(W). п - 1) >
>а(ё2д(уи2д№),п)-а(й2д(У),й2д(цг).п-\)>().
Если £ — евклидово пространство и для V, И7 С £ верно (2), то для всех хо € со V7 и у о € со И7, имеем,
(5) 4,2(х0,у0) > й](У,\У) - \(й](У) +d2g(W)) > 0.
17
Если
(б) dl(V,W)>1-(dl(V) + d29(W)),
то существует такой непрерывный линейный функционал ip и такое с € R. что гиперплоскость р(х) = с разделяет множества V и W.
Существуют такие множества V и W в Еп, что V П W = 0 и
d](V, W) = d(d2g(V),d2g(W),n), со V' П со W ф 0.
В бесконечномерном евклидовом пространстве L существуют такие множества V и W > что
d?g(V,W) = \(d2g(V) + d]{W))> О,
В конце параграфа приводится метрический критерий отделимости гиперплоскостями для произвольного конечного семейства множеств (отделимость по Гейлу).
Метрическая теорема отделимости 3.1.3 была обобщена в [53] на Лебеговы пространства Ьр и их конечномерный аналог I” (оо > р > 1), т.е. Rn с нормой
\\*\\р = Х>т-i=i
В §2 даны приложения теорем о метрической отделимости §1 и будут изучаться задачи родственные теореме Юнга, а также в некотором смысле двойственные к задачам §1.
Если в §1 устанавливались неравенства между диаметрами множеств и минимальным расстояниям между ними, то в этом параграфе будут устанавливаться также неравенства между минидиаметрами множеств и максимальным расстоянием между ними.
Результаты этого параграфа являются обобщениями известных теорем Г. Юнга. Г. Блихфельдта (H.F. Blichfeldt), К. Шютте (К. Shiitte) и
В. Ранкина (R.A. Rankin). Следующая теорема является обобщением теоремы Г. Юнга.
Теорема 3.2.2 [26. 52]. Если V С L и 0 < dJ(V), то 82(V,caV) <
W)-
Если dim L = ту то 82(\у со V) < d2g(V) • J2, где J„ =
Также можно получить оценку для хаусдорфова. расстояния между V и 14 — множеством всех выпуклых комбинаций < к точек из V и аналогичные оценки в пространстве
п
2(п -Ь 1) ’
18