discrete · mathematics topics | mathuser

discrete mathematics — complete syllabus

discrete mathematics · topics

Propositional logic · induction · stable matching · graph theory · planar graphs · hypercubes · modular arithmetic · polynomials · error correcting codes · counting · infinity · computability · probability — 14 structured notes.

Part I · Logic, Graphs & Number Theory — Notes 1–7

01 · reasoning & proof

Propositional Logic

truth tables, connectives, implication, quantifiers, proof strategies — the language of mathematical reasoning.

↗ mathuser.com/propositional-logic/ ∧∨

02 · proof technique

Induction

simple & strong induction, sum formulas, inequalities, binary representation, strengthening the hypothesis.

↗ mathuser.com/induction/ ∑

03 · algorithms & design

Stable Matching

Gale–Shapley algorithm, perfect matching, stability, optimality, resident‑hospital / college admissions.

↗ mathuser.com/stable-matching/ GS

04 · fundamentals

Graph Theory

vertices, edges, degrees, handshaking lemma, paths, cycles, connectivity, trees — the language of networks.

↗ mathuser.com/graph-theory/ G

05 · drawing & coloring

Planar Graph & Coloring

Euler's formula V−E+F=2, K₅ and K₃,₃ are non‑planar, 5‑color theorem, four‑color theorem.

↗ mathuser.com/planar-graph-and-coloring/ ⏢

06 · special families

Hypercubes & Complete

Kₙ : n(n−1)/2 edges, densest. Qₙ : bit‑string cubes, recursive construction, large‑cut theorem.

↗ mathuser.com/hypercubes-and-complete-graphs/ Qₙ

07 · number theory

Modular Arithmetic & GCD

congruences, inverses, gcd condition, Euclid's algorithm, fast halving proof, last‑digit tricks.

↗ mathuser.com/modular-arithmetic-and-gcd/ mod

Part II · Polynomials, Counting & Probability — Notes 8–14

08 · algebra over finite fields

Polynomials

roots, unique interpolation, Lagrange construction, polynomial division, finite fields GF(p), secret sharing scheme.

↗ mathuser.com/polynomials-in-discrete-maths-chapter-8/ p(x)

09 · reliable communication

Error Correcting Codes

erasure vs. general errors, Reed-Solomon encoding, Berlekamp-Welch algorithm, Hamming distance, minimum distance theorem.

↗ mathuser.com/error-correcting-code/ ECC

10 · combinatorics

Counting

product rule, binomial coefficients, stars and bars, Binomial Theorem, inclusion-exclusion, derangements.

↗ mathuser.com/counting-in-discrete-maths/ (ⁿₖ)

11 · set theory

Infinity & Countability

bijections, countable sets, ℤ and ℚ are countable, Cantor's diagonalization, power sets, orders of infinity.

↗ mathuser.com/infinity-and-beyond-discrete-maths/ ℵ₀

12 · theory of computation

Computability

Liar's paradox, quines, Halting Problem proof, reductions, Easy Halting, Gödel's Incompleteness Theorem.

↗ mathuser.com/self-reference-and-computability/ ∄

13 · probability theory

Discrete Probability

sample spaces, uniform probability, coin tosses, dice, poker hands, balls and bins, Birthday Paradox, Monty Hall.

↗ mathuser.com/introduction-to-discrete-probability/ P[·]

14 · inference & independence

Conditional Probability

P[A|B], Bayesian inference, Bayes' Rule, Total Probability Rule, mutual independence, Product Rule, Union Bound.

↗ mathuser.com/conditional-probability-independence-and-combinations/ P[A|B]