Дискретная теория Морса

редактировать

Дискретная теория Морса представляет собой комбинаторную адаптацию Теория Морса разработана. Теория имеет различные практические приложения в различных областях прикладной математики и информатики, таких как конфигурационные пространства, вычисления гомологии, шумоподавление, сжатие сетки и анализ топологических данных.

Содержание

1 Обозначения, касающиеся комплексов CW
2 Дискретные функции Морзе
3 Комплекс Морзе
4 Основные результаты
- 4.1 Неравенства Морса
- 4.2 Дискретные гомологии Морса и тип гомотопии
5 См. Также
6 Ссылки

Обозначения, касающиеся комплексов CW

Пусть $X {\ displaystyle X}$ $X$ быть комплексом CW и обозначать $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ его набор ячеек. Определите функцию инцидентности $κ: X × X → Z {\ displaystyle \ kappa: {\ mathcal {X}} \ times {\ mathcal {X}} \ to \ mathbb {Z}}$ $\ kappa: {\ mathcal {X}} \ times {\ mathcal {X}} \ to {\ mathbb {Z}}$ следующим образом: заданы две ячейки $σ {\ displaystyle \ sigma}$ $\ sigma$ и $τ {\ displaystyle \ tau}$ $\ tau$ в $X {\ displaystyle { \ mathcal {X}}}$ ${\ mathcal {X}}$ , пусть $κ (σ, τ) {\ displaystyle \ kappa (\ sigma, ~ \ tau)}$ $\ kappa (\ sigma, ~ \ tau)$ будет степенью из прикрепляемой карты от границы $σ {\ displaystyle \ sigma}$ $\ sigma$ до $τ {\ displaystyle \ tau}$ $\ tau$ . граничный оператор - это эндоморфизм $∂ {\ displaystyle \ partial}$ $\ partial$ свободной абелевой группы, порожденной $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ определяется как

∂ (σ) = ∑ τ ∈ X κ (σ, τ) τ. {\ displaystyle \ partial (\ sigma) = \ sum _ {\ tau \ in {\ mathcal {X}}} \ kappa (\ sigma, \ tau) \ tau.}

{\ displaystyle \ partial (\ sigma) = \ sum _ {\ tau \ in {\ mathcal {X}}} \ kappa (\ sigma, \ tau) \ tau.}

Это определяющее свойство граничных операторов что $∂ ∘ ∂ ≡ 0 {\ displaystyle \ partial \ circ \ partial \ Equiv 0}$ $\ partial \ circ \ partial \ эквив 0$ . В более аксиоматических определениях можно найти требование, чтобы $∀ σ, τ ′ ∈ X {\ displaystyle \ forall \ sigma, \ tau ^ {\ prime} \ in {\ mathcal {X}}}$ $\ forall \ sigma, \ tau ^ {{\ prime}} \ in {\ mathcal {X}}$

∑ τ ∈ Икс κ (σ, τ) κ (τ, τ ′) знак равно 0 {\ Displaystyle \ sum _ {\ tau \ in {\ mathcal {X}}} \ kappa (\ sigma, \ tau) \ kappa (\ tau, \ tau ^ {\ prime}) = 0}

\ sum _ {{ \ tau \ in {\ mathcal {X}}}} \ kappa (\ sigma, \ tau) \ kappa (\ tau, \ tau ^ {{\ prime}}) = 0

, что является следствием приведенного выше определения граничного оператора и требования, чтобы $∂ ∘ ∂ ≡ 0 {\ displaystyle \ partial \ circ \ partial \ Equiv 0}$ $\ partial \ circ \ partial \ эквив 0$ .

Дискретные функции Морса

A вещественная -значная функция $μ: X → R {\ displaystyle \ mu: {\ mathcal {X}} \ to \ mathbb {R}}$ $\ mu: {\ mathcal {X}} \ to {\ mathbb {R}}$ является дискретной функцией Морса, если она удовлетворяет следующим двум свойствам:

Для любой ячейки $σ ∈ X {\ displaystyle \ sigma \ in {\ mathcal {X}}}$ $\ sigma \ в {\ mathcal {X}}$ , количество ячеек $τ ∈ X {\ displaystyle \ tau \ in {\ mathcal {X}}}$ $\ tau \ in {\ mathcal {X}}$ в границе $σ {\ displaystyle \ sigma}$ $\ sigma$ которые удовлетворяют $μ (σ) ≤ μ (τ) {\ displaystyle \ mu (\ sigma) \ leq \ mu (\ tau)}$ $\ mu (\ sigma) \ leq \ mu (\ tau)$ не более один.
Для любой ячейки $σ ∈ X {\ displaystyle \ sigma \ in {\ mathcal {X}}}$ $\ sigma \ в {\ mathcal {X}}$ количество ячеек $τ ∈ X { \ displaystyle \ tau \ in {\ mathcal {X}}}$ $\ tau \ in {\ mathcal {X}}$ , содержащие $σ {\ displaystyle \ sigma}$ $\ sigma$ в своих границах, которые удовлетворяют $μ (σ) ≥ μ (τ) {\ displaystyle \ mu (\ sigma) \ geq \ mu (\ tau)}$ $\ mu (\ sigma) \ geq \ mu (\ tau)$ не более одного.

Можно показать, что мощности в двух условиях не могут быть одновременно один одновременно для фиксированной ячейки $σ {\ displaystyle \ sigma}$ $\ sigma$ , при условии, что $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ является обычным CW сложный. В этом случае каждая ячейка $σ ∈ X {\ displaystyle \ sigma \ in {\ mathcal {X}}}$ $\ sigma \ в {\ mathcal {X}}$ может быть объединена не более чем с одной исключительной ячейкой $τ ∈ X {\ displaystyle \ tau \ in {\ mathcal {X}}}$ $\ tau \ in {\ mathcal {X}}$ : либо граничная ячейка с большим значением $μ {\ displaystyle \ mu}$ $\ mu$ , либо соседняя граничная ячейка с меньшим значением $μ {\ displaystyle \ mu}$ $\ mu$ . Ячейки, которые не имеют пар, т.е. чьи значения функций строго выше, чем их граничные ячейки и, строго ниже, чем их со-граничные ячейки, называются критическими ячейками. Таким образом, дискретная функция Морса разбивает комплекс CW на три различных набора ячеек: $X = A ⊔ K ⊔ Q {\ displaystyle {\ mathcal {X}} = {\ mathcal {A}} \ sqcup {\ mathcal { K}} \ sqcup {\ mathcal {Q}}}$ ${\ mathcal {X}} = {\ mathcal {A}} \ sqcup {\ mathcal {K}} \ sqcup {\ mathcal {Q}}$ , где:

$A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ обозначает критическое непарные ячейки,
$K {\ displaystyle {\ mathcal {K}}}$ ${\ mathcal {K}}$ обозначает ячейки, которые спарены с граничными ячейками, а
$Q {\ displaystyle {\ mathcal {Q }}}$ ${\ mathcal {Q}}$ обозначает ячейки, которые соединены с соседними ячейками.

По построению, существует биекция из устанавливает между $k { \ displaystyle k}$ $k$ -мерные ячейки в $K {\ displaystyle {\ mathcal {K}}}$ ${\ mathcal {K}}$ и $(k - 1) {\ displaystyle (k -1)}$ $(k-1)$ -мерные ячейки в $Q {\ displaystyle {\ mathcal {Q}}}$ ${\ mathcal {Q}}$ , которые можно обозначить как $pk: K k → Q k - 1 {\ displaystyle p ^ {k}: {\ mathcal {K}} ^ {k} \ to {\ mathcal {Q}} ^ {k-1}}$ $p ^ {k}: {\ mathcal {K}} ^ {k} \ to {\ mathcal {Q}} ^ {{k-1}}$ для каждого натуральное число $k {\ displaystyle k}$ $k$ . Дополнительным техническим требованием является то, что для каждого $K ∈ K k {\ displaystyle K \ in {\ mathcal {K}} ^ {k}}$ $K \ in {\ mathcal {K}} ^ {k}$ степень присоединения карты от границы из $K {\ displaystyle K}$ $K$ в свою парную ячейку $pk (K) ∈ Q {\ displaystyle p ^ {k} (K) \ in {\ mathcal {Q}}}$ $p ^ {k} (K) \ in {\ mathcal {Q}}$ - это единица в нижележащем кольце элемента $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ . Например, для целых чисел $Z {\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ единственными допустимыми значениями являются $± 1 {\ displaystyle \ pm 1}$ $\ pm 1$ . Это техническое требование гарантируется, например, если предположить, что $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ является обычным комплексом CW над $Z {\ displaystyle \ mathbb { Z}}$ $\ mathbb {Z}$ .

Фундаментальный результат дискретной теории Морса устанавливает, что комплекс CW $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ изоморфен на уровне гомологии с новым комплексом $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ , состоящим только из критических ячеек. Парные ячейки в $K {\ displaystyle {\ mathcal {K}}}$ ${\ mathcal {K}}$ и $Q {\ displaystyle {\ mathcal {Q}}}$ ${\ mathcal {Q}}$ описывают пути градиента. между соседними критическими ячейками, которые можно использовать для получения граничного оператора на $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ . Некоторые подробности этой конструкции представлены в следующем разделе.

Комплекс Морзе

Градиентный путь - это последовательность парных ячеек

ρ = (Q 1, K 1, Q 2, K 2,…, QM, KM) {\ displaystyle \ rho = (Q_ {1}, K_ {1}, Q_ {2}, K_ {2}, \ ldots, Q_ {M}, K_ {M})}

\ rho = ( Q_ {1}, K_ {1}, Q_ {2}, K_ {2}, \ ldots, Q_ {M}, K_ {M})

удовлетворяет $Q m = p (К м) {\ displaystyle Q_ {m} = p (K_ {m})}$ $Q_ {m} = p (K_ {m})$ и $κ (K m, Q m + 1) ≠ 0 {\ displaystyle \ kappa (K_ { m}, ~ Q_ {m + 1}) \ neq 0}$ $\ kappa (K_ {m}, ~ Q _ {{m + 1}}) \ neq 0$ . Индекс этого градиентного пути определяется как целое число

ν (ρ) = ∏ m = 1 M - 1 - κ (K m, Q m + 1) ∏ m = 1 M κ (K m, Q m) {\ displaystyle \ nu (\ rho) = {\ frac {\ prod _ {m = 1} ^ {M-1} - \ kappa (K_ {m}, Q_ {m + 1})} {\ prod _ {m = 1} ^ {M} \ kappa (K_ {m}, Q_ {m})}}}

{\ displaystyle \ nu (\ rho) = {\ frac {\ prod _ {m = 1} ^ {M-1} - \ kappa (K_ {m}, Q_ {m + 1})} {\ prod _ {m = 1} ^ {M} \ kappa (K_ {m}, Q_ {m})}}}

Деление здесь имеет смысл, поскольку частота встречаемости между парными ячейками должна быть $± 1 {\ displaystyle \ pm 1}$ $\ pm 1$ . Обратите внимание, что по конструкции значения дискретной функции Морзе $μ {\ displaystyle \ mu}$ $\ mu$ должны уменьшаться на $ρ {\ displaystyle \ rho}$ $\ rho$ . Путь $ρ {\ displaystyle \ rho}$ $\ rho$ , как говорят, соединяет две критические ячейки $A, A ′ ∈ A {\ displaystyle A, A '\ in {\ mathcal {A}} }$ $A,A'\in {\mathcal {A}}$ если $κ (A, Q 1) ≠ 0 ≠ κ (KM, A ′) {\ displaystyle \ kappa (A, Q_ {1}) \ neq 0 \ neq \ kappa (K_ {M}, A ')}$ $\kappa (A,Q_{1})\neq 0\neq \kappa (K_{M},A')$ . Это отношение может быть выражено как $A → ρ A '{\ displaystyle A {\ stackrel {\ rho} {\ to}} A'}$ $A{\stackrel {\rho }{\to }}A'$ . Кратность этой связи определяется как целое число $m (ρ) = κ (A, Q 1) ⋅ ν (ρ) ⋅ κ (KM, A ′) {\ displaystyle m (\ rho) = \ kappa (А, Q_ {1}) \ cdot \ nu (\ rho) \ cdot \ kappa (K_ {M}, A ')}$ $m(\rho)=\kappa (A,Q_{1})\cdot \nu (\rho)\cdot \kappa (K_{M},A')$ . Наконец, граничный оператор Морзе на критических ячейках $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ определяется как

Δ (A) = κ ( A, A ′) + ∑ A → ρ A ′ м (ρ) A ′ {\ Displaystyle \ Delta (A) = \ kappa (A, A ') + \ sum _ {A {\ stackrel {\ rho} {\ to}} A '} m (\ rho) A'}

\Delta (A)=\kappa (A,A')+\sum _{{A{\stackrel {\rho }{\to }}A'}}m(\rho)A'

, где сумма берется по всем соединениям пути градиента от $A {\ displaystyle A}$ $A$ до $A ′ { \ displaystyle A '}$ $A'$ .

Основные результаты

Многие из знакомых результатов непрерывной теории Морса применимы в дискретной обстановке.

Неравенства Морзе

Пусть $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ будет комплексом Морзе, связанным с комплексом CW $X {\ Displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ . Число $m q = | A q | {\ displaystyle m_ {q} = | {\ mathcal {A}} _ {q} |}$ $m_ {q} = | {\ mathca l {A}} _ {q} |$ из $q {\ displaystyle q}$ $q$ ячеек в $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ называется $qth {\ displaystyle q ^ {th}}$ $q^{th}$ числом Морса. Пусть $β q {\ displaystyle \ beta _ {q}}$ $\ beta _ {q}$ обозначает $qth {\ displaystyle q ^ {th}}$ $q^{th}$ число Бетти из $X {\ Displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ . Затем для любого $N>0 {\ displaystyle N>0}$ $N>0$ , выполняются следующие неравенства

m N ≥ β N {\ displaystyle m_ {N} \ geq \ beta _ {N}}

m_ {N} \ geq \ beta _ {N}

м N - м N - 1 +… ± м 0 ≥ β N - β N - 1 +… ± β 0 {\ displaystyle m_ {N} -m_ {N-1} + \ ldots \ pm m_ {0} \ geq \ beta _ {N} - \ beta _ {N-1} + \ ldots \ pm \ beta _ {0}}

m_ {N} -m _ {{N-1}} + \ ldots \ pm m_ {0} \ geq \ beta _ {N} - \ beta _ {{N-1}} + \ ldots \ pm \ beta _ {0}

Кроме того, характеристика Эйлера $χ (X) {\ displaystyle \ chi ({\ mathcal {X}})}$ $\ chi ({\ mathcal {X}})$ из $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ удовлетворяет

χ (Икс) знак равно м 0 - м 1 +… ± м тусклый ⁡ Икс {\ Displaystyle \ чи ({\ mathcal {X}}) = m_ {0} -m_ {1} + \ ldots \ pm m _ {\ dim {\ mathcal {X}}}}

\ chi ({\ mathcal {X}}) = m_ {0} -m_ {1} + \ ldots \ pm m _ {\ dim {\ mathcal {X}}}}

Дискретные гомологии Морса и гомотопический тип

Пусть $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ будет обычным CW комплекс с граничным оператором $∂ {\ displaystyle \ partial}$ $\ partial$ и дискретной функцией Морса $μ: X → R {\ display стиль \ mu: {\ mathcal {X}} \ to \ mathbb {R}}$ $\ mu: {\ mathcal {X}} \ to {\ mathbb {R}}$ . Пусть $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ будет ассоциированным комплексом Морзе с граничным оператором Морзе $Δ {\ displaystyle \ Delta}$ $\ Delta$ . Тогда существует изоморфизм групп гомологии

H ∗ (X, ∂) ≃ H ∗ (A, Δ), {\ displaystyle H _ {*} ({\ mathcal {X}}, \ partial) \ simeq H _ {*} ({\ mathcal {A}}, \ Delta),}

{\ displaystyle H _ {*} ({\ mathcal {X}}, \ partial) \ simeq H _ {*} ({\ mathcal {A}}, \ Delta),}

и аналогично для гомотопических групп.

См. Также

Ссылки

Forman, Robin (2002). «Руководство пользователя по дискретной теории Морзе» (PDF). Séminaire Lotharingien de Combinatoire. 48: Ст. B48c, 35 с. MR 1939695.
Козлов, Дмитрий (2007). Комбинаторная алгебраическая топология. Алгоритмы и вычисления в математике. 21 . Берлин: Springer. ISBN 978-3540719618. MR 2361455.
Йонссон, Якоб (2007). Симплициальные комплексы графов. Springer. ISBN 978-3540758587.
Орлик, Питер ; Велкер, Фолькмар (2007). Алгебраическая комбинаторика: лекции в летней школе в Нордфьордейде. Universitext. Springer. DOI : 10.1007 / 978-3-540-68376-6. ISBN 978-3540683759. MR 2322081.
«Дискретная теория Морса». nLab.