- ES Español (Latinoamérica)

- EN English

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.
| Knowledge Area (KA) | Core Tier1 | Core Tier2 |
4.4.1 Enumerative Combinatorics | 1 | 1 |
4.4.2 Graph Theory | 1 | 1 |
4.4.3 Extremal and Probabilistic Combinatorics | Elective | |
4.4.4 Discrete Optimization | 1 | 1 |
4.4.5 Design Theory and Combinatorial Codes | Elective | |
4.4.6 Mathematical Logic and Set Theory | 1 | 1 |
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:
- Apply basic counting principles and inclusion-exclusion to enumeration problems [Familiarity]
- Construct ordinary and exponential generating functions to enumerate combinatorial structures [Usage]
- 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:
- Identify structural properties of graphs (connectivity, planarity, bipartiteness) and apply Euler's formula [Familiarity]
- Apply Hall's marriage theorem and network flow algorithms to matching and routing problems [Usage]
- 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:
- State Turán's theorem and apply it to bound the number of edges in a \(K_r\)-free graph [Familiarity]
- Apply the probabilistic method and the Lovász Local Lemma to prove existence of combinatorial structures [Usage]
- 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:
- Explain the relationship between linear programming relaxations and integer programming bounds [Familiarity]
- Apply network flow and matroid algorithms to solve combinatorial optimization problems [Usage]
- 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:
- Define a BIBD and verify that a given configuration satisfies its parameters [Familiarity]
- Construct a balanced design or orthogonal Latin squares for a given parameter set [Usage]
- 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:
- State Gödel's completeness and first incompleteness theorems and explain their significance [Familiarity]
- Construct formal proofs in first-order logic and determine the satisfiability of formulas [Usage]
- Analyze the undecidability of problems by reduction to the halting problem [Assessment]