Discrete Mathematics (Sep-Dec 2015)

Instructor:               Dr. Debrup Chakraborty  (debrup(AT)cs.cinvestav.mx)

References:                1) Invitation to Discrete Mathematics, by Jiri Matausek and Jaroslav Nesetril
                                     2)  Combinatorics: Topics, techniques, algorithms , by Peter J. Cameron
                                     3) Applied Combinatorics: Fred Roberts

                                     We will not follow strictly any of these texts. Reading reference (1) may be useful.

Classes:                    Monday and Wednesday from 10:00-12:00

 

Grading:                    50% on home-works
                                     10% on periodical quizzes
                                     40% on tests 

Home works:    

                                       
                         Homework 1 (Due September 23)
                         Homework 2 (Due October 7)
                         Homework 3 (Due October 19)   
                         Homework 4 (Due November 18) 
                        Practice problems (not to be submitted)                                                                                                                              

Handouts:               

                                     
                                        Hand out 1 (Equivalence relations)
                                        Hand out 2 (Functions)
                                        Hand out 3 (recurrence relations)
                         
Contents: The course will cover three topics: Algebra and Number theory, Combinatorics, Graph theory

Tentative schedule: We shall fill up as we proceed.

01. Sep 02.   Introduction and motivation
02. Sep 07.   Preliminaries: Basic set theoretic notations; concept of a proof, proof by induction.
03. Sep 09.   Proofs by induction: Weak and strong induction, several examples of proofs by induction, well ordering principle
04. Sep 11.   Relations and functions: Definition of relations. Reflexive, symmetric, antisymmetric and transitive relations. Various ways of representing relations. Equivalence relations and equivalence classes. 
05. Sep 21.   Relations and functions:  Proof of the fact that the equivalence classes of an equivalence relation on X decomposes X. Functions: injection, surjection and bijection.
06. Sep 23.   Orderings: Definition of orderings. Partial and total orders. Immediate predecessors. Hasse Diagrams
07. Sep 24.   Discussions on homework problems.
08. Sep 28.   Orderings: Minimal and minimum (least) elements, extending a partial order to a linear order, embeddings.
09. Sep 30.   Orderings: Height and width of an ordered set. Erdos Szekeres lemma.
10. Oct 05.   Infinite Sets:  Infinite sets, cardinality, countable sets, real numbers are not countable, continuum hypothesis.
11. Oct 08.   Number theory: Divisibility, greatest common divisors, primes
12. Oct 12.   Number theory
13. Oct 14.   Number theory
14. Oct 15.   Number theory
15. Oct 19.   Discussions
16. Oct 21.   Test 1