UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika  1. stopnja Lucija Bogataj Ekstremalna kombinatorika z verjetnostno metodo Delo diplomskega seminarja Mentor: prof. dr. Marko Petkov²ek Ljubljana, 2021

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika 1. stopnja

Lucija Bogataj

Ekstremalna kombinatorika z verjetnostno metodo Delo diplomskega seminarja

Mentor: prof. dr. Marko Petkov²ek

Ljubljana, 2021

Kazalo

1. Uvod 4

1.1. Ekstremalna kombinatorika 4

1.2. Verjetnostna metoda 5

1.3. Glavne ideje dokazovanja 5

1.4. Primeri 6

2. Mnoºice brez vsot 7

3. Turnirji 8

3.1. Hamiltonove poti v turnirjih 9

3.2. Lastnost P_k 11

4. Dominantne mnoºice vozli²£ 15

5. Prekriºno ²tevilo 18

6. Incidence to£k in premic v ravnini 20

7. Zaklju£ek 25

Slovar strokovnih izrazov 25

Literatura 26

Ekstremalna kombinatorika z verjetnostno metodo Povzetek

Ekstremalna kombinatorika se ukvarja z vpra²anji, kako velik oziroma majhen je lahko neki matemati£ni objekt ali druºina objektov, ki zado²£a dolo£enim pogojem.

Verjetnostna metoda re²uje ekstremalne probleme s pomo£jo katere od naslednjih trditev: pri£akovana vrednost je linearni funkcional; slu£ajna spremenljivka ne more biti povsod strogo ve£ja (niti povsod strogo manj²a) od svoje pri£akovane vrednosti;

za dokaz obstoja objekta z dano lastnostjo v neki kon£ni mnoºici objektov zado²£a pokazati, da je verjetnost obstoja takega objekta pozitivna.

S pomo£jo verjetnostne metode so predstavljeni dokazi naslednjih izrekov: V po- ljubni mnoºici neni£elnih ²tevil obstaja podmnoºica brez vsot, katere mo£ je vsaj ena tretjina mo£i prvotne mnoºice. Obstaja turnir z n igralci, ki ima vsaj n!/2ⁿ⁻¹ Hamiltonovih poti. ƒe je n ≥k²2^k+1, potem obstaja turnir z n igralci, pri katerem zunaj vsake podmnoºice igralcev mo£ik obstaja igralec, ki je premagal vse igralce v tej podmnoºici. V grafu z n vozli²£i, katerih stopnja je vsaj d, obstaja dominantna mnoºica vozli²£ mo£i manj²e ali enake n^1+ln(d+1)_d+1 . Graf z n vozli²£i in e ≥4n pove- zavami ima prekriºno ²tevilo ve£je ali enako _64n^e32. Izreku o prekriºnem ²tevilu grafa sledijo ²e Szemerédi-Trotterjev izrek, njegova posledica in Beckov izrek o incidencah to£k in premic v ravnini.

Extremal combinatorics with the probabilistic method Abstract

Extremal combinatorics deals with questions about how big or small a certain ma- thematical object or family of objects can be to satisfy certain restrictions. The probabilistic method entails solving extremal problems using one of the following theorems: The expectation is a linear functional. A random variable cannot always be strictly greater (nor always strictly smaller) than its expectation. For a proof of existence of an object with a certain property within a nite set of objects it is enough to prove that the probability of existence of such an object is positive.

The following theorems which use the probabilistic method are stated and proved:

In any set of nonzero integers there is a sum-free subset with the size of at least one third of the original set. There is a tournament with n players and at leastn!/2ⁿ⁻¹ Hamiltonian paths. If n≥k²2^k+1, then there is a tournament ofn players in which for every k players there is a player who defeated them all. A graph withn vertices with a minimum degree d has a dominating set with at most n^1+ln(d+1)_d+1 vertices.

The crossing number of a graph withn vertices ande≥4n edges is greater or equal to n^1+ln(d+1)_d+1 . The crossing number theorem is followed by the Szemerédi-Trotter theorem, one of its corollaries, and Beck's theorem.

Math. Subj. Class. (2020): 05D40, 05C20, 05C69, 51A20

Klju£ne besede: ekstremalna kombinatorika, verjetnostna metoda, mnoºica brez vsot, turnir, dominantna mnoºica, prekriºno ²tevilo, incidence to£k in premic Keywords: extremal combinatorics, probabilistic method, sum-free set, tourna- ment, dominating set, crossing number, point-line incidence

1. Uvod

1.1. Ekstremalna kombinatorika. Ekstremalna kombinatorika je eno od podro-

£ij kombinatorike, je pa tesno povezana tudi z drugimi matemati£nimi podro£ji:

algebro, geometrijo, verjetnostjo in ra£unalni²tvom. Imenuje se ekstremalna, ker se najve£ ukvarja z vpra²anji, kako velik oziroma majhen je lahko neki matemati£ni objekt ali druºina objektov, ki zado²£a dolo£enim pogojem. Oglejmo si klasi£en primer problema ekstremalne kombinatorike [5].

Zgled 1.1 (Problem znancev in neznancev). Najve£ koliko ljudi lahko pride na za- bavo, £e ºelimo, da se v vsaki trojici gostov dva med seboj poznata ºe od prej, dva pa sta si neznanca? Pokaºimo, da v primeru treh, ²tirih ali petih povabljenih taka moºnost obstaja, £e pa je povabljenih ²est ali ve£ ljudi, to ni mogo£e. Problem mo- deliramo s polnim grafom, katerega vozli²£a predstavljajo goste na zabavi. Povezavo med vozli²£ema u in v pobarvamo rde£e, £e se gosta, ki ju predstavljata vozli²£i u in v, poznata ºe od prej, oziroma modro, £e se ²e ne poznata. Potem je pogoj, da se v vsaki trojici gostov dva med seboj poznata ºe od prej, dva pa sta si neznanca, o£itno izpolnjen natanko tedaj, ko v prirejenem grafu noben trikotnik nima vseh treh povezav pobarvanih z isto barvo. V grah K₁ in K₂ je ta pogoj na prazno izpolnjen, saj sploh ne vsebujeta trikotnikov. Na sliki 1 je prikazano, da je pogoj mogo£e z ustreznim barvanjem izpolniti tudi v grah K3, K4 inK5.

Slika 1. Pravilno barvanje povezav za problem znancev in neznancev v grah K3, K4 inK5.

Za grafK6pa dokaºimo, da v njem pri vsakem barvanju povezav z dvema barvama obstaja trikotnik z vsemi povezavami iste barve. Razmislek prikazuje tudi slika 2. Naj bo v eno od vozli²£ grafa. To vozli²£e je kraji²£e petih povezav in po Dirichletovem principu velja, da so vsaj tri izmed teh povezav pobarvane z isto barvo.

Brez ²kode za splo²nost lahko re£emo, da je ta barva rde£a. Druga kraji²£a treh povezav iste barve ozna£imo s £rkamix, y inz. ƒe je katera od povezav xy, xz in yz rde£a, ºe imamo trikotnik s samimi rde£imi povezavami. V nasprotnem primeru pa so povezave xy, xz inyz vse modre in torej sestavljajo trikotnik s samimi modrimi povezavami.

z

y

x v

?

Slika 2. Problem znancev in neznancev v grafu K₆ nima re²itve.

Graf K₆ je podgraf vsakega grafa K_n, n ≥ 7, zato za te grafe tudi najdemo trikotnik z enako pobarvanimi vsemi tremi povezavami. ♢ Za ekstremalno kombinatoriko je zna£ilno, da obsega zelo ²irok spekter razli£nih posameznih problemov, ki zahtevajo razli£ne pristope k re²evanju. Pri tem se upo- rablja ugotovitve in metode s podro£ja pre²tevanja, teorije mnoºic, verjetnosti in linearne algebre.

1.2. Verjetnostna metoda. Glavni vir tega dela diplomskega seminarja je knjiga Stasysa Jukne, Extremal combinatorics [2]. V njej se osredoto£imo na verjetnostno metodo re²evanja ekstremalnih kombinatori£nih problemov, predstavljeno v 3. in 18.

poglavju.

Bolj obi£ajno je, da v verjetnosti uporabljamo rezultate iz kombinatorike, tukaj pa sta vlogi obrnjeni. Verjetnost sama po sebi nas sicer na za£etku ne zanima, vendar se izkaºe kot koristno orodje, s katerim lahko doseºemo svoj cilj. šelimo pokazati, da znotraj kon£ne mnoºice nekih matemati£nih objektov obstaja objekt z iskanimi lastnostmi. V ta namen zado²£a pokazati, da je verjetnost obstoja takega objekta pozitivna. Oglejmo si preprost zgled tovrstnega sklepanja. Med n realnimi ²tevili zagotovo obstaja ²tevilo, ki ni manj²e od njihovega povpre£ja.

Lema 1.2. Naj bodo x₁, . . . , x_n ∈R in

x₁ +· · ·+x_n

n =a.

Potem obstaja tak j ∈ {1, . . . , n}, da velja x_j ≥a.

Dokaz. Predpostavimo nasprotno, da za vsak j ∈ {1, . . . , n} veljax_j < a. Tedaj je x1+· · ·+xn

n < a+· · ·+a

n = na

n =a.

Dobimo strogi neena£aj, kar je v nasprotju z denicijo ²tevila a. Predpostavka na za£etku dokaza je torej napa£na, zato obstaja tak j ∈ {1, . . . , n}, da je x_j ≥a. □ Na podoben na£in lahko pokaºemo, da med n realnimi ²tevili obstaja ²tevilo, ki ni ve£je od njihovega povpre£ja.

1.3. Glavne ideje dokazovanja. Ve£ina dokazov izrekov, ki so predstavljeni v diplomski nalogi, temelji na kateri od tukaj navedenih trditev. Prva je, da je pri-

£akovana vrednost linearni funkcional, torej veljata aditivnost in homogenost. Za uporabo te lastnosti v dokazih izrekov ekstremalne kombinatorike bo dovolj, da jo dokaºemo za kon£no mnogo diskretnih slu£ajnih spremenljivk, ki imajo ne le ²tevno, ampak celo kon£no zalogo vrednosti in kon£no domeno. Tako so vse obravnavane vsote kon£ne. Pomembno pa je, da za veljavnost trditve ni treba predpostaviti neodvisnosti slu£ajnih spremenljivk.

Denicija 1.3. Naj bo (M,2^M, P) verjetnostni prostor, kjer je

• M neprazna kon£na mnoºica elementarnih dogodkov,

• 2^M poten£na mnoºica mnoºice M (mnoºica vseh dogodkov, pri £emer ele- mentarni dogodek x∈M ozna£imo z dogodkom {x} ∈2^M),

• P : M →[0,1], kjer je∑︁

x∈MP(x) = 1, verjetnostna porazdelitev na M, ki jo za vseA⊆M s predpisomP(A) = ∑︁

x∈AP(x)raz²irimo na mnoºico vseh dogodkov2^M.

Vsako preslikavo f : M → R imenujemo slu£ajna spremenljivka na verjetnostnem prostoru (M,2^M, P). Priredimo ji pri£akovano vrednost E(f)∈R s predpisom

E(f) = ∑︂

x∈M

f(x)P(x).

Trditev 1.4. Naj bosta f, g:M →R slu£ajni spremenljivki na prostoru(M,2^M, P) in α∈R. Potem je

(1) E(αf) = αE(f),

(2) E(f+g) =E(f) +E(g). Dokaz. (1) E(αf) = ∑︂

x∈M

(αf)(x)P(x) = ∑︂

x∈M

αf(x)P(x) =αE(f) (2) E(f+g) = ∑︂

x∈M

(f +g)(x)P(x) = ∑︂

x∈M

(f(x) +g(x))P(x)

= ∑︂

x∈M

(f(x)P(x) +g(x)P(x)) = ∑︂

x∈M

f(x)P(x) + ∑︂

x∈M

g(x)P(x)

=E(f) +E(g) □

Posledica 1.5. Pri£akovana vrednost E je linearni funkcional na linearnem prostoru vseh slu£ajnih spremenljivk verjetnostnega prostora (M,2^M, P).

Druga trditev je neke vrste posplo²itev leme 1.2.

Trditev 1.6. Naj bo f slu£ajna spremenljivka na prostoru (M,2^M, P). ƒe za dani t ∈R velja vsaj ena od izjav

A) E(f)≥t,

B) P(f(x)≥t)>0,

potem obstaja tak x∈M, da velja f(x)≥t.

Dokaz. Da iz vsake od zgornjih neenakosti sledi obstoj elementa s f(x) ≥ t, doka- ºemo tako, da predpostavimo negacijo sklepa izreka (re£emo, da tak x ne obstaja), iz £esar izpeljemo negacijo izjav A) in B).

Denimo torej, da ne obstaja noben tak x∈M, za katerega jef(x)≥t. Potem za vse x∈M veljaf(x)< t. Tedaj je

a) E(f) = ∑︂

x∈M

f(x)·P(x)< ∑︂

x∈M

t·P(x) =t·1 =t;

b) P(f(x)≥t) =P(∅) = 0.

Sklep a) je negacija izjave A), sklep b) pa negacija izjave B). □ Iz E(f)≥tsledif(x)≥tza vsaj enx∈M, kar pomeni, da slu£ajna spremenljivka ne more biti povsod manj²a od svoje pri£akovane vrednosti. ƒisto analogno bi dokazali, da slu£ajna spremenljivka ne more biti povsod ve£ja od svoje pri£akovane vrednosti. Temu se re£e tudi Dirichletov princip, zapisan v jeziku verjetnosti.

1.4. Primeri. V naslednjih poglavjih so podrobneje predstavljeni nekateri primeri problemov ekstremalne kombinatorike, ki jih je moºno re²iti z uporabo verjetnostne metode. To so: izrek 2.3 o mnoºicah brez vsot, izreka 3.5 in 3.7 o turnirjih polnih usmerjenih grah, izrek 4.2 o dominantnih mnoºicah vozli²£, izrek 5.8 o prekriºnem

²tevilu grafa, izreki 6.2, 6.6 in 6.7 o incidencah to£k in premic v ravnini.

2. Mnoºice brez vsot

Prvi primer prihaja s podro£ja ²tevilskih mnoºic. Opazujemo poljubne kon£ne mnoºice celih ²tevil brez 0. Zanima nas, najve£ koliko ²tevil znotraj take mnoºice lahko ozna£imo, tako da vsota nobenih dveh ozna£enih ²tevil ni ozna£eno ²tevilo.

Denicija 2.1. Podmnoºico B neke aditivne grupe imenujemo mnoºica brez vsot,

£e za vsaka dva elementa x, y ∈B, ki sta lahko tudi enaka, veljax+y /∈B. Pokaºimo, da mnoºice brez vsot obstajajo in da so lahko poljubno velike.

Zgled 2.2. Vsaka podmnoºica B ⊂ Z, ki je sestavljena samo iz lihih ²tevil, je mnoºica brez vsot. To je res, ker je vsota dveh lihih ²tevil vedno sodo ²tevilo, ki pa ni vsebovano v B.

Naj bo zdaj n∈NinA={1,2, . . . ,2n}. Tedaj jeB ={n+ 1, n+ 2, . . . ,2n} ⊂A podmnoºica brez vsot mnoºice A, saj je vsota vsakih dveh ²tevil v B ve£ja od 2n,

torej ni vsebovana v B. ♢

Opomnimo, da je smiselno izvzeti ²tevilo 0 in opazovati samo podmnoºice B ⊂ Z\ {0}, saj 0ne more biti v mnoºici brez vsot. Za vsak x∈B je namre£ x+ 0 =x. Jasno je tudi, da je vsaka podmnoºicaB^′ mnoºice brez vsotB mnoºica brez vsot, saj za b₁, b₂ ∈B^′ veljab₁+b₂ ∈/ B, torej vsote b₁+b₂ tudi v B^′ ne more biti.

Iz zgleda 2.2 vidimo, da je za dano kon£no mnoºicoA ⊂Z\{0}moºno, da je njena najve£ja podmnoºica, ki je mnoºica brez vsot, kar celotna mnoºica A. Zanima nas, kako je z obstojem velikih podmnoºic brez vsot, £e je A poljubna kon£na mnoºica neni£elnih celih ²tevil. Odgovor nam poda Erd®sev izrek iz leta 1965.

Izrek 2.3 (Erd®s, 1965). Naj bo A ⊂ Z\ {0} mnoºica N neni£elnih celih ²tevil.

Potem A vsebuje mnoºico brez vsot B ⊆A, ki je mo£i |B|> N/3.

To je zelo zanimiv rezultat: v poljubni mnoºici neni£elnih celih ²tevil obstaja podmnoºica brez vsot, katere mo£ je vsaj ena tretjina mo£i prvotne mnoºice. V splo²nem jo je teºko najti, ni pa teºko dokazati, da obstaja.

Dokazovanje bo potekalo s pomo£jo verjetnostne metode, in sicer z uporabo li- nearnosti pri£akovane vrednosti in Dirichletovega principa za pri£akovano vrednost.

Pred dokazom izreka navedimo ²e dve lemi. Drugo, ki sledi iz prve, bomo uporabili pri dokazu izreka. Lemo 2.4 smo dokazali s pomo£jo spletne strani [3].

Lema 2.4. Obstaja neskon£no mnogo pra²tevil oblike 6k−1.

Dokaz. Izberimo poljubno naravno ²tevilo n > 3. Za dokaz neskon£nosti pra²tevil oblike 6k−1 je dovolj dokazati, da obstaja vsaj eno pra²tevilo, ve£je odn in oblike 6k −1. Naj bo P produkt vseh pra²tevil, manj²ih ali enakih n. Dve zaporedni naravni ²tevili sta si tuji, zato ²teviloP−1v razcepu ne vsebuje nobenega pra²tevila, manj²ega ali enakega n. Vsako pra²tevilo, ve£je od 3, je oblike 6k + 1 ali 6k −1.

’tevilo P je deljivo s6, saj je produkt vseh pra²tevil, manj²ih odn, torej tudi ²tevil 2 in 3. ’teviloP −1 zato ne more biti pra²tevilo oblike 6k+ 1 niti produkt samih pra²tevil oblike 6k+ 1, ker so vsi tak²ni produkti oblike6m+ 1, saj je

(6k+ 1)(6l+ 1) = 36kl+ 6k+ 6l+ 1 = 6(6kl+k+l) + 1.

Torej v razcepu P −1 zagotovo nastopa pra²tevilo, ve£je od n in oblike 6k−1. □ Lema 2.5. Obstaja neskon£no mnogo pra²tevil oblike 3k+ 2.

Dokaz. Po lemi 2.4 obstaja neskon£no pra²tevil oblike6k−1. Ta so vsa ºelene oblike 3l+ 2:

6k−1 = 3·2k−1 = 3·2k−3 + 2 = 3(2k−1) + 2 = 3l+ 2. □ Zdaj pa dokaºimo Erd®sev izrek.

Dokaz izreka 2.3. Vzemimo mnoºicoA ⊂Z\ {0} mo£iN. Poi²£imo ²tevilo iz mno- ºice A, ki ima najve£jo absolutno vrednost. Naj bo p pra²tevilo, ki je ve£je od dvakratnika absolutne vrednosti tega ²tevila, tj. p >2maxa∈A|a|, in je oblike3k+ 2. Tako pra²tevilo p zagotovo obstaja, saj lema 2.5 pove, da je pra²tevil take oblike neskon£no. Denirajmo mnoºico

S :={k+ 1, k+ 2, . . . , k+ (k+ 1)}

in glejmo nanjo kot na podmnoºico aditivne grupe Zp =Z3k+2 ostankov celih ²tevil pri deljenju sp. MnoºicaS je podmnoºica grupeZp brez vsot, saj zas₁, s₂ ∈Svelja

s₁+s₂ ∈ {2k+ 2, . . . ,4k+ 2} ≡ {2k+ 2, . . . ,3k+ 1} ∪ {0,1,2, . . . , k}(mod p), ta mnoºica pa je tuja S, zato s₁+s₂ ∈/ S. Za t∈Zp\ {0} denirajmo

A_t :={a∈A | at (mod p)∈S}.

Pokaºimo, da je A_t mnoºica brez vsot. Naj bostaa₁, a₂ ∈A_t. Sledia₁t(mod p)∈S in a₂t (mod p)∈S. S je brez vsot, zato

a1t+a2t (mod p)∈/S =⇒ (a1+a2)t (modp)∈/ S =⇒ a1+a2 ∈/ At. A_t je podmnoºica A. Potrebno je le ²e pokazati, da je za neki t mnoºica A_t mo£i ve£ kotN/3. Ker jeppra²tevilo, za poljuben a∈Azavzamejo ²tevilaatpo modulu p vse razli£ne vrednosti {1,2, . . . , p−1}, ko t prete£e {1,2, . . . , p−1}. To drºi: za t₁, t₂ ∈ {1,2, . . . , p−1} iz veljavnosti at₁ ≡ at₂ (mod p) sledi t1 ≡ t₂ (mod p), saj sta sia inptuji ²tevili in kongruenco lahko kraj²amo. Za razli£net dobimo razli£ne at in vseh je p−1, torej vsi moºni. Takih t, da je at po modulu pvsebovan v S, je

|S|. Iz tega za vsak a∈A sledi P(︁

at(modp)∈S)︁

= |S|

p−1 = k+ 1 3k+ 1. Oglejmo si pri£akovano vrednost mo£i mnoºice A_t.

E(|At|) = ∑︂

a∈A

1·P(a∈At) = ∑︂

a∈A

P(︁

at(mod p)∈S)︁

=N· k+ 1

3k+ 1 > N k+ 1 3k+ 3 = N

3. Slu£ajna spremenljivka |A_t| ne more biti povsod manj²a od svoje pri£akovane vre- dnosti, zato obstaja tak²en t, da je |At|> N/3. □

3. Turnirji

Predstavljajmo si tekmovanje mednigralci, kjer vsak od igralcev z vsakim drugim odigra po en dvoboj, ki se ne more kon£ati neodlo£eno. Situacijo lahko matemati£no predstavimo s polnim usmerjenim grafom, ki ga poimenujemo turnir. Formalna denicija se glasi:

Denicija 3.1. Naj boT = (V, A)usmerjen graf brez zank, v katerem za vsaki dve razli£ni vozli²£i x, y ∈ V natanko eden od usmerjenih parov (x, y), (y, x) pripada mnoºici usmerjenih povezav A. Tak²en graf imenujemo turnir.

Vsako vozli²£e predstavlja enega igralca, usmerjena povezava med dvema vozli-

²£ema pa izid dvoboja med igralcema v kraji²£ih. Po dogovoru je pu²£ica usmerjena proti igralcu, ki je tekmo izgubil. Povezava (x, y) torej pomeni, da je igralec x premagal igralca y.

Zgled 3.2. Slika 3 prikazuje turnir med ²tirimi igralci. V ={a, b, c, d}, A={(a, b), (c, a),(a, d),(c, b),(b, d),(c, d)}.

a b

d c

Slika 3. Turnir T = ({a, b, c, d}, {(a, b),(c, a),(a, d),(c, b),(b, d),(c, d)}).

Igralec c je zmagal dvoboje z vsemi ostalimi tremi igralci. Igralec d je bil trikrat

premagan. Igralec a je premagal igralca b. ♢

3.1. Hamiltonove poti v turnirjih. V tem razdelku je predstavljen izrek mate- matika T. Szele iz leta 1943 o ²tevilu Hamiltonovih poti v turnirjih. Dokaz izreka velja za prvo uporabo verjetnostne metode v kombinatoriki.

Denicija 3.3. Naj bo T = (V, A) turnir z n igralci. Hamiltonova pot turnirja T je taka permutacija igralcev (x₁, x₂, . . . , x_n), da za vsak i ∈ {1,2, . . . , n−1} velja (xi, xi+1) ∈A; to pomeni, da je prvi igralec v permutaciji premagal drugega, drugi tretjega, in tako dalje do igralca xn−1, ki je premagal igralcaxn.

Turnir iz zgleda 3.2 ima Hamiltonovo pot (c, a, b, d).

Lema 3.4. V vsakem turnirju obstaja vsaj ena Hamiltonova pot.

Dokaz. Dokaz uporabi indukcijo po ²tevilu igralcev v turnirju.

Osnova indukcije (n = 1): V tem primeru je (x₁) Hamiltonova pot.

Denimo zdaj, da za vsak turnir velikosti n−1 obstaja Hamiltonova pot. Naj bo T turnir velikosti n in x eden od igralcev. Po indukcijski predpostavki v turnirju T − x obstaja neka Hamiltonova pot (x₁, x₂, . . . , xn−1). Lo£imo dva primera, in sicer primer, ko je igralec x premagal vse ostale igralce, in primer, ko obstaja tak i ∈ {1,2, . . . , n−1}, da je x_i premagal igralca x. V prvem primeru igralca x pre- prosto dodamo na za£etek permutacije in tako je (x, x₁, x₂, . . . , xn−1) Hamiltonova pot turnirja velikosti n.

x₁ x₂ x₃ · · · xn−1

x

Slika 4. Nova Hamiltonova pot z dodanim igralcem, ki je premagal vse druge.

x₁ x₂ · · · x_j x_j+1 x_j+2 · · · xn−1

x

Slika 5. Nova Hamiltonova pot z dodanim igralcem, ki ga je prema- gal igralec x_j, igralci x_i, i > j pa ne.

V drugem primeru naj boj = max{i∈ {1,2, . . . , n−1}|xi je premagal igralcax}. Nova Hamiltonova pot je tedaj (x₁, x₂, . . . , x_j, x, x_j+1, . . . , x_n−1).

Slika 4 prikazuje le povezave stare Hamiltonove poti in povezave igralca x, slika 5 pa le povezave stare Hamiltonove poti in povezave igralca x z igralcix_j,x_j+1, . . ., xn−1. Novi Hamiltonovi poti sta predstavljeni s £rnimi usmerjenimi povezavami. □ Obstajajo turnirji z natanko eno Hamiltonovo potjo. Dobimo jih lahko na primer na naslednji na£in: £e je(x₁, x₂, . . . , x_n)Hamiltonova pot in je vsak igralec premagal vse igralce z vi²jim indeksom v tej Hamiltonovi poti, je dana Hamiltonova pot edina moºna. Na sliki 6 je prikazan primer turnirja z eno samo Hamiltonovo potjo za n = 6.

x₁ x₂

x₃ x₄ x₅

x₆

Slika 6. Turnir z eno samo Hamiltonovo potjo.

Zdaj pa sledi izrek, ki bo povedal nekaj o obstoju turnirjev z ve£jim ²tevilom Hamiltonovih poti.

Izrek 3.5 (Szele, 1943). Obstaja turnir znigralci, ki ima vsajn!/2ⁿ⁻¹ Hamiltonovih poti.

V tabeli 1 je za turnirje velikosti od 1 do 10 prikazana vrednost n!/2ⁿ⁻¹.

n 1 2 3 4 5 6 7 8 9 10

n!/2ⁿ⁻¹ 1 1 1,5 3 7,5 22,5 78,75 315 1417,5 7087,5 Tabela 1. Vrednost n!/2ⁿ⁻¹ za n∈ {1,2, . . . ,10}.

Izrek pravi, da na primer lahko najdemo turnir velikosti 5, ki ima vsaj 8 (kar je zgornji celi del ²tevila 7,5) Hamiltonovih poti. Slika 7 prikazuje en tak²en turnir in vseh 15Hamiltonovih poti tega turnirja.

Dokaz izreka 3.5. Vzemimo poljuben turnir T = (V, A) z n igralci, dobimo ga de- nimo tako, da je izid vsake tekme med dvema igralcema dolo£en z metom po²tenega

kovanca in so meti med seboj neodvisni. Deniramo slu£ajno spremenljivko X kot

²tevilo Hamiltonovih poti turnirja T. Za vsako permutacijo π = (x₁, x₂, . . . , x_n) deniramo slu£ajno spremenljivko X_π kot indikator dogodka, da je permutacija π Hamiltonova pot turnirja T. Potem je X = ∑︁

πX_π. Pri£akovana vrednost slu-

£ajne spremenljivke X_π je enaka verjetnosti, da je naklju£no izbrana permutacija Hamiltonova pot, kar je 2⁻⁽ⁿ⁻¹⁾, saj je za vsak i∈ {1,2, . . . , n−1} verjetnost, da je (xi, xi+1)∈ A, enaka 1/2. Moºnih je n!razli£nih permutacij. Upo²tevamo ²e, da je pri£akovana vrednost linearni funkcional, in dobimo

E(X) = E (︄

∑︂

π

X_π )︄

=∑︂

π

E(X_π) = n!/2ⁿ⁻¹.

Vemo, da slu£ajna spremenljivka ne more biti povsod strogo manj²a od svoje pri£ako- vane vrednosti. Sledi, da obstaja tak turnirT znigralci, ki ima vsaj E(X) =n!/2ⁿ⁻¹

Hamiltonovih poti. □

Slika 7. Turnir s petimi igralci, ki ima 15 Hamiltonovih poti.

3.2. Lastnost P_k. Pri turnirjih lahko opazujemo obstoj igralca, ki je premagal vse igralce v neki izbrani podmnoºici igralcev, v odvisnosti od mo£i izbrane podmnoºice.

Denicija 3.6. Turnir ima lastnost Pk, £e za vsako podmnoºico igralcev mo£i k med preostalimi igralci obstaja igralec, ki je premagal vse igralce v tej podmnoºici.

Formalno: turnir T = (V, A) ima lastnost P_k, £e za vsako podmnoºico S ⊆ V, za katero je |S|=k, obstaja taky∈V, y /∈S, da je (y, x)∈A za vsak x∈S.

Oglejmo si prisotnost oziroma odsotnost lastnosti P₁ v nekaj majhnih turnirjih.

Turnir z dvema igralcema ne more imeti lastnosti P₁, saj vedno eden od igralcev ostane nepremagan. Turnir s tremi igralci lahko ima, lahko pa nima lastnosti P1.

Levi od turnirjev s ²tirimi igralci na sliki 8 nima lastnosti P₁, saj za igralca c ne obstaja noben igralec, ki ga je premagal. Desni turnir s ²tirimi igralci pa ima lastnost P₁.

a b a b

c

a b

d c

a b

d c

Slika 8. Primeri turnirjev, ki so nanizani od leve proti desni izme- ni£no z odsotno oziroma prisotno lastnostjo P1.

Razi²£imo, kako je z lastnostjo P2 v turnirjih s ²tirimi igralci. Da bi veljala lastnostP2, mora za vsako mnoºico igralcev mo£i2obstajati neki tretji igralec, ki je premagal oba igralca v tej mnoºici. V pomo£ nam je slika 9. Brez ²kode za splo²nost si najprej izberemo mnoºico {a, d} in igralca c, ki je premagal igralca a in d. Nato izberemo mnoºico {c, d}. Igralec a ni premagal igralca c, zato ostane le ²e igralec b; naj torej b premaga cin d. Zdaj pa poi²£imo igralca, ki je premagal oba igralca v mnoºici {a, b}. Takega igralca ni. Torej ne obstaja taka razporeditev zmag in porazov, da bi imel turnir s ²tirimi igralci lastnost P₂.

a b

d c

a b

d c

a b

d c

Slika 9. Turnir s ²tirimi igralci, ki ima lastnost P₂, ne obstaja.

Lahko bi razmi²ljali ²e naprej na posameznih primerih. ƒe ima neki graf na primer lastnost P₄, to pomeni, da za vsako podmnoºico vozli²£ S ={x₁, x₂, x₃, x₄} obstaja vozli²£e y /∈ S, tako da so pu²£ice obrnjene od y proti vozli²£em iz S, torej (y, x₁),(y, x₂),(y, x₃),(y, x₄)∈A. Izrek 3.7 nam da zagotovilo obstoja grafa z lastnostjo P_k za neki k, £e je len dovolj velik glede nak.

Izrek 3.7 (Erd®s, 1963). ƒe je n ≥k²2^k+1, potem obstaja turnir z n igralci, ki ima lastnost P_k.

Tabela 2 prikazuje meje zaniz izreka pri posameznihk ∈ {1, . . . ,10}. Izrek pravi, da na primer za turnir n ≥ 512 igralcev lahko najdemo tako razporeditev zmag in porazov, da za vsake ²tiri izbrane igralce obstaja igralec izmed preostalih n−4, ki je premagal vse te ²tiri igralce.

Nekaj delov dokaza, ki ne uporabljajo verjetnostne metode, si pripravimo vnaprej.

Lema 3.8. Za vsak k ≥2 in n≥k²2^k+1 velja (︃n

k )︃(︄

1− (︃1

2

)︃k)︄n−k

< n^k

k!e^{−(n−k)2−k}.

k 1 2 3 4 5 6 7 8 9 10 k²2^k+1 4 32 144 512 1600 4608 12544 32768 82944 204800

Tabela 2. Vrednost k²2^k+1 zak ∈ {1,2, . . . ,10}.

Dokaz. Za k ≥2velja (︁_n

k

)︁= _k!(n−k)!^n! = n(n−1)···(n−k+1) k! < ⁿ_k!^k.

Vemo, da je limm→∞(1−m⁻¹)^−m = e. Zaporedje je strogo padajo£e, zato sledi (1−m⁻¹)^−m > e oziroma (1−m⁻¹)^m < e⁻¹. Zdaj pa m nadomestimo z 2^k in obe strani potenciramo z (n−k)2^−k:

(︁1−2^−k)︁2^k

< e⁻¹ =⇒ (︁

1−2^−k)︁^n−k

< e^{−(n−k)2−k}. □ Lema 3.9. Za k≥2 in f(x) = e^x2−x je f(k)< k!.

1 2 3

2 4 6

f(x) x y

Slika 10. f(x) = e^x2−x < x! zax∈N, x≥2. Dokaz. Odvod funkcije f(x) je

f^′(x) = e^x2−x(2^−x+x(−2^−xln 2)) = 2^−xe^x2−x(1−xln 2)

in je enak 0 priζ = 1/ln 2≈1,442695. Pozitiven je prix < ζ in negativen prix > ζ. Torej f(x) pri x=ζ zavzame svoj maksimum f(ζ)≈1,700186, pri x > ζ pa pada.

Zato je f(k)<1,700186< k!za vse k≥2. □ Lema 3.10. Za vsak k ≥2 velja 2 lnk+ (k+ 1) ln 2−2k <0.

Dokaz. Naj bo h(x) = 2 lnx+ (x+ 1) ln 2−2x (slika 11). Odvod h^′(x) = 2

x+ ln 2−2

je enak 0 pri ϑ = _{2−ln 2}² ≈ 1,530394 in je negativen pri x > ϑ. Vrednost h(ϑ) ≈

−0,455802je negativna, torej je h(k)<0 za vse k ≥2. □ Lema 3.11. Za vsak k ≥2 in n≥k²2^k+1 je n^ke^−n2−k <1.

Dokaz. Deniramo g_k(x) =x^ke^−x2−k. Odvod

g_k^′(x) =kx^k−1e^−x2−k +x^ke^−x2−k(−2^−k) =e^−x2−kx^k−1(k−2^−kx)

= 2^−ke^−2−kxx^k−1(︁

2^kk−x)︁

0,5 1 1,5 2 2,5 3

−6

−4

−2 h(x)

x y

Slika 11. Za vsak x≥2velja h(x) = 2 lnx+ (x+ 1) ln 2−2x <0.

je pri η = 2^kk enak 0 in je negativen pri x > η. Sledi, da pri poljubnem k ≥ 2 vrednosti g_k(n) =n^ke^−n2−k padajo, £e jen > η inn pove£ujemo. Trdimo, da je pri x =k²2^k+1 vrednost gk(x) manj²a od 1. Kar trdimo, preoblikujemo v ekvivalentno neena£bo:

k^2k2^k(k+1)e^−2k2 <1

k^2k2^k(k+1) < e^2k2 /ln lnk^2k+ ln 2^k(k+1) <lne^2k2 2klnk+k(k+ 1) ln 2<2k² 2 lnk+ (k+ 1) ln 2−2k <0

To pa iz leme 3.10 vemo, da je res. □

Dokaz izreka 3.7. Nadaljevanje dokaza bo delovalo zak ≥2, zato zak = 1dokaºemo posebej. V tem primeru izrek pravi: ƒe jen≥4, potem obstaja turnir znigralci, ki ima lastnost P₁. Obstaja taka razporeditev zmag in porazov, da je vsakega igralca premagal vsaj eden izmed ostalih igralcev, na primer prvi premaga drugega, drugi tretjega, . . .,n-ti prvega.

Od sedaj naprej naj bo k ≥ 2. Vzemimo poljuben turnir T = (V, A) z n igralci, dobimo ga denimo tako, da je izid vsake tekme med dvema igralcema dolo£en z metom po²tenega kovanca in so meti med seboj neodvisni. Naj bo n ≥ k²2^k+1. Naj bo D dogodek, da ima turnir T lastnost P_k. ƒe dokaºemo P(D)>0, se bomo prepri£ali, da turnir z n igralci, ki ima lastnost P_k, obstaja.

ZD_S ozna£imo dogodek, da za mnoºicoS, v kateri jek igralcev, ne obstaja noben tak y /∈S, ki je premagal vse igralce v S. DogodekD se zgodi natanko tedaj, ko se ne zgodi nobeden od dogodkov D_S, S ⊆V,|S|=k. Velja

D=

⎛

⎝

⋃︂

S⊆V,|S|=k

D_S

⎞

⎠

C

in zato

P(D) =P

⎛

⎝

⎛

⎝

⋃︂

S⊆V,|S|=k

D_S

⎞

⎠

C⎞

⎠= 1−P

⎛

⎝

⋃︂

S⊆V,|S|=k

D_S

⎞

⎠.

Iskana verjetnostP(D)bo strogo ve£ja od0natanko tedaj, ko boP (︂

⋃︁

S⊆V,|S|=kD_S)︂

strogo manj od 1. V splo²nem velja pravilo, da je verjetnost unije dogodkov manj²a ali enaka vsoti verjetnosti teh dogodkov, zato

P

⎛

⎝

⋃︂

S⊆V,|S|=k

DS

⎞

⎠≤ ∑︂

S⊆V,|S|=k

P (DS). Vseh moºnih mnoºic S je (︁_n

k

)︁, saj je toliko izborov k elementov izmed n elementov.

Verjetnosti posameznih dogodkov DS so si med seboj enake zaradi simetri£nosti problema. DogodekD_S je enak preseku dogodkov, da posamezeny /∈S ni premagal vseh elementov izS, ti pa so med seboj neodvisni. Verjetnost, day /∈S ni premagal vseh elementov iz S, je 1−P(y je premagal vse iz S) = 1−(¹₂)^k. Moºnihy jen−k. Iz tega sledi

P(D_S) = (︄

1− (︃1

2

)︃k)︄n−k

in ∑︂

S⊆V,|S|=k

P(D_S) = (︃n

k )︃(︄

1− (︃1

2

)︃k)︄n−k

. Za k≥2 nam lema 3.8 pove, da velja

(︃n k

)︃(︄

1− (︃1

2

)︃k)︄n−k

< n^k

k!e^{−(n−k)2−k}.

ƒe ozna£imo f(x) =e^x2−x, dobimo n^k

k!e^{−(n−k)2−k} =n^ke^−n2−kf(k) k! . Z upo²tevanjem leme 3.9 sledi

n^ke^−n2−kf(k)

k! < n^ke^−n2−k.

To pa je po lemi 3.11 za k ≥2in n≥k²2^k+1 manj²e od 1, kar smo ºeleli dokazati.

Povzemimo ²e enkrat sklepanje skozi celoten dokaz:

1−P(D) =P

⎛

⎝

⋃︂

S⊆V,|S|=k

D_S

⎞

⎠≤ ∑︂

S⊆V,|S|=k

P (D_S) = (︃n

k )︃(︄

1− (︃1

2

)︃k)︄n−k

< n^k

k!e^{−(n−k)2−k} < n^ke^−n2−k <1, za vsak k≥2 in vsak n≥k²2^k+1.

Pogledamo za£etek in konec in dobimo P(D) > 0, to pa je natanko tisto, kar smo ºeleli. Iz tega namre£ sledi, da za n ≥k²2^k+1 obstaja turnir z n igralci, ki ima

lastnost P_k. □

4. Dominantne mnoºice vozli²£

V tem poglavju predstavimo dokaz Alonovega izreka o dominantnih mnoºicah vozli²£ v enostavnih neusmerjenih grah.

Denicija 4.1. Dominantna mnoºica vozli²£ grafa G = (V, A) je taka mnoºica S ⊆ V, da je vsako vozli²£e v ∈ V vsebovano v S ali pa je sosednje vsaj enemu vozli²£u iz S.

V grafu, ki nima nobene povezave, je edina moºna dominantna mnoºica vozli²£ kar mnoºica vseh vozli²£. Po drugi strani je v polnem grafu vsaka neprazna podmnoºica vozli²£ S ºe dominantna mnoºica vozli²£, saj je vsako vozli²£e povezano z vsakim drugim, zato je vsebovano v S ali sosednje vsaj enemu vozli²£u v S (pravzaprav je sosednje vsem vozli²£em v S).

Na sliki 12 so narisani trije gra, z rde£o so ozna£ene njihove moºne dominantne mnoºice, in sicer poln graf K6 z dominantno mnoºico mo£i 1, graf z 10 vozli²£i, ki mu lahko ozna£imo dominantno mnoºico mo£i 3, in graf brez povezav, v katerem morajo biti v dominantni mnoºici prav vsa vozli²£a.

Jasno je, da je mnoºica vseh vozli²£ vedno dominantna mnoºica vozli²£. Alonov izrek nam da oceno za poljuben graf, s kako malo vozli²£i, £e jih prav izbiramo, je zagotovo moºno sestaviti dominantno mnoºico vozli²£. Ocena je odvisna od ²tevila vozli²£ grafa in od stopnje vozli²£a, ki ima med vsemi vozli²£i najmanj²o stopnjo.

Slika 12. Trije primeri grafov z rde£e ozna£enimi dominantnimi mnoºicami vozli²£.

Izrek 4.2 (Alon, 1990). Naj bo G = (V, A) graf z n vozli²£i, naj bo d najmanj²a vrednost stopnje katerega koli vozli²£a grafa G. Potem v G obstaja dominantna mnoºica vozli²£ mo£i manj²e ali enake n^1+ln(d+1)_d+1 .

n\d 1 2 3 4 5 6 7

2 1

3 2 2

4 3 2 2

5 4 3 2 2

6 5 4 3 3 2

7 5 4 4 3 3 2

8 6 5 4 4 3 3 3

9 7 6 5 4 4 3 3

10 8 6 5 5 4 4 3

11 9 7 6 5 5 4 4

12 10 8 7 6 5 5 4 13 11 9 7 6 6 5 5 14 11 9 8 7 6 5 5 15 12 10 8 7 6 6 5

Tabela 3. Vrednost ⌊n^1+ln(d+1)_d+1 ⌋ zan ∈ {2,3, . . . ,15} ind∈ {1,2, . . . ,7}.

V tabeli 3 je izra£unana vrednost n^1+ln(d+1)_d+1 za nekaj majhnihn ind, zaokroºena na spodnji celi del. Izrek 4.2 trdi, da na primer v katerem koli grafu s 15 vozli²£i, ki so vsa povezana z vsaj sedmimi drugimi, zagotovo obstaja takih pet vozli²£, da bodo vsa preostala vozli²£a sosednja vsaj enemu od najdenih petih.

Dokaz izreka 4.2. Zad= 0izrek dokaºemo posebej. Izrek tedaj trdi, da v poljubnem grafu obstaja dominantna mnoºica mo£i manj²e ali enake n^1+ln(1)₁ =n. To drºi, saj je mnoºica vseh n vozli²£ grafa vedno tudi dominantna.

V preostalem delu dokaza predpostavimo d≥1. Izberemo verjetnostp∈(0,1)in sestavimo naklju£no podmnoºico vozli²£ S ⊆ V, tako da vsako vozli²£e neodvisno od ostalih uvrstimo v S z verjetnostjop. Ko imamo mnoºicoS, deniramo mnoºico T ⊆V tistih vozli²£, ki niso vS in niso sosednja nobenemu elementu iz S. Tako bo mnoºica S∪T dominantna mnoºica vozli²£, saj so vsa vozli²£a izven S∪T sosednja kak²nemu vozli²£u iz S ⊆S∪T. Zdaj je dovolj le ²e pokazati, da je za pravo izbiro verjetnostip pri£akovana vrednost mo£i mnoºice S∪T manj²a ali enaka n^1+ln(d+1)_d+1 . Mnoºica T je izbrana tako, da nobeno vozli²£e iz S ne more biti v T. Torej sta S in T disjunktni, zato je |S∪T| =|S|+|T| in tudi E(|S∪T|) =E(|S|) +E(|T|). Poljubno vozli²£e v z verjetnostjo p pripadaS, vseh vozli²£ je n. Sledi

E(|S|) =∑︂

v∈V

1·P(v ∈S) = np.

Izra£unajmo ²e E(|T|): Da bov vsebovan vT, mora veljati, da nitiv niti katero koli od njegovih sosednjih vozli²£ ni v S. Sosednjih vozli²£ ima po predpostavki izreka vsaj d, zato jeP(v ∈T)≤(1−p)^d+1 in velja

E(|T|) = ∑︂

v∈V

1·P(v ∈T)≤n·(1−p)^d+1.

Za vsak x ∈ R je 1−x ≤ e^−x, saj ima g(x) = e^−x+x−1 ni£lo v x = 0, odvod g^′(x) = −e^−x+1pa tudi ni£lo vx= 0, levo od ni£le je negativen, desno pa pozitiven.

Minimum funkcije g je vrednost 0 in neenakost velja. Za laºjo predstavo je graf funkcije g(x)narisan na sliki 13. Od tod sledi 1−p≤e^−p in(1−p)^d+1 ≤e^−p(d+1). Oceni pri£akovanih vrednosti se²tejemo in dobimo

E(|S∪T|)≤np+ne^−p(d+1).

Vzemimo p= ^ln(d+1)_d+1 . Res je p∈(0,1)za vsak d ∈N, saj je funkcija f(x) = ^ln(x+1)_x+1 pozitivna zax∈(0,∞), padajo£a zax > e−1≈1,718in manj²a od1tudi prix= 1 in x= 2: f(1) = ^{ln 2}₂ ≈0,347,f(2) = ^{ln 3}₃ ≈0,366, f^′(x) = ^1−ln(x+1)_(x+1)2 <0 za vsakx >

e−1. V pomo£ je slika grafa funkcije f(x) na sliki 13. Velja torej E(|S∪T|)≤np+ne^−p(d+1)

=n

(︃ln(d+ 1)

d+ 1 +e^{−ln(d+1)d+1 (d+1)} )︃

=n

(︃ln(d+ 1) d+ 1 + 1

d+ 1 )︃

=n1 + ln(d+ 1) d+ 1 .

Slu£ajna spremenljivka zagotovo lahko zavzame vrednost, manj²o ali enako svoji pri£akovani vrednosti, zato mora obstajati tak izbor mnoºice S, da je |S ∪T| ≤

n^1+ln(d+1)_d+1 in torej v grafu G obstaja dominantna mnoºica mo£i manj²e ali enake

n^1+ln(d+1)_d+1 . □

−1,5 −1 −0,5 0,5 1 1,5 1

2 3

g(x)

x y

0,5 1 1,5 2 2,5 3

−0,1 0,1 0,2 0,3

f(x)

x y

Slika 13. Grafa funkcij g(x) =e^−x+x−1in f(x) = ^ln(x+1)_x+1 . 5. Prekriºno ²tevilo

Grafe lahko nari²emo v ravnini. Zanima nas, kdaj lahko to storimo tako, da se povezave ne kriºajo med seboj oziroma koliko najmanj kriºanj je potrebnih pri posameznem grafu. ƒe se dve povezavi sekata v skupnem vozli²£u, tega ne ²tejemo kot kriºanje povezav. Neformalno re£emo, da je graf ravninski, £e ga lahko nari²emo v ravnini tako, da se povezave sekajo kve£jemu v skupnih kraji²£ih. Prekriºno ²tevilo grafa je minimalno ²tevilo kriºanj povezav grafa, narisanega v ravnini.

Pri Diskretni matematiki 1 smo govorili o grah v ravnini, ki jih lahko priredimo le ravninskim grafom, in sicer tako, da do kriºanj povezav ne prihaja. Tu pa bomo obravnavali predvsem grafe, ki niso ravninski. Da ne bo prihajalo do zamenjav, namesto izraza graf v ravnini uporabljamo izraz v ravnino narisan graf.

Denicija 5.1. Jordanov lok v ravnini R² je zaloga vrednosti zvezne injekcije ϕ : [0,1]→R². To£ki ϕ(0) inϕ(1) sta kraji²£i tega loka,ϕ((0,1)) je notranjost loka.

Denicija 5.2. V ravnino narisan graf Gje par (V, A), za katerega velja

• V ⊆R², V ̸=∅, V je kon£na mnoºica to£k,

• A je kon£na mnoºica Jordanovih lokov s kraji²£i izV,

• vsaka dva razli£na Jordanova lokaa₁, a₂ ∈A se sekata kve£jemu v eni to£ki,

• nobena to£ka v ∈V ne leºi v notranjosti kak²nega Jordanovega loka a∈A. Naj bo G= (V, A) v ravnino narisan graf. Priredimo mu (abstraktni) graf G^′ = (V^′, A^′) tako, da je V^′ = V in A^′ ={{x, y} | ∃a ∈ A : x, y sta kraji²£i a}. Oznake uporabljamo nekoliko ohlapno in v nadaljevanju tako za graf v abstraktnem smislu kot za pripadajo£ v ravnino narisan graf uporabljamo isto oznako G= (V, A). Denicija 5.3. Graf G = (V, A) je ravninski, £e ga je moºno narisati v ravnino tako, da za vsaki razli£ni povezavi a1, a2 ∈A veljaa1∩a2 ⊆V.

Kaj pa, £e graf ni ravninski?

Denicija 5.4. Kriºanje razli£nih povezav a₁, a₂ ∈ A v ravnino narisanega grafa G= (V, A)je a1∩a2, £e ta presek ni element V.

Denicija 5.5. Prekriºno ²tevilo grafa G je najmanj²e moºno ²tevilo kriºanj po- vezav v ravnino narisanega grafa G, gledano med vsemi moºnostmi, kako graf G narisati v ravnino. Prekriºno ²tevilo grafa G ozna£imo s cr(G).

Graf G je torej ravninski natanko tedaj, ko velja cr(G) = 0. Vpra²amo se, kako veliko je lahko prekriºno ²tevilo v odvisnosti od ²tevila vozli²£nin ²tevila povezave. Pri iskanju odgovora si bomo pomagali s trditvijo 5.6 za ravninske grafe, ki smo jo spoznali pri Diskretni matematiki 1. Trditev najdemo tudi v knjigi [1] kot posledico 4.2.8 na strani 75.

Trditev 5.6. Za ravninski graf z n vozli²£i inepovezavami, n ≥3, veljae≤3n−6. Od tod izpeljemo oceno za prekriºna ²tevila grafov, ki niso nujno ravninski. Naj ima graf G n ≥ 3 vozli²£ in e povezav. Njegovo prekriºno ²tevilo naj bo cr(G). Nari²imo ga v ravnino tako, da je kriºanjcr(G). ƒe mu povsod, kjer se dve povezavi kriºata, eno odstranimo, dobimo ravninski graf zn vozli²£i ine−cr(G)povezavami.

Zanj po trditvi 5.6 velja e −cr(G) ≤ 3n −6. Neena£bo preuredimo v cr(G) ≥ e−3n+ 6. Neenakost je veljavna tudi, £e na desni od²tejemo 6, s tem pa dobimo oceno cr(G)≥e−3n, ki velja tudi za vse moºne primeren <3, to so(n = 1, e= 0), (n = 2, e= 0)in(n= 2, e= 1), ki imajo vsi prekriºno ²tevilo enako0. Tako dobimo Trditev 5.7. Za poljuben graf G z n vozli²£i in e povezavami velja

cr(G)≥e−3n.

Trditev 5.7 nam da ºe prvo oceno za prekriºno ²tevilo grafa z n vozli²£i in e povezavami. Za grafe, v katerih je e ≥ 4n, pa lahko z ra£unanjem pri£akovanih vrednosti pokaºemo, da velja tudi:

Izrek 5.8 (Neena£ba prekriºnih ²tevil). Naj bo G graf z n vozli²£i in e ≥4n pove- zavami. Potem velja

cr(G)≥ e³ 64n².

Dokaz. Vzemimo graf G= (V, A)in ga nari²imo v ravnino tako, da ima slika cr(G) kriºanj povezav. Priredimo mu podgraf H = (V_H, A_H), in sicer tako, da neodvisno nekatera vozli²£a grafaGobdrºimo, druga pa odstranimo. Verjetnost, da posamezno vozli²£e obdrºimo, naj bo p. Ohranimo tudi vse povezave, katerih obe kraji²£i smo ohranili. Ozna£imo ²tevilo vozli²£ grafa H z nH in ²tevilo povezav z eH. Po trditvi 5.7 za graf H velja

cr(H)≥eH −3nH.

Spomnimo se, da smo graf H dobili na slu£ajen na£in, zato so cr(H), n_H in e_H slu£ajne spremenljivke. Velja

E[cr(H)]≥E[e_H]−3E[n_H].

Vsako vozli²£e iz G smo obdrºali z verjetnostjo p, zato E[n_H] =∑︂

v∈V

P(v ∈V_H) =∑︂

v∈V

p=np.

Povezavo smo obdrºali, £e smo obdrºali obe vozli²£i, med katerima poteka, torej E[e_H] =∑︂

a∈A

P(a∈A_H) = ∑︂

a={v₁,v2}∈A

P(v₁ ∈V, v₂ ∈V) = ep².

Ko smo odstranili nekatera vozli²£a in s tem nekatere povezave, so izginila tudi nekatera kriºanja povezav. ’tevilo kriºanj, ki so ostala, ozna£imo zx_H. Morda jeH moºno narisati tudi tako, da je kriºanj manj, zato je E[x_H]≥E[cr(H)]. Posamezno kriºanje iz Gje ostalo po odstranitvi vozli²£ le, £e sta ostali povezavi, ki se kriºata, torej so ostala ²tiri vozli²£a.

E[x_H] = ∑︂

kkriºanje vG

P(k kriºanje v H) = cr(G)p⁴ Ko vse to zdruºimo, dobimo

E[xH]≥E[cr(H)]≥E[eH]−3E[nH], cr(G)p⁴ ≥ep²−3np.

Po predpostavki izreka je e ≥ 4n. Lahko vzamemo p = ⁴ⁿ_e . Iz dobljene neenakosti izrazimo cr(G), ki nas zanima.

cr(G)≥ e p² − 3n

p³ cr(G)≥ e

16n² e²

− 3n

64n³ e³

cr(G)≥ e³

64n² □

6. Incidence to£k in premic v ravnini

V geometriji imamo kar nekaj na£inov, kako za premicopin to£kotizrazimo, kar s simboli zapi²emo t∈p. Na primer: to£ka je na premici, to£ka leºi na premici, to£ka pripada premici, premica vsebuje to£ko, premica poteka skozi to£ko. V resnici gre za relacijo, pravimo ji relacija incidence to£k in premic. Vpeljemo pojem inciden£na struktura, kar je povzeto po formalni deniciji v £lanku [4].

Denicija 6.1. Inciden£na struktura je trojica (T, P, I), kjer jeT mnoºica to£k,P mnoºica premic in I relacija, za katero velja I ⊆ T ×P, (t, p) ∈ I ⇐⇒ t ∈ p. Z besedami, to£ka tje v relacijiI s premicopnatanko tedaj, ko to£kat leºi na premici p. Relacija I je relacija incidence to£k in premic. Mo£ relacije I je ²tevilo incidenc dane inciden£ne strukture.

V evklidski ravnini skozi dve razli£ni to£ki obstaja natanko ena premica in vsaki dve razli£ni premici imata najve£ eno skupno to£ko. Zanimivo vpra²anje je, kaj lahko povemo o ²tevilu incidenc pri danem ²tevilu to£k in ²tevilu premic. Spodnja meja je ni£, saj lahko premice in to£ke v ravnino postavimo tako, da nobena to£ka ne leºi na nobeni od premic. O zgornji meji govorita izreka 6.2 in 6.6 v nadaljevanju.

Izrek 6.2 (Szemerédi-Trotterjev izrek, 1983). Naj bo T mnoºica n razli£nih to£k in P mnoºica mrazli£nih premic v ravnini. Potem je ²tevilo incidenc navzgor omejeno s 4(mn)^2/3+m+ 4n.

Dokaz. Ozna£imo z x = |{(t, p) ∈ T × P | t ∈ p}| ²tevilo incidenc pripadajo£e inciden£ne strukture (T, P, I).

Inciden£ni strukturi(T, P, I)priredimo v ravnino narisan grafGtako, da mnoºica to£k T postane mnoºica vozli²£ grafa, povezave grafa G pa so vse daljice, katerih kraji²£i sta sosednji to£ki iz T na eni od premic iz P. ƒe neka premicap vsebujekp

to£k iz T, prispeva h grafu k_p−1 povezav. ’tevilo incidenc je enako vsoti ²tevila incidenc na posameznih premicah:

∑︂

p∈P

k_p =x.

Vseh premic je m, zato je ²tevilo povezav grafa G enako

∑︂

p∈P

(k_p−1) =x−m.

Zdaj pa v dokazu lo£imo dva primera.

1. primer: Za ²tevilo povezav velja x−m <4n. Tedaj sledi x < m+ 4n.

Ker je m+ 4n ≤4(mn)^2/3+m+ 4n, je v tem primeru izrek dokazan.

2. primer: Za ²tevilo povezav velja x−m ≥4n. Po izreku 5.8 je cr(G)≥ (x−m)³

64n² .

Ocenimo prekriºno ²tevilo grafa G ²e navzgor. V grafu G lahko pride do kriºanja povezav le tam, kjer se sekata dve premici iz P. Vsaka premica se z vsako drugo premico v ravnini lahko seka najve£ enkrat, zato

cr(G)≤ m(m−1)

2 < m². Dobimo

(x−m)³

64n² ≤cr(G)< m² (x−m)³ <64m²n²

x−m <4(mn)^2/3 x <4(mn)^2/3+m.

Tudi v tem primeru je res x <4(mn)^2/3+m+ 4n. □ Z zgledom pokaºimo, da je ta meja lahko doseºena do konstantnega faktorja na- tanko.

Zgled 6.3. Naj bo mnoºica to£k mreºaT = [k]×[4k²]. Oznaka[k]pomeni mnoºico {1,2, . . . , k}. Vseh to£k je 4k³. V mnoºici premic P naj bodo premice oblike y = ax+b za vse razli£ne kombinacije izborov a inb, da je a∈[k]inb ∈[2k²]. Dobimo k·2k² = 2k³ razli£nih premic. ƒe je x naravno ²tevilo, je tudi y=ax+b naravno.

Poleg tega za x∈[k] velja

1≤ax+b ≤kx+b≤k²+ 2k² = 3k² <4k²,

kar pomeni, da je(x, ax+b)∈T. Sledi, da za vsaka∈[k],b∈[2k²]inx∈[k]dobimo eno incidenco to£k in premic. ’tevilo incidenc je enako k·2k² ·k = 2k⁴, po izreku 6.2 pa mora biti manj²e ali enako4(4k³·2k³)^2/3+ 2k³+ 4·4k³ = 16k⁴+ 2k³+ 16k³ = 16k⁴+ 18k³.

Na sliki 14 je prikazan primer zak = 2. To£k je32, premic je16. Modro ozna£ene to£ke leºijo na eni premici, takih je 6, rde£e ozna£ene na dveh premicah, takih je 13. Pride do32incidenc to£k in premic. Izrek 6.2 pa nam zagotavlja, da je incidenc manj ali enako 4(mn)^2/3+m+ 4n = 4(32·16)^2/3+ 16 + 4·32 = 400. ♢

1 2 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Slika 14. Zgled 6.3 za k = 2. Modro ozna£ene to£ke leºijo na eni premici, rde£e ozna£ene na dveh, sive pa ne leºijo na premicah.

V dokazih dveh izrekov, ki sledita, bomo potrebovali razmisleka iz naslednjih lem.

Lema 6.4. Naj bo k ∈N, k ≥2. Potem je 1

k−1 ≤ 2 k.

Dokaz. Iz k ≥ 2 s pri²tevanjem k na obeh straneh neena£be dobimo 2k ≥ k + 2 oziroma 2k−2≥k, od tod po deljenju z2sledik−1≥ ^k₂, nato ²e delimo s(k−1)^k₂, kar je strogo pozitivno ²tevilo, in dobimo ²_k ≥ _k−1¹ . □

Lema 6.5. Naj bo n∈N, n≥3. Potem je 1

3 ≤ n−2 n .

Dokaz. Iz n ≥ 3 sledi 2n ≥ 6 in 3n ≥ n+ 6, od tod pa n ≤ 3n−6 = 3(n −2).

Neena£bo delimo s 3n in dobimo ¹₃ ≤ ⁿ⁻²_n . □

Izrek 6.6. Za n razli£nih to£k v ravnini je ²tevilo premic, ki vsebujejo vsaj k ≥ 2 izmed teh to£k, navzgor omejeno z 2¹²n²/k³+ 2⁴n/k.

Pogojk ≥2je res potreben, saj zak = 1zadostuje ºe ena to£ka (n= 1), pa lahko nari²emo poljubno mnogo premic, ki vsebujejo vsaj eno to£ko.

Dokaz izreka 6.6. Naj bo T mnoºica n to£k v ravnini, P pa mnoºica m premic, ki vsebujejo vsaka vsaj k ≥ 2 to£k iz T. Za ²tevilo incidenc x velja x ≥ mk, zato iz izreka 6.2 sledi

mk ≤x≤4(mn)^2/3+m+ 4n, od tod pa dobimo

m(k−1)≤4(mn)^2/3+ 4n.

(1)

Lo£imo dva primera.

1. ƒe jen≤(mn)^2/3, v neena£bi (1) desnin nadomestimo z(mn)^2/3 in z uporabo leme 6.4 sledi

m(k−1)≤4(mn)^2/3+ 4(mn)^2/3 = 8(mn)^2/3 m¹⁻²³ ≤ 8n^2/3

k−1 ≤ 16n^2/3 k m≤ 2¹²n²

k³ .

2. ƒe pa jen ≥(mn)^2/3, nadomestimo(mn)^2/3 znin s pomo£jo leme 6.4 dobimo m(k−1)≤4n+ 4n = 8n

m ≤ 8n

k−1 ≤ 16n k .

V obeh primerih torej velja m≤2¹²n²/k³+ 2⁴n/k. □ Sledi Beckov izrek, znan tudi kot izrek dveh skrajnosti, ki pravi, da kon£na mno- ºica to£k v ravnini gotovo pade v eno od dveh skrajnosti: prva je, da velik deleº to£k leºi na eni premici, druga pa, da obstaja veliko razli£nih premic, ki gredo skozi vsaj dve to£ki.

Izrek 6.7 (Beck, 1983). Naj bo T mnoºica n ≥1 to£k v evklidski ravnini in naj bo C = 3(2¹⁶+ 2⁸) = 197 376. Potem velja vsaj ena od naslednjih trditev:

A) Obstaja premica, ki vsebuje vsaj n/C >5,0×10⁻⁶n to£k iz T.

B) Obstaja vsaj n²/(4C²)>6,4×10⁻¹²n² premic, katerih vsaka vsebuje vsaj dve to£ki iz T.

Dokaz. Za vse n ≤C velja trditev A, saj je tedaj n/C ≤1 in ker je n ≥ 1, gotovo obstaja vsaj ena premica, ki vsebuje vsaj eno to£ko izT (pravzaprav jih je neskon£no mnogo). Za vse n ≤ 2C, n ≥2, velja tudi trditev B, saj je tedaj n²/(4C²) ≤1, in ker je n ≥ 2, gotovo obstaja vsaj ena premica, ki vsebuje vsaj dve to£ki iz T. Za n ≤2C torej izrek drºi.

Dokaºimo izrek ²e za n > 2C (v resnici nam bo zado²£ala predpostavka, da je n ≥3). Naj bo s naravno ²tevilo, a, b razli£ni to£ki iz T in p(a, b) premica skozi a in b. Par to£k {a, b} imenujmo s-povezan, £e je

2^s ≤ |p(a, b)∩T| ≤2^s+1−1.

Za danisnavzgor ocenimo ²tevilo vsehs-povezanih parov to£k. Premic, ki vsebujejo od2^sdo2^s+1−1to£k izT, je manj kot premic, ki vsebujejo vsaj2^sto£k izT, ²tevilo teh pa je po izreku 6.6 navzgor omejeno z 2¹²n²/2^3s+ 2⁴n/2^s. Zato je tudi premic, ki vsebujejo od 2^s do 2^s+1−1 to£k iz T, manj kot 2¹²n²/2^3s+ 2⁴n/2^s. Vsaka taka premica vsebuje kve£jemu

(︃2^s+1−1 2

)︃

= (2^s+1−1)(2^s+1−2)

2 < 2^s+1·2^s+1

2 = 2^2s+1 = 2·2^2s

razli£nih parov to£k izT, ki sos-povezani. ƒe zmnoºimo zgornjo mejo ²tevila premic s s-povezanimi pari to£k iz T in zgornjo mejo za ²tevilo razli£nih parov to£k, ki jih taka premica vsebuje, dobimo, da je pri danem s vseh s-povezanih parov to£k iz T manj kot 2¹³n²/2^s+ 2⁵n·2^s. Naj bo

S ={s ∈N| C ≤2^s≤n/C}={s∈N | log₂C≤s ≤log₂n/C}

in naj bo N skupno ²tevilo vseh s-povezanih parov, pri katerih je s∈S. Po formuli za vsoto zaporednih £lenov geometrijskega zaporedja dobimo

N <2¹³n²∑︂

s∈S

2^−s + 2⁵n∑︂

s∈S

2^s

= 2¹³n²

⌊log₂n/C⌋

∑︂

s=⌈log₂C⌉

2^−s + 2⁵n

⌊log₂n/C⌋

∑︂

s=⌈log₂C⌉

2^s

= 2¹³n² 2^{−⌈log2C⌉}(︁

1−2^{−(⌊log2n/C⌋−⌈log2C⌉+1)})︁

1− ¹₂ +

+ 2⁵n 2^⌈log2C⌉(︁

1−2^{⌊log2n/C⌋−⌈log2C⌉+1})︁

1−2

= 2¹³n²·2(︁

2^{−⌈log2C⌉}−2^{−⌈log2C⌉}2^{−⌊log2n/C⌋+⌈log2C⌉−1})︁

+ + 2⁵n(−1)(︁

2^⌈log2C⌉−2^⌈log2C⌉2^{⌊log2n/C⌋−⌈log2C⌉+1})︁

= 2¹³n²(︁

2^{1−⌈log2C⌉}−2^{−⌊log2n/C⌋})︁

+ 2⁵n(︁

2^{1+⌊log2n/C⌋}−2^⌈log2C⌉)︁

≤2¹³n²(︁

2^1−log2C −2^−log2n/C)︁

+ 2⁵n(︁

2^1+log2n/C −2^log2C)︁

= 2¹³n² (︃2

C − C n

)︃

+ 2⁵n (︃2n

C −C )︃

= 2¹³ (︃2n²

C −Cn )︃

+ 2⁵ (︃2n²

C −Cn )︃

<(︁

2¹³+ 2⁵)︁2n² C

= 2⁵(2⁸+ 1) 2n² 3·2⁸(2⁸+ 1)

= n² 3·4,

saj je C = 3(2¹⁶+ 2⁸). Predpostavili smo, da je n ≥3, zato je po lemi 6.5 1

3 ≤ n−2 n . Iz zgornje ocene za N sledi

N < n²

3·4 ≤ n−2 n ·n²

4 = n(n−2)

4 .

Vseh parov razli£nih to£k iz T je (︁_n

2

)︁, tistih, ki so s-povezani za kak²en s ∈ S, je manj ali enako N, torej je ²tevilo vseh parov razli£nih to£k iz T, ki niso s-povezani za noben s∈S, ve£je ali enako (︁_n

2

)︁−N. Velja ocena (︃n

2 )︃

−N > n(n−1)

2 − n(n−2)

4 = 2n² −2n−n²+ 2n

4 = n²

4 . Vsaka premica, ki poteka skozi katerega od teh parov, torej bodisi

a) vsebuje ve£ kot n/C to£k iz T bodisi b) vsebuje manj kot C to£k iz T.

ƒe obstaja premica, ki zado²£a pogoju a), velja trditev A. V nasprotnem primeru vsi pari to£k izT, ki nisos-povezani za nobens ∈S, leºijo na premicah, ki vsebujejo manj kot C to£k iz T. ’tevilo parov to£k iz T, ki jih lahko taka premica vsebuje, pa je manj²e od C². Ker je teh parov vsaj n²/4, mora obstajati ve£ kot

n²/4 C² = n²

4C²

premic, katerih vsaka vsebuje vsaj dve to£ki iz T, torej velja trditev B. □ 7. Zaklju£ek

Pokazali smo, da nastopajo problemi ekstremalne kombinatorike na razli£nih po- dro£jih matematike. Predstavili smo nekatere ekstremalne probleme na primerih mnoºic celih ²tevil, turnirjev, grafov ter to£k in premic v ravnini. Ti matemati£ni objekti hitro postanejo preveliki oziroma preve£ ²tevil£ni, da bi navedene probleme lahko smiselno re²evali na roke, zato se posluºimo ocen. V obravnavanih primerih smo pokazali, kako ocene pridobiti neposredno ali posredno s pomo£jo ra£unanja ver- jetnosti ali pri£akovanih vrednosti. Ob tem pa je bila poleg pre²tevanja in verjetnosti koristna tudi uporaba drugih matemati£nih orodij, na primer lastnosti pra²tevil, ra-

£unanja z ostanki, analize realnih funkcij, matemati£ne indukcije, spretnosti pri delu z neena£bami in izrazi ter splo²no znanih lastnosti prou£evanih objektov.

Slovar strokovnih izrazov adjacent sosednji

co-prime numbers tuji ²tevili crossing kriºanje

crossing number prekriºno ²tevilo dominating set dominantna mnoºica pigeonhole principle Dirichletov princip point-line incidence incidenca to£k in premic probabilistic method verjetnostna metoda sum-free set mnoºica brez vsot

tournament turnir

Literatura

[1] R. Diestel, Graph theory, Graduate texts in mathematics 173, Springer, New York, 1997.

[2] S. Jukna, Extremal combinatorics with applications in computer science, Texts in theoretical computer science, Springer, Berlin, 2011.

[3] B. Valentin£i£, Porazdelitev pra²tevil, v: Pra²tevila, verzija 10. 4. 2005, [ogled 19. 11. 2020], dostopno na www.educa.fmf.uni-lj.si/izodel/sola/2003/ura/valentincic/

porazdelitev.html.

[4] Incidence structure, v: Wikipedia, The Free Encyclopedia, [ogled 17. 4. 2021], dostopno na en.wikipedia.org/wiki/Incidence_structure.

[5] Theorem on friends and strangers, v: Wikipedia, The Free Encyclopedia, [ogled 2. 11. 2019], dostopno na en.wikipedia.org/wiki/Theorem_on_friends_and_strangers.