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.
After successful completion of this course, a student will be able to
Analyse a given combinatorial problem with a view to solve it by applying one of the standard techniques they learned.
Slightly extend some of the techniques learned and apply the extended technique to solve harder problems.
Describe clearly a few open problems in the area and their current status.
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.
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.
László Lovász, Combinatorial Problems and Exercises. (AMS Chelsea Publishing); 2nd edition. ISBN-13: 978-0821842621
Noga Alon and Joel H. Spencer, The Probabilistic Method Wiley-Blackwell; 4th revised edition ISBN-13: 978-1119061953
Herbert S. Wilf, Generating Functionology. A K Peters/CRC Press, 3rd edition ISBN-13: 978-1568812793
Stasys Jukna, Extremal Combinatorics: With Applications in Computer Science Springear; 2nd ed. ISBN-13: 978-3642173639
Richard Stanley, Enumerative Combinatorics: Volume 1. Cambridge University Press, 2nd edition. ISBN: 9781107015425
Richard Stanley, Enumerative Combinatorics: Volume 2. Cambridge University Press, 2nd edition. ISBN: 9780511609589
László Babai and Péter Frankl, Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science. Preliminary Version 2 (September 1992).
- Proposing Faculty : Deepak Rajendraprasad
- Department / Centre : Computer Science and Engineering
- Programme : B.Tech
- Proposal Type: New Course
- Offerings: S5 and S7, Aug-Dec 2018
- Offered in Jan-May, 2020 by Deepak
- Offered in July-Dec, 2018 by Deepak