Department of
Applied
Mathematics

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 06: Sample problems (drawing without lifting pencil, 3 houses + 3 wells, etc). Types of proofs: proof by contradiction, mathematical induction; Fibonacci numbers (\(F_0=1, F_1=1, F_{n+1}=F_n+F_{n-1}\)); the golden ration \(\phi=(1+\sqrt{5})/2\); proof of the inequalities \( \phi^{n-1}\leqslant F_n \leqslant \phi^n\) by induction.


October 13: Basic notations (\(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\) for sets of numbers; writing a set; union, intersection, difference, complement of sets). Ordered pair \((x,y)\), ordered \(n\)-tuple, Cartesian product and \(n\)-fold product. Relations; Composing relations; Functions; Injective, surjective, bijective functions; bijection \(X\to Y\) implies \(|X|=|Y|\); permutations; number of functions from \([n]\to[m]\); number of subsets of a set; number of injective functions; number of permutations.


October 20: Recap: number of functions from \([n]\to[m]\), number of subsets of a set, number of injective functions, number of permutations. Number of disjoint subsets; Binomial coefficient \(n\choose k\); notation \(X\choose k\); Double counting; example: \(\displaystyle\left|{X\choose k}\right|={|X|\choose k}\); \(\sum_{k=0}^n{n\choose k}=2^n\); Pascal's identity: \({n-1\choose k}+{n-1\choose k-1}={n\choose k}\); Counting the number of nonnegative integer solutions of \(x_1+x_2+\ldots+x_r=n\); Relations: reflexive, symmetric, antisymmetric, transitive.


October 27: Equivalence relations: equivalence classes; Order; Partial vs. Total Order; Poset; notation \(\preceq\); example of a poset: power set with "subset of" relation; Minimal, maximal, minimum, maximum elements; Hasse Diagram; Every finite poset has at least one minimal element; Drawing Hasse Diagram by recursively removing minimal elements; chains, antichains; Notation: \(\alpha(P),\omega(P)\); Theorem: \(\alpha(P)\omega(P)\geqslant |P|\); Application: Erdös-Szekeres theorem.


November 03: 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; Introduction to Probability: definition of probability space (only finite set of outcomes); Probabilities as arbitrary functions \(f:2^\Omega\to [0,1]\) that satisfy some axioms.


November 10: 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]=\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; Proof \((x+y)^n=\sum_{k=0}^n{n\choose k}x^ky^{n-k}\) for \(x,y\geqslant 0, x+y>0\) via \(n\) tosses of a biased coin.


November 24: 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, expected number of left maxima in a random permutation; Every graph has a bipartitite subgraph with at least half the number of edges (proof using expectation); Asymptotic notation.


December 01: Graphs and definition of 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); Definition of Incidence matrix.


December 08: (MM) Sections 4.2-4.4 of Invitation to DM; some discussions about weighted graphs and adjacency matrix.


December 15: Definition of a tree; end-vertex lemma; tree-growing lemma; various equivalent charecterizations of trees: path uniqueness, minimimal connectedness, maximal graph without cycles, Euler's formula \(|V|=|E|+1\); Isomorphism testing on trees in polynomial time; Spanning Trees; every connected graph contains a spanning tree.


January 05: Definitions: simple arc, drawing of a graph, planar drawing, plane graph, planar graph, Jordan curve (simple closed curve); Jordan curve theorem (without proof); Application: Non-panarity of \(K_5\); Euler's formula; Applications: Upper bounds on the number of edges of planar graphs and triangle-free planar graphs; Consequence: Non-planarity of \(K_5, K_{3,3}\).


January 12: 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.