Discrete Mathematics II

Syllabus

• Review: inclusion–exclusion, classical recurrences and combinatorial proof techniques.
• Minimax theorems for interval systems; bipartite matchings (Kőnig–Hall) and related results (Gallai-type relations).
• Tutte’s theorem for matchings in general graphs (statement and applications).
• Higher connectivity concepts (with algorithmic aspects).
• Network flows and max-flow/min-cut (Ford–Fulkerson theorem); extensions and applications.
• Depth-first search and applications.
• Linear recurrences: solving constant-coefficient linear recurrences.
• Lattice paths: reflection principle; Catalan numbers and classical applications.
• Ramsey theory circle: bounds and constructions (including modular/generalized frameworks); Euclidean Ramsey results (statements).
• Set systems in extremal combinatorics: Sperner theorem, LYM inequality, Erdős–Ko–Rado, De Bruijn–Erdős, Fisher inequality, Oddtown (statements).
• Polynomial method: two-distance sets; set system bounds; ℓ-intersecting families (selected results).
• Combinatorial designs and structures: finite projective/affine planes, Latin squares.