4.4. Discrete Mathematics and Combinatorics (DMC)

4.4. Discrete Mathematics and Combinatorics (DMC)

This area covers the mathematics of finite and countable structures, including combinatorial enumeration, graph theory, discrete optimization, and the logical foundations of mathematics. It underpins theoretical computer science, operations research, and modern data science.

Table 4.4: List of KUs in the Discrete Mathematics and Combinatorics area.

4.4.1. DMC/Enumerative Combinatorics  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Systematic counting of discrete structures using bijections, recursions, generating functions, and the principle of inclusion-exclusion.
Topics:
Core

  • Basic counting principles: permutations, combinations, and the binomial theorem
  • Principle of inclusion-exclusion and applications to derangements and Euler's totient function
  • Ordinary and exponential generating functions; solving recurrences
  • Integer partitions, Young tableaux, and the hook-length formula
  • Bijective proofs and Möbius inversion on posets

Learning Outcomes:
Core:

  1. Apply basic counting principles and inclusion-exclusion to enumeration problems [Familiarity]
  2. Construct ordinary and exponential generating functions to enumerate combinatorial structures [Usage]
  3. Derive closed-form formulas for combinatorial sequences using bijections and Möbius inversion [Assessment]

4.4.2. DMC/Graph Theory  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Structure and properties of graphs: connectivity, colorings, matchings, planarity, and spectral graph theory.
Topics:
Core

  • Graphs: definitions, isomorphism, degree sequences, trees, and spanning trees
  • Connectivity, Menger's theorem, and network flows (max-flow min-cut)
  • Matchings (Hall's theorem), graph colorings, and the chromatic polynomial
  • Planar graphs, Euler's formula, Kuratowski's theorem, and the four-color theorem
  • Adjacency and Laplacian matrices, eigenvalues, and expander graphs

Learning Outcomes:
Core:

  1. Identify structural properties of graphs (connectivity, planarity, bipartiteness) and apply Euler's formula [Familiarity]
  2. Apply Hall's marriage theorem and network flow algorithms to matching and routing problems [Usage]
  3. Analyze a graph's spectrum to bound its chromatic number and connectivity properties [Assessment]

4.4.3. DMC/Extremal and Probabilistic Combinatorics ↑ Back to top

Extremal problems on graphs and set systems, the probabilistic method, and random graphs.
Topics:
Non Core

  • Turán-type problems: Turán's theorem and the Kruskal-Katona theorem
  • The probabilistic method: first and second moment methods, Lovász Local Lemma
  • Erdős-Rényi random graphs: threshold phenomena and component structure
  • Ramsey theory: Ramsey numbers, van der Waerden's theorem, and Hales-Jewett
  • Algebraic methods in combinatorics: polynomial method and Chevalley-Warning theorem

Learning Outcomes:
NonCore:

  1. State Turán's theorem and apply it to bound the number of edges in a \(K_r\)-free graph [Familiarity]
  2. Apply the probabilistic method and the Lovász Local Lemma to prove existence of combinatorial structures [Usage]
  3. Analyze threshold phenomena in Erdős-Rényi random graphs using first and second moment methods [Assessment]

4.4.4. DMC/Discrete Optimization  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Integer programming, network flows, matroids, matching algorithms, and the theory of NP-completeness.
Topics:
Core

  • Integer linear programming: branch and bound, cutting planes, and totally unimodular matrices
  • Network flow algorithms: shortest paths, max-flow, min-cost flow
  • Matroid theory: independent sets, greedy algorithm, and matroid intersection
  • Complexity theory: P vs. NP, NP-completeness, and reductions
  • Approximation algorithms and the polynomial-time approximation scheme (PTAS)

Learning Outcomes:
Core:

  1. Explain the relationship between linear programming relaxations and integer programming bounds [Familiarity]
  2. Apply network flow and matroid algorithms to solve combinatorial optimization problems [Usage]
  3. Prove NP-completeness of a combinatorial problem via polynomial reduction [Assessment]

4.4.5. DMC/Design Theory and Combinatorial Codes ↑ Back to top

Combinatorial designs, Latin squares, finite geometries, and their connections to error-correcting codes.
Topics:
Non Core

  • Block designs: balanced incomplete block designs (BIBDs), Fisher's inequality, and symmetric designs
  • Latin squares, orthogonality, and applications to experimental design
  • Finite projective and affine planes; connection to combinatorial designs
  • Hadamard matrices and their applications in coding and signal processing
  • Connections between combinatorial designs and linear codes (Hamming, Golay)

Learning Outcomes:
NonCore:

  1. Define a BIBD and verify that a given configuration satisfies its parameters [Familiarity]
  2. Construct a balanced design or orthogonal Latin squares for a given parameter set [Usage]
  3. Relate the structure of a combinatorial design to the parity-check matrix of a corresponding linear code [Assessment]

4.4.6. DMC/Mathematical Logic and Set Theory  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Propositional and first-order logic, proof systems, Gödel's completeness and incompleteness theorems, and axiomatic set theory.
Topics:
Core

  • Propositional logic: syntax, semantics, satisfiability, and resolution
  • First-order logic: models, soundness, and the Gödel completeness theorem
  • Gödel's incompleteness theorems and their implications for formal systems
  • Axiomatic set theory (ZFC): ordinals, cardinals, and the axiom of choice
  • Computability: Turing machines, decidability, and the halting problem

Learning Outcomes:
Core:

  1. State Gödel's completeness and first incompleteness theorems and explain their significance [Familiarity]
  2. Construct formal proofs in first-order logic and determine the satisfiability of formulas [Usage]
  3. Analyze the undecidability of problems by reduction to the halting problem [Assessment]

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone