Category: Computer Science
Published: Sunday, 24 May 2015

This is a graduate level course being offered at Indiana University as part of the foundational requirements for MS/PhD. I took this course on Spring 2013 with Prof. Esfandiar Haghverdi. The book we mainly used was Extremal Combinatorics: With Applications in Computer Science (Texts in Theoretical Computer Science. An EATCS Series). Other books are: Modern Graph Theory (Graduate Texts in Mathematics) and Additive Combinatorics (Cambridge Studies in Advanced Mathematics). These are good resources but more on the advance side. Getting help with this material is not that easy.

The following is a compilation of my solutions to assignments given in class.

- Assignment 1 - [Solution]
- Assignment 2 - [Solution]
- Assignment 3 - [Solution]
- Assignment 4 - [Solution]

- Multilinear Polynomials
- Alon-Babai-Suzuki’s Conjecture related to binary codes in non-modular version
- Extremal results on finite sets
- Dimension and Polynomials

Extremal Combinatorics is all about finding bounds. Usually you have some sort of discrete and finite object (say a graph) and considering its structure (say number of edges and vertices) you want to estimate a non-trivial property (for example, number of triangles in it -number of 3-edges fully connected-). A classical type of result is the Handshaking Lemma. The main figure of this field is Paul Erdős, a brilliant Mathematician of the past century (which indicates that this is a relatively new field of Mathematics). I think this type of field that specializes in discrete and finite structures is going to become more relevant as it relates to Computer Science and networks in particular. Amazingly enough it seems that this is a harder subject of study than the classic Mathematical Analysis that deal with infinite and uncountable sets. Strange how infinite sets are, to an extent, easy to analyze than finite ones (I recommend a series of Lectures by Prof. N J Wildbergeron this subject).