Login
Course Information
Identification

CS 604: Combinatorics
 
Description

Min-max results. Dilworth"s theorem, Hall"s theorem. Menger"s theorem. Topics on tournaments. Perfect graphs. The weak perfect graph theorem. Ramsey theory. Set Systems. Sperner, Erdos-Rado and the Erdos-Ko-Rado theorems. Colex orders and the Kruskal-Katona theorem.

The probabilistic method. Some sample applications of the probabilistic method. Second moment method and applications. Matroid theory. The theory of designs. Combinatorics and Algorithm design. The Lovasz-theta function and its use in designing algorithms.
 
References

K. R. Parthasarathy, Basic Graph Theory, Tata McGraw-Hill, 1994.

B. Bollobas, Combinatorics, Cambridge University Press, 1986.

I. Anderson, Combinatorics of finite sets, Oxford University Press, 1987.

N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley and Sons, 1992.
 
Home Page

http://www.cse.iitb.ac.in/~cs604
 
Prerequisites

NIL
 
Other Details

Duration : Full Semester Total Credit : 6
Type : Theory
 
Current Semester (Autumn 2017-18)

Status : Not Offered Instructor : ---
 
Next Semester (Spring 2017-18)

Status : Offered Instructor : Prof. Sundar Vishwanathan




Last Modified Date: 09-May-2016

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback