Alphabeta Math

Combinatorics

100 pages in 7 parts

Combinatorics here is finite mathematics done to the standard of the infinite kind. Counting is assembled from the sum and product rules applied to finite sets, giving factorials and binomial coefficients, then inclusion-exclusion, which corrects an overcount, and the pigeonhole principle, which produces an object without exhibiting it. Formal power series make a sequence into an algebraic object with no question of convergence, and a linear recurrence becomes a rational generating function whose partial fractions return a closed form. Finite partial orders split into chains and antichains, with Sperner's theorem and Dilworth's, and the incidence algebra turns an order into a ring whose zeta function inverts to the Mobius function. Graphs follow: degrees, walks, connectivity, trees and spanning trees, Eulerian and Hamiltonian circuits, hereditary classes, and proper colourings. Ramsey's theorem says disorder is impossible at scale, Turan and Erdos-Stone give the extremal counterpart, and matchings, covers, Konig, Hall, Menger and max-flow min-cut are the min-max theorems. Planarity and Euler's formula bound the edges and yield the five colour theorem. Finite probability spaces close the collection, where expectation is a finite sum and the probabilistic method turns a positive probability into an existence proof.

The probability track begins here: it proves that a measure of total mass one agrees with the finite probability spaces and random variables established here, rather than replacing them. The Euclidean topology page of the topology track draws on the binomial coefficients, and the algebraic blocks scaffolded to continue it rest on the inner product geometry of Linear Algebra.

Pathway

The parts run in order. Everything a page needs from this group has been read by the time you reach it, and the level on each row is how many dependency steps into the group that page sits.

  1. Part 1 · Counting

    2 pages

    Every count in this category is assembled from two rules, the sum rule and the product rule, applied to finite sets whose cardinality is a natural number rather than a symbol. Factorials and binomial coefficients follow, and then the two principles that do the work when a direct count is unavailable: inclusion-exclusion, which corrects an overcount, and the pigeonhole principle, which produces an object without exhibiting it.

  2. Part 2 · Generating functions

    8 pages · after Part 1

    A formal power series is a sequence written so that algebra acts on coefficients, with no question of convergence anywhere. Coefficient extraction, inversion and formal differentiation solve recurrences, permutation statistics contribute q-factorials and Eulerian polynomials, symbolic combinatorics turns labelled constructions into EGF identities, and lattice paths convert the same series into Catalan-type counts. The same formal language governs set and integer partitions: Stirling and Bell numbers encode labelled decompositions, Ferrers conjugation identifies parts with largest parts, Euler's distinct-equals-odd identity and the Durfee-square decomposition turn product formulas into structure, Franklin's involution yields the pentagonal recurrence for p(n), and Burnside-Pólya cycle indices convert necklace, bracelet and weighted colouring orbits into explicit substitutions.

  3. Part 3 · Order, chains and Mobius inversion

    2 pages · after Part 1

    A finite partial order splits into chains and antichains, and each is bounded by the other: Sperner's theorem for the Boolean lattice, Dilworth's for any finite order. The incidence algebra turns the same order into a ring of functions on its intervals, in which the zeta function is invertible, and its inverse is the Mobius function that generalises inclusion-exclusion.

  4. Part 4 · Graphs

    8 pages · after Parts 1 and 2

    A graph begins with connectivity, trees, Eulerian and Hamiltonian circuits, hereditary classes, and colouring. Linear-algebra methods then encode incidences and set systems in matrices, proving results such as Fisher and Graham-Pollak, while block designs and finite projective planes show the same counting identities in structured examples. The new spectral page adds the adjacency and Laplacian dictionaries: powers count walks, the Laplacian detects components and algebraic connectivity, Kirchhoff's matrix-tree theorem turns spanning-tree counts into determinants and eigenvalue products, and canonical spectra for Kn, Cn, Km,n, and the Petersen graph lead to basic expander estimates.

  5. Part 5 · Ramsey and extremal graph theory

    2 pages · after Part 4

    Ramsey's theorem says a large enough complete graph, however its edges are coloured, contains a monochromatic clique, so total disorder is impossible. Extremal graph theory asks the quantitative form of the same question: how many edges force a given subgraph, with Turan's theorem and the Erdos-Stone bound answering it in terms of the chromatic number.

    • Ramsey Theory21 results

      Graph colouring supplies the two-colour language, while finite pigeonhole and counting principles support the recursive and probabilistic bounds.

      6 definitions, 3 lemmas, 9 theorems, 3 corollariesExamples & counterexamples →
    • Extremal Graph Theory20 results

      Finite simple graphs, ordinary subgraphs, degree and neighbourhood notation, finite counting, chromatic number, and Ramsey arrow notation provide the setting.

      4 definitions, 4 lemmas, 1 proposition, 8 theorems, 3 corollariesExamples & counterexamples →

  6. Part 6 · Flows, matchings and planarity

    2 pages · after Part 4

    Matchings, vertex covers and cuts are the same problem seen from two sides, and the min-max theorems say so: Konig and Hall for bipartite matching, Menger for disjoint paths, max-flow min-cut for networks. Planarity then constrains a graph by geometry rather than by counting, and Euler's formula bounds the edges, which is what forces a vertex of small degree and gives the five colour theorem.

  7. Part 7 · Probability and the probabilistic method

    26 pages · after Parts 1, 4 and 5

    Finite probability and expectation turn density into witnesses for homogeneous sets, induced-copy estimates, sparse pairs, and Erdős--Hajnal alternatives. Modules, blockades, pure pairs, combs, restriction, and sparsification develop clique-or-stable-set structure for the bull and C5. The quantitative induced-density page starts from few labelled induced copies, uses good-copy extension and restricted blockades, and turns finite density recursion into logarithmic and log-log homogeneous-set bounds, with explicit empty-block and singleton conventions. In the co-bird-free comb setting, overlapping induced E copies yield anticonnected classes, and iterated mixed quotients end in a pure blockade with an E-free pattern. This supports the relevant Erdős--Hajnal input and the special-vertex criterion for property (∗) for {E}.