Part VIII: Combinatorics and Discrete Mathematics

Discrete mathematics studies finite and countable structures. It is the mathematics of computing, of counting, and of the combinatorial backbone underlying continuous analysis.

8.1 Graph Theory

Graph: G = (V, E) with vertex set V and edge set E ⊆ V×V (directed) or E ⊆ {X ⊆ V : |X|=2} (undirected).

Key notions: Degree (number of edges at a vertex), path (sequence of distinct adjacent vertices), cycle (path returning to start), connected (path between any two vertices), tree (connected acyclic graph).

Euler's theorem: A connected graph has an Eulerian circuit (using every edge exactly once) if and only if every vertex has even degree.

Hamiltonian cycles: A cycle visiting every vertex exactly once. No clean characterization is known; determining whether a Hamiltonian cycle exists is NP-complete.

Planarity: A graph is planar if it can be drawn in the plane without edge crossings. Kuratowski's theorem: G is planar iff it contains no subdivision of K₅ or K₃,₃.

Coloring: The chromatic number χ(G) is the minimum number of colors needed to color vertices so no two adjacent vertices share a color. The Four Color Theorem (proved by Appel-Haken 1976, with computer assistance): every planar graph is 4-colorable.

Ramsey theory: For any graph property P, there exists n such that any graph on n vertices or its complement has property P. R(3,3) = 6: among 6 people, there must be 3 mutual friends or 3 mutual strangers.

8.2 Order Theory

Partial order: A reflexive, antisymmetric, transitive relation ≤ on a set P.

Total (linear) order: Every pair is comparable.

Well-order: A total order with no infinite descending chains. Every non-empty set has a least element. (The ordinals are well-ordered.)

Lattice (order-theoretic): A poset where every pair has a meet (greatest lower bound) and join (least upper bound).

Zorn's Lemma: Equivalent to the Axiom of Choice: if every chain in a partially ordered set has an upper bound, the set has a maximal element. This is used to prove existence of bases, algebraic closures, maximal ideals, and many other mathematical objects.

8.3 Combinatorics

Counting principles:

• Multiplication rule: if A has m choices and B has n choices independently, there are mn choices for (A,B)
• Addition rule: if A and B are disjoint, |A ∪ B| = |A| + |B|
• Inclusion-exclusion: |A₁ ∪ … ∪ Aₙ| = ∑|Aᵢ| − ∑|Aᵢ∩Aⱼ| + … ± |A₁∩…∩Aₙ|

Binomial coefficients: C(n,k) = n!/(k!(n−k)!) counts k-element subsets of an n-element set. Generating function: ∑_k C(n,k)xᵏ = (1+x)ⁿ.

Generating functions: Encoding a sequence (aₙ) as a power series ∑ aₙxⁿ transforms combinatorial identities into algebraic ones.

Ramsey numbers, Turán's theorem, Szemerédi regularity lemma: The deep theorems of extremal graph theory and additive combinatorics. Szemerédi's theorem: any subset of ℤ with positive upper density contains arithmetic progressions of arbitrary length.

8.4 Number Theory

Primes: An integer p > 1 is prime if its only divisors are 1 and p. By the Fundamental Theorem of Arithmetic, every integer > 1 factors uniquely into primes.

Euclid's theorem: There are infinitely many primes.

Prime distribution: The prime number theorem (Hadamard, de la Vallée Poussin, 1896): π(x) ∼ x/ln(x) where π(x) counts primes up to x. The error term is governed by the zeros of the Riemann zeta function — connecting number theory to complex analysis.

Fermat's Last Theorem: For n ≥ 3, there are no positive integer solutions to xⁿ + yⁿ = zⁿ. Proved by Andrew Wiles (1995) using elliptic curves and modular forms — a 350-year problem requiring a vast synthesis of modern mathematics.

Modular arithmetic: The integers mod n, ℤ/nℤ, form a ring. Chinese Remainder Theorem: if m, n are coprime, ℤ/mnℤ ≅ ℤ/mℤ × ℤ/nℤ.

Quadratic reciprocity: For distinct odd primes p, q: (p/q)(q/p) = (−1)^((p−1)(q−1)/4) where (p/q) is the Legendre symbol. One of the most beautiful results in mathematics; Gauss gave 6 proofs.

Elliptic curves: Equations y² = x³ + ax + b define curves with a group law. Their Mordell-Weil group is finitely generated. Elliptic curves over finite fields underlie modern cryptography (ECC).

---