i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 81 — #1 i
i
i
i
i
i
RAZPOREDITVE HIPERRAVNIN
MATJAŽ KONVALINKA
Fakulteta za matematiko in fiziko
Univerza v Ljubljani
Math. Subj. Class. (2010): 52C35
Razporeditev hiperravnin je končna množica hiperravnin (afinih podprostorov ko-
dimenzije 1) v evklidskem prostoru Rn. V tem preglednem članku definiramo osnovni
algebrski strukturi, povezani z razporeditvami: delno urejeno množico presekov in karak-
teristični polinom. Videli bomo, kako uporabiti karakteristični polinom za izračun števila
območij, na katera razporeditev razkosa prostor, in pokazali nekaj metod za iskanje ka-
rakterističnega polinoma.
HYPERPLANE ARRANGEMENTS
A hyperplane arrangement is a finite set of hyperplanes (affine subspaces of codimen-
sion 1) in the Euclidean space Rn. In this survey we define two basic structures: the
intersection poset and the characteristic polynomial. We see how to use the characteristic
polynomial to compute the number of regions created by the hyperplanes, and show some
methods for finding the characteristic polynomial.
Osnovne definicije in primeri
Iz srednješolske matematike vsi poznamo premico v ravnini in ravnino v
prostoru. Vemo, da ima vsaka premica enačbo oblike
ax+ by = c,
kjer so a, b, c poljubna realna števila; pri tem ne sme veljati a = b = 0.
Premica gre skozi izhodǐsče natanko tedaj, ko je c = 0. Podobno ima ravnina
v prostoru enačbo
ax+ by + cz = d,
kjer so a, b, c, d poljubna realna števila, za katera ne velja a = b = c = 0.
Ravnina gre skozi izhodǐsče natanko tedaj, ko je d = 0.
Posplošitev premice v ravnini in ravnine v prostoru je hiperravnina:
množica točk (x1, . . . , xn) ∈ Rn, za katere velja
a1x1 + a2x2 + . . .+ anxn = b,
kjer je (a1, . . . , an) ∈ Rn \ {0} in b ∈ R. Hiperravnina je afin podprostor
vektorskega prostora Rn (premaknjen linearni podprostor) dimenzije n− 1
in gre skozi izhodǐsče natanko tedaj, ko je b = 0.
Obzornik mat. fiz. 59 (2012) 3 81
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 82 — #2 i
i
i
i
i
i
Matjaž Konvalinka
Zanimale nas bodo končne razporeditve hiperravnin v Rn (angl. hyper-
plane arrangements), se pravi končne množice hiperravnin v Rn. Naš glavni
vir in izvrsten uvod v široko področje kombinatorike razporeditev je [3].
Tam lahko bralec najde tiste dokaze, ki so v našem pregledu izpuščeni. Za
nekatere lastnosti razporeditev, ki jih tu ne bomo obravnavali, denimo ma-
ksimalno število incidenc, največja možna kombinatorna obsežnost itd., glej
[1]. Za razporeditve hiperravnin bomo uporabljali pisane velike črke, torej
A,B itd. V nadaljevanju bomo končnim razporeditvam hiperravnin rekli
preprosto razporeditve. Na sliki 1 je primer razporeditve (premic) v R2.
Slika 1. Primer razporeditve v R2.
Na prvi pogled je očitno, da razporeditev razdeli prostor Rn na več ob-
močij. Na primer, razporeditev na sliki 1 razdeli ravnino na 10 območij.
Prav tako je očitno, da je število območij lahko občutljivo za majhne spre-
membe: če malo premaknemo eno od treh premic, ki se sekajo v isti točki,
bo število območij naraslo na 11.
Strogo definiramo območje razporeditve A kot povezano komponento
prostora
Rn \
⋃
H∈A
H.
Ni težko videti, da je območij končno mnogo, da je vsako od njih odprta
konveksna množica in zato homeomorfno notranjosti krogle. Število območij
označimo z r(A).
Primer 1. Denimo, da imamo razporeditev Am v ravnini, ki vsebuje m
premic v splošni legi: to pomeni, da se vsaki dve premici sekata v natanko
eni točki in da nobene tri premice nimajo skupne točke. Trdimo, da je
r(Am) = (m2 + m + 2)/2. To je očitno res, če je m = 0: imamo samo
eno območje (celo ravnino). Predpostavimo, da trditev velja za m − 1,
torej da ima razporeditev Am−1 natanko (m2−m+ 2)/2 območij. Dodamo
novo premico; predstavljamo si, da potujemo po njej od enega konca do
drugega. Vsakič, ko presekamo drugo premico, se ustvari novo območje;
eno območje pa se ustvari še na koncu. Ker nova premica po predpostavki
seka vsako od starih premic v drugi točki, smo dodali m območij, tako da
je r(Am) = r(Am−1) +m = (m2 −m+ 2)/2 +m = (m2 +m+ 2)/2. ♦
82 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 83 — #3 i
i
i
i
i
i
Razporeditve hiperravnin
Primer 2. Oglejmo si koordinatno razporeditev Kn, ki je definirana s koor-
dinatnimi hiperravninami xi = 0, i = 1, . . . , n. Območja za n = 2 ustrezajo
kvadrantom, za n = 3 pa oktantom. Za splošen n je območij 2n: da je točka
(x1, . . . , xn) ∈ Rn \
⋃
H∈Kn H, mora veljati xi 6= 0 za vsak i; lahko je videti,
da je območje določeno z izborom xi > 0 ali xi < 0 za vsak i, možnosti je
očitno 2n. ♦
Opazimo še, da ima družina vseh hiperravnin koordinatne razporeditve
neprazen presek. Takim razporeditvam rečemo centralne; se pravi, razpo-
reditev A je centralna, če velja
⋂
H∈AH 6= ∅.
Primer 3. Kitkasta razporeditev (angl. braid arrangement) Bn je definirana
z
(
n
2
)
hiperravninami xi − xj = 0 za 1 ≤ i < j ≤ n. Območje je določeno
s tem, da izberemo, ali velja xi < xj ali xi > xj za vsaka i, j, i < j.
To pomeni, da je območje določeno s tem, da določimo, kateri od xi-jev
je najmanǰsi, kateri je drugi najmanǰsi itd., se pravi z neko permutacijo
koordinat x1, x2, . . . , xn. Zatorej velja r(Bn) = n!. Na primer, razporeditev
B3, prikazana na sliki 2, razdeli prostor na šest območij, določenih z x1 <
x2 < x3, x1 < x3 < x2, x2 < x1 < x3, x2 < x3 < x1, x3 < x1 < x2 in
x3 < x2 < x1.
Opazimo, da je tudi kitkasta razporeditev centralna: presek je premica
x1 = x2 = . . . = xn. ♦
Slika 2. Kitkasta razporeditev B3, presekana z ravnino x1 + x2 + x3 = 0.
Kitkasta razporeditev ima kar nekaj zanimivih
”
deformacij“, na primer
naslednje tri.
Primer 4. Denimo, da imamo dan graf G = (V,E), kjer je množica vozlǐsč
V = {1, . . . , n}. Definirajmo grafično razporeditev AG s hiperravninami
xi − xj = 0 za ij ∈ E. Kitkasta razporeditev ustreza polnemu grafu Kn.
Enostavno se da dokazati, da je število območij enako številu acikličnih
usmeritev grafa G, se pravi številu takih izbir usmeritev vseh povezav grafa,
za katere dobljeni usmerjeni graf nima ciklov.
Shijevo razporeditev Sn definirajo hiperravnine xi − xj = 0, 1 za i < j.
Catalanovo razporeditev Cn definirajo hiperravnine xi − xj = −1, 0, 1 za
i < j. Kasneje bomo videli, da je r(Sn) = (n+ 1)n−1 in r(Cn) = (2n)!/(n+
81–93 83
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 84 — #4 i
i
i
i
i
i
Matjaž Konvalinka
1)! = (n + 2)(n + 3) · · · (2n). Obe števili sta zanimivi s kombinatoričnega
stalǐsča: število (n+ 1)n−1 je (med drugim) enako številu označenih dreves
na n + 1 točkah (se pravi številu povezanih grafov na {1, 2, . . . , n + 1} z
n povezavami), drugo pa je enako n!Cn, kjer je Cn =
1
n+1
(
2n
n
)
Catalanovo
število. Catalanova števila so izjemno pomembna v enumerativni kombina-
toriki, štejejo na primer:
• triangulacije (n+ 2)-kotnika;
• pravilne postavitve n oklepajev in n zaklepajev;
• poti od (0, 0) do (2n, 0) z dovoljenima korakoma (1, 1) in (1,−1), ki se
ne spustijo pod os x.
Slika 3 prikazuje razporeditev S3. ♦
Slika 3. Shijeva razporeditev S3, presekana z ravnino x1 + x2 + x3 = 0.
Delno urejena množica presekov, Möbiusova funkcija in
karakteristični polinom
Izkaže se, da lahko veliko pomembnih lastnosti razporeditve razberemo iz
presekov hiperravnin. V tem razdelku bomo definirali dva ključna objekta:
delno urejeno množico presekov in njen karakteristični polinom. V zadnjem
razdelku bomo potem spoznali različne načine računanja karakterističnega
polinoma. Veliko rezultatov bomo navedli brez dokaza ali pa bomo dokaz
samo skicirali.
Spomnimo se, da je množica P z dvomestno relacijo ≤ delno urejena, če
velja:
1. refleksivnost: za vsak x ∈ P je x ≤ x;
2. antisimetričnost: če velja x ≤ y in y ≤ x, je x = y;
3. tranzitivnost: če velja x ≤ y in y ≤ z, je tudi x ≤ z.
Če je x ≤ y in x 6= y, pǐsemo x < y. Če velja x < y, ne obstaja pa z,
za katerega bi veljalo x < z < y, pravimo, da y pokriva x. Delno urejena
84 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 85 — #5 i
i
i
i
i
i
Razporeditve hiperravnin
množica P je stopničasta, če obstaja funkcija rang : P → N, za katero velja
rang(y) = rang(x) + 1, kadar y pokriva x.
Spomnimo se, da (končne) delno urejene množice pogosto predstavimo
s Hassejevim diagramom: grafom, katerega točke so elementi množice P ,
povezani pa so tisti pari (x, y), za katere y pokriva x. Hassejev diagram
običajno narǐsemo tako, da je x pod y, če je x < y. Če je delno urejena
množica stopničasta, vse elemente z istim rangom narǐsemo na isti vǐsini.
Definicija 1. Naj bo A razporeditev hiperravnin v Rn. Označimo z L(A)
množico vseh nepraznih presekov hiperravnin iz A, vključno s prostorom
Rn (ki je presek prazne družine hiperravnin). V L(A) uvedemo dvomestno
relacijo ≤ obratne vsebovanosti : definirajmo, da je x ≤ y, če je x ⊇ y. To je
relacija delne urejenosti, množici L(A) z relacijo ≤ pravimo delno urejena
množica presekov (angl. intersection poset).
Primer 5. Oglejmo si delno urejeno množico presekov za kitkasto razpo-
reditev B3. Prazni presek R3 je manǰsi od vseh preostalih (to se pravi:
vsebuje vse preostale preseke kot podmnožice). Takoj nad R3 v Hassejevem
diagramu pridejo preseki enoelementnih družin hiperravnin, se pravi hiper-
ravnine same. Ker se vse tri hiperravnine sekajo v premici x1 = x2 = x3,
je v L(B3) samo še en element, ki je večji od vseh preostalih (se pravi: je
vsebovan v vseh preostalih presekih). Glej sliko 4, levo. Vzemimo še dve
vzporedni premici v R2. Imamo najmanǰsi element in dva elementa (pre-
mici), ki ga pokrivata. Ker se premici ne sekata, drugih elementov ni. Glej
sliko 4, desno. ♦
Slika 4. Hassejev diagram delno urejene množice presekov za kitkasto razporeditev B3
in razporeditev dveh vzporednih premic.
Takoj opazimo, da velja naslednje: L(A) ima vedno minimalni element
(torej element 0̂, za katerega velja 0̂ ≤ x za vse x ∈ L(A)); to je Rn, presek
prazne družine hiperravnin. Elementi, ki pokrivajo 0̂, so kar hiperravnine
same. Velja še, da ima L(A) maksimalni element (torej element 1̂, za kate-
rega velja x ≤ 1̂ za vse x ∈ L(A)) natanko tedaj, kadar je A centralna raz-
poreditev: maksimalni element je v tem primeru kar
⋂
H∈AH 6= ∅. Delno
urejena množica presekov je stopničasta: preveriti se da, da je primerna
funkcija
rang(x) = n− dimx,
81–93 85
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 86 — #6 i
i
i
i
i
i
Matjaž Konvalinka
kjer je x običajna (afina) dimenzija elementa x (ki je presek hiperravnin in
zato premaknjen vektorski podprostor). Na primer, za kitkasto razporeditev
B3 imamo ves prostor R3 z rangom 3−3 = 0, tri ravnine z rangom 3−2 = 1
in premico x1 = x2 = x3 z rangom 3 − 1 = 2. Rang se res poveča za 1, ko
se premaknemo navzgor po Hassejevem diagramu.
V teoriji delno urejenih množic ima pomembno mesto Möbiusova funk-
cija. Tu bomo predstavili njeno nekoliko poenostavljeno različico. Predpo-
stavimo, da je P končna delno urejena množica z minimalnim elementom
0̂. Potem definiramo Möbiusovo funkcijo µP : P → Z takole: definiramo
µP (0̂) = 1, za x > 0̂ pa potem vzamemo
µP (x) = −
∑
y<x
µP (y).
Definicijo lahko zapǐsemo še drugače: velja∑
y≤x
µP (y) =
{
1 : x = 0̂
0 : x 6= 0̂ .
Kadar je jasno, o kateri delno urejeni množici govorimo, pǐsemo namesto
µP samo µ.
Primer 6. Vzemimo naravno število n in definirajmo Dn kot množico vseh
deliteljev števila n, urejeno z relacijo | (deli). Lahko je preveriti, da je (Dn, |)
delno urejena množica. Preveriti se da, da je
µ(d) =
{
0 : d je deljiv s kvadratom nekega praštevila,
(−1)k : d = p1p2 · · · pk, kjer so p1, p2, . . . , pk različna praštevila
Möbiusova funkcija v Dn. Tej funkciji pravimo tudi klasična Möbiusova
funkcija, ki je pomembna v teoriji števil, glej [2]. Hassejev diagram D24,
skupaj z vrednostmi µ(d), je na sliki 5, levo. Slika 5, desno, prikazuje
Möbiusovo funkcijo za L(B3). ♦
Izkaže se, da lahko večino pomembnih lastnosti delno urejene množice
presekov in s tem razporeditve hiperravnin preberemo iz polinoma, ki izhaja
neposredno iz Möbiusove funkcije delno urejene množice presekov.
Definicija 2. Naj bo A razporeditev. Vemo, da je njena delno urejena
množica presekov L(A) končna in ima minimalen element, zato imamo na
voljo Möbiusovo funkcijo µ. Definiramo karakteristični polinom delno ure-
jene množice presekov s formulo
χA(t) =
∑
x∈L(A)
µ(x)tdimx.
86 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 87 — #7 i
i
i
i
i
i
Razporeditve hiperravnin
1
2 3
4 6
8 12
24
1
−1 −1
0 1
0 0
0
1
−1 −1 −1
2
Slika 5. Hassejev diagram in vrednosti Möbiusove funkcije za D24 in za L(B3).
Primer 7. Za kitkasto razporeditev B3 imamo (glej sliko 5, desno)
χB3(t) = t
3 − 3t2 + 2t = t(t− 1)(t− 2).
V naslednjem razdelku bomo dokazali, da velja splošna formula
χBn(t) = t(t− 1)(t− 2) · · · (t− n+ 1). ♦
Element 0̂ = Rn ∈ L(A) ima dimenzijo n. Za vsako hiperravnino imamo
en element x dimenzije n−1, ki pokriva 0̂ in ima zato µ(x) = −1. To pomeni,
da velja
χA(t) = t
n − |A|tn−1 + . . .
Tu |A| označuje moč množice A, se pravi število hiperravnin v razporeditvi
A.
Pomembnost karakterističnega polinoma najlepše predstavi naslednji iz-
rek, ki ga bomo navedli brez dokaza.
Izrek 1 (Zaslavsky, 1975). Za poljubno razporeditev A v Rn velja r(A) =
(−1)nχA(−1).
Na primer, za kitkasto razporeditev Bn po izreku Zaslavskega in prej-
šnjem primeru dobimo
r(Bn) = (−1)n(−1)(−1− 1)(−1− 2) · · · (−1− n+ 1) = n!,
kar se ujema z našim direktnim izračunom.
”
Naivna“ metoda za izračun karakterističnega polinoma je, da na roko
izračunamo vse neprazne preseke hiperravnin, narǐsemo Hassejev diagram
delno urejene množice, z rekurzivno zvezo izračunamo vrednost Möbiusove
81–93 87
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 88 — #8 i
i
i
i
i
i
Matjaž Konvalinka
funkcije za vse njene elemente in zapǐsemo karakteristični polinom. Za raz-
poreditve z veliko elementi in za neskončne družine razporeditev (npr. za
kitkasto razporeditev, Catalanovo razporeditev) ta metoda običajno ni smi-
selna. V zadnjem razdelku bomo predstavili nekaj neočitnih metod za izra-
čun karakterističnega polinoma.
Računanje karakterističnega polinoma
Whitneyjev izrek
Spomnimo, da je razporeditev A centralna, če je
⋂
H∈AH 6= ∅. Za centralno
razporeditev A lahko definiramo dimA = dim
⋂
H∈AH.
Če je razporeditev A centralna, je centralna tudi vsaka njena podrazpo-
reditev B ⊆ A (vključno s prazno podrazporeditvijo), saj je⋂
H∈B
H ⊇
⋂
H∈A
H.
Če razporeditev ni centralna, so nekatere podrazporeditve centralne, ne-
katere pa ne. Označimo s C(A) množico vseh centralnih podrazporeditev
razporeditve A.
Primer 8. Razporeditev premic A v ravnini na sliki 6 ni centralna, saj se
premice ne sekajo v isti točki. So pa centralne vse njene podrazporeditve,
ki ne vsebujejo vseh treh premic. Tako ima C(A) sedem elementov. ♦
Slika 6. Necentralna razporeditev s sedmimi centralnimi podrazporeditvami.
Izrek 2 (Whitneyjev izrek, 1932). Za razporeditev A v Rn velja
χA(t) =
∑
B∈C(A)
(−1)|B|tdimB.
Izreka ne bomo dokazovali. Omenimo samo, da dokaz uporabi po-
membno dejstvo, da je delno urejena množica presekov polmreža za stik
(angl. meet-semilattice), torej da imata vsaka dva elementa stik (največjo
skupno spodnjo mejo), ter da je mreža (angl. lattice), torej da imata vsaka
88 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 89 — #9 i
i
i
i
i
i
Razporeditve hiperravnin
dva elementa spoj (najmanǰso skupno zgornjo mejo), natanko tedaj, ko je
razporeditev centralna. V mreži pa imamo za računanje Möbiusove funkcije
posebno formulo, ki se pri razporeditvah poenostavi v Whitneyjev izrek.
Primer 9. Izračunajmo karakteristični polinom koordinatne razporeditve.
Ker je koordinatna razporeditev centralna, je centralna tudi vsaka njena
podrazporeditev. Za vsako podmnožico I množice {1, 2, . . . , n} je presek
ravnin xi = 0, i ∈ I, podprostor dimenzije n− |I|. Po Whitneyjevem izreku
je torej
χKn(t) =
∑
I⊆{1,2,...,n}
(−1)|I|tn−|I| =
n∑
k=0
(
n
k
)
(−1)ktn−k = (t− 1)n.
Tu smo uporabili dve dejstvi: prvič, da je število podmnožic moči k množice
z n elementi enako binomskemu koeficientu
(
n
k
)
= n!k!(n−k)! , in drugič, da
velja binomski izrek (x + y)n =
∑
k
(
n
k
)
xn−kyk. Velja tudi r(Kn) = (−1)n
(−1− 1)n = 2n, kar smo že izračunali neposredno iz definicije. ♦
Rekurzivna zveza
Dana je razporeditev A. Izberimo poljubno hiperravnino H0 ∈ A. Ozna-
čimo z A′ podrazporeditev A \ {H0}, se pravi razporeditev A, ki ji odstra-
nimo hiperravnino H0. Označimo z A′′ razporeditev, ki jo dobimo, če vse
hiperravnine v A′, ki imajo neprazen presek s H0, presekamo s H0. Natanč-
neje,
A′′ = {x ∩H0 : x ∈ A, x 6= H0, x ∩H0 6= ∅}.
Primer 10. Na sliki 7, levo zgoraj, je prikazana razporeditev A premic v
ravnini; premica H0 je odebeljena. Desno zgoraj je razporeditev A′, se pravi
A brez H0. Spodaj je prikazana razporeditev A′′ (v R) presekov s H0. ♦
Slika 7. Razporeditve A, A′ in A′′.
Opazimo, da sta A′ in A′′
”
manǰsi“ razporeditvi kot A; obe imata manǰse
število elementov, A′′ pa je poleg tega tudi razporeditev v manǰsi dimenziji.
81–93 89
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 90 — #10 i
i
i
i
i
i
Matjaž Konvalinka
Izrek 3. Naj bodo A,A′,A′′ kot zgoraj. Potem velja
χA(t) = χA′(t)− χA′′(t).
Izrek je dokaj enostavna posledica Whitneyjevega izreka (ima pa tudi
druge neodvisne dokaze).
Primer 11. Naj bo G = (V,E) graf (brez zank). Barvanje grafa G s t bar-
vami je izbira ene od t barv za vsako vozlǐsče, tako da povezani vozlǐsči nista
pobarvani z isto barvo. Se pravi, barvanje je preslikava c : V → {1, . . . , t},
za katero velja ij ∈ E ⇒ c(i) 6= c(j). Definirajmo PG(t) kot število barvanj
grafa G s t barvanji. Izkaže se, da je PG(t) polinom stopnje |V |, imenujemo
ga kromatični polinom grafa G. Na primer, če je G = Kn (poln graf na n
vozlǐsčih), imamo za prvo vozlǐsče na voljo t barv, za drugo samo še t − 1
barv itd. Torej je PKn(t) = t(t− 1) · · · (t− n+ 1).
Kromatični polinom ustreza preprosti rekurzivni zvezi. Izberimo po-
ljubno povezavo e = ij grafa G in označimo z G′ graf G brez povezave e,
z G′′ pa graf, kjer vozlǐsči i in j identificiramo, se pravi, ju nadomestimo
z novim vozlǐsčem, ki je povezano z vsemi vozlǐsči grafa G \ {i, j}, ki so v
grafu G povezana z i ali j. Izberimo poljubno barvanje c grafa G′. Če sta
vozlǐsči i in j pobarvani z različnima barvama, je c tudi barvanje grafa G.
Če pa sta pobarvani z istima barvama, potem ju identificiramo in dobimo
barvanje c′′ grafa G′′. Dokazali smo
PG(t) = PG′(t)− PG′′(t).
Ta formula nas spominja na rekurzivno formulo za karakteristični polinom
razporeditve. Dokažimo, da je za grafično razporeditev AG karakteristični
polinom kar kromatični polinom grafa G, torej da velja χAG(t) = PG(t).
Trditev očitno velja za prazni graf na n vozlǐsčih, saj sta oba polinoma enaka
tn. Predpostavimo, da trditev velja za vse grafe z manj kot m povezavami,
in naj bo |E(G)| = m. Izberimo povezavo e = ij grafa G in označimo
hiperravnino xi = xj s H0. Če odstranimo H0, očitno dobimo razporeditev,
ki pripada grafu G′; se pravi, velja (AG)′ = AG′ . Po indukciji je χ(AG)′(t) =
PG′(t). Če pa vsako hiperravnino presekamo s hiperravnino xi = xj , je
učinek isti, kot če bi identificirali vozlǐsči i in j v grafu G; se pravi, velja
(AG)′′ = AG′′ . Po indukciji je χ(AG)′′(t) = PG′′(t). Torej je
χAG(t) = χ(AG)′(t)− χ(AG)′′(t) = PG′(t)− PG′′(t) = PG(t).
V posebnem je za kitkasto razporeditev
χBn(t) = PKn(t) = t(t− 1) · · · (t− n+ 1). ♦
90 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 91 — #11 i
i
i
i
i
i
Razporeditve hiperravnin
Metoda končnih obsegov
V tem podrazdelku bomo predstavili morda najbolj presenetljivo me-
todo za računanje karakterističnega polinoma, ki jo je v tej obliki zapisal
Athanasiadis. Spomnimo se najprej, da obstaja končni obseg velikosti q
natanko tedaj, ko je q = pk potenca praštevila. Vsi obsegi iste moči so
izomorfni; označimo s Fq (do izomorfizma določeni) obseg moči q. Karakte-
ristika obsega Fq je p: to pomeni, da v Fq velja p = 0. Za q = p je Fp = Zp,
obseg ostankov pri deljenju s p.
Predpostavimo, da so vse hiperravnine podane nad obsegom racional-
nih števil. Če vse enačbe pomnožimo s skupnim večkratnikom imenovalcev,
dobimo enačbe s celimi koeficienti. Če vse koeficiente vzamemo po prašte-
vilskem modulu p, dobimo enačbo nad končnim obsegom Fq za q = pk za
vsak k. Označimo dobljeno razporeditev nad obsegom Fq z Aq.
Lahko se zgodi, da je nova razporeditev bistveno drugačna od prvotne.
Na primer, če začnemo s premicama x = 0 in x = 2y, ima L(A) štiri
elemente: R2, obe premici in njun presek (izhodǐsče). Če pa vzamemo vse
koeficiente modulo 2, dobimo samo eno premico x = 0, zato ima L(A2k)
samo dva elementa.
Ni pa težko dokazati, da velja L(A) ∼= L(Apk) (se pravi, A in Apk
imata – do izomorfizma – isto delno urejeno množico presekov) za vse razen
za končno mnogo praštevil p. Glavna prednost nove razporeditve je, da
so vse hiperravnine zdaj končne množice (kot podmnožice končne množice
Fnq ), zato lahko računamo z njihovimi močmi. Naslednji izrek je tako dokaj
preprost (uporabi samo neko osnovno lastnost Möbiusove funkcije, ki je
v tem pregledu nismo omenili). Spomnimo, da HC pomeni komplement
množice H.
Izrek 4 (Athanasiadis, 1996). Naj bo A razporeditev v Qn in naj velja
L(A) ∼= L(Aq) za q, ki je potenca praštevila. Potem je
χA(q) = q
n −
∣∣∣∣ ⋃
H∈Aq
H
∣∣∣∣ = ∣∣∣∣ ⋂
H∈Aq
HC
∣∣∣∣.
Primer 12. Oglejmo si, kako preprosto je z metodo končnih obsegov izra-
čunati karakteristični polinom grafične razporeditve. Pǐsimo A = AG. Naj
bo p dovolj velik, da je L(A) ∼= L(Aq) za q = pk. Če je H v A podana
z xi = xj , je H
C v Aq množica točk (α1, . . . , αn) ∈ Fnq , za katere velja
αi 6= αj . Potem je
χA(q) =
∣∣∣∣ ⋂
H∈Aq
HC
∣∣∣∣
=
∣∣{(α1, . . . , αn) ∈ Fnq : αi 6= αj za vsako povezavo ij ∈ E(G)}∣∣.
81–93 91
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 92 — #12 i
i
i
i
i
i
Matjaž Konvalinka
Zadnji izraz pa je po definiciji enak PG(q). Torej sta χA(t) in PG(t) poli-
noma, ki imata enako vrednost za neskončno mnogo vrednosti t, kar pomeni,
da sta enaka. ♦
Primer 13. Oglejmo si Shijevo razporeditev Sn, ki je podana z xi − xj =
0, 1 za i < j. Za dovolj veliko praštevilo p velja
χSn(p) =
∣∣{(α1, . . . , αn) ∈ Znp : i < j ⇒ αi 6= αj in αi 6= αj + 1}∣∣ .
Denimo, da imamo tako n-terico (α1, . . . , αn). Narǐsimo 0, 1, . . . , p − 1 kot
točke na krožnici, ki naraščajo v smeri urinega kazalca. Označimo točko
α1 z 1, točko α2 z 2 itd. Ker je αi 6= αj za i 6= j, ima vsaka točka
največ eno oznako. Ker iz αi = αj + 1 sledi i > j, so zaporedne (v
smeri urinega kazalca) oznake naraščajoče. Glej sliko 8 za p = 11, n = 6
in (α1, α2, α3, α4, α5, α6) = (6, 1, 2, 7, 9, 3). Naj bo B1 množica zapore-
dnih oznak, ki se začnejo z 1; v našem primeru je to {1, 4}. Preskočimo
eno točko in vzemimo za B2 (lahko prazno) množico zaporednih oznak,
ki se začnejo v naslednji točki; nadaljujemo. V našem primeru dobimo
B1 = {1, 4}, B2 = {5}, B3 = ∅, B4 = {2, 3, 6}, B5 = ∅. Ker vsaki množici Bi
pripada natanko ena neoznačena točka, smo dobili p−n disjunktnih množic
(B1, B2, . . . , Bp−n), 1 ∈ B1, katerih unija je {1, 2, . . . , n}. Konstrukcija se da
tudi obrniti: za dane disjunktne množice (B1, B2, . . . , Bp−n), 1 ∈ B1, kate-
rih unija je {1, 2, . . . , n}, in izbrani α1 ∈ Zp naredimo naslednje. Označimo
točko α1 z 1, naslednje točke označimo s preostalimi elementi B1. Presko-
čimo eno točko, označimo točke z elementi B2; nadaljujemo. Za αi potem
vzamemo točko, katere oznaka je i.
Torej je χSn(p) enak številu izbir α1 in disjunktnih množic (B1, B2, . . . ,
Bp−n), 1 ∈ B1, katerih unija je {1, 2, . . . , n}. Ker lahko α1 izberemo na p
načinov in ker imamo za 2, . . . , n na voljo p− n množic Bi, kamor jih lahko
damo, je možnosti p(p− n)n−1. Torej je
χSn(t) = t(t− n)n−1.
Iz tega takoj sledi, da je r(Sn) = (−1)nχSn(−1) = (n+ 1)n−1. ♦
Primer 14. Izračun za Catalanovo razporeditev Cn, podano z xi − xj =
0, 1,−1 za i < j, je zelo podoben. Za dovolj velik p velja
χCn(p) =
∣∣{(α1, . . . , αn) ∈ Znp : i 6= j ⇒ αi 6= αj in αi 6= αj ± 1}∣∣ .
Torej imamo enak preštevalni problem kot v preǰsnjem primeru, le da zdaj
dve sosednji točki ne smeta biti označeni. To pomeni, da bodo množice
B1, . . . , Bp−n, definirane kot zgoraj, imele največ en element. Za α1 imamo
92 Obzornik mat. fiz. 59 (2012) 3
i
i
“Konvalinka” — 2012/7/26 — 10:24 — page 93 — #13 i
i
i
i
i
i
0
1
23
4
5
6
7
8 9
10
2
3
6
1
4
5
Slika 8. Računanje karakterističnega polinoma Shijeve razporeditve z metodo končnih
obsegov.
spet p izbir, potem imamo p−n− 1 izbir, v katero od množic B2, . . . , Bp−n
damo element 2, p− n− 2 izbir, kam damo element 3, itd. Dobimo torej
χCn(t) = t(t− n− 1)(t− n− 2) · · · (t− 2n+ 1)
in r(Cn) = n!Cn. ♦
LITERATURA
[1] M. Juvan, Kombinatorne lastnosti razporeditev, magistrsko delo, 105 strani, Ljubljana,
1993
[2] E. Weisstein, Möbius function, MathWorld, dostopno na
http://mathworld.wolfram.com/MoebiusFunction.html
[3] R. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics,
389–496, IAS/Park City Math. Ser., 13, Amer. Math. Soc., Providence, RI, 2007
VESTI
STROKOVNO SREČANJE IN 64. OBČNI ZBOR DMFA
SLOVENIJE – VABILO K SODELOVANJU
Spoštovani člani DMFA Slovenije, učitelji, raziskovalci in vsi ljubitelji mate-
matike, fizike in astronomije. Vljudno vas vabimo k sodelovanju na našem
vsakoletnem srečanju, ki bo tokrat potekalo v Rimskih Toplicah 19. in
20. oktobra 2012. Tam bomo predstavili sedanjo dejavnost društva, k
pripravi predavanj povabili nekaj uglednih slovenskih matematikov in fizi-
kov, prisluhnili različnim strokovnim prispevkom naših članov in pripravili
Obzornik mat. fiz. 59 (2012) 3 93