Combinatorics

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

   3 pages

   Every count in this category is assembled from the sum rule and the product rule on finite sets, giving factorials and binomial coefficients, then inclusion-exclusion for overcounts and the pigeonhole principle for forced coincidences. Additive characters of a finite abelian group, valued in ${\mathbb{C}}^{\times }$, satisfy normalized orthogonality — $1$ on equal characters and $0$ otherwise, with nontrivial characters summing to zero — proved from representation orthogonality, with a choice-free dictionary to one-dimensional complex representations. Designs extend counting to incidence structures: two-designs and Steiner systems are defined, and Skolem's construction produces a Steiner triple system of every order $6m+1$, $m\ge 1$, from a half-idempotent quasigroup, its block families checked for exact pair coverage.

   • level 0Finite Counting, Factorials and Binomial Coefficients26 results

     This page builds finite counting from the ground up: what | A| means, the two rules that every count is assembled from, and the factorials and binomial coefficients they produce.

     8 definitions, 2 lemmas, 13 theorems, 2 corollaries, 1 remarkExamples & counterexamples
   • level 1Finite Abelian Characters for Combinatorics3 results

     This page is the library's small shared interface for characters of finite abelian groups, written additively and valued in the multiplicative group ℂ^× of nonzero complex numbers.

     1 definition, 2 lemmasExamples & counterexamples
   • level 1Inclusion–Exclusion, the Pigeonhole Principle and Double Counting21 results

     Finite cardinality, finite sums over arbitrary finite index sets, the sum and product rules, binomial coefficients, and the canonical embedding of the naturals into the reals supply the counting and arithmetic background.

     5 definitions, 2 lemmas, 8 theorems, 2 corollaries, 3 false statements, 1 remarkExamples & counterexamples

2. Part 2 · Generating functions

   7 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.

   • level 1Formal Power Series22 results

     Commutative rings, finite commutative-monoid sums, polynomial convolution, units, domains, and the published real Laurent-series field supply the algebraic setting.

     7 definitions, 2 lemmas, 2 propositions, 9 theorems, 2 corollariesExamples & counterexamples
   • level 2Combinatorial Classes and the Symbolic Method38 results

     Formal power series, coefficient extraction, summable families, composition, differentiation, and the x-adic topology supply the exact background for this development.

     9 definitions, 1 lemma, 10 theorems, 7 corollaries, 6 examples, 3 counterexamples, 2 false statementsExamples & counterexamples
   • level 2Linear Recurrences and Rational Generating Functions32 results

     Formal power series over a commutative ring, coefficient extraction with its linearity and extensionality, the unit criterion for a formal power series, and the formal derivative with its algebra are published.

     8 definitions, 5 lemmas, 5 propositions, 7 theorems, 6 corollaries, 1 remarkExamples & counterexamples
   • level 3Counting up to Symmetry: Burnside and Pólya20 results

     Burnside's orbit count is already published elsewhere in the library, so this page starts where that theorem becomes a reusable machine: cycle indices, colouring actions, and Pólya's enumeration formulas.

     3 definitions, 2 lemmas, 7 theorems, 3 corollaries, 3 false statements, 2 remarksExamples & counterexamples
   • level 3Lattice Paths and Catalan Numbers74 results

     Formal power series and coefficient extraction supply the algebraic language of the page, and the page uses the constant-one square root in ℚ⟦ x⟧ exactly where the Catalan generating function needs it.

     12 definitions, 15 lemmas, 18 theorems, 10 corollaries, 11 examples, 2 counterexamples, 3 false statements, 3 remarksExamples & counterexamples
   • level 3Set Partitions, Stirling Numbers and Exponential Generating Functions21 results

     This page fixes the Stirling-number notation once, proves the finite recurrences and change-of-basis formulas that connect powers, falling factorials, and cycle counts, and then turns to the labelled symbolic method.

     6 definitions, 1 lemma, 9 theorems, 4 corollaries, 1 remarkExamples & counterexamples
   • level 4Integer Partitions and the Twelvefold Way21 results

     This page fixes one partition convention and then uses it in two directions.

     3 definitions, 1 lemma, 9 theorems, 4 corollaries, 2 false statements, 2 remarksExamples & counterexamples

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.

   • level 2Chains, Antichains, Sperner and Dilworth32 results

     Finite partial orders supply comparability, chains, and the order laws used throughout, while finite cardinality makes height, width, and level sizes exact natural numbers.

     9 definitions, 10 lemmas, 8 theorems, 3 corollaries, 2 false statementsExamples & counterexamples
   • level 3Incidence Algebras and Möbius Inversion24 results

     Partial orders supply intervals, chains and Boolean lattices, while commutative rings supply the coefficients for addition and multiplication.

     6 definitions, 4 lemmas, 7 theorems, 4 corollaries, 3 false statementsExamples & counterexamples

4. Part 4 · Graphs

   9 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 $K_n$, $C_n$, $K_{m,n}$, and the Petersen graph lead to basic expander estimates.

   • level 1Skolem construction and design prerequisites3 results

     The three explicit block families give a Steiner triple system of every order 6m+1 for m≥1.

     2 definitions, 1 theoremExamples & counterexamples
   • level 2Graphs, Walks and Connectivity37 results

     Finite cardinality supplies graph order, size, degree counts and the enumeration of two-element subsets, while Double counting: ∑ x ∈ X| R x| = | R| = ∑ y ∈ Y| Rʸ| for a…

     15 definitions, 7 lemmas, 5 theorems, 5 corollaries, 4 false statements, 1 remarkExamples & counterexamples
   • level 3Eulerian and Hamiltonian Graphs22 results

     The page first fixes degree and connectivity conventions for finite multigraphs and digraphs, including how loops contribute.

     6 definitions, 6 lemmas, 7 theorems, 3 corollariesExamples & counterexamples
   • level 3Graph Colouring6 results

     Finite simple graphs, finite cardinality, vertex neighbourhoods and maximum degree supply the combinatorial setting.

     3 definitions, 2 lemmas, 1 theoremExamples & counterexamples
   • level 3Induced Subgraphs and Hereditary Graph Classes23 results

     Published finite-simple-graph, induced-subgraph, graph-isomorphism, complementation, connectivity, and finite-counting definitions provide the setting.

     9 definitions, 9 lemmas, 3 theorems, 2 corollariesExamples & counterexamples
   • level 3Linear Algebra Methods in Combinatorics64 results

     This page uses coordinate spaces over fields, the standard bilinear form, orthogonal complements, row reduction, rank-nullity and determinants to turn finite set systems into linear-algebra problems.

     10 definitions, 17 lemmas, 13 theorems, 3 corollaries, 10 examples, 3 counterexamples, 5 false statements, 3 remarksExamples & counterexamples
   • level 3Trees, Forests and Spanning Trees27 results

     Published finite-simple-graph conventions, path and cycle definitions, connected components, vertex degrees, graph deletion, and finite-cardinality results supply the structural setting.

     6 definitions, 10 lemmas, 8 theorems, 3 corollariesExamples & counterexamples
   • level 4Algebraic and Spectral Graph Theory24 results

     This page builds the standard algebraic dictionaries that turn finite graphs into matrices: adjacency matrices count walks, Laplacians detect components, and Kirchhoff's…

     6 definitions, 1 proposition, 13 theorems, 4 corollariesExamples & counterexamples
   • level 4Block Designs and Finite Projective Planes23 results

     Double counting, modular arithmetic on ℤ/n, finite fields, and the linear-algebra view of incidence matrices are the prerequisites behind this page.

     8 definitions, 2 lemmas, 9 theorems, 4 corollariesExamples & counterexamples

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.

   • level 3Ramsey 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
   • level 4Extremal 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.

   • level 4Matchings, Covers, Menger and Network Flows26 results

     Finite graphs provide the common language for matchings, covers, paths, and cuts.

     6 definitions, 9 lemmas, 1 proposition, 6 theorems, 3 corollaries, 1 remarkExamples & counterexamples
   • level 5Plane Graphs, Euler's Formula and the Five Colour Theorem36 results

     Euclidean polygonal topology provides the separation setting for embedded edges.

     5 definitions, 14 lemmas, 5 propositions, 6 theorems, 6 corollariesExamples & counterexamples

7. Part 7 · Probability and the probabilistic method

   27 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 $C_5$, and the quantitative induced-density page converts few labelled induced copies, good-copy extension and restricted blockades into logarithmic and log-log homogeneous-set bounds. In co-Bird-free combs, overlapping induced $E$ copies yield anticonnected classes and mixed quotients end in a pure blockade with an $E$-free pattern, feeding the special-vertex criterion for property $(\ast )$. The part closes both deductions: $E$ and Bird reduce by a pendant leaf to $P_5$ and the bull, and generic generalized niceness upgrades the certified family properties to the Erdős--Hajnal property, with no numerical exponent claimed.

   • level 1Finite Probability Spaces and Random Variables32 results

     Finite sums and their reindexing laws, finite cardinality and Cartesian products, functions, and ordered-field arithmetic provide the background.

     11 definitions, 6 lemmas, 13 theorems, 2 corollariesExamples & counterexamples
   • level 5Finite Probability and the Probabilistic Method27 results

     Finite probability spaces supply expectation, indicators, independence, variance, Markov's inequality, and the second-moment bound.

     6 definitions, 7 lemmas, 1 proposition, 12 theorems, 1 corollaryExamples & counterexamples
   • level 6Regular Pairs and Induced Counting25 results

     A finite simple graph and its complement, the edges between two vertex sets and the pure and mixed pairs among them, an induced embedding, an induced copy of a fixed graph…

     5 definitions, 8 lemmas, 9 theorems, 2 corollaries, 1 remarkExamples & counterexamples
   • level 6The Erdős–Hajnal Property and Homogeneous Sets14 results

     The published clique and stable-set numbers of a finite graph, the notions of a hereditary class and of an H-free class, the complement of a graph and of a class, and the…

     2 definitions, 1 lemma, 3 propositions, 5 theorems, 2 corollaries, 1 remarkExamples & counterexamples
   • level 7Modules, Substitution and Prime Graphs36 results

     Modules record when a vertex set is indistinguishable from outside the set.

     4 definitions, 22 lemmas, 4 theorems, 4 corollaries, 2 remarksExamples & counterexamples
   • level 7Sparse Restricted Subgraphs and the Rödl–Nikiforov Theorems26 results

     The input from the regular-pairs page is the whole quantitative engine here: edge density, ε-regular pairs, typical-degree estimates, the induced counting lemma, and the theorem producing large self-regular subsets.

     2 definitions, 12 lemmas, 2 theorems, 7 corollaries, 3 remarksExamples & counterexamples
   • level 8Blockades, Combs and Pattern Graphs11 results

     This page is intentionally narrow. It fixes the blockade vocabulary used in the iterative Erdős–Hajnal literature, isolates the pattern-graph viewpoint for pure blockades…

     5 definitions, 3 lemmas, 2 theorems, 1 remarkExamples & counterexamples
   • level 8Bull-Free Graphs and the Erdős-Hajnal Property22 results

     This page develops good functions, α-narrowness, modular decomposition, and the basic bull-free structural lemmas.

     8 definitions, 4 lemmas, 2 propositions, 6 theorems, 2 corollariesExamples & counterexamples
   • level 8Polynomial Rödl, Virality and Erdős–Hajnal Equivalence15 results

     The prerequisite pages provide homogeneous sets and the Erdős–Hajnal property on hereditary classes, together with induced-copy counts, family-free graphs, and restricted sets in the maximum-degree normalization.

     3 definitions, 3 lemmas, 2 theorems, 3 corollaries, 2 examples, 2 counterexamplesExamples & counterexamples
   • level 9Pure Pairs, Forests and Path–Antipath Classes21 results

     This page collects pure-pair results for path–antipath and forest classes, together with the leaf–co-leaf extension construction.

     4 definitions, 5 lemmas, 8 theorems, 4 corollariesExamples & counterexamples
   • level 9Quantitative Induced Density and the Log-Log Step18 results

     This page proves quantitative sparse-or-dense induced-subgraph bounds from few labelled induced copies.

     5 definitions, 10 lemmas, 2 theorems, 1 corollaryExamples & counterexamples
   • level 9Quotient Blockades and Mixing Relations7 results

     This page isolates the quotient construction used at the start of Section 6 of the six-vertex extension paper.

     2 definitions, 5 lemmasExamples & counterexamples
   • level 10Classical and Log-Log Erdős–Hajnal Bounds3 results

     Homogeneous sets, sparse induced subgraphs, greedy colouring, the product bound |V|≤χα, complementation, and base-2 logarithms are the ingredients behind the quantitative Erdős–Hajnal estimates.

     2 theorems, 1 corollaryExamples & counterexamples
   • level 10Cographs, Perfect Patterns and Pure Pairs21 results

     This page packages the cograph recursion with the perfect-graph and κ(G)=α(G)ω(G) formulations that the later Erdos-Hajnal pages use.

     6 definitions, 3 lemmas, 1 proposition, 9 theorems, 1 corollary, 1 remarkExamples & counterexamples
   • level 11The Five-Cycle and the Erdős-Hajnal Property9 results

     This page follows the direct Section 4 route for C 5 rather than the later star-expansion route.

     1 definition, 3 lemmas, 3 theorems, 2 corollariesExamples & counterexamples
   • level 12Iterative Sparsification and the Five-Vertex Path22 results

     This draft page follows the source split that the design called out: the first half proves that P 5 is nice by iteratively building pure or sparse blockades, and the second…

     1 definition, 15 lemmas, 5 theorems, 1 corollaryExamples & counterexamples
   • level 12Star Expansions and the Erdős-Hajnal Property16 results

     This draft page follows the star-expansion route from Sections 6 to 8 of the five-hole paper.

     1 definition, 4 lemmas, 7 theorems, 4 corollariesExamples & counterexamples
   • level 13Iterative Restriction and Comb-Extraction Lemmas5 results

     This page isolates the reusable Section 2 lemmas that sit between the earlier P 5 blockade machinery and the later six-vertex structure pages.

     1 definition, 4 lemmasExamples & counterexamples
   • level 13Small-Graph Erdős-Hajnal Consequences13 results

     This page closes the finite small-graph inventory that the earlier substitution, bull, C 5, and P 5 pages make possible.

     6 definitions, 1 lemma, 2 theorems, 4 corollariesExamples & counterexamples
   • level 14Leaf Reducibility and Wonderful Families7 results

     This page picks up the Huang-Ju-Zhou Section 2 route exactly where the published leaf-reducible material stops.

     1 definition, 6 lemmasExamples & counterexamples
   • level 15Comb Structure in co-Bird-Free Graphs13 results

     Two small induced configurations force a vertex selected by a complete nonadjacent pair to be pure on every induced E.

     2 definitions, 10 lemmas, 1 theoremExamples & counterexamples
   • level 15Generalized Niceness and Reduction Outcomes10 results

     This draft page follows the Section 3 reduction route recorded in the batch-15 scaffold.

     1 definition, 8 lemmas, 1 corollaryExamples & counterexamples
   • level 16From Generalized Niceness to Erdős-Hajnal6 results

     This page closes the generalized-niceness route. The preceding page produced a constant-scale restricted theorem; the present page adds the Rödl initialization that removes…

     2 lemmas, 1 theorem, 3 examplesExamples & counterexamples
   • level 16Property (*) and Comb Outcomes12 results

     This page packages the second reduction stage in Huang-Ju-Zhou.

     1 definition, 6 lemmas, 1 theorem, 4 examplesExamples & counterexamples
   • level 17The Structural Criterion for Property (*)10 results

     The structural hypothesis partitions every comb block into an F 1-free part and a pure-blockade part whose pattern is F 2-free.

     2 definitions, 7 lemmas, 1 theoremExamples & counterexamples
   • level 18Comb Structure in co-E-Free Graphs14 results

     This page develops the overlap-quotient proof of the special-vertex co-E comb partition and the resulting local route to property () for {E}.

     2 definitions, 9 lemmas, 2 theorems, 1 corollaryExamples & counterexamples
   • level 19The Erdős–Hajnal Theorems for the E-Graph and Bird6 results

     This page closes the two headline deductions of the source: the E-graph and Bird each have the Erdős–Hajnal property.

     1 lemma, 2 theorems, 3 corollariesExamples & counterexamples