UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika  1. stopnja Barbara Lipnik Poincaré-Mirandov izrek Delo diplomskega seminarja Mentor: izr. prof. dr. Ale² Vavpeti£ Ljubljana, 2021

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika 1. stopnja

Barbara Lipnik

Poincaré-Mirandov izrek Delo diplomskega seminarja Mentor: izr. prof. dr. Ale² Vavpeti£

Ljubljana, 2021

Kazalo

1. Uvod 4

2. Poincaré-Mirandov izrek 5

3. Steinhausov izrek o ²ahovnici 7

3.1. Dokaz posplo²enega Steinhausovega izreka o ²ahovnici 13

4. Dokaz Poincaré-Mirandovega izreka 18

5. Posledice 21

6. Povezava z Brouwerjevim izrekom o negibni to£ki 22 7. Poskus posplo²itve Poincaré-Mirandovega izreka na prostor zaporedij ℓ² 24

7.1. Protiprimer 24

8. Posplo²itev Poincaré-Mirandovega izreka na prostor zaporedij ℓ² 25

Slovar strokovnih izrazov 28

Literatura 28

Poincaré-Mirandov izrek Povzetek

Diplomsko delo obravnava posplo²itev dobro poznanega izreka v eni dimenziji, in sicer izreka o vmesni vrednosti. Natan£neje, njegove posledice, ki zagotovi obstoj ni£le funkcije. Ta izrek je dobro poznan tudi kot izrek o ni£li. Dijaki se z njim sre£ajo ºe v srednji ²oli, ²tudentom matematike je ºe nekaj samoumevnega. Izrek o ni£li nam pove, da ima vsaka zvezna funkcija na zaprtem intervalu, £e v robnih to£kah zavzame nasprotno predzna£eni vrednosti, vsaj eno ni£lo. Izrek lahko, z nekaterimi modikacijami, posplo²imo na poljubno dimenzijo. V delu dokaºemo, da ima vsaka zvezna preslikava na enotski kocki v n-dimenzionalnem evklidskem prostoru, pod dolo£enim pogojem, vsaj eno ni£lo. Pogoj, ki ga potrebujemo, je, da so komponentne funkcije te preslikave razli£no predzna£ene na ustreznih stranicah enotske kocke. V delu opi²emo tudi ekvivalenco te posplo²itve izreka o ni£li oziroma Poincaré-Mirandovega izreka, in Brouwerjevega izreka o negibni to£ki. Predstavimo diskreten dokaz Poincaré-Mirandovega izreka, kjer si pomagamo s Steinhausovim izrekom o ²ahovnici. Predstavimo tudi moºne posplo²itve Poincaré-Mirandovega izreka na nekatere neskon£no dimenzionalne prostore.

The Poincaré-Miranda theorem Abstract

This thesis deals with the generalization of a well-known theorem in one dimension, namely the Intermediate value theorem. Specically, its corollary, which proves that a function has a root. This theorem is well known. Students learn about it already in high school. For math students, this is almost a self-evident result. The theorem says that every continuous function on a closed interval that changes sign at the boundary points has at least one root in this interval. With some modications, this theorem can be generalized to an arbitrary dimension. We prove that every continuous map on a unit cube in a n-dimensional Euclidean space has, under a certain condition, at least one root. The assumption we need is that each component function of the map changes sign on the corresponding sides of the unit cube. Here, we also show the equivalence of this generalization of a one-dimensional theorem, namely the Poincaré-Miranda theorem, and The Brouwer xed point theorem. We give a discrete proof of the Poincaré-Miranda theorem using the Steinhaus chessboard theorem. We present possible generalizations of the Poincaré-Miranda theorem to certain innite-dimensional spaces.

Math. Subj. Class. (2020): 58C30, 55M20

Klju£ne besede: ni£le funkcije, negibne to£ke, preslikave, zveznost, Poincaré- Mirandov izrek

Keywords: roots of a function, xed points, maps, continuity, Poincaré-Miranda's theorem

1. Uvod

V matematiki so pogost predmet obravnave razli£ne funkcije, preslikave in njihove lastnosti. Ena od njihovih pomembnih lastnosti, s katerimi se pogosto ukvarjamo, so ni£le. Za dolo£ene preslikave znamo eksplicitno zapisati ni£le, za druge znamo pokazati, da ni£el ni, spet v tretjem primeru pa bi si ºeleli dokazati vsaj, da kak²na ni£la obstaja, £etudi je ne znamo eksplicitno zapisati. Z raziskovanjem ni£el funkcij se matematiki ukvarjajo prakti£no ºe od nekdaj.

V 19. stoletju je £e²ki matematik Bernard Bolzano prvi dokazal pomemben izrek, ki za dolo£ene funkcije zagotavlja obstoj vsaj ene ni£le. Pravi, da ima vsaka zvezna funkcija na zaprtem intervalu, za katero velja, da ima v kraji²£ih intervala nasprotno predzna£eni vrednosti, na tem intervalu ni£lo. V nadaljevanju bomo Bolzanov izrek imenovali kar izrek o ni£li. Ta nam zagotovi vsaj eno ni£lo, morda pa jih obstaja tudi ve£. Izrek o ni£li se zdi intuitivno zelo jasen, sploh, ko ga predstavimo gra£no.

Se je pa izkazal za ²iroko uporabnega.

ƒe smo z relativno preprostimi pogoji v eni dimenziji dobili tako uporaben rezul- tat, se je smiselno vpra²ati, ali se da to ugotovitev posplo²iti tudi na vi²je, poljubne dimenzije. Odgovor na to je prvi podal francoski matematik in lozof Henri Poin- caré, ko je konec 19. stoletja zapisal takrat brez natan£nega dokaza posplo²en izrek o ni£li. Poincaré se je takrat pravzaprav ukvarjal z iskanjem periodi£nih re-

²itev problema treh teles. Pri²el je do sistema n ena£b za n neznank, za katerega je ºelel dokazati, da obstaja re²itev. Izrek, ki ga je zapisal, lahko torej razumemo kot posplo²itev Bolzanovega izreka o ni£li. Zaprti interval, ki je domena funkcije v izreku o ni£li nadomestimo s produktom intervalov, £emur re£emo ve£dimenzionalna kocka. Funkcija v ve£dimenzionalnem prostoru postane preslikava z ve£ komponen- tnimi funkcijami. Pogoj, da mora funkcija zavzeti nasprotno predzna£eni vrednosti na robnih to£kah intervala pa posplo²imo tako, da zahtevamo, da imajo komponen- tne funkcije na nasprotnih stranicah ve£dimenzionalne kocke razli£no predzna£ene vrednosti.

Poincaréjev rezultat je dolgo £asa ostal brez posebne veljave. Znova pa se je iz- rek za£el pojavljati v literaturi po tem, ko je leta 1940 italijanski matematik Carlo Miranda dokazal, da je ekvivalenten Brouwerjevemu izreku o negibni to£ki. Po- incaréjeva posplo²itev izreka o ni£li je tako postala znana pod imenom Poincaré- Mirandov izrek. Izrek je s tem dobil novo veljavo in tudi ve£ posplo²itev. Posplo²i- tve v veliki meri ciljajo na bolj splo²no domeno preslikave kot je ve£dimenzionalna kocka, na ²ir²i pogoj kot je pozitivna oz. negativna vrednost komponentnih funkcij na dolo£enih stranicah kocke in pa na raz²iritev iz kon£no dimenzionalnih prostorov na neskon£no dimenzionalne. Nekatere nadaljne posplo²itve so opisane v [4].

V naslednjem poglavju bomo predstavili Poincaré-Mirandov izrek in intuicijo, ki bo vodilo tudi pri dokazu, ki ga bomo predstavili v £etrtem poglavju. Pred doka- zom se bomo v tretjem poglavju posvetili ²e Steinhausovemu izreku o ²ahovnici, ki ga bomo uporabili pri dokazu naslovnega izreka. Steinhausov izrek o ²ahovnici je nekak²na vez med intuitivno idejo dokaza iz drugega poglavja in formalnim mate- mati£nim dokazom. Za tem bomo predstavili nekaj preprostih posledic Poincaré- Mirandovega izreka in njegovo povezavo z Brouwerjevim izrekom o negibni to£ki. V zadnjih poglavjih pa se bomo lotili posplo²itve Poincaré-Mirandovega izreka na ne- skon£no dimenzionalne prostore. Pojasnili bomo, zakaj izreka ne moremo uporabiti na poljubnem neskon£no dimenzionalnem prostoru, pokazali pa bomo posplo²itev na Hilbertovi kocki.

2. Poincaré-Mirandov izrek

Pri formulaciji izreka bomo uporabili nekatere oznake. S simbolom Iⁿ bomo ozna£ili n-dimenzionalno enotsko kocko v evklidskem prostoru Rⁿ, kjer je n ∈ N dimenzija prostora. Natan£neje, Iⁿ= [0,1]ⁿ. Denirajmo ²e nasprotna lica kocke.

Denicija 2.1. Naj bo Iⁿ = [0,1]ⁿ ⊂ Rⁿ. Za i = 1,2, . . . , n lahko deniramo i-ti nasprotni lici in sicer, i-to zadnje lice kot

I_i⁻ ={(x1, x2, . . . , xn)∈ Iⁿ:xi = 0}

in i-to prednje lice kot

I_i⁺={(x₁, x₂, . . . , x_n)∈ Iⁿ :x_i = 1}.

ƒe to ubesedimo,i-to zadnje lice sestavljajo to£ke kocke, ki imajoi-to komponento enako0. Podobno,i-to prednje lice sestavljajo to£ke, ki so nai-ti komponenti enake 1. Da si laºje predstavljamo, kaj konkretno to pomeni, si poglejmo nekaj primerov.

V eni dimenziji je enotska kocka kar enotski interval, torej I = [0,1]. Ker je n = 1 imamo samo en par nasprotnih lic. To£ka, ki predstavlja prvo zadnje lice je levo kraji²£e intervala, tj. to£ka 0. Po drugi strani pa je prvo prednje lice to£ka 1. V dveh dimenzijah sta nasprotni lici nasprotna robova kvadrata [0,1]². Imamo torej dva para nasprotnih lic:

I₁⁻ ={0} ×[0,1], I₁⁺ ={1} ×[0,1], I₂⁻ = [0,1]× {0}, I₂⁺ = [0,1]× {1}.

To vidimo na sliki 1. Na enak na£in so denirana nasprotna lica za vse vi²je dimen- zije. V treh dimenzijah, na primer, imamo tri pare nasprotnih lic. En par nasprotnih lic predstavljata nasprotni, disjunktni ploskvi kocke. Sedaj lahko zapi²emo naslovni izrek.

Slika 1. Para nasprotnih lic dvodimenzionalne enotske kocke.

Izrek 2.2 (Poincaré-Mirandov izrek). Naj bodo f₁, f₂, . . . , f_n zvezne funkcije deni- rane nan-dimenzionalni kockiIⁿ. Naj za vsaki= 1,2, . . . , nveljaf_i(I_i⁻)⊂(−∞,0]

inf_i(I_i⁺)⊂[0,∞). Tedaj obstaja to£ka vIⁿ, v kateri so vse funkcijef₁, . . . , f_nhkrati enake ni£. Torej ima preslikava f = (f₁, f₂, . . . , f_n) v tej to£ki ni£lo.

ƒe izrek pogledamo v enodimenzionalnem prostoru, ko za n vzamemo 1, dobimo ravno izrek o ni£li. Zdi se torej, da je to ustrezna posplo²itev. S pomo£jo skice si za laºjo predstavo poglejmo, kaj izrek pove. Za primer vzemimo prvi netrivialen primer, torej n = 2. Ukvarjamo se s preslikavo f = (f1, f2), kjer vsaka od zveznih funkcij f₁ in f₂ slika iz enotskega kvadrata v realna ²tevila, tj.

f₁, f₂: [0,1]×[0,1]→R.

(a) Graf funkcijef₁. (b) Graf funkcijef₂.

Slika 2. Komponentni funkciji preslikave f = (f₁, f₂), ki ustrezata pogojem iz izreka.

Za prvo komponentno funkcijo mora veljati, da je nenegativna na prvem prednjem licu in nepozitivna na prvem zadnjem licu. Podobno mora biti druga, f₂, nenega- tivna za vse x ∈ I₂⁺ in nepozitivna za x ∈ I₂⁻. Izrek pravi, da obstaja to£ka, kjer bosta obe komponentni funkciji hkrati enaki ni£. To pomeni, da bo imela preslikava f v tej to£ki ni£lo. Na sliki 3 sta grafa obeh komponentnih funkcij zdruºena. S te

Slika 3. Grafa funkcij f1 in f2 skupaj.

slike lahko razberemo, da v prikazanem primeru obstaja natanko ena to£ka, v kateri sta obe komponentni funkciji hkrati enaki 0. Vsaka od komponentnih funkcij na sliki zavzame vrednost ni£ na celi krivulji. To je intuitivno jasno, saj smo zahtevali zveznost in razli£no predzna£enost na nasprotnih robovih kvadrata. Da v tem pri- meru prese£na to£ka obstaja, se lahko prepri£amo tudi tako, da pogledamo presek obeh grafov z ravnino z = 0, ki je prikazan tudi na sliki 4. Presek grafa funkcije f₁ je krivulja, na kateri je f₁ = 0, in enako je presek grafa funkcije f₂ z ravnino z = 0 krivulja, kjer je f₂ = 0. ƒe se spomnimo slike 1 in pogoja, kje morata biti f₁ inf₂ ve£ji oziroma manj²i od ni£, vidimo, da ti krivulji sekata enotski kvadrat le na ustreznih nasprotnih stranicah. S tem smo se intuitivno prepri£ali o pravilnosti trditve vsaj za prikazani primer. Da jo lahko formalno dokaºemo, pa bo potreb- nega nekaj dodatnega dela. Pri dokazu si bomo pomagali z diskretnimi metodami.

Diskretni pristopi se ve£krat uporabljajo za dokazovanje topolo²kih rezultatov, saj

Slika 4. Presek z ravninoz = 0.

jih je praviloma laºje dokazati ali pa se lahko na ta na£in izognemo kompleksnej-

²im matemati£nim konceptom. V tem delu se bomo dokaza Poincaré-Mirandovega izreka lotili s pomo£jo diskretnega rezultata, ki ga bomo obravnavali v naslednjem poglavju. To je Steinhausov izrek o ²ahovnici. ƒeprav obstaja ve£ razli£nih doka- zov, je dokaz s pomo£jo Steinhausovega izreka o ²ahovnici konceptualno preprost za razumevanje, saj sledi intuiciji, ki smo jo dobili v dvodimenzionalnem primeru Poincaré-Mirandovega izreka. Poleg tega se z diskretnim pristopom izognemo zah- tevnej²im matemati£nim pojmom.

3. Steinhausov izrek o ²ahovnici

V tem poglavju se bomo ukvarjali s Steinhausovim izrekom o ²ahovnici (ang.

Steinhaus chessboard theorem), ki ga bomo nato posplo²ili, to posplo²itev pa bomo uporabili za dokaz Poincaré-Mirandovega izreka. Rezultati tega poglavja se opirajo na vire [1, 8, 11, 12]. Najprej zapi²imo originalni Steinhausov izrek o ²ahovnici.

Izrek 3.1. Naj bodo na nekaterih poljih n×n ²ahovnice postavljene mine. Velja ena od spodnjih trditev.

(1) Kralj lahko pride z levega roba plo²£e do desnega, ne da bi pre£kal katero od polj z minami.

(2) Trdnjava se lahko premakne s spodnje strani do zgornje tako, da se premika le po poljih z minami.

Denirajmo ²e povezano verigo.

Denicija 3.2. Za mnoºice A₁, A₂, . . . , A_n pravimo, da tvorijo (povezano) verigo,

£e velja A_i∩A_i+1 ̸=∅ za vse i= 1, . . . , n−1.

Verigo tvorijo mnoºice, ki imajo zaporedoma neprazne preseke. Izrek torej pravi, da £e imamo mreºo velikosti n×n in nekatera polja ozna£imo, na primer jih po- barvamo s £rno, potem obstaja ali veriga belih (nepobarvanih) polj z leve strani do desne ali pa veriga £rnih polj s spodnje strani do zgornje. Izrek zagotavlja verigo s spodnje do zgornje strani, ki ne vsebuje diagonalnih premikov, kar pa ni bistvenega pomena za na²o uporabo. Formalno barvanje deniramo s funkcijo.

Denicija 3.3. Naj boX mnoºica inn∈N. FunkcijiF:X → {1,2, . . . , n}re£emo funkcija barvanja. ƒe za x∈X veljaF(x) =i, re£emo, da je x pobarvan z i.

Kako bi izrek 3.1 posplo²ili na ve£ dimenzij, se zdi precej o£itno. Namesto s kvadrati v ravnini bomo mreºo naredili z n-dimenzionalnimi kockami. Vsako od kock bomo pobarvali z eno od n barv. Potem bi naj obstajala veriga kock, vseh pobarvanih z isto barvo i, ki povezuje ustrezni nasprotni strani mreºe. Lahko bi rekli, da povezuje i-ti lici za£etne mreºe.

Slika 5. Zgled Steinhausovega izreka v dveh dimenzijah za mreºo 4×4.

To intuitivno posplo²itev lahko tudi formalno deniramo. ’e pred tem pa zapi²imo opombo. Na skici 5 na levi mreºi vidimo, da imamo pot za trdnjavo po samih £rnih poljih s spodnjega do zgornjega roba. Vedno velja natanko ena od moºnosti iz izreka, zato poti za kralja po belih poljih z levega roba ²ahovnice do desnega roba ni. Vendar pa imamo pot po belih poljih za kralja ne od leve do desne ampak od spodnjega do zgornjega roba. Podobno velja na desni skici. Imamo pot za kralja po belih poljih z levega do desnega roba ²ahovnice, nimamo poti za trdnjavo od spodnjega do zgornjega roba, imamo pa pot za trdnjavo z leve na desno. To velja zato, ker je bila odlo£itev, katero barvo bomo pripisali kateremu robu mreºe, poljubna. V duhu izreka, vseeno je, ali i²£emo pot za kralja z leve strani do desne in za trdnjavo s spodnje do zgornje, ali obratno, za kralja s spodnje do zgornje in trdnjavo z leve do desne. ƒe torej zamenjamo, katero barvo (guro) smo pripisali kateremu robu na ²ahovnici, nam izrek ponovno zagotovi obstoj ene od dveh poti.

V splo²nem, za vsako permutacijo σ ∈ S_n, kjer je S_n mnoºica permutacij n barv, s katerimi barvamo n dimenzionalno mreºo, obstaja neka barva i, za katero obstaja veriga med σ(i)-tima nasprotnima stranicama mreºe. Formalizirajmo intuicijo o posplo²itvi Steinhausovega izreka o ²ahovnici.

Denicija 3.4. Naj bo Iⁿ n-dimenzionalna enotska kocka. Z D(k) ozna£imo raz-

£lenitev kocke Iⁿ nakⁿ manj²ih n-dimenzionalnih kock z robom dolºine ¹_k, torej D(k) =

{︃[︃i₁

k,i₁+ 1 k

]︃

× · · · × [︃i_n

k,i_n+ 1 k

]︃

⃓

⃓ i_j ∈ {0,1, . . . , k−1}, j = 1, . . . , n }︃

. V dveh dimenzijah dobimo za k = 2 mnoºico

D(2) = {︃[︃i1

2,i1+ 1 2

]︃

× [︃i2

2,i2+ 1 2

]︃

⃓

⃓ i_j ∈ {0,1}

}︃

. Kar je, £e razpi²emo, enako

D(2) = {︃[︃

0,1 2 ]︃

× [︃

0,1 2 ]︃

, [︃

0,1 2 ]︃

× [︃1

2,1 ]︃

, [︃1

2,1 ]︃

× [︃

0,1 2 ]︃

, [︃1

2,1 ]︃

× [︃1

2,1 ]︃}︃

.

Slika 6. Raz£lenitev dvodimenzionalne kocke D(2).

Dobili smo torej raz£lenitev 2-dimenzionalne enotske kocke na 2² = 4 dvodimenzio- nalne kocke z robom dolºine ¹₂, kar je prikazano na sliki 6. Posplo²eni Steinhausov izrek o ²ahovnici lahko sedaj zapi²emo tudi formalno.

Izrek 3.5 (Posplo²eni Steinhausov izrek o ²ahovnici). Naj boD(k)raz£lenitev enot- ske kocke Iⁿ. Za poljubno funkcijo barvanja F: D(k)→ {1,2, . . . , n} obstaja barva i ∈ {1,2, . . . , n}, za katero obstaja veriga P1, P2, . . . , Pr v celoti pobarvana z i in za katero velja, da je

P1∩ I_i⁻ ̸=∅ in Pr∩ I_i⁺̸=∅.

Veriga torej povezuje i-ti nasprotni lici kocke Iⁿ.

Steinhausov izrek o ²ahovnici bomo dokazali kasneje. Preden se lotimo dokaza, uvedimo ²e nekaj oznak in pojmov.

Denicija 3.6. Naj bodo x0 ∈ R, d∈R\ {0} in s ∈N. Mnoºica C(x0, d, s)⊂ Rⁿ oblike

C(x₀, d, s) = {︃

x₀, x₀+ 1

d, . . . , x₀+ s d

}︃n

se imenuje kombinatori£na n-kocka. Za vsak i = 1, . . . , n deniramo njena i-ta zadnja in prednja lica (v tem vrstnem redu) kot

C_i⁻(x₀, d, s) = {x∈C(x₀, d, s)|x(i) =x₀}, C_i⁺(x₀, d, s) = {︂

x∈C(x₀, d, s)|x(i) =x₀+ s d

}︂

. Primer kombinatori£ne 2-kocke C(0,4,4) = {︁

0,¹₄,¹₂,³₄,1}︁2

prikazuje slika 7, kjer so ozna£eni tudi pari prednjih in zadnjih lic kocke.

V nadaljevanju bomo potrebovali kombinatori£no kocko, katere elementi so sredi-

²£a kock raz£lenitve D(k) in plast to£k zunaj Iⁿ. Za k ∈R\ {0} je to C

(︃

− 1

2k, k, k+ 1 )︃

= {︃

− 1 2k, 1

2k, . . . ,1− 1

2k,1 + 1 2k

}︃n

.

Ker se bomo v nadaljevanju ukvarjali samo s tak²nimi kombinatori£nimin-kockami, bomo oznako skraj²ali na C(k). Za ilustracijo si poglejmo kombinatori£no 2-kocko za primer k = 2, torej

C(2) = {︃

−1 4,1

4,3 4,5

4 }︃2

.

Na sliki 8 sta prikazani raz£lenitev D(2) in kombinatori£na kocka C(2) skupaj.

Slika 7. Primer kombinatori£ne kocke C(0,4,4)dimenzije 2.

Slika 8. Primer v dveh dimenzijah: D(2) inC(2).

Opazimo, da je v vsaki kocki d ∈ D(k) natanko en element iz C(k). Poleg to£k v C(k), za katere velja, da leºijo znotraj Iⁿ, imamo ²e plast to£k zunaj n- dimenzionalne enotske kocke. Podmnoºico to£k v C(k), ki leºijo zunaj enotske kocke, bomo imenovali rob C(k). Rob lahko opi²emo kot

∂C(k) =

n

⋃︂

i=1

(C_i⁻(k)∪C_i⁺(k)),

kjer za vsak i s C_i⁻(k) in C_i⁺(k) ozna£imo zadnje in prednje lice kombinatori£ne kocke:

C_i⁻(k) = {︃

x∈C(k)| x(i) =− 1 2k

}︃

, C_i⁺(k) = {︃

x∈C(k) | x(i) = 1 + 1 2k

}︃

. V dokazu posplo²enega Steinhausovega izreka si bomo pomagali s posebnimi ma- temati£nimi objekti, ki se imenujejo simpleksi. Simpleks jen-razseºen analog triko- tnika. Po viru [9] lahko bolj formalno zapi²emo: n-simpleks je konveksna ogrinja£a n + 1 ano neodvisnih to£k x₀, x₁, . . . , x_n ∈ R^N. To£ke x₀, x₁, . . . , x_n so ano ne- odvisne, £e so vektorji x₁ −x₀, x₂ −x₀, . . . , x_n −x₀ linearno neodvisni. Simpleks zapi²emo z mnoºico to£k x₀, x₁, . . . , x_n, ki jim pravimo tudi ogli²£a, kot

[x₀, x₁, . . . , x_n] = {︄ _n

∑︂

i=0

t_ix_i ⃓

⃓

n

∑︂

i=0

t_i = 1, t_i ≥0 }︄

.

V tem delu bomo potrebovali nekoliko bolj speci£ne simplekse. Omejili se bomo na standardne n-simplekse in vedno, ko bomo katero mnoºico ozna£ili za simpleks, bomo to razumeli po spodnji deniciji (standardnega) simpleksa.

Denicija 3.7. Naj bo Sn mnoºica permutacij ²tevil {1,2, . . . , n} in naj bodo x0, x1, . . . , xn∈ Rⁿ. Mnoºico S = [x0, x1, . . . , xn] imenujemo n-simpleks, £e obstaja taka permutacija σ∈S_n, da velja

x₁ =x₀+e_σ(1), x₂ =x₁+e_σ(2), . . . x_n=xn−1+e_σ(n), kjer so e_i standardni bazni vektorji.

Imamo torej kon£no zaporedje to£k, za katere velja, da pridemo od prve do za- dnje s premikom po baznem vektorju. Na sliki 9 so prikazani simpleksi za majhne dimenzije. Za potrebe dokaza bomo za bazo prostora Rⁿ namesto standardnih ba-

Slika 9. 0-simpleks je to£ka, 1-simpleks je daljica, 2-simpleks je tri- kotnik itd.

znih vektorjev uporabili skalirane standardne vektorje. Ko naredimo raz£lenitev kocke Iⁿ, dobimo D(k). V kockah d iz raz£lenitveD(k)za bazne vektorje dolo£imo z ¹_k pomnoºene standardne bazne vektorje Rⁿ. Torej bodo bazni vektorji oblike e_i = (0, . . . ,0,_k¹,0, . . . ,0), kjer je ¹_k nai-tem mestu; e_i(i) = ¹_k ine_i(j) = 0 zaj ̸=i. Potem simpleks v Iⁿ predstavimo z zaporedjem to£k izIⁿ, ki so zaporedoma druga od druge oddaljene za enotno razdaljo _k¹ v smeri nekega baznega vektorja.

Denicija 3.8. Simpleks S^′, razpet na neki podmnoºici ogli²£ simpleksaS, imenu- jemo lice simpleksa S. ƒe je razpet na m ogli²£ih, pi²emo m-lice. Glavno lice sim- pleksa S je simpleks, ki je razpet nanodn+ 1ogli²£ih simpleksaS. Glavno lice na- sproti ogli²£ax_i simpleksaS = [x₀, x₁, . . . , x_n]je simpleks [x₀, . . . , xi−1, x_i+1, . . . , x_n] za i= 0,1, . . . , n.

Na sliki 10 lahko vidimo z oranºno ozna£ena glavna lica nasproti ogli²£a x₀ pri 1-simpleksu, 2-simpleksu in 3-simpleksu. Glavno lice je simpleks za ena manj²e dimenzije, kot je originalni simpleks.

Slika 10. Glavna lica simpleksov.

Denirajmo ²e triangulacijo. Preprosto povedano je triangulacija nekega objekta razdelitev tega objekta na trikotnike. Oziroma, ²ir²e, na simplekse.

Denicija 3.9. Triangulacija kompaktnega podprostora P ⊂Rⁿ je kon£na druºina simpleksov T, za katero velja

• £e staS₁, S₂ ∈T inS₁∩S₂ ̸=∅, potem je presek S₁∩S₂ lice tako simpleksa S₁ kot S₂,

• unija vseh simpleksov triangulacijeT je P.

Naj bo Sn mnoºica permutacij ²tevil od 1 do n. Triangulacija kocke [0,¹_k]ⁿ s simpleksi je

(1) T_n,k = {︃[︃

0, e_α(1), e_α(1)+e_α(2), . . . ,

r

∑︂

i=1

e_α(i), . . . , (︃1

k, . . . ,1 k

)︃]︃ ⃓

⃓

⃓

⃓

α∈S_n }︃

. Druºina Tn,k ima toliko elementov, kot je permutacij n ²tevil. Poglejmo si, kako izgleda triangulacija kocke s simpleksi v dveh in treh dimenzijah. Slika 11 na levi prikazuje triangulacijo dvodimenzionalne kocke. Ker so elementi triangulacije sim- pleksi, skica na desni ni triangulacija po na²i deniciji. Ker imamo dve razli£ni permutaciji mnoºice {1,2}, smo dobili tudi dva razli£na simpleksa, ki sta elementa triangulacije. V treh dimenzijah si ºe teºje predstavljamo triangulacijo s3-simpleksi.

Slika 11. Levo je triangulacija dvodimenzionalne kocke, desno pa ne.

Za ilustracijo je prikazana na sliki 12. Zaenkrat smo denirali samo triangulacijo

Slika 12. Triangulacija tridimenzionalne kocke.

n-dimenzionalne kocke v izhodi²£u. O£itno lahko enako denicijo uporabimo za katerokoli n-dimenzionalno kocko, le premaknemo za£etno to£ko.

Uvedimo ²e eno oznako. Z D(k)˜︁ ozna£imo mnoºico n-dimenzionalnih kock s stra- nico dolºine ¹_k, ki jo dobimo iz to£k C(k). Pravzaprav bo D(k)˜︁ premaknjena D(k), z dodatno plastjo manj²ih kock. Zapisano z ena£bo:

D(k) =˜︁

{︃[︃2i₁−1

2k ,2i₁+ 1 2k

]︃

× · · · ×

[︃2i_n−1

2k ,2i_n+ 1 2k

]︃

⃓

⃓ ij ∈ {0,1, . . . , k}

}︃

.

Kot primer je na sliki 13 prikazana mnoºica D(4)˜︁ . (Skupaj zD(4) inC(4).) Naj T

Slika 13. Mnoºico D(4)˜︁ sestavljajo kocke z dolºino stranice ¹₄, ki imajo ogli²£a v C(4).

ozna£uje triangulacijo n-dimenzionalne kocke [︃

− 1

2k,1 + 1 2k

]︃n

= ⋃︂

d∈D(k)˜︁

d.

Triangulacijo dobimo tako, da vsako kocko d∈D(k)˜︁ trianguliramo po deniciji (1).

Zaradi simetrije in dejstva, da vsa ogli²£a simpleksov iz triangulacij kock d leºijo v mnoºici C(k), sledi, da je T triangulacija kocke [︁

− _2k¹,1 + _2k¹ ]︁n

. Za vsak simpleks S bomo z V(S)ozna£ili mnoºico vseh ogli²£ simpleksa. Po konstrukciji velja, da so vsa ogli²£a simpleksov triangulacije T v mnoºici C(k).

3.1. Dokaz posplo²enega Steinhausovega izreka o ²ahovnici. Pri dokazu Ste- inhausovega izreka o ²ahovnici bomo uporabili pomoºno lemo. Najprej bomo bar- vanje kock D(k) raz²irili na barvanje to£k C(k). Pokazali bomo, da obstaja veriga simpleksov v T z dolo£enimi lastnostmi, ki jih bomo opisali v nadaljevanju.

Lema 3.10. Za poljubno funkcijo barvanja F: D(k) → {1,2, . . . , n} deniramo funkcijo Φ : C(k)→ {1,2, . . . , n}, ki vsaki to£ki x∈C(k) priredi barvo

(2) Φ(x) =

{︃ F(d) za x∈d∈D(k) ; x /∈∂C(k)

min{i | x∈C_i⁻(k)∪C_{i( mod}⁺ _n)+1(k)} ; x∈∂C(k) . Potem obstaja taka veriga simpleksov S₁, . . . , S_m ∈ T, da velja

Φ(V(S_p∩S_p+1)) ={1,2, . . . , n} za vse p∈ {1,2, . . . , m−1}.

Velja tudi

S1∩C_i⁻(k)̸=∅, Sm∩C_i⁺(k)̸=∅ za vse i∈ {1,2, . . . , n}.

Funkcija Φ torej vse to£ke x ∈ C(k), ki niso na robu C(k), pobarva z barvo, ki pripada kocki, v kateri leºi x. To£kam, ki leºijo na robu ∂C(k), pa oznako dolo£i po zgornjem predpisu. Tistim, ki so element nekega zadnjega lica C_i⁻(k) in ne tudi kak²nega prednjega lica, priredi najmanj²i indeks lica, katerega element je obravnavana to£ka. To£kam, ki so element le nekega (ali ve£) prednjih lic C_i⁺(k), pa priredi vrednost i− 1, kjer je i najmanj²i indeks lica, v katerem je ta to£ka.

Vrednost pripi²emo po modulu. Za to£ke, ki so element tako nekega zadnjega kot prednjega lica, pa vzamemo najmanj²o vrednost med tistimi, ki bi jih dobili po zgornjem postopku. Primer prikazuje slika 14. Na levi strani je prikazano neko

barvanje dvodimenzionalne kocke za k = 4, torej F(D(4)), desno pa je rezultat barvanja s funkcijo Φuporabljeno na C(4), ki smo jo dobili iz leve skice.

Slika 14. Primer slike funkcije Φ.

Lema torej pravi, da obstaja veriga simpleksov triangulacije T, za katero velja, da je slika to£k v preseku vsakih dveh zaporednih simpleksov verige s funkcijoΦkar cela mnoºica {1,2, . . . , n}. To pomeni tudi, da je presek dveh zaporednih simple- ksov v verigi glavno lice obeh simpleksov. Vsako ogli²£e lica v preseku ima drugo barvo. Poleg tega velja ²e, da ima prvi simpleks verige S₁ neprazen presek z vsemi zadnjimi lici C_i⁻(k) in podobno zadnji simpleks verige S_m neprazen presek z vsemi C_i⁺(k). Lema spominja na dokaz Spernerjeve leme, ki se pogosto uporablja v dokazu Brouwerjevega izreka o negibni to£ki in mu je tudi ekvivalentna.

Dokaz leme 3.10. Funkcija Φ je dobro denirana, saj za vsak x ∈ C(k) obstaja natanko en d∈D(k), za katerega velja x∈d.

Rekli bomo, da je simpleksS n-pobarvan, £e so njegova ogli²£a pobarvana z vsemi barvami {1, . . . , n}, torej Φ(V(S)) ={1,2, . . . , n}. Velja, da ima vsak n-pobarvan n-simpleks natanko dve n-pobarvani glavni lici. To drºi, saj ima n-simpleks n+ 1 ogli²£ in ker so njegova ogli²£a pobarvana z vsemi barvami od1don, obstaja natanko ena barva, ki se ponovi na dveh ogli²£ih. Ozna£imo ti ogli²£i z x_k inx_h. Glavno lice simpleksa ima n ogli²£ in bon-pobarvano natanko tedaj, ko bo imelo vsako ogli²£e svojo barvo. Torej, da dobimo n-pobarvano glavno lice, moramo med n+ 1 ogli²£i simpleksa izbrati n razli£no pobarvanih ogli²£. To lahko naredimo na dva na£ina.

Prvi£ tako, da izberemo vsa ogli²£a razenx_kin drugi£, da izberemo vsa ogli²£a razen x_h. To sta edini moºnosti, da izberemo n razli£no ozna£enih ogli²£ in s tem dobimo ravno dve n-pobarvani lici.

Verigo simpleksov bomo konstruirali induktivno. V nadaljevanju bomo z oznako conv(x₁, x₂, . . . , x_p) ozna£ili konveksno ovojnico to£k x₁, x₂, . . . , x_p. Naj bo S₁ = conv(z₀, z₁, . . . , z_n), kjer zai-to to£ko velja, da so vse njene koordinate do vklju£no i-te enake _2k¹, vse ve£je od i pa enake −_2k¹ :

(3) zi(j) =

{︃ −_2k¹ ; j > i

1

2k ; j ≤i j = 1, . . . , n.

Torej

z₀ = (︃

− 1 2k,− 1

2k, . . . ,− 1 2k

)︃

, z₁ =

(︃ 1 2k,− 1

2k, . . . ,− 1 2k

)︃

, ...

z_n = (︃ 1

2k, 1

2k, . . . , 1 2k

)︃

.

Simpleks S₁ vsebuje to£ko (︁

−_2k¹ , . . . ,−_2k¹ )︁

∈ D(k)˜︁ . Po deniciji funkcije Φ velja Φ(z_i) = i+ 1, saj to£ke z_i leºijo na zadnjih licih C(k) in vrednost Φ(z_i) dobimo kot najmanj²i indeks zadnjega lica kombinatori£ne kocke, katerega element jez_i. To velja za vse 0 ≤ i ≤ n−1, iz £esar sledi, da je S₁ n-pobarvan. To bo tudi prvi simpleks verige, ki jo i²£emo.

Simpleks S₁ ima eno n-pobarvano (glavno) lice na robu kocke C(k), in sicer conv(z₀, . . . , zn−1). Drugo n-pobarvano lice tega simpleksa torej ne leºi na robu

∂C(k). Ozna£imo ga s F. Po prej²njem razmisleku je jasno, da vsako n-pobarvano lice simpleksa leºi v preseku dveh simpleksov natanko tedaj, ko ne leºi na robu

∂C(k). Lice F ∈ S₁ je torej tudi lice nekega drugega simpleksa, recimo mu S₂. Ta simpleks ima ²e natanko eno prosto n-pobarvano lice, torej lice, ki ni v verigi simpleksov, ki jo gradimo. Vsak simpleks si glavno lice deli z najve£ enim drugim simpleksom. Simpleks S₂ je torej edini, ki vsebuje F in ²e ni v verigi. Zato ga dodamo. Postopek ponavljamo. V vsakem koraku imamo neki simpleks S_j, ki je zadnji v verigi. Ta ima natanko eno prosto n-pobarvano lice, ki pripada natanko enemu drugemu simpleksu, ki ²e ni v verigi. Zato ga dodamo. Dodajanje novih simpleksov ponavljamo, dokler ne pridemo do lica F^′, ki ima vse to£ke na robu

∂C(k). Postopek se vedno kon£a, saj ima T kon£no ²tevilo simpleksov. Z opisanim

Slika 15. Zgled konstrukcije verige simpleksov za C(4). postopkom dobimo verigo S₁, S₂, . . . , S_m, za katero velja

Φ(V(Sk∩Sk+1)) = {1,2, . . . , n} zak = 1, . . . , m−1.

Iz konstrukcije sledi tudi S₁∩C_i⁻(k)̸=∅ za vsaki∈ {1, . . . , n}, saj je S₁∩

(︄ _n

⋂︂

i=1

C_i⁻(k) )︄

= (︃

− 1 2k,− 1

2k, . . . ,− 1 2k

)︃

.

Prepri£ati se moramo ²e, da velja tudi S_m ∩ C_i⁺(k) ̸= ∅ za vse i ∈ {1, . . . , n}. Simpleks, ki iman-pobarvano lice na ∂C(k), ima torej n ogli²£, ki pripadajo ∂C(k) in vsako ima druga£no barvo. Ozna£imo to lice s F. Ogli²£e v_i ∈ F barve i pripada C_i⁻(k) ∪ C_i⁺_{(mod n)+1}(k) po deniciji (2) funkcije Φ. Lice F je torej ali enako konveksni ovojnici conv(z₀, . . . , zn−1), katere to£ke smo dobili po ena£bi (3), ali pa conv(w_o, . . . , wn−1), kjer so

w_i(j) =

{︃ 1 + _2k¹ ; j > i 1−_2k¹ ; j ≤i za i∈ {0, . . . , n} inj = 1,2, . . . , n. Torej

w0 = (︃

1 + 1

2k,1 + 1

2k, . . . ,1 + 1 2k

)︃

, w₁ =

(︃

1− 1

2k,1 + 1

2k, . . . ,1 + 1 2k

)︃

, ...

wn = (︃

1− 1

2k,1− 1

2k, . . . ,1− 1 2k

)︃

. O£itno robna to£ka(︁

1+_2k¹ , . . . ,1+_2k¹)︁

=w₀leºi vconv(w₀, . . . , wn−1). Vidimo, da po deniciji velja Φ(w_i) =iza vsei= 0, . . . , n−1, torej jeΦ(conv(w₀, . . . , wn−1)) = {1,2, . . . , n}. Zadnji simpleks mora torej biti S_m := conv(w₀, . . . , wn−1, w_n). To je n-simpleks in element triangulacije T.

Da sta res samo ti dve moºnosti za liceF, se lahko hitro prepri£amo. ƒe obstaja v F ogli²£e, ki leºi v nekem zadnjem licu kockeC_i⁻, potem morajo vsa ogli²£aF leºati v zadnjih licih, saj bi se sicer barva nekega ogli²£a ponovila. Podobno, £e je v F ogli²£e, ki leºi v nekem prednjem licuC_j⁺, ne pa tudi v zadnjem, potem morajo tudi vsa ostala ogli²£a leºati le v prednjih licih, da se barve ne ponovijo. Prva od dveh moºnosti, torej simpleks z licem, katerega vsa ogli²£a leºijo v zadnjih licih C(k), je ravno simpleks S₁. Za kon£ni simpleks nam tako ostane simpleks z licem, katerega ogli²£a so izklju£no v prednjih licih. O£itno velja Sm ∩C_i⁺ ̸= ∅ za vse i, saj je S_m∩C_i⁺=(︁

1 + _2k¹ , . . . ,1 + _2k¹)︁

. □

Slika 15 prikazuje konstrukcijo verige simpleksov za dvodimenzionalni primer C(4). Za dokaz posplo²enega Steinhausovega izreka o ²ahovnici potrebujemo verigo kock s podobnimi lastnostmi. Z zgornjo lemo, ki nam zagotovi verigo simpleksov, bomo znali konstruirati tudi verigo kock.

Dokaz izreka 3.5. Spomnimo se, kaj pravi posplo²eni Steinhausov izrek o ²ahovnici.

Za raz£lenitev n-dimenzionalne enotske kocke na manj²e n-dimenzionalne kocke, ki jih pobarvamo s poljubno funkcijo barvanja velja, da obstaja veriga enako pobar- vanih manj²ih kock, ki povezuje nasprotni lici enotske kocke. Pri dokazu si bomo pomagali z lemo 3.10. Iz verige simpleksov, ki povezuje nasprotna lica kombina- tori£ne kocke, bomo konstruirali verigo n-dimenzionalnih kock, ki bo povezovala nasprotni stranici enotske kocke.

Ponovno denirajmo funkcijo barvanja Φ : C(k) → {1,2, . . . , n} na enak na£in kot v lemi;

Φ(x) =

{︃ F(d) zax∈d∈D(k) ;x /∈∂C(k)

min{i | x∈C_i⁻(k)∪C_i⁺_{(mod n)+1}(k)} ;x∈∂C(k) .

Po lemi 3.10 obstaja veriga simpleksov S1, S2, . . . , Sm v T, ki zado²£a pogojem iz leme. Ker veljaS_m∩C_i⁺(k)̸=∅za vsei= 1, . . . , n, obstaja najmanj²i indeksℓ₁, da velja

S_ℓ1 ∩C_i⁺(k)̸=∅

za nekii∈ {1,2, . . . , n}. To je indeks zadnjega simpleksa verige, ki ²e ima neprazen presek s katerim od prednjih lic kombinatori£ne kocke C(k). S tem smo izbrali indeks nasprotnih lic, med katerima bomo iskali verigo. Za ta i ozna£imo z ℓ₂ ∈ {1,2, . . . , ℓ₁} najve£ji indeks, za katerega je

S_ℓ2 ∩C_i⁻(k)̸=∅.

Tak ℓ₂ obstaja, saj jeS₁∩C_i⁻(k)̸=∅. ’teviloℓ₁ je najmanj²i indeks simpleksa v ve- rigi, ki ²e seka katero prednje lice kocke, torej za vseℓ < ℓ1veljaSℓ∩(︂

⋃︁n

j=1C_j⁺(k) )︂

=

∅. Potem jeℓ₂ najve£ji indeks simpleksa iz verige, ki ²e ima neprazen presek zi-tim zadnjim licem C_i⁻(k). Za simplekse verige, ki imajo indekse strogo med ℓ₂ in ℓ₁, velja, da imajo prazen presek z i-tim prednjim in zadnjim licem kocke C(k). Ker veljaΦ(S_j∩S_j+1) ={1,2, . . . , n}za vsakj = 1,2, . . . , m−1, lahko najdemo tako za- poredje ogli²£, vseh pobarvanih z i, da vsako ogli²£e leºi v preseku dveh zaporednih simpleksov verige. Dobimo torej zaporedje (z_r)^ℓ_r=1^1−ℓ2, kjer je z_r ∈ S_ℓ2+r−1∩S_ℓ2+r in Φ(z_r) =i. Povedano z besedami, z zaporedjem za£nemo pri zadnjem simpleksu, ki

²e sekai-to zadnje lice kocke, torej S_ℓ2. Prvi £len zaporedja je zipobarvano ogli²£e, ki leºi v preseku S_ℓ2 ∩S_ℓ2+1. Naslednji £len bo potem z i pobarvano ogli²£e iz pre- sekaSℓ2+1∩Sℓ2+2 in tako naprej do zipobarvanega ogli²£a, ki leºi v preseku prvega simpleksa, ki seka i-to prednje lice kockeC(k), to je Sℓ1 in njegovega predhodnika v verigi, S_ℓ1−1. Prepri£ajmo se, da noben £len tega zaporedja(z_r)^ℓ_r=1^1−ℓ2 ne leºi na robu kocke ∂C(k).

Po deniciji Φ so edine to£ke, ki leºijo na robu ∂C(k) in so ozna£ene z i, tiste, ki leºijo v C_i⁻(k)∪C_i⁺_{(mod n)+1}(k). Po konstrukciji z_r ∈/ C_i⁻(k) za vse r > 1, saj smo sicer v protislovju z denicijo ²tevila ℓ₂. Velja tudi z₁ ∈/ C_i⁻(k). To je res, ker je v preseku C_i⁻(k)∩S_ℓ2 samo ena to£ka, recimo z₀. To£ka z₀ ne more biti enaka z₁, saj je z₁ ∈ S_ℓ2 ∩S_ℓ2+1. ƒe bi bila z₀ = z₁ ∈ S_ℓ2 ∩S_ℓ2+1, bi pri²li do protislovja z denicijo ²tevila ℓ₂, saj je z₀ ∈ C_i⁻(k) in bi bil tudi presek simpleksa S_ℓ2+1 z i- tim zadnjim licem neprazen. Prav tako pa velja, da to£ke zaporedja ne leºijo na prednjem licu kocke: z_r ∈/ C_i⁺_{(mod n)+1}(k) za vse r ≤ ℓ₁ −ℓ₂. Ker bi bili sicer v protislovju z izbiro indeksa i. Indeks i smo namre£ izbrali kot indeks simpleksa, ki se prvi dotakne katerega prednjega lica kocke. Torej veriga simpleksov seka C_i⁺(k) prej kot katerikoli drug C_∗⁺(k), ker je ∗ ∈ {1, . . . , n} \ {i}.

Ugotovili smo, da za 1 ≤ r ≤ ℓ₁ −ℓ₂ ogli²£a z_r niso v C_i⁻(k)∪C_i⁺_{(mod n)+1}(k). Ker je za ogli²£a na robu edina moºnost, da so pobarvana z i, to, da so v C_i⁻(k)∪ C_i⁺_{(mod n)+1}(k), lahko sklepamo, da za vse z ∈ (z_r)^ℓ_r=1^1−ℓ2 velja z /∈ ∂C(k). Vemo, da za vse to£keC(k), ki ne leºijo na robuC(k), velja, da vsaka leºi v natanko eni kocki raz£lenitveD(k). To pomeni, da za vsako od to£kz_rna²ega zaporedja obstaja kocka P_rizD(k), da veljaz_r ∈P_r. Velja tudiF(P_r) = Φ(z_r) =iza vser∈ {1, . . . , ℓ₁−ℓ₂}.

Slika 16. Zaporedje kock, ki jih dobimo iz zaporedja simpleksov in ki povezujejo drugo prednje in zadnje lice I².

Iz zaporedja (z_r)^ℓ_r=1^1−ℓ2 smo dobili verigo kock P₁, . . . , P_ℓ1−ℓ₂, kjer je P_j ∈ D(k) in z_j ∈ P_j. Primer konstrukcije verige kock iz verige simpleksov lahko vidimo na sliki 16. Za vse j = 1,2, . . . , ℓ₁−ℓ₂−1 jeP_j∩P_j+1 ̸=∅po konstrukciji. Za razpolovi²£e daljice med sredi²£ema zaporednih kock zaporednima £lenoma v (z_r)^ℓ_r=1^1−ℓ2 lahko z gotovostjo re£emo, da je v preseku obeh kock. Velja namre£ z_j, z_j+1 ∈ S_j+1 ∈ T. Po konstrukciji triangulacije T sledi

|z_j(s)−z_j+1(s)| ≤ 1 k

za vse koordinate s= 1, . . . , n. Zaporedni to£kiz_j inz_j+1 se torej razlikujeta najve£

za ¹_k na vsaki koordinati. Ker je z_j v sredi²£u kocke P_j, je vsaka druga to£ka, ki je od z_j na vsaki koordinati oddaljena za najve£ _2k¹ , prav tako v P_j. Ker je to£ka

1

2(z_j +z_j+1) od z_j oddaljena za najve£ _2k¹ na vsaki koordinati, je ¹₂(z_j +z_j+1) ∈P_j in podobno tudi ¹₂(z_j+z_j+1)∈P_j+1. Sledi

P_j∩P_j+1 ̸=∅.

Prepri£ajmo se ²e, da drºi tudi P₁ ∩ I_i⁻ ̸= ∅ in P_ℓ1−ℓ2 ∩ I_i⁺ ̸= ∅. S podobnim razmislekom kot zgoraj pridemo do ugotovitve, da je P1∩ I_i⁻ ̸=∅. Ker sta z0, z1 ∈ Sℓ2, z1 ∈P1 in z0 ∈C_i⁻(k), je ¹₂(z0+z1)∈P1∩ I_i⁻̸=∅. Podobno je

1

2(z_ℓ1−1+z_ℓ1)∈P_ℓ1 ∩ I_i⁺ ̸=∅.

S tem smo dokazali izrek. □

4. Dokaz Poincaré-Mirandovega izreka

V tem poglavju bomo uporabili posplo²eni Steinhausov izrek o ²ahovnici za dokaz Poincaré-Mirandovega izreka. Dokaza se bomo lotili s protislovjem. Denirali bomo funkcijo barvanja raz£lenitve Iⁿ in poiskali pobarvano verigo, ki nas bo privedla do protislovja. V dokazu bomo potrebovali ²e Lebesgueovo lemo. Zato najprej doka- ºimo to. Dokaz in formulacija Lebesgueove leme sledita [3]. ’e prej pa denirajmo premer mnoºice. Denicija je povzeta po [10].

Denicija 4.1. Naj bo (X, d) metri£ni prostor. Premer mnoºice A ⊂ X je supre- mum razdalj med to£kami A. Ozna£imo

diamA= sup{d(a, b)| a, b∈A}.

Izrek 4.2 (Lebesgueova lema). Naj bo X kompakten metri£ni prostor. Naj bo U poljubno odprto pokritje prostora X. Potem obstaja tak²no realno ²tevilo ε >0, da za vsako mnoºico A⊂X velja, da £e je njen premer manj²i od ε, potem obstaja tak

£lan pokritja U ∈ U, da velja A⊂U.

Vsaka mnoºica z dovolj majhnim premerom torej v celoti leºi v neki mnoºici pokritja. Dokaºimo s protislovjem.

Dokaz. Recimo, da za neki kompaktni metri£ni prostor izrek ne velja. Potem obstaja tako odprto pokritje U, da implikacija iz izreka ne bo veljala. Torej za vsak ε >0 obstaja neka mnoºica z diamA < ε, ki pa ni v celoti vsebovana v nobenem £lanu pokritjaU. Denirajmo zaporedje mnoºic. Zaε= _n¹ naj boA_nmnoºica zdiamA_n<

1

n, ki ni cela vsebovana v nobeni mnoºici pokritja. V vsaki mnoºiciA_n izberimo neki element a_n, s £imer dobimo zaporedje to£k v kompaktnem prostoru. To zaporedje mora imeti stekali²£e, ki ga ozna£imo z a. To£ka a je vsebovana v neki mnoºici pokritjaa∈U ∈ U in ker jeU odprta, obstaja krogla s sredi²£em va, ki je cela vU. Kroglo s sredi²£em v a in polmerom r ozna£imo z B(a, r). Potem lahko zapi²emo

∃m ∈N:B (︃

a, 1 m

)︃

⊂U.

Ker jeastekali²£e, v krogliB(a,_m¹)leºi neskon£no mnogo £lenov zaporedja(a_n)^∞_n=1. Poi²£imo mnoºico A_i, ki bo v celoti leºala znotraj krogle s sredi²£em v a. Idejo dokaza prikazuje slika 17. Naj bo ²tevilo M₀ >2m. Potem za vsak M > M₀ velja

a_M ∈B (︃

a, 1 M0

)︃

=⇒ A_M ⊂B (︃

a, 1 m

)︃

⊂U.

S tem smo pri²li do protislovja z lastnostjo mnoºicA_n, ki niso podmnoºice nobenega

£lana pokritja U. □

Slika 17. Mnoºice A_M z dovolj majhnim premerom leºijo znotraj krogle s sredi²£em v stekali²£u.

Dokaz Poincaré-Mirandovega izreka 2.2. Predpostavimo, da preslikavaf nima ni£le na n-dimenzionalni kocki Iⁿ. Denirajmo mnoºice

U_i ={x∈ Iⁿ | f_i(x)̸= 0}

za vsei= 1, . . . , n. Vse mnoºiceU_iso odprte, saj jeR−{0}odprta in vsaka funkcija f_ije zvezna. Praslika odprte mnoºice z zvezno funkcijo pa je odprta. Druºina odprtih mnoºic {U_i}ⁿ_i=1 je odprto pokritje za Iⁿ, saj f na Iⁿ nima ni£le. Po Lebesgueovi lemi obstaja tak ε >0, da za vsakp∈ Iⁿ obstaja j ∈ {1,2, . . . , n}, da je

B(p, ε)⊂U_j.

Izberimo dovolj velik k, da bodo vsen-dimenzionalne kocke iz raz£lenitveIⁿ vsebo- vane v kateri od krogel s polmerom ε. Potem mora veljati

⃓

⃓

⃓

⃓ (︃1

k,1

k, . . . ,1 k

)︃ ⃓

⃓

⃓

⃓

<2ε,

√︃ 1 k² + 1

k² +. . .+ 1

k² <2ε, 1

k

√n <2ε, 1 k < 2

√nε.

Izberimo torej tak k in naredimo raz£lenitev D(k) enotske kocke Iⁿ na kocke z robom dolºine ¹_k. Potem za vsako kocko d ∈ D(k) obstaja tak j = 1,2, . . . , n, da velja d⊂U_j. Denirajmo funkcijo barvanja

F: D(k)→ {1,2, . . . , n}, F(d) = min{j | d∈U_j}.

Ta funkcija je dobro denirana na D(k). Po posplo²enem Steinhausovem izreku o

²ahovnici obstaja veriga kock P₁, . . . , P_r∈D(k), pobarvanihi, da velja P₁∩ I_i⁻ ̸=∅, P_r∩ I_i⁺ ̸=∅in P_j ∩P_j+1 ̸=∅ za j = 1,2, . . . , r−1.

Mnoºica

W :=

r

⋃︂

j=1

P_j

je povezana in zaprta. Ker ima P₁ neprazen presek z i-tim zadnjim licem, obstaja x∈P1 ∩ I_i⁻. Podobno obstaja neki y∈Pr∩ I_i⁺ in velja

f_i(x)≤0, f_i(y)≥0.

Ker je f zvezna, jef_i(W)povezana mnoºica v R. To pomeni, da jef_i(W) interval, ki vsebuje [f_i(x), f_i(y)]. Ker je 0 ∈ [f_i(x), f_i(y)], obstaja neka to£ka p ∈ W, za katero velja f_i(p) = 0. Obstaja torej neki j ∈ {1,2, . . . , n}, da jep∈ P_j. Toda, ker so vse kocke v verigi pobarvane z i, velja tudi p∈ U_i. Da je p∈ U_i pa pomeni, da je fi(p)̸= 0. Pri²li smo do protislovja. Preslikavaf torej ima ni£lo na Iⁿ. □

5. Posledice

V tem poglavju bomo predstavili nekaj posledic Poincaré-Mirandovega izreka.

Opiramo se na vir [5]. Prva preprosta, pravzaprav neposredna posledica, ki jo izpeljemo iz Poincaré-Mirandovega izreka, govori o sovpadanju preslikav.

Posledica 5.1. Naj bosta g, h: Iⁿ → Iⁿ zvezni preslikavi. Naj bo h(I_i⁻) ⊆ I_i⁻ in h(I_i⁺)⊆ I_i⁺ za vse i. Potem obstaja to£ka c∈ Iⁿ, da velja g(c) =h(c).

Dokaz. Denirajmo novo funkcijof(x) :=h(x)−g(x). Ta ustreza pogojem Poincaré- Mirandovega izreka, zato obstaja to£ka c ∈ Iⁿ za katero velja f(c) = 0. Torej, f(c) = h(c)−g(c) = 0 in tako sledi h(c) = g(c). □ Poglejmo si ²e eno posledico, ki na prvi pogled nima neposredne zveze z izrekom.

Izrek 5.2 (Izrek o stiskanju kocke). Naj bo g: Iⁿ →X zvezna preslikava v metri£ni prostor X. Naj bo g(∂Iⁿ) =X. Potem obstaja tak i ∈ {1, . . . , n}, da je presek slik i-tih nasprotnih lic neprazen, torej g(I_i⁻)∩g(I_i⁺)̸=∅.

Izrek pravi, da za zvezno funkcijo g, ki izn-dimenzionalne kocke slika v metri£ni prostor, ki je enak sliki roba te kocke, obstaja par nasprotnih lic n-dimenzionalne kocke, ki ima, preslikan s funkcijo g, neprazen presek. Ta izrek v treh dimenzijah lahko povemo tudi na bolj vizualen na£in. Tridimenzionalne kocke ni mogo£e narisati na ravnino tako, da bi bile vse disjunktne ploskve kocke disjunktne tudi na risbi.

Primer vidimo na sliki 18.

Slika 18. Vedno, ko nari²emo kocko v ravnini, obstajata disjunktni ploskvi kocke, ki imata na risbi neprazen presek.

Dokaz. Izrek bomo dokazali s protislovjem. Recimo torej, da veljag(I_i⁻)∩g(I_i⁺) =∅ za vsak i= 1,2, . . . , n. Denirajmo mnoºice

A_i :=g(I_i⁻), B_i :=g(I_i⁺).

Z novimi oznakami torej za vsak i velja A_i∩B_i =∅. Ker je X metri£ni prostor, je seveda tudi normalen in zato obstaja zvezna preslikava h = (h₁, h₂, . . . , h_n) : X → Rⁿ, da velja

h_i(A_i) ={0} in h_i(B_i) = {1}

za vsak i. Velja h(A_i)⊂ I_i⁻, saj je

h(A_i) = (h₁(A_i), . . . , hi−1(A_i), h_i(A_i), h_i+1(A_i), . . . , h_n(A_n))

= (h1(Ai), . . . , hi−1(Ai),0, hi+1(Ai), . . . , hn(An))⊂ I_i⁻.

Podobno velja h(B_i)⊂ I_i⁺. Vidimo, da velja h(X) = h(g(∂Iⁿ)) = h

(︄

g (︄ _n

⋃︂

i=1

I_i⁻∪ I_i⁺ )︄)︄

=h (︄ _n

⋃︂

i=1

g(I_i⁻)∪g(I_i⁺) )︄

=h (︄ _n

⋃︂

i=1

A_i∪B_i )︄

= (︄ _n

⋃︂

i=1

h(A_i)∪h(B_i) )︄

⊂∂Iⁿ.

Zdaj denirajmo preslikavof =h◦g. Preslikava f slikai-to zadnje lice ponovno na

Slika 19. Komutativni diagram funkcijf, g in h. i-to zadnje lice in i-to prednje lice na i-to prednje lice:

f(I_i⁻) = h(g(I_i⁻)) = h(Ai)⊂ I_i⁻, f(I_i⁺) = h(g(I_i⁺)) = h(B_i)⊂ I_i⁺.

Po posledici 5.1 za poljubno drugo preslikavo H: Iⁿ→ Iⁿ velja, da obstaja c∈ Iⁿ, v kateri imata preslikavi isto vrednost, torej f(c) = H(c). Izberimo preslikave H(x) =a za vsaka∈ Iⁿ. Po posledici torej velja, da za vsako to£koaizIⁿ obstaja neka to£ka, v kateri f zavzame vrednost a. Preslikava f je torej surjektivna iz Iⁿ spet v Iⁿ. Pri²li smo do sklepa, da je f(Iⁿ) =Iⁿ, kar pa je v nasprotju s tem, da je slika f(Iⁿ) podmnoºica roba ∂Iⁿ. Torej na²a za£etna predpostavka ne drºi in imata sliki nekih nasprotnih lic res neprazen presek. □

ƒeprav smo v celotnem delu do zdaj za domeno funkcije, za katero smo uporabili Poincaré-Mirandov izrek, izbrali enotsko n-dimenzionalno kocko [0,1]ⁿ, ta omeji- tev ni potrebna. O£itno izrek velja za poljuben n-dimenzionalni kvader, saj je ta homeomorfen enotski kocki.

6. Povezava z Brouwerjevim izrekom o negibni to£ki

V kopici izrekov o negibni to£ki je Brouwerjev izrek ²e posebej poznan. Ob- staja veliko zanimivih neformalnih razli£ic tega izreka in njegovih posledic. Tudi Poincaréjev izrek, zdaj znan kot Poincaré-Mirandov izrek, je pridobil na veljavi in prepoznavnosti ²ele, ko je Carlo Miranda dokazal njegovo ekvivalenco z Brouwerje- vim izrekom o negibni to£ki. Spomnimo najprej, kaj to£no slednji pove. V izreku obravnavamo preslikavo iz n-dimenzionalne krogle vase. Kroglo s sredi²£em v to£ki S in z radijem r ozna£imo z Bⁿ(S, r) ={x∈Rⁿ;|x−S| ≤r}.

Izrek 6.1 (Brouwerjev izrek o negibni to£ki). Naj bo f zvezna preslikava iz n- dimenzionalne krogle nazaj vase. Potem ima f negibno to£ko.

Izrek govori o n-dimenzionalni krogli, toda topolo²ko je ta homeomorfna enotski kocki, ki jo obravnava Poincaré-Mirandov izrek, zato ga lahko uporabimo tudi na n-dimenzionalni (enotski) kocki. O tem se lahko hitro prepri£amo. Naj bo h ho- meomorzem med kroglo Bⁿ in nekim drugim prostorom X, v na²em primeru nas zanima X =Iⁿ. Imamo zvezno preslikavo f: X →X. Ozna£imo z

g =h⁻¹◦f ◦h.

Preslikava g slika iz Bⁿ nazaj v Bⁿ. Uporabimo lahko Brouwerjev izrek o negibni to£ki, ki nam zagotovi obstoj neke to£ke c∈Bⁿ, za katero je g(c) =c. To pomeni

g(c) =h⁻¹(f(h(c)) = c f(h(c)) = h(c), s £imer smo pokazali, da ima preslikava f negibno to£ko.

Spomnimo se posledice 5.1. ƒe za h izberemo identiteto, za g pa poljubno presli- kavo, posledica pravi, da v enotski kockiIⁿobstaja to£kac, da veljac=h(c) = g(c). To pomeni, da imagnegibno to£ko. Vidimo torej, da iz Poincaré-Mirandovega izreka sledi Brouwerjev izrek. Dokaºemo lahko tudi obratno.

Pri dokazovanju, da Brouwerjev izrek implicira Poincaré-Mirandov izrek, se zgle- dujemo po viru [6]. Naj bo g: Iⁿ → Rⁿ preslikava, za katero za vsak i = 1, . . . , n velja

g_i(I_i⁻)⊂(−∞,0], g_i(I_i⁺)⊂[0,∞).

Denirajmo preslikavo h= (h₁, . . . , h_n) :Rⁿ → Iⁿ s predpisom h_i(x₁, . . . , x_i, . . . , x_n) =

⎧

⎨

⎩

0 ;x_i ≤0 x_i ;x_i ∈[0,1]

1 ;x_i ≥1

za vsak i= 1, . . . , n. Vidimo, da preslikava h elemente kocke Iⁿ preslika same vase in je tudi zvezna. Denirajmo ²e eno zvezno preslikavo:

f: Rⁿ→Rⁿ, f =h−g◦h.

Za vsak x∈Rⁿ velja

|f(x)| ≤ |h(x)|+|g(h(x))|

≤√︁

h₁(x)² +· · ·+h_n(x)²+√︁

g₁(h(x))² +· · ·+g_n(h(x))²

≤√

1 +· · ·+ 1 +√︁

(max{g₁(x)| x∈ Iⁿ})² +· · ·+ (max{g_n(x) |x∈ Iⁿ})²

=√ n+√

n max

i=1,...,n(max{gi(x)| x∈ Iⁿ}) =: R0.

Zgoraj smo najprej upo²tevali trikotni²ko neenakost, potem pa dejstvo, da h slika v Iⁿ. Preslikava f torej slika prostor Rⁿ na kroglo Bⁿ(0, R₀). Posledi£no f slika Bⁿ(0, R₀) spet vase. Po Brouwerjevem izreku o negibni to£ki obstaja to£ka x^∗ ∈ Bⁿ(0, R₀), za katero velja f(x^∗) = x^∗. Dokaºimo, da to£ka x^∗ leºi znotraj enotske kocke Iⁿ. ƒe x^∗ ∈ I/ ⁿ, potem obstaja tak i∈ {1, . . . , n}, da je ali x^∗_i <0ali x^∗_i >1. Najprej si poglejmo prvo moºnost, torej, da je i-ta komponenta negibne to£ke za neki indeks i manj²a od ni£. Da je x^∗ negibna to£ka preslikave f, pomeni

x^∗ =h(x^∗)−g(h(x^∗))

=(︁

h1(x^∗), . . . , hn(x^∗))︁

−(︁

g1(h1(x^∗), . . . , hn(x^∗)), . . . , gn(h1(x^∗), . . . , hn(x^∗)))︁

.