Diskretna matematika 2

Dimenzija delno urejenih množic. Dilworthov, Hallov in Spernerjev izrek. Teorija načrtov: načrti, t-načrti, ciklične konstrukcije načrtov, Fisherjeva neenakost. Polyeva teorija: permutacijske grupe, Burnsidova lema, simetrije in štetje. Simetrijske lastnosti grafov: grupa avtomorfizmov, vozliščno-tranzitivni, povezavno-tranzitivni, ločno-tranzitivni grafi, Cayleyjevi grafi, Sabidussijev izrek. Kartezični produkt grafov: vlakna, projekcije, povezanost, hiperkocke, Hammingovi grafi, hanojski grafi. Ramseyjeva teorija.
Predavatelj izbere še eno temo iz teorije grafov ali kombinatorike.

M. Aigner, G. M. Ziegler: Proofs from THE BOOK, 3. izdaja, Springer, Berlin, 2004.
C. Godsil, G. Royle: Algebraic Graph Theory, Springer, New York, 2001.
J. H. van Lint, R. M. Wilson: A Course in Combinatorics, 2. izdaja, Cambridge Univ. Press, Cambridge, 2001.
R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA-založništvo, Ljubljana, 1997.

Študent pregledno spozna področja diskretne matematike: diskretno geometrijo, kombinatoriko in teorijo grafov. Pri študiju problemov so poudarjene povezave z drugimi področji matematike.

Znanje in razumevanje: Pregledno poznavanje širokega spektra diskretnih matematičnih struktur in poglobljeno znanje o nekaterih izmed njih.
Uporaba: Matematične strukture, ki jih obravnava diskretna matematika, je moč uporabiti pri reševanju praktičnih problemov na primer v optimizaciji ali pri programiranju, pomembno vlogo pa imajo tudi v drugih vejah matematike.
Refleksija: Povezovanje teoretičnih spoznanj s praktičnimi uporabami na primer v optimizaciji in pri programiranju ter z uporabami na drugih področjih matematike. Sposobnost prepoznavanja problemov, ki jih lahko uspešno opišemo z diskretnimi matematičnimi modeli.
Prenosljive spretnosti – niso vezane le na en predmet: Slušatelj prek izbranih primerov spozna različne metode dokazovanja matematičnih rezultatov in uvidi povezave med različnimi vejami matematike. Sposoben je samostojno prebirati strokovno literaturo iz diskretne matematike in sorodnih področij.

Predavanja, vaje, domače naloge, konzultacije

2 kolokvija namesto izpita iz vaj / izpit iz vaj
izpit iz teorije
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Sandi Klavžar:
ILIĆ, Aleksandar, KLAVŽAR, Sandi, RHO, Yoomi. Generalized Lucas cubes. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2012, vol. 6, no. 1, str. 82-94. [COBISS-SI-ID 16242265]
BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas. Domination game and an imagination strategy. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]
HAMMACK, Richard H., IMRICH, Wilfried, KLAVŽAR, Sandi. Handbook of product graphs, (Discrete mathematics and its applications). Boca Raton, London, New York: CRC Press, cop. 2011. XVIII, 518 str., ilustr. ISBN 978-1-4398-1304-1. [COBISS-SI-ID 15916121]
IMRICH, Wilfried, KLAVŽAR, Sandi, RALL, Douglas F. Topics in graph theory : graphs and their Cartesian product. Wellesley (Mass.): A. K. Peters, 2008. XIV, 205 str., ilustr. ISBN 978-1-56881-429-2. [COBISS-SI-ID 14965081]
Matjaž Konvalinka:
KONVALINKA, Matjaž. Skew quantum Murnaghan-Nakayama rule. Journal of algebraic combinatorics, ISSN 0925-9899, 2012, vol. 35, no. 4, str. 519-545. [COBISS-SI-ID 16250713]
KONVALINKA, Matjaž, PAK, Igor. Geometry and complexity of O'Hara's algorithm. Advances in applied mathematics, ISSN 0196-8858, 2009, vol. 42, iss. 2, str. 157-175. [COBISS-SI-ID 15545945]
KONVALINKA, Matjaž. On quantum immanants and the cycle basis of the quantum permutation space. Annals of combinatorics, ISSN 0218-0006, 2012, vol. 16, no. 2, str. 289-304. [COBISS-SI-ID 16310873]
Primož Potočnik:
KNOR, Martin, POTOČNIK, Primož, ŠKREKOVSKI, Riste. The Wiener index in iterated line graphs. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2012, vol. 160, iss. 15, str. 2234-2345. [COBISS-SI-ID 16409945]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of symbolic computation, ISSN 0747-7171, 2013, vol. 50, str. 465-477. [COBISS-SI-ID 16520537]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. On the nullspace of arc-transitive graphs over finite fields. Journal of algebraic combinatorics, ISSN 0925-9899, 2012, vol. 36, no. 3, str. 389-401. [COBISS-SI-ID 16162137]
JUVAN, Martin, POTOČNIK, Primož. Teorija grafov in kombinatorika : primeri in rešene naloge, (Izbrana poglavja iz matematike in računalništva, 39). Ljubljana: Društvo matematikov, fizikov in astronomov Slovenije, 2000. VI, 173 str., graf. prikazi. ISBN 961-212-105-2. [COBISS-SI-ID 106210560]
Riste Škrekovski:
FINK, Jiří, LUŽAR, Borut, ŠKREKOVSKI, Riste. Some remarks on inverse Wiener index problem. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2012, vol. 160, iss. 12, str. 1851-1858. [COBISS-SI-ID 16295257]
GREGOR, Petr, ŠKREKOVSKI, Riste. Parity vertex colorings of binomial trees. Discussiones mathematicae, Graph theory, ISSN 1234-3099, 2012, vol. 32, no. 1, str. 177-180. [COBISS-SI-ID 16514649]
MADARAS, Tomáš, ŠKREKOVSKI, Riste. Lightness, heaviness and gravity. V: HORNÁK, Mirko (ur.), JENDROL, Stanislav (ur.). Cycles and colourings 2003 : Stará Lesná, Slovakia, August 31-September 5, 2003, (Discrete mathematics, ISSN 0012-365X, Vol. 307, Issues 7-8). Amsterdam: North-Holand, 2007, vol. 307, iss. 7-8, str. 939-951. [COBISS-SI-ID 14249817]