# Discrete Mathematics DMI002 (Winter 13/14)

## 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.

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.