Теория Морса минимальных сетей, страница 9

Обобщенным числом Стирлинга 2-ого рода ℎ (, ) будем называть количество способов разбить -множество на подмножеств мощности не менее ℎ. Естественно предполагать, что ≥ ℎ.Таким образом, (, ) = 2 ( + − 2, ).В наших обозначениях классические числа Стирлинга 2-ого рода равны 1 (, ). Для чисел 1 (, ) имеются различные способы их вычисления, см. [9], как с помощью рекуррентных соотношений(, ) = ( − 1, ) + ( − 1, − 1),так и в явном виде(−1) ∑︁(−1) .(, ) =! =0Поэтому далее мы выразим требуемые нам числа (, ) = 2 (+−2, )через классические числа Стирлинга 2-ого рода.Предложение 1.2 При > имеет место формула−1∑︁ 2 ( − , − ) = 1 (, ).=0Доказательство.

Легко увидеть, что количество разбиений -множества на подмножеств, из которых одноэлементные, равно 2 ( −, − ). В самом деле, количество способов выбрать одноэлементныхподмножеств -множества равно . Оставшееся ( − )-множество нужноразбить на − множеств мощности не менее 2; количество способовсделать это равно по определению 2 ( − , − ). Суммируя теперь по от 0 до − 1, получаем требуемую формулу. Выражение чисел (, ) через классические Стирлинга 2-огородаПоложив в предложении 1.2 = + − 2 и = , и учитывая, что(, ) = 2 ( + − 2, ), получаем следствиеСети в метрических пространствах44Следствие 1.1 Числа (, ) связаны между собой следующим набором соотношений−1∑︁+−2(, − ) = 1 ( + − 2, ), = 1, . . . , − 2.(1.2)=0Соотношения (1.2) позволяют последовательно рекуррентным образом вычислять при фиксированном все числа (, ), = 1, .

. . , − 2,начиная с (, 1).Перепишем соотношения (1.2) в матричном виде⎛⎞−3 ⎞ ⎛1. . . . . . . . . . . . . . . 2(−2)1 2(−2)(, − 2)⎜. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎟ ⎜⎟···⎜⎟⎜⎟−1 ⎟ ⎜1⎜0...1 +−2 . . . +−2 ⎟ ⎜ (, ) ⎟⎜⎟=⎝. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎠ ⎝⎠···0 . . . . . . . . . . . . . .⎛. . . . . . . . .1⎞ (, 1)1 (2( − 2), − 2)⎜⎟···⎜⎟⎟=⎜⎜ 1 ( + − 2, ) ⎟⎝⎠···1 ( − 1, 1)Для того, чтобы выразить числа (, ) через классические числа Стирлинга 2-ого рода, нужно обратить это равенство.Лемма 1.7 Имеет место равенство−3 ⎞−111 2(−2). . . . . . . . . . . . .

. . 2(−2)⎜. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎟⎟⎜−1 ⎟1⎜0=...1...+−2+−2 ⎟⎜⎝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎠1⎛ 0 . 1. . . . . . . . . . . . . . . . . . . . . .−3 ⎞1 −2(−2) . . . .

. . . . . . . . . . . . (−1)−3 2(−2)⎜. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎟⎜⎟−1 ⎟1=⎜...1 −+−2. . . (−1)−1 +−2⎜0⎟.⎝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎠0 ...........................1⎛Сети в метрических пространствах45Доказательство. Доказательство получается прямой проверкой определения обратной матрицы с использованием при = + − 2 и = тождества∑︁−(−1) −= 0,которое является частным случаем более общего тождества, см.

[18],∑︁− − = (1 + ) .Используя матричный вид соотношений (1.2) и лемму 1.7, получаемтеоремуТеорема 1.1 Числа (, ) могут быть выражены через классическиечисла Стирлинга 1 (·, ·) 2-ого рода следующим образом(, ) =−1∑︁(−1) +−21 ( + − 2 − , − ).=0Значения чисел (, ) при некоторых и ∖34567891033.11 234567811 31 10151 251051051 5649012609451 119 1918945017325103951 246 6825 56980 190575 270270 1351351 501 22935 302995 1636635 4099095 4729725 2027025Конфигурационное пространство всехрегулярных сетей с данной границейПостроение пространства и функции ℓПусть (, ) — некоторое метрическое пространство и = { }=1 —фиксированная граница в пространстве .

Напомним, см. п.2) раздел 3Сети в метрических пространствах46Введения, что мы рассматриваем сети, затягивающие границу , типкоторых определяется некоторым геометрическим деревом из множества . Для того, чтобы имело смысл рассматривать сети всех типов измножества , мы будем предполагать, что метрическое пространство состоит из не менее, чем − 2 точек.Рассмотримпространство ˜ , представляющее собой несвязную сум⨆︀му ˜ =[].

Пространства [] будем рассматривать как подмножества∈этой суммы. Зададим теперь на пространстве ˜ отношение эквивалентности следующим образом.Определение. Две точки (сети) Γ1 ∈ [1 ] и Γ2 ∈ [2 ] будем считатьэквивалентными, если и только если, проредуцировав их по всем внутренним вырожденным ребрам, мы получим одну и ту же сеть.Построим теперь фактор-пространство = ˜ /∼, где ∼ — описаннаявыше эквивалентность. Через обозначим стандартную проекцию ˜ нафактор-пространство .Пространство состоит из всех классов эквивалентности по отношению ∼. Опишем теперь как устроены эти классы.

Пусть ϒ — классэквивалентности сети Γ, тогда ϒ состоит из всех сетей, получающихсяиз сети Γ некоторой комбинацией расщеплений ее подвижных вершин иредукций по ее вырожденным внутренним ребрам. Любую сеть из классаэквивалентности ϒ назовем представителем данного класса. Заметим,что поскольку операции редукции и расщепления сохраняют длину сети,то все сети из одного класса эквивалентности имеют одинаковую длину.Следовательно, на пространстве корректно определена функция длины ℓ.В каждом классе эквивалентности существует и единственна сеть(представитель), которая является регулярной сетью.

Такую сеть мы назовем регулярным представителем данного класса. Очевидно, что любая регулярная сеть с границей является регулярным представителем некоторого класса эквивалентности. Таким образом, имеется взаимнооднозначное соответствие между регулярными сетями с границей и классами эквивалентности. Это соответствие мотивирует следующееопределение.Определение. Пространство назовем конфигурационным пространством всех регулярных сетей с данной границей.Сети в метрических пространствах47В дальнейшем, если не оговорено противное, элементы (классы эквивалентности) пространства будут рассматриваться как регулярныесети с данной границей.3.2Стратификация пространства Поскольку проекция : ˜ → две различные сети Γ1 и Γ2 , принадлежащие пространству [], переводит в различные регулярные сети изпространства , то мы имеем вложение пространства [] в пространство .

Образ пространства[] при этом вложении обозначим через ⟨⟩. Яс⋃︀но, что =⟨⟩.∈Лемма 1.8 Отношение 1 ≥ 2 имеет место тогда и только тогда,когда имеет место включение ⟨1 ⟩ ⊂ ⟨2 ⟩.Доказательство. Пусть выполняется отношение 1 ≥ 2 . Возьмемкакую-нибудь регулярную сеть Γ ∈ ⟨1 ⟩. Тип сети Γ, вообще говоря,может отличаться от 1 . Рассмотрим ее класс эквивалентности −1 (Γ).В этом классе эквивалентности возьмем сеть Γ1 ∈ [1 ]. Поскольку дерево 1 больше дерева 2 , то можно сделать расщепления подвижныхвершин сети Γ1 так, что сеть Γ1 превратится в некоторую сеть Γ2 из [2 ],эквивалентную сети Γ1 . Таким образом, класс −1 (Γ) содержит сеть из[2 ], и, следовательно, Γ ∈ ⟨2 ⟩.Пусть теперь имеет место включение ⟨1 ⟩ ⊂ ⟨2 ⟩. Возьмем какуюнибудь регулярную сеть Γ1 ∈ ⟨1 ⟩.

Поскольку мы предполагаем, что|| ≥ − 2, то сеть Γ1 можно выбрать так, чтобы тип сети Γ1 совпадалс 1 . Тогда, в силу включения ⟨1 ⟩ ⊂ ⟨2 ⟩, в классе эквивалентностиϒ1 = −1 (Γ1 ) содержится некоторая сеть Γ2 ∈ [2 ]. Поскольку регулярная сеть Γ1 является регулярным представителем класса ϒ1 , то еепараметризующее дерево 1 не меньше, чем параметризующее дереволюбой другой сети из класса ϒ1 , в частности, — сети Γ2 . Таким образом,1 ≥ 2 . Поскольку любое геометрическое дерево ′ ∈ имеет некоторогопотомка среди бинарных геометрических деревьев (−3) , т.е.

′ ≥ ,то получаем следствие.Сети в метрических пространствах48Следствие 1.2 =⋃︁⟨⟩.∈(−3)Определение. Множество ⟨⟩, соответствующее бинарному дереву ∈ (−3) , будем называть листом пространства . Конечное пересечение листов пространства назовем стратом.Лемма 1.9 Пусть нам дан набор геометрических деревьев 1 ,. . .

, .Обозначим через их общего родителя. Тогда пересечение ⟨1 ⟩ ∩ · · · ∩⟨ ⟩ совпадает с множеством ⟨⟩.Доказательство. Нужно доказать два включения⟨1 ⟩ ∩ · · · ∩ ⟨ ⟩ ⊂ ⟨⟩и⟨1 ⟩ ∩ · · · ∩ ⟨ ⟩ ⊃ ⟨⟩.Поскольку ≥ , = 1, . . . , , то второе включение следует из леммы 1.8. Докажем первое включение ⟨1 ⟩ ∩ · · · ∩ ⟨ ⟩ ⊂ ⟨⟩. Рассмотрим˜ еекакую-нибудь регулярную сеть Γ̃ ∈ ⟨1 ⟩∩· · ·∩⟨ ⟩; обозначим через −1тип. Тогда класс эквивалентности ϒ̃ = (Γ̃) содержит эквивалентныесети Γ ∈ [ ], = 1, . . . , . Поскольку сеть Γ̃ является регулярным пред˜ ≥ , = 1, . . . , , и, следовательно, ˜ ≥ .ставителем класса ϒ̃, то ˜ ⊂ ⟨⟩. СледоваНо тогда, в силу леммы 1.8, имеет место включение ⟨⟩тельно, регулярная сеть Γ̃ содержится в множестве ⟨⟩.

Таким образом,первое включение доказано. Утверждение 1.3 Набор стратов пространства совпадает с набором множеств {⟨⟩ : ∈ }.Доказательство. Взяв в лемме 1.9 в качестве деревьев 1 ,. . . , произвольные бинарные деревья, получаем, что каждый страт совпадает снекоторым множеством ⟨⟩.Обратно. Пусть ∈ — некоторое геометрическое дерево. Рассмотрим все бинарные геометрические деревья 1 ,. . . , , которые меньше дерева . Тогда является общим родителем для набора деревьев 1 ,.

. . , , и, по лемме 1.9, пространство ⟨⟩ совпадает со стратом⟨1 ⟩ ∩ · · · ∩ ⟨ ⟩. Сети в метрических пространствах49Фактически все страты пространства перечисляются геометрическими деревьями.Пусть Γ — некоторая регулярная сеть. Наименьший по включениюстрат, содержащий сеть Γ, назовем минимальным стратом для сети Γ.Лемма 1.10 Невырожденная сеть Γ ∈ имеет тип тогда и только тогда, когда страт ⟨⟩ является минимальным стратом для сетиΓ.Доказательство. Пусть регулярная сеть Γ имеет тип . Тогда страт⟨⟩ содержит сеть Γ.

Рассмотрим еще какой-нибудь страт ⟨′ ⟩, содержащий сеть Γ. Принадлежность сети Γ страту ⟨′ ⟩ означает, что в классеэквивалентности ϒ = −1 (Γ) существует представитель Γ′ типа ′ . Поскольку сеть Γ является регулярным представителем класса ϒ, то ее тип не меньше типа ′ . Следовательно, по лемме 1.8, имеет место включение ⟨⟩ ⊂ ⟨′ ⟩. Таким образом, ⟨⟩ — минимальный страт для сетиΓ.Пусть ⟨⟩ — минимальный страт для регулярной сети Γ. Обозначимчерез ′ тип сети Γ.