SZEMINÁRIUMI FELDOLGOZÁSRA JAVASOLT TÉMÁK

Tournamentek vizsgálata — Kapcsolatuk a lineáris programozással.

Lehet-e egy ultiversenyt jól megszervezni? Azaz, adva 3n versenyző, a lehetséges

\binom{3n}{3} három elemű részhalmazt be lehet-e osztani \frac{1}{n}\binom{3n}{3} n elemű csoportra (az egy

fordulóban lejátszandó mérkőzések), melyek mindegyike a 3n elemű halmaz particióját adja? A kérdést természetes módon meg lehet kérdezni 3 szereplős játékok helyett tetszőleges pozitív egész k szereplős játékra. Az erre a feladatra Baranyai Zsolt által bizonyított igenlő állítás bizonyításának az ismertetését javaslom. Katona Gyulával való konzultáció alapján Baranyai Zsolt kandidátusi disszertáciőjának tanulmányozását látom célszerűnek. Ez megtalálható az MTA Matematikai Kutató Intézetének könyvtárában. Érdemesenek tartom megjegyezni, hogy ezt a témát nemcsak a probléma, hanem a felhasznált módszer érdekessége miatt is ajánlom. A kérdés megfogalmazható, mint egy egész értékű lineáris programozási feladat, és ilyen módszert követ a bizonyítás. Míg a lineáris programozás klasszikus eseteire viszonylag jól kidolgozott elmélet létezik, az egész értékű lineáris programozásról csak speciális esetekben alkalmazható részeredmények ismeretesek. Ebbe ad némi betekintést az említett probléma vizsgálata.

A lineáris programozás problémájanak egy másik irányú érdekes általánosítása a kvadratikus programozás. Erről Lovász László írt érdekes tárgyalást, mely megtalálható az ELTE homepage-én a

http://www.cs.elte.hu/forro.html

című lapon. Ezt azért nem tüntetem fel a javasolt témák között, mert ennek feldolgozása több időt és energiát igényel, mint amit egy vagy néhány előadásban fel tudunk dolgozni. Ha mégis van jelentkező ennek ismertetésére, akkor azt szívesen vesszük.

Szabályos tizenhétszög szerkesztése

Gindikin egy oroszul írt, de angol fordításban is megjelent könyvének (Rasskazi o matematikach i fizikach — Történetek matematikusokról és fizikusokról) Gaussról írt részében elmagyarázza a szabályos tizenhétszög szerkesztését. A tárgyalásmód elemi, de nagyon tanulságos. Különösen azok számára érdekes ez, akiket érdekel a Galois elmélet szemléletes tartalma, és az hogy erre hogyan lehet rájönni. Tulajdonképpen a

∑_{k=0}^{16} x^{k} = 0 egyenlet Galois csoportját határozza meg a szerző szemléletes módon, illetve

megmagyarázza, hogy ebből miért következik a szabályos tizehétszög szerkeszthetősége. Ehhez csak lazán kapcsolódó, de szintén tanulságos azoknak az ebben a könyvben szereplő számelméleti problémáknak a tárgyalása, melyeknek egy speciális és könnyen ellenőrízhető esete tette lehetővé az említett Galois csoport meghatározását.

Egy másik kérdés, melynek lehetséges tárgyalását ez a könyv vetette fel számomra, de amelyiknek sem a megoldását sem az irodalomban elérhető tárgyalását nem ismerem, a következő casus irreducibilisnek nevezett probléma. Tekintsük a harmadfokú egyenletetet abban az esetben, amikor mind a három gyök valós. Ismeretes, hogy a harmadfokú egyenlet megoldóképlete szerint ekkor a gyökök kiszámításához komplex számokból is kell köbgyököt vonni. Az igazán tartalmas állítás viszont az lenne, hogy ezeket a gyököket nemcsak e megoldóképlet szerint, hanem sehogyan sem lehet csupán valós számokat használva az összeadás, kivonaás, szorzás, osztás és gyökvonás művelete segítségével felírni. Ennek bizonyításához valószínűleg a Galois elmélet alaposabb ismerete szükséges.

Holley egyenlőtlenség — alkalmazások a kombinatorikában és statisztikus fizikában

A Holley egyenlőtlenség a statisztikus fizikában fogalmazódott meg. Egyik következménye az FKG (Fortuin–Kasteleyn–Ginibre) egyenlőtlenség, mely fontos szerepet játszott Geoffrey Grimmett Bolyai kollégiumbeli előadásában is. Ez az egyenlőtlenség a kombinatorikában, az un. moduláris függvények vizsgálatában is hasznosnak bizonyult. Ez az egyenlőtlenség bizonyos a szemlélet alapján ,,nyílvánvaló”, de formálisan bonyolultan felírható és nehezen bizonyítható állítások igazolására használható. Csak vázlatosan, pongyolán fogalmazok meg egy ilyen állítást, amelyik érzékelteti az ilyen tipusú állítások jellegét. Ha egy statisztikus fizikai modellben egy rács pontjaiban 0 vagy 1 állapotú spinek ülnek, és a modell Hamilton függvényét úgy változtatjuk meg, hogy a sok 1 állapotú spint tartalmazó állapotok energiája csökken, akkor a megváltoztatott Hamilton függvény által meghatározott Gibbs állapotban több 1 állapotú spin van. (Egy Gibbs állapot szerinti mérték a kis energiájú konfigurációkra van koncentrálva.)

Pontosabban megfogalmazva, a Holley egyenlőtlenség a következő kérdéssel foglalkozik: Legyen adva egy X véges halmaz, és legyen μ és ν két valószínűségi mérték az X részhalmazait mint elemeket tartalmazó halmazokon. Azaz, az {A_{1}, …, A_{k}}, A_{j} ⊆ X, j = 1, …, k tipusú halmazoknak van μ illetve ν mértéke, és

μ({A_{1}, …, A_{k}}) = ∑_{j=1}^{k} μ(A_{j}), ν({A_{1}, …, A_{k}}) = ∑_{j=1}^{k} ν(A_{j}).

Továbbá ∑_{A⊆X} μ(A) = 1 és ∑_{A⊆X} ν(A) = 1. A μ és ν mértékek szemléletes jelentése:

Véletlenszerűen kijelöljük az X halmaz bizonyos pontjait, és μ(A) illetve ν(A) annak a valószíműsége, hogy pontosan az A halmaz elemeit választottuk ki. Azt mondjuk, hogy μ ≥ ν, ha létezik olyan csatolás (coupling) a μ és ν mértékek között, mely szerint az első koordináta egy valószínűséggel tartalmazza a másodikat. Pontosabban, létezik olyan P valószínűségi mérték az {(A_{i_{1}}, B_{j_{1}}) , …, (A_{i_{k}}, B_{j_{k}})}, (A_{i_{r}}, B_{j_{r}}) ∈ X × X párokból álló halmazokon, melyekre

P {{(A_{i_{1}}, B_{j_{1}}) , …, (A_{i_{k}}, B_{j_{k}})}) = ∑_{r=1}^{k} P (A_{i_{r}}, B_{j_{r}}) ,

∑_{B⊆X} P (A, B) = μ(A), ∑_{A⊆X} P (A, B) = ν(B),

és P (A, B) = 0, ha B ⊈ A. A Holley egyenlőtlenség célja jól használható, ellenőrízhető elégséges feltételt adni arra, hogy μ ≥ ν.

A Holley egyenlőtlenség a következő állítás: μ ≥ ν, ha μ(A ∪ B)ν(A ∩ B) ≥ μ(A)ν(B) minden A ⊆ X és B ⊆ X halmazra. Az egyenlőtlenség eredeti bizonyítása a Markov folyamatok elméletének ravasz alkalmazásán alapul. Jóval később síkerült találni egyszerűbb, természetes, kombinatorikus bizonyítást. Ezt az eredményt Járai Antal fogja ismertetni a szemináriumon, mivel ennek ismerete egyébként is hasznos PhD. munkájában.

Izoperimetrikus problémák

A klasszikus izoperimetrikus probléma a következő: Egységnyi területű tartományok közül melyiknek a területe a legnagyobb? A válasz az, hogy a kör. E kérdés következő általánosítását is nevezhetjük (általánosított) izoperimetrikus problémának. Legyen adva egy folytonos e(n) > 0 függvény a sík egységvektorain, és egy G tartomány a síkon síma ∂G határral. Tekintsük az ∮_{∂G} e(n_{G}(x)) dx integrált a ∂G határon, ahol n_{G}(x) a G külső normális egységvektora az x ∈ ∂G pontban. Egységnyi területű G tartományok közül melyikre lesz az adott integrál minimális?

A fenti kérdésre egyszerű geometriai képpel leírható válasz adható. Minden n ∈ R^{2} egységvektorhoz defináljuk az {x: x ∈ R^{2}, e(n)xn ≤ 1} félsíkot, ahol xn skalárszorzatot jelöl. A keresett tartományt ezen félsíkok metszete adja meg, pontosabban ennek a metszetnek olyan kinagyítása, melynek a területe egységnyi. További érdekes probléma annak vizsgálata, hogy ha egy tartományra a funkcionál értéke közel van az optimumhoz, akkor a tartomány alakja mennyire hasonlít az optimális tartományéhoz.

A fenti kérdések a geometria természetes, klasszikus problémáihoz tartoznak, de fontosak egyéb matematikai és fizikai problémák vizsgálatában is. Vizsgálatukban a konvex geometria fontos fogalmai és eredményei, mint például a vegyes térfogat, Minkowski egyenlőtlenség, stb. szerepelnek. A kérdések alapos vizsgálatához nem elegendő néhány előadás. De remélhetőleg a Matematikai Intézet geometriai osztályának néhány munkatársa is előad, illetve tanácsot ad néhány cikk ismertetésére, és ezek lehetővé teszik, hogy némi betekintést kapjunk ebbe a problémakörbe.

Makai Endre által esetleges feldolgozásra ajánlott irodalom:

H. Busemann: The isoperimetric problem in the Minkowski plane, Amer. J. Math.

69 (1947), 863–871, (a “súlyozott” izoperimetrikus probléma R^{2}-ben)

H. Busemann: The isoperimetric problem for Minkowski area, Amer. J. Math. 71 (1949), 743–762, (a “súlyozott” izoperimetrikus probléma R^{n}-ben)

H. Busemann: The geometry of Finsler spaces, Bull. Amer. Math. Soc. 56 (1950), 5–16, (általános mese a Minkowski geometriáról)

L. Fejes Tóth: Elementarer Beweis einer isoperimetrischen Ungleichung, Acta Mathematica Acad. Sci. Hung. 1 (1950), 273–276, (R^{2}-ben az izoperimetrikus egyenlőtlenség egy, az egyenlőtlenség stabilítását is magában foglaló élesítésének bizonyítása, igazából integrálgeometriával. De leírva csak a papírhajtogatás van).