Combinatorics

Basic principles of counting. Binomial coefficients, set partitions, Stirling numbers of the first and second kind, Bell numbers, Lah numbers, partitions of integers. Twelve-fold way. Inclusion exclusion principle, rook polynomials. Polya theory: action of groups on sets, Burnside lemma, number of orbits. Generating function and applications to recurrence relations. Catalan numbers. Partially ordered sets and lattices: chains and antichains, Dilworth’s theorem, Sperner’s theorem. Design theory: designs, t-designs, cyclic constructions of designs.

Miklos Bona, A Walk Through Combinatorics, 2nd ed. World Scientific, New York, 2006.
N. Biggs, Discrete Mathematics, 2nd ed., Oxford Univerisity Press (2002)
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
Primož Potočnik, Zapiski predavanj iz Diskretne matematike I, http://www.fmf.uni-lj.si/~potocnik/Ucbeniki/DM-Zapiski2010.pdf

Students familiarize themselves with some classical problems of combinatorics and learn how to independently solve them.

Knowledge and understanding: Knowledge about basic concepts from classical combinatoricsRF, and understanding of basic connections among them. Basic knowledge of exact counting of objects from a given set and with specific properties.
Application: Use of discrete mathematical structures for representation of various objects and processes. Such representations play a key role in data processing with computers.
Reflection: Connection of theoretical knowledge with applications, for instance in optimizations and computer programming. Capability of recognizing problems that could be successfully described by discrete mathematical models.
Transferable skills: Knowledge about basic approaches regarding use of discrete mathematical structures. Exactness at thinking and problem solving. Capability of reading and understanding of expert literature on discrete mathematics and other closely related fields.

Lecture and exercises.

Written and oral exam.

Sandi Klavžar:
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:
POTOČNIK, Primož. Tetravalent arc-transitive locally-Klein graphs with long consistent cycles. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 270-281. [COBISS-SI-ID 16862041]
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ž. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2004, vol. 91, no. 2, str. 289-300. [COBISS-SI-ID 13087321]