The Gold Standard of Extremal Combinatorics

Chapter index

An extremal question needs four ingredients. First specify the universe: perhaps all simple undirected graphs on n labelled vertices. Then specify a restriction, such as containing no triangle. Choose an objective, such as the number of edges. Finally ask for the maximum or minimum of that objective among all allowed objects. Each ingredient can change the answer.

Here a simple graph has no loops and at most one edge for each unordered pair of distinct vertices. A triangle means three vertices with all three connecting edges present. Crossings in a drawing are irrelevant. A graph with a thousand repeated records of one connection still has only one edge between that pair under this definition.

For a fixed forbidden graph H, ex(n,H) denotes the largest number of edges in an n-vertex simple graph containing no copy of H as a subgraph. This article uses ordinary subgraphs: extra edges among the selected vertices are permitted. An induced-subgraph question, which also specifies which edges must be absent, is a different question.

The maximum exists because there are only finitely many possible graphs on the chosen vertex set. There are C(n,2)=n(n−1)/2 possible pairs, each present or absent, so the search space contains 2 raised to C(n,2) graphs. Finiteness establishes existence of an optimum; it does not make exhaustive search practical.

Compare three tasks on the same twelve-vertex universe. Counting all triangle-free graphs is enumerative. Finding one triangle-free graph with thirty edges is constructive. Determining the greatest possible edge count is extremal. These tasks share definitions but require different evidence. A successful answer to one should not quietly be reported as an answer to another.

For prerequisite repair, How Mathematics Works: Combinatorics explains combinations and double counting. You need those ideas here because the proof will count the same incidences from different viewpoints.

Contents · Next chapter

Suppose you build an allowed object with objective value L. For a maximisation problem, you have proved that the optimum is at least L. You have not proved that every other object is smaller. A universal argument giving value at most U establishes the opposite side. Together they yield L≤optimum≤U.

If L=U, the exact answer is established. If L<U, the interval is still useful: it identifies what remains unresolved. An attractive picture with many edges is not a substitute for the upper argument, and a sophisticated inequality does not establish attainability without a matching example.

Consider a triangle-free graph on twelve vertices. Divide the vertices into groups of five and seven, place every edge between the groups, and place none within either group. There are 5×7=35 edges. A triangle is impossible because any three vertices include two in the same group, and that pair is not joined.

Now use groups of six and six. The same reasoning gives thirty-six edges. The earlier construction was valid but suboptimal. This is a useful diagnostic: finding an object that cannot accept an additional edge is weaker than finding an object with the greatest possible edge count among all allowed objects.

The five-seven construction is already maximal with respect to adding a single missing edge: any added within-group edge creates a triangle with a vertex in the other group. Yet it is not maximum. Reorganising the partition improves the total. Local inability to add an edge therefore does not certify global optimality.

The extremal principle and infinite descent specialist develops the related proof habit of choosing an extreme object. Here the extra responsibility is to show that the chosen numerical limit applies throughout the entire feasible class.

Previous chapter · Contents · Next chapter

Let G have n vertices and m edges, and suppose G is triangle-free. Write d(v) for the degree of vertex v, the number of its neighbours. If uv is an edge, u and v cannot share a neighbour: such a neighbour would complete a triangle. Their neighbourhoods are therefore disjoint subsets of the n vertices, so d(u)+d(v)≤n.

Sum this inequality over all m edges. Each vertex v appears as an endpoint d(v) times, contributing d(v) on each appearance. Thus the left side becomes the sum of squared degrees. We obtain Σ d(v)²≤nm. This is the important change of viewpoint: an inequality attached to one edge has become an inequality about all vertex degrees.

The degree sum is 2m because every edge has two endpoints. Also, Σ d(v)²≥(Σ d(v))²/n=4m²/n. One way to see the inequality is to expand the nonnegative sum Σ(d(v)−2m/n)². Variation around the mean cannot make that sum negative.

Combining the two bounds gives 4m²/n≤nm. If m=0, the desired conclusion is immediate. Otherwise divide by m and multiply by n to obtain m≤n²/4. Since m is an integer, m≤floor(n²/4). This is Mantel’s theorem in its extremal form.

For n=12, the upper bound is thirty-six. Chapter 2 constructed a triangle-free graph with exactly thirty-six edges, so ex(12,K₃)=36. For n=11, the bound is floor(121/4)=30, attained by a complete bipartite graph with groups of five and six.

Notice which assumptions did the work. The graph is simple and undirected, and the forbidden object is a triangle. If there were repeated edges or directed arcs, the degree count would need reformulation. If triangles were allowed, the disjoint-neighbourhood step would fail. The algebra is only as reliable as that structural step.

Previous chapter · Contents · Next chapter

For a complete bipartite graph with part sizes a and n−a, the edge count is a(n−a). Completing the square gives n²/4−(a−n/2)². The largest integer value occurs when the two sizes differ by at most one. Balancing is therefore a calculation, not a visual preference for symmetry.

With twelve vertices, moving from a six-six partition to five-seven loses one edge; moving to four-eight loses four edges. If a=6+t, the count is 36−t². This provides a precise sensitivity calculation within this family of constructions. It does not classify every triangle-free graph with a similar number of edges.

For even n, equality in the degree-squares step requires all degrees to equal n/2. Equality in every edge inequality also requires d(u)+d(v)=n. To understand the structure, choose an edge uv. Its disjoint neighbourhoods each have n/2 vertices and together cover the graph. Each neighbourhood is independent, because an internal edge would form a triangle with u or v. Regularity then forces every cross-edge to be present.

This recovers the balanced complete bipartite equality case for even n. For odd n, equal degrees at n/2 are impossible, so that particular equality argument cannot be copied unchanged. The floor in the theorem matters. The balanced construction still attains the bound, but a proof about equality must respect integer parity.

A second experiment begins with the six-six construction and adds one edge inside one group. That edge forms six triangles, one with each vertex in the other group. This proves an exact triangle count for this specific modification. Mantel’s theorem alone only guarantees at least one triangle once the count exceeds thirty-six; it does not identify the triangles or imply that every thirty-seven-edge graph arises by this operation.

This distinction separates a universal theorem from a construction-specific observation. Both are valuable, but their scopes should remain visible.

Previous chapter · Contents · Next chapter

A clique K_r is a set of r vertices with every pair connected. Turán’s theorem generalises the triangle problem: among n-vertex graphs containing no K_(r+1), a complete r-partite graph with parts as equal as possible has the maximum number of edges. Within a part there are no edges; between different parts all edges are present.

Why does the construction avoid K_(r+1)? Any r+1 selected vertices must include two in the same part. Those two are not adjacent, so the selection cannot be a clique. Its edge count, for part sizes n₁,…,n_r summing to n, is (n²−Σ n_i²)/2. This counts all pairs and subtracts the within-part pairs.

Balancing minimises Σ n_i². If two part sizes a and b satisfy a≥b+2, moving one vertex from the larger to the smaller changes their squared sum by −2(a−b−1), a strictly negative quantity. Repeating such moves leaves sizes differing by at most one and increases the number of cross-edges.

For eleven vertices with no K₄, use three parts of sizes 4,4,3. The edge count is 4×4+4×3+4×3=40. Turán’s theorem says that forty is optimal. The convenient real-valued bound (1−1/r)n²/2 gives 121/3 when r=3; integer rounding gives forty in this example. For general parameters, use the balanced-part formula for the exact value rather than assuming a rounded approximation always suffices.

The balancing calculation proves optimality within complete multipartite graphs. The full theorem additionally says that an arbitrary graph avoiding the clique cannot do better. That global step is substantial. It is covered in MIT’s graph theory lecture on Mantel and Turán. Keep the distinction explicit when presenting a partial proof.

Previous chapter · Contents · Next chapter

Extremal combinatorics also studies collections of sets. Let the ground set be [n]={1,2,…,n}, and let F be a family of distinct subsets. An antichain is a family in which no member is contained in a different member. The objective is to maximise the number of members of F.

For n=4, all six two-element subsets form an antichain. Sets of the same size cannot strictly contain one another. The four singletons also form an antichain, but are smaller as a family. Merely choosing a uniform size guarantees feasibility; choosing the right size improves the objective.

Sperner’s theorem states that the largest antichain has C(n,floor(n/2)) members. A full middle layer, containing all subsets of that size, attains the bound. Unlike the graph examples, the quantity being maximised is the number of sets, not the number of elements in one set or the total number of memberships.

A small example prevents a common misreading. The family {{1},{2,3},{2,4}} is an antichain even though its members have different sizes. None contains another. So the theorem is not proved simply by observing that the largest single layer is the middle layer. One must also rule out a mixed-size family that might be larger.

An application-shaped model is a collection of feature bundles, with containment interpreted as one bundle including all the features of another. An antichain selects bundles without containment between distinct choices. This is a formal restriction, not a guarantee that the bundles have equal price, quality or usefulness. Those properties require a separate objective or data.

The next chapter supplies the missing universal argument. It counts how often one subset can appear along an ordering of the ground elements, thereby comparing all family sizes on a common scale.

Previous chapter · Contents · Next chapter

There are n! orderings of [n]. Each ordering produces a chain: begin with the empty set, then take the first element, the first two elements, and so on until all n elements have been included. Every two sets in this chain are comparable by containment. An antichain can therefore meet it at most once.

Fix a member A of F with k elements. It appears in the chain of an ordering precisely when the first k positions contain the elements of A. There are k! ways to order those elements and (n−k)! ways to order the others. Thus A occurs in k!(n−k)! of the n! chains counted with their generating orderings.

Count pairs consisting of an ordering and a member of F appearing in its chain. Counting by orderings gives at most n! pairs. Counting by family members gives Σ over A in F of |A|!(n−|A|)!. Division by n! yields Σ over A in F of 1/C(n,|A|)≤1, the LYM inequality.

Every binomial coefficient C(n,k) is at most M=C(n,floor(n/2)). Hence every summand is at least 1/M, and |F|/M≤1. Therefore |F|≤M. The middle-layer construction reaches M, completing both sides of the extremal problem.

For six ground elements, M=C(6,3)=20. A member of size two uses 1/15 of the LYM total, whereas a member of size three uses 1/20. Suppose an antichain has three members of size two and b members of size three. Then 3/15+b/20≤1, so b≤16. The inequality rules out b=17 immediately.

However, satisfying this numerical inequality does not prove that a proposed family exists. Its particular sets must still avoid containment. LYM is a necessary condition for the family; it is not a substitute for checking the relationships among its members. Charles University’s LYM notes provide a route into the broader set-family theory.

Previous chapter · Contents · Next chapter

Label six features A,B,C,D,E,F. Suppose a catalogue may contain distinct bundles, with no listed bundle containing another. If every three-feature bundle is permitted, there are twenty possibilities, and these form a maximum antichain by Sperner’s theorem. This is an exact solution for the stated combinatorial model.

Now require the catalogue to include the two-feature bundle AB. Any three-feature bundle containing both A and B must be removed. There are four such triples: ABC, ABD, ABE and ABF. Retaining the other sixteen triples and adding AB gives seventeen bundles. No retained triple contains AB, and no two retained triples contain one another, so feasibility is directly verified.

The construction proves a lower bound of seventeen for the modified problem. LYM alone, applied to one pair and b triples, gives 1/15+b/20≤1, hence b≤18 after integer rounding. That upper bound is weaker than the direct containment count, which gives b≤16. When the allowed sizes are exactly two and three and AB is the only pair, seventeen is therefore the exact answer.

If additional two-feature bundles are permitted, the problem changes again. Different pairs exclude overlapping collections of triples, so simply subtracting four for every new pair can double-count the forbidden triples. The right calculation uses the union of excluded triples, or an inclusion-exclusion argument, and then checks any other permitted sizes.

This case shows how a general theorem and local structure cooperate. The theorem supplies a broad ceiling; the specified bundle exposes constraints that the ceiling does not fully capture. A sharper argument may come from understanding one forced choice rather than applying a more elaborate general inequality.

For real catalogues, containment may not represent dominance. Adding a feature can increase cost, weight or complexity. Before adopting the antichain model, decide whether the intended restriction is literally set inclusion or a comparison involving several measured quantities. The mathematical answer remains conditional on that decision.

Previous chapter · Contents · Next chapter

A four-cycle consists of four distinct vertices with edges around a closed loop. Additional diagonal edges do not prevent it from being a subgraph. In a graph containing no four-cycle, two distinct vertices can have at most one common neighbour. Two common neighbours would give the required four distinct vertices and four cycle edges.

For each vertex v, count unordered pairs of its neighbours. There are C(d(v),2) such pairs. Summing over v counts each pair of vertices once for each common neighbour. The restriction therefore gives Σ C(d(v),2)≤C(n,2).

Using Σ d(v)=2m and Σ d(v)²≥4m²/n, the left side is at least 2m²/n−m. Consequently 2m²/n−m≤n(n−1)/2. Solving this quadratic inequality for nonnegative m yields m≤n(1+sqrt(4n−3))/4. Take the floor when converting the real expression to an integer upper bound.

For n=10, this bound is approximately 17.707, so a four-cycle-free graph has at most seventeen edges. We have not constructed a graph attaining seventeen, so this calculation should be reported as an upper bound, not an exact extremal answer. The distinction is especially important when the algebra produces a plausible-looking integer.

Compare the order of growth with the triangle-free problem. The four-cycle bound grows on the scale n raised to 3/2, while the balanced triangle-free construction has roughly n²/4 edges. A complete bipartite graph avoids triangles but contains many four-cycles when both parts have at least two vertices. A construction useful for one forbidden pattern can be unsuitable for another.

The mechanism here is a capacity restriction on common neighbours. In an incidence system, it can model a rule that two objects share at most one intermediary. The translation must still preserve distinct vertices and the meaning of each edge; repeated records are not additional independent incidences.

Previous chapter · Contents · Next chapter

An independent set contains no edge between any two of its vertices. If edges represent pairwise incompatibility, such a set is a mutually compatible selection under that model. The independence number α(G) is its greatest possible size. A useful lower bound is α(G)≥Σ 1/(d(v)+1), known as the Caro–Wei bound.

To see the mechanism, order all vertices uniformly at random. Select each vertex that appears before all its neighbours. Two adjacent vertices cannot both be selected, because each would have to precede the other. The selected set is therefore independent. Vertex v is selected with probability 1/(d(v)+1), since each vertex in its closed neighbourhood is equally likely to appear first.

Adding these selection probabilities gives the expected size Σ 1/(d(v)+1). At least one ordering achieves a size at least the expectation. Independence between the selection events is unnecessary: linearity of expectation applies even when the events depend on one another. MIT’s independent-set material develops this proof route.

Consider a star with one centre and five leaves. The centre has degree five and each leaf has degree one, so the bound is 1/6+5/2=8/3. Since the independent-set size is an integer, the bound guarantees at least three vertices. The five leaves actually form an independent set of size five. The bound is valid without being sharp.

Now compare two disjoint triangles. Every vertex has degree two, giving a bound of six times 1/3=2. Exactly one vertex can be taken from each triangle, so the bound is sharp. Both examples have six vertices, but their degree distributions and constraints lead to different conclusions.

A single random ordering need not achieve the expectation. On the star, placing the centre first selects only the centre. The existence proof says some ordering is good, not that every trial succeeds. Turning an existence argument into a reliable algorithm requires its own analysis.

Previous chapter · Contents · Next chapter

A small exhaustive search can verify examples and expose mistaken conjectures. On six labelled vertices, there are fifteen possible edges and 2¹⁵=32768 simple graphs. One can inspect every graph, reject those containing a triangle, and record the largest remaining edge count. The result should be nine, attained by the complete bipartite graph with parts of size three.

The triangle test must examine every triple and require all three pair edges. Testing only triangles visible in a particular drawing is incorrect. Likewise, a four-cycle test must allow extra diagonals; rejecting only induced four-cycles would answer a different problem. Representation and acceptance conditions belong in the specification before optimisation begins.

For antichains on a four-element ground set, there are sixteen possible subsets and 2¹⁶=65536 possible families. Testing all families for containment between distinct members gives maximum size six. The computation validates a finite instance of Sperner’s theorem, not the statement for every n.

A report of a computational optimum should preserve the feasible witness, objective value and reason the search was complete. If pruning discards part of the space, prove that discarded objects cannot improve the current result. If symmetries reduce duplicate cases, verify that every equivalence class still has a representative.

A heuristic search has a different evidential role. Finding a graph with L edges proves the lower bound L once the graph is checked. Failing to find a graph with L+1 edges does not prove that none exists. Search effort, random seeds and repeated unsuccessful trials cannot replace a completeness argument.

Computation is especially useful during learning when paired with a proof. First enumerate a small case; then identify the invariant or double count that explains the observed limit. Finally change one rule and see which line of the proof stops working. That sequence turns output into mathematical understanding.

Previous chapter · Contents · Next chapter

The first recurring error is reversing a bound. A feasible construction is a lower bound on a maximum; a universal ceiling is an upper bound. Repair the argument by writing L≤optimum≤U before inserting numbers. For minimisation, the roles reverse, so memorising a slogan without naming the objective is unsafe.

The second error is treating average information as a pointwise guarantee. An average degree of six does not imply every degree is six. In Mantel’s proof, the degree-squares inequality handles unevenness rather than assuming it away. If a later argument needs regularity, supply a separate reason for it.

The third error is confusing a prohibited subgraph with a prohibited induced subgraph. A complete graph on four vertices contains a four-cycle as a subgraph, but its four vertices do not induce a chordless cycle. Deleting diagonals is allowed when identifying an ordinary subgraph; it is not allowed when specifying an induced one.

The fourth error is giving a structural interpretation to an edge-count theorem that it does not establish. Thirty-seven edges on twelve vertices force a triangle, but the theorem does not locate it, assign it a cause or explain the real-world relationships represented by its edges. A guaranteed pattern can be mathematically real while its practical significance remains unestablished.

The fifth error is using a pairwise model for a genuinely collective restriction. Three tasks may overload a shared resource even when every pair fits. A conflict graph alone cannot encode that triple-only constraint. A hypergraph, whose edges may contain more than two vertices, can express it, but graph theorems do not automatically extend with the same formulas.

The Ramsey Theory root provides a complementary perspective on unavoidable patterns under colouring. Its six-person specialist is a useful comparison: a complete coloured graph and a graph with a forbidden subgraph ask related but distinct questions.

Previous chapter · Contents · Next chapter

Try the following cases before reading their answers. The purpose is to decide which structure survives a change, not merely substitute a new number into a familiar formula.

Case A: A simple undirected network has thirteen vertices and forty-three distinct edges. Must it contain a triangle? Yes. Mantel’s bound is floor(169/4)=42. A six-seven complete bipartite graph demonstrates that forty-two can avoid triangles, so forty-three is the first edge count that guarantees one for this vertex count.

Case B: The same report records forty-three directed messages, with repeated messages between the same people allowed. Does the previous conclusion follow? No. All forty-three messages could be sent from one person to another. There would be only one underlying unordered pair. The report counts events, whereas Mantel’s theorem counts distinct edges in a simple undirected graph.

Case C: A twelve-vertex graph is known to have no K₄. Must it have at most thirty-six edges? No. Three parts of size four give a complete tripartite graph with 4×4+4×4+4×4=48 edges and no K₄. The forbidden clique changed, so the triangle-free ceiling no longer applies. Turán’s theorem establishes forty-eight as optimal here.

Case D: A family of twenty-one distinct subsets of six features is claimed to have no containment between different members. Is that possible? No. Sperner’s theorem limits such an antichain to twenty. But twenty-one product descriptions with repeated feature sets do not automatically violate the theorem: a family of distinct subsets and a list with repetitions are different mathematical objects.

Case E: A six-feature antichain contains AB and only three-feature sets besides it. Can it have eighteen members? No. AB excludes four of the twenty triples, leaving at most sixteen triples plus AB, or seventeen members. The sharper answer comes from direct containment, not from LYM alone.

After each answer, identify the exact definition used. A correct numerical result accompanied by an incorrect model is not successful transfer. The learning goal is to preserve the proof’s conditions when the story changes.

Previous chapter · Contents · Next chapter

Begin with small constructions: balanced bipartite graphs, middle layers of subsets and independent sets in stars. For each, write down why it is allowed and calculate its objective. Next learn one universal upper proof and one universal lower proof. Mantel, LYM and the random-order independent-set argument expose three different mechanisms without requiring a large catalogue of named results.

Then practise improving a loose bound. The forced-AB catalogue case is suitable because every excluded triple can be listed. Move to larger ground sets only after you can explain why overlapping exclusions must be counted once. A useful notebook records the universe, restriction, construction, upper argument and remaining gap on the same page.

Does extremal combinatorics always give an exact answer?

No. Bounds may leave a gap, and some problems are studied through asymptotic growth rather than exact finite values. State what was proved: an exact optimum, a range, an order of growth or a particular construction. These are different achievements.

Is an extremal theorem an optimisation algorithm?

Not necessarily. A proof may identify the best possible value across a class without efficiently finding the best object inside a particular input. A constructive proof may suggest an algorithm, but its running time and guarantees need separate examination.

Does triangle-free mean bipartite?

No. A cycle of length five is triangle-free but is not bipartite. Balanced complete bipartite graphs attain the triangle-free edge maximum; this does not mean every graph avoiding triangles has that form. Distinguish the entire feasible class from the extremal examples.

How can this help outside a mathematics exercise?

It can establish capacity limits or unavoidable configurations in a carefully defined discrete model. Examples include selections under pairwise incompatibility, incidence patterns and families of feature sets. The usefulness depends on whether the restrictions describe the actual system. A proof certifies the model’s conclusion; it does not validate the model against reality.

Which sources support further study?

MIT’s introductory extremal combinatorics notes cover graph-size questions and classical clique bounds. Yufei Zhao’s graph theory and additive combinatorics notes extend the subject to forbidden subgraphs and constructions. Mykhaylo Tyomkyn’s set-family notes develop LYM and shadows. MIT’s probabilistic-method notes explain independent-set bounds. These are technical learning sources, not claims of a current research-record survey.

The numerical networks and feature-catalogue cases in this guide are explanatory models. Rework them with a changed vertex count, a forced subset or a different forbidden pattern. A strong final explanation states both what can be built and why the claimed limit applies, while leaving any unresolved gap visible.

Previous chapter · Contents · Gold Standard master