Discrete mathematics 1

Mathematics Education
2 year
Lecturer (contact person):

Prof. Dr. Marko Petkovšek

Hours per week – 2. semester:
Content (Syllabus outline)

Basics of combinatorial counting:
Basic principles of counting. Binomial coefficients, set partitions, Stirling numbers of the first and second kind, Bell numbers, Lah numbers, partitions of an integer. Twelve-fold way. Inclusion-exclusion principle and rook polynomials. Recurrence equations, solutions via generating functions and, algebra of formal power series, Catalan numbers.
Basics of graph theory:
Basic definitions. Homomorphisms, isomorphisms and automorphisms of graphs. Connectivity. Trees and binary graphs. Closed walks and cycles. Eulerian circuit and Hamiltonian cycle. Planar graphs and Euler's formula. Vertex and edge colorings.


R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA-založništvo, Ljubljana, 1997.
J. H. van Lint, R. M. Wilson: A Course in Combinatorics, 2nd edition, Cambridge Univ. Press, Cambridge, 2001.
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
D. Veljan: Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.

Objectives and competences

Students get familiar with elementary discrete structures, basic concepts from combinatorics and basic graph theory.

Intended learning outcomes

Knowledge and understanding: Knowledge about basic concepts from classical combinatorics and graph theory, and understanding of basic connections among them. Basic knowledge of exact enumeration of objects with specific properties.
Application: Use of discrete mathematical structures for representation of various objects and processes. Such representations play a key role in computerized data processing.
Reflection: Connection of theoretical knowledge with applications, for instance in solving optimization problems and in programming. Capability of recognizing problems that could be successfully described using discrete mathematical models.
Transferable skills: Knowledge of basic techniques for applications of discrete mathematical structures. Exactness in thinking and problem solving. Capability of reading and understanding specialized literature on discrete mathematics and related fields.

Learning and teaching methods

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)

Lecturer's references

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]
Marko Petkovšek:
PETKOVŠEK, Marko. Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2002, vol. 244, no. 1-3, str. 375-388. [COBISS-SI-ID 11414873]
PETKOVŠEK, Marko, ZAKRAJŠEK, Helena. Enumeration of I-graphs: Burnside does it again. Ars mathematica contemporanea, ISSN 1855-3966. [Tiskana izd.], 2009, vol. 2, no. 2, str. 241-262. [COBISS-SI-ID 15497049]
PETKOVŠEK, Marko. Counting Young tableaux when rows are cosets. Ars combinatoria, ISSN 0381-7032, 1994, let. 37, str. 87-95. [COBISS-SI-ID 8048473]
PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337]
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]