Discrete structures

Propositional logic. Propositional syntax. Logical equivalence, tautologies, contradiction. Disjunctive and conjunctive normal form. Functionally complete sets of logical connectives. Logical argument.

Predicate calculus. Domain and predicates. Interpretation. Well-formed formula. Tautologies and equivalence.

Relations and ordered sets. Binary relations and their properties. Operations on relations. Inverse relation. Product and power of relations. Closures. Equivalence relation. Partial order, linear order.

Basics of graph theory: degree, regularity, subgraph, some families of graphs, bipartite graphs, matrices of graphs. Trees. Euler and Hamiltonian paths and cycles. Planar graphs. Graph coloring.

R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA-založništvo, Ljubljana, 1997.
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
D. Veljan: Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.
N. Prijatelj: Osnove matematične logike I, DMFA-založništvo, Ljubljana, 1992.
N. Prijatelj: Osnove matematične logike II, DMFA-založništvo, Ljubljana, 1992.
N. Prijatelj: Matematične strukture I : Množice - relacije – funkcije, DMFA-založništvo, Ljubljana, 1996

Students learn the basics of mathematical proofs and correct logic inference, basic discrete structures, and the basics of graph theory.

Knowledge and understanding: Knowledge about basic concepts of logic, order structures and graph theory, and understanding of basic connections among them.
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.

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ž, PAK, Igor. Triangulations of Cayley and Tutte polytopes. Advances in mathematics, ISSN 0001-8708, 2013, vol. 245, str. 1-33. [COBISS-SI-ID 16706905]
KONVALINKA, Matjaž. The role of residue and quotient tables in the theory of k-Schur functions. Journal of combinatorial theory. Series A, ISSN 0097-3165, 2015, vol. 136, str. 1-38. [COBISS-SI-ID 17339993]

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. http://dx.doi.org/10.1007/s10801-011-0340-2. [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:
KAISER, Tomáš, ŠKREKOVSKI, Riste. T-joins intersecting small edge-cuts in graphs. Journal of graph theory, ISSN 0364-9024, 2007, vol. 56, no. 1, str. 64-71. [COBISS-SI-ID 14373977]
DVOŘÁK, Zdeněk, ŠKREKOVSKI, Riste. A theorem about a contractible and light edge. SIAM journal on discrete mathematics, ISSN 0895-4801, 2006, vol. 20, no. 1, str. 55-61. [COBISS-SI-ID 14249305]
JUNGIĆ, Veselin, KRÁL', Daniel, ŠKREKOVSKI, Riste. Colorings of plane graphs with no rainbow faces. Combinatorica, ISSN 0209-9683, 2006, vol. 26, no. 2, str. 169-182. [COBISS-SI-ID 13954393]