MA 4090: Combinatorics and Graph Theory (sharing with Dr. Pradipto Banerjee)
All the updates related to MA 4090 are announced here. I am teaching the combinatorics part.
Class timings:
Tuesday: 08:30 am to 10:00 am
Saturday: 09:00 am to 10:30 pm
Examination and Grades:
The grades will be decided by the marks obtained in the surprise tests, mid-term, the final examination, and also by the performance in the class.
Syllabus:
Basic counting: Bijections, Counting objects with repetitions, de Bruijn-Erdos theorem, Listing combinatorial objects.
Permutations: Combinatorial representation of a permutation, Descents and Eulerian polynomial, Tree representation for permutations.
Inclusion-Exclusion principle: Use of Rook polynomial, Some arithmetic and Mobius functions.
Parity: Parity in Graph theory, Eulerian circuits in graphs, digraphs and de Bruijn circuits, Hypercubes and Gray codes,
Parity of a permutation, Quadratic reciprocity. Pigeonhole principle: Ramsey theorem, The infinite case.
Geometry: Regular polytopes and tessellations of plane, triangulations and Sperner's lemma.
Recurrence relations: Fibonacci recurrence relation, Linear homogeneous recurrence relations with constant coefficients,
Case of repeated roots, Difference tables and sums of polynomials, Other types of recurrence relations.
References:
- Sharad S. Sane, Combinatorial Techniques, Texts and Reading in Mathematics, Hindustan Book Agency, 2013.
- Tremblay and Manohar, Discrete Mathematics Structures with Applications to Computer Science, McGraw Hill, 1997
- Liu and Mohapatra, Elements of Discrete Mathematics, Tata McGraw Hill, 2008.
Assignments:
The assignments have to be submitted right after the class on the respective due dates. The assignments can be submitted after the due date and time as well,
but only 50% of the marks will be credited into your account, unless you have a valid reason for the late submission.
- Assignment 1: Updated on: 04.09.2016, Due on 16.09.2016.
- Assignment 2: Updated on: 28.09.2016, Due on 17.10.2016.
Some of the assignments and tutorial sheets are being prepared by Mr. Jadav Ganesh, a tutorial assistant for MA 4090 in July - Nov 2016.