Tečaj iz algebraične kombinatorike - 2007

o tečaju | prosojnice | domače naloge | projekti knjižnica | zanimive povezave

Obvestila

Tabela krepko-regularnih grafov do 1300 vozlišč.

11.jun. Dodiplomci ste dobili pisni izpit za domov (rok je 15. junij 2007) - dodal sem še eno novo nalogo čisto na koncu.

8.jun. Predstavitve projektov pa bodo v četrtek 14. junija ob 15h (zberemo se pred mojo pisarno).

Dobili ste daljši seznam projektov (ps, pdf) rok za oddajo načrta je 1. junij 2007.

Predavanja: ob petkih od 12h do 14h
na Jadranski 21 (3.05).

Predavatelj: Aleksandar Jurišić
pisarna: Jadranska 21/0.05 (vhod s strani Gradaščice)
tel: 4778-638,
(doma 28-32-895)
e-pošta: ajurisic@valjhun.fmf.uni-lj.si,

Vaje: ob torkih od 10h do 11h

Asistent: Matjaž Urlep
pisarna: Jadranska 21/0.06 (vhod s strani Gradaščice)
tel: 47-68-183
govorilne ure: po dogovoru
e-pošta: matjaz.urlep@fri.uni-lj.si

Predavanja v spomladanskem sem. '07:

16. feb. Uvod, (I) KONSTRUKCIJE: incidenčne strukture, t-designi, preštevanje na dva načina, projektivne ravnine, projektivni prostori, primeri
23. feb. PG(2,2), PG(2,3), PG(2,4), Fisherjeva neenakost, kvadratni designi, pravokotne škatle (angl. orthogonal arrays, OA)), nekatere konstrukcije in ocene za OA.
2. mar.(II) GRAFI, LASTNE VREDNOSTI IN REGULARNOST: število različnih lastnih vrednosti, ponovitev osnov teorije matrik, lastne vrednosti posameznih komponent, regularnost in dvodelnost, lastne vrednosti komplementa in en primer uporabe (lastne vrednosti polnega in polnega večdelnega grafa), lastne vrednostni grafov povezav, Gramova matrika in njena uporaba.
9. mar. (I) Hadamardove matrike (kot ekstremne matrike, definicija, Hadamardova matrična domneva, majhni primeri, rekurzivna konstrukcija, konferenčne matrike in 2-designi),
(III) KREPKO-REGULARNI GRAFI: regularnost, definicija, primeri, trivialni primeri, zveza med parametri, komplement, matrike sosednosti in lastne vrednosti.
16. mar. povezani grafi z natanko tremi lastnimi vrednostmi, večkratnosti lastnih vrednosti, klasifikacija , Paleyjevi grafi, Kreinov pogoj, Smitovi grafi, grafi (negativnega) LS tipa (LS=latinski kvadrat), TD grafi, Steinerjevi grafi; enoličnost v primeru nekaterih parametrov ter super-eksponentno mnogo grafov v primeru nekih drugih, zelo podobnih parametrov; Neumaierjev izrek.
23. mar. dopustna zaporedja presečnih števil, majhni primeri (P(13), Tuttova 8-kletka, Clebschov graf, Shrikhandejev graf, Schlaeflyjev graf), Moorovi grafi, znamenit odprt problem (3250).
(IV) DELNE GEOMETRIJE: definicija, klasifikacija, psevdogeometični grafi, kvadratne forme, izotropični prostori
30. mar. klasični posplošeni četverokotniki, majhni primeri.
(V) ASOCIATIVNE SHEME: definicija, Bose-Mesnerjeva algebra, trivialna shema.
6. apr. shema z dvema razredoma, primeri (Hammingova shema H(d,n), shema bilinearnih form BFS(d,m,q), Johnsonova shema J(n,d), Grassmanova shema J_q(n,d) in ciklomatična shema C(q,d)), preverjanje aksiomov in simetrija, primitivnost in neprimitivnost, dve baze in dualnost (primitivni idempotenti, lastne vrednosti in dualne lastne vrednosti, Kreinovi parametri.
13. apr. računanje Kreinovih parametrov, Kreinove ocene, absolutne meje, metrične in kometrične asociativne sheme, Kreinov pogoj in krepko regularen graf,
(VI) EKVITABILNE PARTICIJE: definicija, orbite delovanja, karakteristični vektor in matrika, kvocijent, lastne vrednosti, krov, antipoden krov.
20. apr. (VII) RAZDALJNO-REGULARNI GRAFI: definicija, primer, razdaljno tranzitivni grafi, presečna števila, lastnosti presečnih števil, lastne vrednosti, neprimitivni razdaljno regularni grafi in Smitov izrek, klasifikacija, klasične družine in parametrizacija z Gaussovimi koeficienti, antipodni razdaljno-regularni grafi, dvodelna podvojitev (bipartite double).
27. apr. nadomestimo 1. junija.
4. maj antipodni razdaljno-regularni grafi: Gardinerjev izrek, povezave z drugimi področji, orodja, cilji.
11. maj izrek o večkratnosti starih lastnih vrednosti, izrek o novih lastnih vrednostih, antipodni krovi majhnega premera: d=3: trditev o lokalno cikličnih razdaljno-regularnih grafih, 1-skeleti Platonskih teles s trikotniškimi lici (tetraeder, kocka, ikozaeder), Kleinov graf in Mathonova konstrukcija, d=4 in 5: presečno zaporedje in vsa presečna števila, lastne vrednosti in večkratnosti, Kreinovi parametri in Q-polinomska lastnost lista dopustnih parametrov.
18. maj (VIII) 1-HOMOGENI GRAFI: primeri, lokalno nepovezani 1-homogeni grafi, lokalno krepko regularni, lokalen pristop in CAB lastnost, klasifikacija lokalno Moorovih 1-homogenih grafov, klasifikacija Terwilligerjevih grafov s c₂.
25. maj kosinusno zaporedje, moduli.
(IX) TESNI GRAFI: lastne vrednosti povezanega regularnega grafa, Terwilligerjev izrek o mejah za lastne vrednosti lokalnega graha, karakterizacija tesnih grafov z 1-homogeno lastnostijo in z lastnimi, primeri.
1. jun. parametrizacija z dvema kosinusnima zaporedjema, karakterizacija tesnih grafov z določeno parametrizacijo d+1 parametrov, AT4 družina, domneva, klasifikacija poddružine AT4(sq,q,q), enoličnost Pattersonovega grafa in karakterizacija Suzukijeve grupe.
17. jun. predstavitve projektov in kratko predavanje o enoličnosti majhnega krepko-regularnega grafa.

Vse postscript (ps) datoteke si lahko ogladate z Ghostscript in GSview, ki so na voljo za večino računalnikov in brskalnikov.

Osnovni podatki o tečaju iz algebraične kombinatorike, 2007

vsebina | učbeniki

Namen tečaja: Študirali bomo prepletanje algebre in kombinatorike, ki je znano pod imenom algebraična kombinatorika. To je diskretna matematika, kjer pa imajo objekti in strukture določeno stopnjo regularnosti ali simetrije. Pomembnejša področja praktičnih uporab algebraične kombinatorike so teorija kodiranja za odpravljanje napak, teorija statističnega načrtovanja eksperimentov, ter (prek končnih geometrij in končnih obsegov) tudi kriptografija. poznali bomo številne zanimive kombinatorne objekte. Namen tega tečaja je splošen uvod v algebraično kombinatoriko ter osvetlitev njenih pomembnejših dosežkov v zadnjih petdesetih letih.

Vsebina tečaja: poskusili bomo obravnavati čim več tem z naslednjega seznama:

t-designi
Latinski kvadrati, transverzalni designi in pravokotne škatle,
Hadamardove matrike in rekurzivne konstrukcije (Reed-Mullerjeve kode prvega reda)
konferenčne matrike,
Paleyeve matrike in grafi,
krepko-regularni grafi,
delne geometrije,
asociativne sheme,
ekvitabilne particije,
razdaljno-regularni grafi,
1-homogeni grafi,
tesni grafi.

Učbeniki:

L. M. Batten, Combinatorics of Finite Geometries, Cambridge University Press, 2. izdaja, 1997.
N.L. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 2nd edition, 1994.
N.L. Biggs in A. T. White, Permutation groups and combinatorial structures, Cambridge University Press, Cambridge, 1979.
P. J. Cameron, Projective and Polar Spaces, QMW Maths Notes, 1991.
P. J. Cameron in J. H. van Lint, Designs, Graphs, Codes and Their Links, London Math. Soc. Student Texts 22, Cambridge Univ. Press, Cambridge, 1991.
J.D. Dixon in B. Mortimer, Permutation groups, Springer, New York, 1996.
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
C. D. Godsil in G. Royle, Algebraic Graph Theory Springer Verlag (New York), 2001.
J. H. Van Lint in R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2. izdaja, 2001.

Referenčne knjige:

A. E. Brouwer, A. M. Cohen in A. Neumaier, Distance-Regular Graphs, Springer, New York, 1989.
C. J. Colbourn in J. Dinitz (urednika), CRC Handbook of Combinatorial Designs, CRC-Press, 1996.
R. L. Graham, M. Groetschel, L. Lovasz (uredniki), Handbook of Combinatorics: 2-volume set, MIT Press, 1996.
F. Buekenhout (urednik), Handbook of Incidence Geometry: Buildings and Foundations, North-Holland, 1995.

Domače naloge: Prepričan sem, da se znanje najbolje pridobi z intenzivnim skupinskim študijem (kjer ima vsak posameznik priložnost testirati svoje predloge in vprašanja) ter najbolje utrdi z reševanjem večjega števila nalog. Priporočam, da rešite približno 5 vprašanj na teden. Rešitve naj bodo lično napisane do naslednjega predavanja.
Dobili boste tudi nekaj obveznih domačih nalog in morda seminarsko nalogo (če bo koga zanimalo).