Dyskretne twierdzenie o punkcie stałym

W matematyce dyskretnej dyskretny punkt stały jest punktem stałym dla funkcji zdefiniowanych na skończonych zbiorach, zwykle podzbiorach siatki liczb całkowitych. ${\ Displaystyle \ mathbb {Z} ^ {n}}$ .

Dyskretne twierdzenia o punkcie stałym zostały opracowane przez Iimurę, Murotę i Tamurę, Chena i Denga oraz innych. Yang zapewnia ankietę.

Podstawowe koncepcje

Ciągłe twierdzenia o punkcie stałym często wymagają funkcji ciągłej . Ponieważ ciągłość nie ma znaczenia dla funkcji na zbiorach dyskretnych, jest zastępowana warunkami, takimi jak funkcja zachowująca kierunek . Takie warunki oznaczają, że funkcja nie zmienia się zbyt drastycznie podczas przemieszczania się między sąsiednimi punktami siatki liczb całkowitych. Istnieją różne warunki zachowania kierunku, w zależności od tego, czy sąsiednie punkty są uważane za punkty hipersześcianu (HGDP), simpleksu (SGDP) itp. Definicje można znaleźć na stronie poświęconej funkcji zachowania kierunku .

Ciągłe twierdzenia o punkcie stałym często wymagają zbioru wypukłego . Analogiem tej właściwości dla zbiorów dyskretnych jest zbiór całkowo-wypukły .

Dla funkcji na zbiorach dyskretnych

Skupiamy się na funkcjach $X$ jest niepustym podzbiorem przestrzeni euklidesowej $} ^{n}}$ $mathbb {$ . ch( X ) oznacza wypukłą otoczkę X .

Twierdzenie Iimura-Murota-Tamura : Jeśli X jest skończonym całkowo -wypukłym podzbiorem Z $\ Displaystyle \ mathbb {Z} ^ {n}}$ i ${\ Displaystyle f: X \ to {\text{ch}}(X)}$ jest hipersześcienną funkcją zachowującą kierunek (HDP) , wtedy f ma punkt stały.

Twierdzenie Chen-Denga : Jeśli X jest skończonym podzbiorem ${\ Displaystyle \ mathbb {R} ^ {n}}$ i ${\ Displaystyle f: X \ do {\ tekst {ch }}(X)}$ jest po prostu zachowujące kierunek (SDP) , wtedy f ma punkt stały.

Twierdzenia Yanga :

[3.6] Jeśli X jest skończonym całkowo wypukłym podzbiorem Z $\ Displaystyle \ mathbb {Z} ^ {n}}$ , ${\ Displaystyle f: X \ do \ mathbb {R} ^ { n}}$ jest po prostu zachowaniem kierunku brutto (SGDP) i dla wszystkich x w X istnieje jakieś g ( x )> 0 takie, że ${\ displaystyle x + g (x)f(x)\in {\text{ch}}(X)}$ , wtedy f ma punkt zerowy.
[3.7] Jeśli X jest skończonym $hipersześciennym$ podzbiorem $f: X \ do \mathbb {R} ^{n}}$ z minimalnym punktem a i maksymalnym punktem : X to SGDP i dla dowolnego x w X : ${\ Displaystyle f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\równoważnik 0}$ i ${\ Displaystyle f_ {i} (x_ {1}, \ ldots, x_ {i-1}, b_ {i}, x_{i+1},\ldots,x_{n})\geq 0}$ , wtedy f ma punkt zerowy. Jest to dyskretny odpowiednik twierdzenia Poincarégo – Mirandy . Jest to konsekwencja poprzedniego twierdzenia.
[3.8] Jeśli X jest skończonym całkowo -wypukłym podzbiorem Z $\ Displaystyle \ mathbb {Z} ^ {n}}$ i $)}$ ${\ Displaystyle f: X \ do {\ tekst { ch$ } } $wtedy$ takie, że , f ma punkt stały Jest to dyskretny odpowiednik twierdzenia Brouwera o punkcie stałym .
$^ {n}}$ Jeśli jest i $Z}$ ${\ Displaystyle f (x) -x}$ to SGDP, wtedy f ma punkt stały (wynika to łatwo z poprzedniego twierdzenia, biorąc X za podzbiór ${\ Displaystyle \ mathbb {Z } ^{n}}$ to ogranicza f ).
[3.10] Jeśli X jest skończonym całkowo wypukłym podzbiorem Z $\ Displaystyle \ mathbb {Z} ^ {n}}$ , ${\ Displaystyle F: X \ do 2 ^ {X}}$ a mapowanie punkt-zestaw i dla wszystkich x w X : ${\ Displaystyle F (x) = {\ tekst {ch}} (F (x)) \ cap \ mathbb {Z} ^ {n}}$ i istnieje funkcja f taka, że $)}$ ${\ Displaystyle f (x) \ in {\ tekst {ch}} ($ $($ i $y)}$ SGDP, to jest punkt y w X taki, że ${\ Displaystyle y \ w fa$ . Jest to dyskretny odpowiednik twierdzenia Kakutaniego o punkcie stałym , a funkcja f jest analogiem funkcji ciągłego wyboru .
[3.12] Załóżmy, że $X$ jest skończonym , całkowo-wypukłym podzbiorem , a także jest symetryczny tym sensie, że x jest w X - x jest w X . Jeśli $że$ jest słabo symetryczną triangulacją ch ( ) w tym sensie, jest na granica triangulacji iff - s jest ) i ${\ Displaystyle f (x) \ cdot f (-y) \ równoważnik 0}$ dla każdej pary prosto połączonych punktów x , y na granicy ch( X ), wtedy f ma punkt zerowy.
Więcej twierdzeń znajdziesz w ankiecie.

Dla funkcji nieciągłych na zbiorach ciągłych

Dyskretne twierdzenia o punkcie stałym są blisko spokrewnione z twierdzeniami o punkcie stałym na funkcjach nieciągłych. Te również używają warunku zachowania kierunku zamiast ciągłości.

Twierdzenie Heringsa-Laana-Talmana-Yanga o punkcie stałym :

Niech X będzie niepustym wypukłym zwartym podzbiorem ${\ displaystyle \ mathbb {R} ^ {n}}$ . Niech f : X → X będzie lokalnie brutto zachowującą kierunek (LGDP) : w dowolnym punkcie x , który nie jest stałym punktem f , kierunek jest równy ${\ displaystyle f (x) -x}$ rażąco zachowane w pewnym sąsiedztwie x , w tym sensie, że dla dowolnych dwóch punktów ${\ Displaystyle (f (y) -y) \ cdot (f (z) -z) \ geq 0}$ , z w tym sąsiedztwie jego iloczyn wewnętrzny jest nieujemny, tj.: − . Wtedy f ma punkt stały w X .

Twierdzenie jest pierwotnie określone dla polytopes, ale Philippe Bich rozszerza je na wypukłe zbiory zwarte, por. Twierdzenie 3.7 w jego artykule „Some fixed point theoremes for nieciągłe odwzorowania”.

Zauważ, że każda funkcja ciągła jest LGDP, ale funkcja LGDP może być nieciągła. Funkcja LGDP może nawet nie być ani górna, ani dolna półciągła . Ponadto istnieje konstruktywny algorytm aproksymacji tego stałego punktu.

Aplikacje

Dyskretne twierdzenia o punkcie stałym zostały użyte do udowodnienia istnienia równowagi Nasha w dyskretnej grze oraz istnienia równowagi Walrasa na dyskretnym rynku.