Mathematics (Sep-Dec 2015)
Dr. Debrup Chakraborty (debrup(AT)cs.cinvestav.mx)
1) Invitation to Discrete
Mathematics, by Jiri Matausek and Jaroslav Nesetril
2) Combinatorics: Topics,
techniques, algorithms , by Peter J.
3) Applied Combinatorics: Fred Roberts
We will not follow strictly any of these
texts. Reading reference (1) may be useful.
Monday and Wednesday from 10:00-12:00
50% on home-works
10% on periodical quizzes
40% on tests
Homework 1 (Due September 23)
(Due October 7)
(Due October 19)
(Due November 18)
Practice problems (not to be submitted)
Hand out 1 (Equivalence relations)
Hand out 2 (Functions)
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
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
06. Sep 23. Orderings: Definition of
orderings. Partial and total orders. Immediate predecessors. Hasse
07. Sep 24. Discussions on homework problems.
08. Sep 28. Orderings: Minimal and minimum
(least) elements, extending a partial order to a linear
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,
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