# 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