Basic Information
Objectives
Graph theory and Combinatorics have wide applications in almost every area of Computer Science. Though a first course in Graph Theory lays foundational concepts, the extent of applications of Graph Theory makes it necessary to have a deeper look at Graph Theory from structural, extremal, probabilistic and algebraic view points. The course aims to introduce advanced topics on Graphs that have large applications in Computer Science, from various viewpoints and provide pointers to applications along the way.
Prerequisite: A course on Discrete Mathematics (CS1200 or equivalent) and a course on Graph Theory (MA2130 or equivalent) are a must. Mathematical maturity is an added advantage.
Audience: Undergraduate students.
Syllabus:
Connectivity: Bi-connected and 3-connected graphs. Cycle spaces and characterization of 3-connected graphs. Menger’s theorem. Algorithmic Applications.Planar Graphs: Kuratowski’s theorem. Algebraic Characterization. Algorithmic applications. Planar Separator Theorem and its applications.
Substructures inside a graph:
- Ramsey Theory: Introduction. Ramsey type theory for graphs. Ramsey numbers. Induced versions.
- Graph Minors: Topological Minors. Well quasi ordering. Forbidden minors. Graph Minor for Trees. Tree decompositions. Algorithmic applications.
- Dense Graphs: Existence of subgraphs. Szemeredi regularity lemma. Applications of regularity : Triangle freeness. Property testing.
- MidSem 20%
- EndSem 30%
Random Graphs: Models. Properties of almost all graphs. Connectivity, giant component. Appearance of subgraphs in random graphs. Matchings in random graphs. Threshold phenomenon. Models for real-world networks: Configuration and Preferential attachment models. Applications.