Discrete Mathematics DMI002 (Winter 13/14)
(Lecturers: Petr Kolman, Jiri Matousek)
Welcome to the web page of the Discrete Mathematics course.
The lectures are scheduled on Tuesdays 12:20-13:50PM, room S11.
We will cover parts of a book by J. Matousek and J. Nesetril
(see Literature below), sometimes with moderate variations,
plus a concise introduction to discrete probability.
A brief list of the topics covered in each lecture will be provided at
the end of this page.
Tutorials
will be taught by Hans Raj Tiwary .
Literature
-
J. Matousek and J. Nesetril, Invitation to Discrete Mathematics,
Oxford University Press, preferably the 2nd edition.
Errata.
Material covered at the lectures
Oct 1 (JM)
Sample problems (3 houses + 3 wells, drawing without lifting a pencil, etc.).
Mathematical induction: basic general formulation; Fibonacci numbers
(F0=0,
F1=1,Fn+1=Fn+Fn-1)
the golden ratio phi=(1+sqrt 5)/2, proof of the inequality
Fn ≤ phin-1 by induction.
Oct 8 (JM)
Basic notation (N,Z,Q,R for sets of numbers; writing a set; lower and upper
integer part; union, intersection, difference of sets). Ordered pair (x,y),
ordered n-tuple, Cartesian product, the plane as R times R. Relation
(binary, n-ary), notation xRy. Composing relations. Function as a special
case of a binary relation.
Injective, surjective, bijective functions (or mappings).
Useful fact: if there is a bijection X -> Y, then |X|=|Y|.
Permutations, two-line and one-line notation; permutation regarded
as a rearrangement of elements.
Oct 15 (JM)
The number of functions from an n-element set to an m-element set.
The number of all subsets of a set; two proofs; notation 2X.
The number of injective functions (proof by induction). Binomial coefficient
n choose k; theorem: it counts all k-element subsets
of an n-element set (double counting). Notation X choose k.
Oct 22 (JM)
Sum of n choose k over k equals 2^n, counting proof. Pascal's indentity
(n-1 choose k-1 + n-1 choose k = n choose k, counting proof).
Counting the number of placements of m indentical balls into r numbered
boxes; result = m+r-1 choose r-1. Binomial theorem; sketch of a proof
by induction on n, and a proof by counting. Reflexive, symmetric, transitive,
weakly antisymmetric relations. Equivalences (= reflexive, symmetric,
transitive). Examples. Theorem (without proof): equivalences are in
a bijective correspondence with partitions (into equivalence classes).
Ordering (= relfexive, transitive, weakly antisymmetric).
Oct 29 (HRT)
Partial ordering (definition recap); partially ordered set (poset)
definition; notation \preceq (curly less than equal to) in the context
of orderings/posets to replace relation R; example of a poset,
powerset with "subset of" relation; Hasse diagram definition; examples
with powerset/subset of for sets of size 2 and 3; notation \prec
(curly less than); Definition of minimal element/contrast with
minimum; Example of how one could potentially draw Hasse diagram by
putting minimal elements on a higher layer and throwing them and
continuing recursively (example with {1,2,3}x{1,2,3} with the relation
(a_1,b_1)R(a_2,b_2)); Theorem without proof that every finite poset has
at least one minimal element; chains, antichains, definitions/quick
example using the previously drawn poset for power set of three
elements with "subset of" relation; notations alpha(P), omega(p);
theorem (with proof) alpha(P).omega(P)\ge |P|; application:
Erdos-Szekeres lemma on increasing/decreasing subsequences.
Nov 5 (JM)
Inclusion-exclusion principle: formulation in words and by a formula.
Proof (by counting). The hatcheck lady problem, the number D(n)
of permutations without a fixed point. A remark on two other problems
solved by inclusion-exclusion (the Euler function, counting surjective functions).
Nov 12 (JM)
Introduction to discrete probability following
this syllabus:
items 1-16.
Nov 19 (JM)
Items 17-27.
Nov 26 (JM)
Finishing the probability syllabus (item 34, bipartite subgraphs, left to
tutorials). Graphs: definition; vertices, edges, adjacent vertices, neighbor.
Complete graphs, complete bipartite graphs, path, cycle. Bipartite graph.
Graph isomorophism: definition, isomorphism as renaming vertices,
remark on the difficulty of proving graphs nonisomorphic.
Dec 3 (PK)
Estimating the number or nonisomorphic graphs with n vertices.
Simple cases of pairs of graphs that are not isomorphic (different number of vertices, edges, maximum degree, different score).
Eulerian graphs (definition, theorem). Notes about multigraphs, graphs with loops; directed graphs.
Directed Eulerian graphs (definition, theorem without proof).
Dec 10 (PK)
Graph operations: addition of an edge, deletion of an edge, deletion of a vertex.
Trees - definition, end-vertex lemma, tree-growing lemma, alternative tree characterizations.
Dec 17 (PK)
Drawing of a graph. Planar drawing, planar graphs. Jordan curve theorem (without proof). Euler's formula.
Upper bounds on number of edges in planar graphs; implications for K_{3,3} and K_5.
Jan 7, 2014 (PK)
Kuratowski's theorem (without proof). Coloring of graphs,
chromatic number. "Five color" theorem. Platonic solids and planar graphs.