MU-307 Combinatorics & Graph Theory

Unit · year 3

MU-307 · Combinatorics & Graph Theory

Threads structure · number24 lectures5 theorems

Extremal and structural results about finite configurations.

PREREQUISITES

L01	Enumerative Combinatorics: A Refresher —
L02	Generating Functions —
L03	Recurrences and Asymptotics —
L04	The Probabilistic Method Ramsey's theorem
L05	Ramsey Numbers Ramsey's theorem
L06	Ramsey's Theorem Ramsey's theorem
L07	Bounds on Ramsey Numbers Ramsey's theorem
L08	Extremal Graph Theory: The Question Turán's theorem
L09	Turán's Theorem Turán's theorem
L10	The Erdős–Stone Theorem Turán's theorem
L11	Bipartite Graphs and Matchings Hall's marriage theorem
L12	Hall's Marriage Theorem Hall's marriage theorem
L13	König's Theorem and Applications Hall's marriage theorem
L14	Network Flows The max-flow min-cut theorem
L15	The Max-Flow Min-Cut Theorem The max-flow min-cut theorem
L16	Ford–Fulkerson and Algorithmic Aspects The max-flow min-cut theorem
L17	Connectivity and Menger's Theorem The max-flow min-cut theorem
L18	Planar Graphs and Euler's Formula Kuratowski's theorem
L19	Kuratowski's Theorem Kuratowski's theorem
L20	Graph Colouring and the Four-Colour Theorem —
L21	Chromatic Polynomials —
L22	Random Graphs and Thresholds —
L23	Spectral Graph Theory: A First Look —
L24	Synthesis: Order Forced by Size Ramsey's theorem, Turán's theorem

Complete disorder is impossible in large enough structures.

A matching exists iff every set of vertices has enough neighbours.

Maximum flow equals minimum cut capacity.

A graph is planar unless it contains K5 or K3,3.

The maximum edges in a graph with no large clique.