Discrete mathematics 2

Dimension of a partially ordered set. Dilworth’s, Hall’s, Sperner’s theorem. Design theory: designs, t-designs, cyclic construction of designs, Fisher’s inequality. Polya theory: permutation groups, Burnside lemma, symmetries and counting. Symmetry properties of graphs: automorphism group, vertex-transitive, edge-transitive, arc-transitive graphs, Cayley graphs, Sabidussi theorem. Cartesian product of graphs: fibers, projections, connectivity, hypercubes, Hamming graphs, Hanoi graphs. Ramsey theory.
The lecturer selects one topic from graph theory or combinatorics.

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.

A student gets an overview of the following discrete mathematics fields: discrete geometry, combinatorics and graph theory. During the study the connection with other fields of mathematics are emphasized.

Knowledge and understanding: General understanding of broad spectrum of discrete mathematical structures and in-depth knowledge about some of them.
Application: Mathematical structures from discrete mathematics have applications in optimization and computer programming, and play an important role in some other fields of mathematics.
Reflection: Connection of theoretical knowledge with practical applications, for instance in optimization, computer programming and other fields of mathematics. Capability of recognizing problems that could be successfully described by discrete mathematical models.
Transferable skills: Through the presentation of various selected examples a student gets familiar with various methods for proving mathematical results and gets insight into connections between different fields of mathematics. It becomes capable of reading and understanding of expert literature on discrete mathematics and other closely related fields.

Lectures, exercises, homework, consultations

2 midterm exams instead of written exam, written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of 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]