Syllabus
Notion of a set (Cantor), language of set theory, formula.
Describe a set by enumeration or as a set of elements of a given property.
Basic set operations (including power set and sums) and their properties.
Cartesian product, (binary) relations, composition of relations.
Functions, functions one-to-one, onto, bijections.
Properties of relations (reflexivity, symmetry, ...).
The equivalence relation on a set, the decomposition of a set, the correspondene, examples.
Combinatorial counting.
Number of mappings (injective mappings) from n-element to m-element set, number of subsets of an n-element set.
Variations, permutations, combinations.
Binomial coefficients, binomial theorem.
The Inclusion and Exclusion Principle.
Asymptotic estimates of factorials and binomial coefficients.
Graphs: definition, basic terminology, graph isomorphism.
Vertex degree, the handshaking lemma, graph score.
Paths in a graph, connectivity, components.
Graph metric, derived notions.
Trees: their characterization and properties, the number of trees on a given set.
Tree isomorphism, tree encoding.
Spanning tree, minimum spanning tree algorithms.
Partial order, linear order, the greatest/smallest, maximal/minimal element, chain/antichain, supremum/infimum, examples.
The existence of a minimal element and the linear extension theorem for finite sets.
Isomorphism of sets with respect to relations.
Representation of a partial order by inclusion.
Good ordering, induction principle for natural numbers.
Euler trails.
Euler subgraphs and their description using vector spaces (space of cycles and cuts).
Planar graphs.
Plane drawing of a graph.
Euler formula and its consequences.
Coloring of a planar graph by five colors.
Bonus topics:
Ramsey theorem for graphs, Ramsey multicolored theorem.
Lower bound on Ramsey numbers.
Annotation
Basic course in discrete mathematics for bachelor's program Mathematics. Elements of set theory (sets, relations), introduction to combinatorics and graph theory.