Learning Objectives

The objective of this course is to introduce the students to various techniques in combinatorics by guiding them through a set of carefully chosen problems.

Learning Outcome

After successful completion of this course, a student will be able to

  1. Analyse a given combinatorial problem with a view to solve it by applying one of the standard techniques they learned.

  2. Slightly extend some of the techniques learned and apply the extended technique to solve harder problems.

  3. Describe clearly a few open problems in the area and their current status.

Syllabus

Elementary techniques (to be reviewed)

Bijective proofs, mathematical induction, pigeonhole principle, double counting, parity arguments, and inclusion-exclusion principle.

Advanced techniques (to be introduced)

Generating functions. Ordinary, exponential and other special generating functions, formal power series.

Probabilistic arguments. Positive probability based existence arguments, moment based arguments, alteration technique, Lovász local lemma.

Linear Algebraic arguments. Dimensionality arguments, orthogonality and rank arguments.

Problem selection

The problems to introduce and illustrate the power of the above techniques will be chosen from these areas: sets, partitions, sequences, permutations, graphs, partial orders, algorithms, geometry and number theory.

Textbooks

  1. László Lovász, Combinatorial Problems and Exercises. (AMS Chelsea Publishing); 2nd edition. ISBN-13: 978-0821842621

  2. Noga Alon and Joel H. Spencer, The Probabilistic Method Wiley-Blackwell; 4th revised edition ISBN-13: 978-1119061953

  3. Herbert S. Wilf, Generating Functionology. A K Peters/CRC Press, 3rd edition ISBN-13: 978-1568812793

  4. Stasys Jukna, Extremal Combinatorics: With Applications in Computer Science Springear; 2nd ed. ISBN-13: 978-3642173639

References

  1. Richard Stanley, Enumerative Combinatorics: Volume 1. Cambridge University Press, 2nd edition. ISBN: 9781107015425

  2. Richard Stanley, Enumerative Combinatorics: Volume 2. Cambridge University Press, 2nd edition. ISBN: 9780511609589

  3. László Babai and Péter Frankl, Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science. Preliminary Version 2 (September 1992).

Meta Data

  • Proposing Faculty : Deepak Rajendraprasad
  • Department / Centre : Computer Science and Engineering
  • Programme : B.Tech
  • Proposal Type: New Course
  • Offerings: S5 and S7, Aug-Dec 2018

Past Offerings

  • Offered in Jan-May, 2020 by Deepak
  • Offered in July-Dec, 2018 by Deepak

Course Metadata

Item Details
Course Title Combinatorics
Course Code CS4503
Course Credits 3-0-0-3
Course Category PME
Approved on Senate of IIT Palakkad