Discrete Mathematics

This is a basic course for undergraduate students. Exercises are led by Dr. Andrew Goodall.

Organization

The lectures are scheduled on Mondays at 10:40am in lecture room S11. The final grade for the course will be based on an exam at the end of the semester. You must obtain a "pass" in the tutorial to be able to take the exam for this course.

Syllabus

Follow this link to see what was covered during the past year in this course. The exact material covered during the lectures will be updated on this page. The following is a list of Books and other material relevant to the lectures.



Invitation to Discrete Mathematics by Jiří Matoušek and Jaroslav Nešetřil
Notes on Probability by Jiří Matoušek

Material Covered in the Lectures


October 03: Sample problem (drawing without lifting pencil); types of proofs: case analysis, proof by contradiction, mathematical induction; Fibonacci numbers \(F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}\); the golden ratio \(\phi=(1+\sqrt{5})/2\); proof of the inequalities \(\phi^{n-2}\leqslant F_n \leqslant \phi^{n-1}\) by induction; proof that \(\sum_{i=1}^n i = n(n+1)/2\).


October 10: Basic notation \(\mathbb{N,Z,Q,R}\); writing a set; operations on sets: union, intersection, difference, complement; ordered pair, tuples; cartesian product, \(n\)-fold product; relations; composition of relations; functions: injection, surjection, bijection; number of functions from an \(n\)-element set to an \(m\)-element set; number of subsets of a set (two proofs); number of odd and even sized subsets of a set.


October 17: Number of injective functions from \([n]\) to \([m]\); pigeonhole principle; permutations: two-line and one-line notation; number of permutations of a finite set; Binomial coefficients; notation \(X\choose k\); double counting; \(\displaystyle\left|{X\choose k}\right|={|X|\choose k}\); \(\sum_{k=0}^n{n\choose k}=2^n\); Pascal's identity; number of nonnegative integer solutions of \(x_1+x_2+\ldots+x_r=n\); binomial theorem (proof by induction); applications: \(\sum_{k=0}^n{n\choose k}=2^n\), number of odd subsets of a set.


October 24: Equivalence relation; partitition into equivalence classes; example: \(x\sim y\) iff \( x=y\text{ mod }5\); Order; linear/total vs. partial; Poset; minimal, maximal, minimum, maximum elements; Every finite poset has at least one minimal element; partial orders can be extended to total orders; Drawing posets: Hasse diagram.


October 31: Chains, antichains; Notation: \(\alpha(P),\omega(P)\); Theorem: \(\alpha(P)\omega(P)\geqslant |P|\); Application: Erdös-Szekeres theorem; Inclusion-Exclusion principle (including a proof by counting); fixed point of a permutation; number \(D(n)\) of permutations without a fixed point; The hatcheck lady.


November 07: Definitions: Probability space, uniform probability; Example: Probability of getting exactly \(k\) heads in the throw of \(n\) coins; Finite version of Boole's inequality: \(P\left[\bigcup_{i=1}^n B_i\right]\leqslant\sum_{i=1}^n P[B_i]\), equality when \(B_i\)'s are disjoint; Example: Probability that a random graph is bipartite; Conditional probability; Baye's theorem; Independent events; Product of probability spaces; Independence of events of the form \(A_1\times\Omega_1\) and \(\Omega_2\times A_2\) in product spaces; Tossing a fair coin \(n\) times vs. "fair throw" of \(n\) coins.


November 14: Definitions: Random variable, expectation; Indicator function; Linearity of expectation, independent random variables; Examples: expected number of heads in a sequence of \(n\) tosses of a fair coin; Every graph has a bipartitite subgraph with at least half the number of edges (proof using expectation).


Noevmber 21: Graphs; examples: complete graph, cycle, path, complete bipartite; Graph isomorphism; Comments on computational aspect (the dificulty in verifying non-isomorphism); Estimating the number of nonisomorphic graphs; Graph score; Handshake lemma; Score theorem (without proof).


November 28: Subgraphs/Induced subgraphs; paths and cycles in a graph; connectedness/components; walk; graph representations: drawing, listing vertices/edges, adjacency matrix; Eulerian graphs; A graph is Eulerian if and only if every vertex has even degree; comments about directed graphs and directed Eulerian graphs.


December 05: Revision


December 12: Trees; End-vertex lemma; Tree-growing lemma; five different tree characterizations; Spanning tree; A graph has a spanning tree iff it is connected.


December 19: Simple arc; drawing; topological graph; planar drawing; faces of a planar drawing; Jordan curve theorem (without proof); Application: \(K_5\) is not planar; Kuratowski theorem (without proof): subdivision as well as minor versions; Euler formula for planar graphs; number of edges in planar graphs; number of edges in triangle-free planar graphs; Application: \(K_5, K_{3,3}\) are not planar.


January 09: Platonic solids and planar graphs; Proof that only five kinds of platonic solids exist; Coloring maps: the four-color theorem (without proof); Definition: Dual graph; Chromatic number problem; Six-color theorem for planar graphs; five-color theorem for planar graphs.


End of lectures.