Part III · The Deep Theory

Ramsey Theory

Created by Felipe Casadei

Any six people at a party include three who all know each other or three who are all strangers to each other. After this chapter you will know why that is forced, how far it generalises, and why the whole subject is a proof that complete disorder is impossible.

Order you cannot avoid

Chapter 7 asked how many edges you have to pile onto a graph before a fixed shape is unavoidable. This chapter asks a stranger question. What is forced by size alone, when nobody promises you any edges at all?

The honest first answer is: nothing. Take a graph with a million vertices and no edges. It contains no triangle, and no amount of extra vertices will produce one. Take a complete graph on a million vertices instead, so every pair is joined. It contains no three vertices that are pairwise non-adjacent. So no single shape is unavoidable in large graphs. The question looks dead.

Frank Ramsey's move, in a 1930 paper about a decision problem in formal logic, was to stop asking for one shape and start asking for one of two opposite shapes. Notice that the two examples above fail in opposite ways. The edgeless graph has no triangle but is drowning in pairwise non-adjacent vertices. The complete graph has no pairwise non-adjacent trio but is drowning in triangles. Neither dodges both. Ramsey proved that nothing does.

That single idea opens into four questions, and they are the four parts of this chapter. First, why is it true, and how far does it stretch beyond graphs? Second, exactly how big is "big enough"? Those numbers are called Ramsey numbers, and they are famously hard to pin down. Third, can we demand an exact copy of a pattern rather than merely a copy with extra edges allowed? That harder demand is still satisfiable, but only by building a host graph on purpose. Fourth, if the big graph is also connected, or 2-connected, or 3-connected, what short list of shapes must show up?

One warning before the notation. This chapter counts vertices, never edges. Every theorem here has the form "every graph with at least \(n\) vertices contains …". A reader who carries over Chapter 7's habit of thinking in edge density will misread all of them.

New notation in this chapter

Thirteen of these are new; the rest come from Chapter 1 and Chapter 5 and are listed because this chapter leans on them hard. If plain set language such as \(Y \subseteq X\) ("Y is a subset of X") is still shaky, Chapter 0 is the bootstrap.

Six people at a party

Here is the puzzle that opens every course on this subject. Six people are in a room. Any two of them either know each other or do not. Claim: some three of them are mutual acquaintances, or some three are mutual strangers.

Turn it into a graph. Vertices are people. Join two people by an edge when they are acquainted. Then "three mutual acquaintances" is a triangle, and "three mutual strangers" is a set of three vertices with no edges among them. Equivalently, paint the edges of the complete graph \(K^6\) (six vertices, all fifteen pairs joined) in two colours: violet for acquainted, gold for strangers. The claim becomes: every violet/gold painting of \(K^6\) contains a violet triangle or a gold triangle.

Two things must be shown. Six is enough, and five is not. Start with the failure at five, because it is the more surprising half.

Read the picture slowly, because its shape is the shape of every lower bound in this chapter. To prove that some number is not big enough, you exhibit one colouring that dodges every target. The pentagon-and-pentagram colouring is that exhibit. There is no cleverness left to add: the violet edges form a ring through all five vertices, the gold edges form a five-pointed star through all five vertices, and neither shape contains three mutually joined vertices.

Now the other half. Six people always suffice, and the argument is short enough to hold in your head.

The engine of that argument is the pigeonhole principle: if you sort five things into two boxes, some box gets at least three. That principle, applied over and over, is most of Ramsey theory. Combining the two figures gives the first exact result of the chapter.

Ramsey's theorem: total order or total disorder

Replace 3 by an arbitrary \(r\) and the party puzzle becomes Ramsey's theorem.

Recall from Chapter 1 that \(K^r\) is the complete graph on \(r\) vertices, and \(\overline{K^r}\) is its complement, meaning \(r\) vertices with no edges at all. Diestel writes the superscript for the number of vertices, so \(K^3\) is the triangle; much of the wider literature writes \(K_3\) for the same graph. This course keeps Diestel's convention throughout. "Induced subgraph" means we take some vertices and all the edges of \(G\) among them; for complete and edgeless targets the induced version and the ordinary version say the same thing, so you can ignore the word for now. It starts to matter later in the chapter, and then it matters enormously.

The proof does not look for the clique or the independent set directly. It builds a shrinking sequence of candidate pools.

Here is why the halving is enough. Each round costs half the pool and buys one vertex with a fixed attitude toward everything chosen after it: either "joined to all of them" or "joined to none of them". If you start with \(2^{2r-3}\) vertices you can afford \(2r-3\) rounds. That gives \(2r-3\) picked vertices, each labelled with one of two attitudes. Sorting \(2r-3\) items into two boxes leaves some box with at least \(r-1\) of them, by pigeonhole again. Take those \(r-1\) vertices plus one survivor from the final pool. If their shared attitude was "joined to all later ones", every pair among them is joined, so they form \(K^r\). If it was "joined to none", no pair is joined, so they form \(\overline{K^r}\).

That argument also hands us a number: the smallest workable \(n\) is at most \(2^{2r-3}\), which is \(4^r/8\). This bound is due to Erdős and Szekeres in 1935, and the chapter's later sections will show that the truth is genuinely exponential rather than merely bounded by an exponential.^[1]

Colouring bundles, not just edges

Ramsey's original theorem is more general than the graph version, and the extra generality costs nothing once the language is right. The trick is to stop talking about edges and start talking about bundles of a fixed size.

Why is this the right language? Because \([X]^2\), the set of 2-element subsets of \(X\), is precisely the set of possible edges on vertex set \(X\). Painting the edges of a complete graph in two colours is a 2-colouring of \([X]^2\). A monochromatic set of size \(r\) is a set of \(r\) vertices all of whose pairs got one colour, which is a one-coloured \(K^r\). So the graph theorem is the case \(k=2\), \(c=2\). Taking \(k=3\) colours triples instead of pairs, and there is no graph picture for that, which is exactly the point: the theorem was never really about graphs.

Infinity makes the proof easier

Ramsey proved an infinite version too, and it is cleaner than the finite one because there is no size bookkeeping at all.

The proof idea recycles the halving picture, with "infinite" playing the role of "at least half". For \(k=1\) it is pigeonhole with infinitely many pigeons: finitely many colours cannot split an infinite set into finite pieces, so one colour class is infinite. For larger \(k\), pick a point \(x_0\) and give each \((k-1)\)-bundle of the remaining points the colour that the bundle-plus-\(x_0\) received. That is a colouring one bundle-size down, so by induction there is an infinite set on which those inherited colours agree, which means \(x_0\) has one fixed colour attitude toward that whole infinite set. Recurse inside it to produce \(x_1, x_2, x_3, \dots\), each with a fixed attitude toward everything chosen after it. Finitely many colours and infinitely many \(x_i\) means infinitely many of them share an attitude, and those form the infinite monochromatic set.

Now comes a move worth pausing on. The finite theorem in full generality follows from the infinite one, by contradiction.

Suppose it fails for some \(k, c, r\). Call a colouring of the \(k\)-bundles of \(\{0, 1, \dots, n-1\}\) bad if no \(r\)-element subset is monochromatic under it. Failure means bad colourings exist for every \(n\). Chop any bad colouring on \(n\) points down to the first \(n-1\) points and you get a bad colouring one size smaller, so the bad colourings sit in an infinite tree: level \(n\) holds the bad colourings on \(n\) points, and each is a child of the bad colouring it shrinks to. Every level is finite, because there are only finitely many colourings of finitely many bundles. König's infinity lemma from Chapter 8 says an infinite tree with finite levels has an infinite branch.^[7] Follow that branch: it is a coherent, ever-extending sequence of bad colourings, and their shared values define a single bad colouring of all the \(k\)-bundles of \(\mathbb{N}\), the natural numbers. That contradicts the infinite theorem, which promised an infinite monochromatic set and therefore certainly an \(r\)-element one.

How big is "big enough"?

Ramsey's theorem promises that \(R(r)\) is finite. It does not say what it is, and nobody else does either. The halving proof gives an upper bound of \(2^{2r-3}\). Chapter 11 supplies a matching-in-spirit lower bound of \(2^{r/2}\), proved by the probabilistic method: paint the edges of a large complete graph by coin flips, count the expected number of monochromatic \(K^r\)s, and show that if the graph is small enough that count is below 1, so some painting has none.^[1]

So \(2^{r/2} \le R(r) \le 4^r/8\). The two ends are both exponential, but the bases differ, and the gap between \(\sqrt{2}\) and \(4\) is an enormous multiplicative distance once \(r\) is large. Closing it is one of the oldest open problems in combinatorics. Exact values of \(R(r)\) are known only for very small \(r\), and the difficulty is not a shortage of computers: the number of edge colourings to check explodes far faster than the graphs grow.^[1]

One conjecture is worth stating because it says something sharp about how weak Ramsey's guarantee really is. Read the bounds backwards: a graph on \(n\) vertices is only guaranteed a clique or an independent set of size about \(\log n\), which is tiny. The Erdős–Hajnal conjecture says that forbidding a single fixed pattern changes that completely.

Ramsey numbers for other targets

Demanding a complete graph is greedy. Often the pattern you want is sparse, and sparse patterns should be cheaper to force. That intuition is correct and can be made exact.

Exact Ramsey numbers are rare, which makes the next result striking. It pins down the value exactly, for every tree at once.

Both halves of the proof are short. For the lower bound, exhibit a graph on \((s-1)(t-1)\) vertices that dodges both targets: take \(s-1\) separate copies of the complete graph \(K^{t-1}\). Each island has only \(t-1\) vertices, one too few for \(T\), and \(T\) is connected so it cannot straddle islands. The complement of that graph joins every pair of vertices on different islands and no pair on the same island, so it is the complete multipartite graph \(K^{s-1}_{t-1}\); any set of pairwise adjacent vertices there uses at most one vertex per island, so it has at most \(s-1\) vertices, one too few for \(K^s\). Figure 9.4 draws the smallest interesting case.

For the upper bound, suppose \(G\) has \((s-1)(t-1)+1\) vertices and \(\overline{G}\) contains no \(K^s\). Colour \(G\)'s vertices properly, in the sense of Chapter 5: adjacent vertices get different colours. Each colour class is a set of pairwise non-adjacent vertices of \(G\), which is a set of pairwise adjacent vertices of \(\overline{G}\), so it has at most \(s-1\) members. Fitting more than \((s-1)(t-1)\) vertices into classes of size at most \(s-1\) needs at least \(t\) classes, so the chromatic number satisfies \(\chi(G) \ge t\). Here \(\chi(G)\) is the chromatic number, the fewest colours a proper colouring can use. Chapter 5 then supplies a subgraph in which every vertex has at least \(t-1\) neighbours, and a graph with minimum degree at least \(t-1\) contains every tree on \(t\) vertices: grow the tree one vertex at a time, and at each step there are more available neighbours than tree vertices used so far.^[2]

Sparse targets are cheap: bounded degree buys linear Ramsey numbers

Trees against cliques is a special case. The general phenomenon is that thin target graphs have small Ramsey numbers, and the sharpest version of that statement replaces "thin" by a bound on the maximum degree \(\Delta(H)\), the largest number of neighbours any single vertex of \(H\) has.

Compare the two bounds to feel the drop. A complete graph on \(r\) vertices needs about \(4^r\) vertices to be forced. A graph on \(r\) vertices with maximum degree 5 needs only \(c \cdot r\), a straight line. The constant \(c\) depends on \(\Delta\) alone, and the proof makes it astronomically large, but it never depends on how big \(H\) is.

The proof is the first big pay-off of Szemerédi's regularity lemma from Chapter 7, and it is worth following at the level of shape even if the machinery is beyond this course.^[6] Take any graph \(G\) with \(c\,|H|\) vertices. The regularity lemma chops its vertices into a bounded number of equal chunks so that almost every pair of chunks behaves like a random bipartite graph. Build a small summary graph, one node per chunk, joined when the pair is one of the well-behaved ones. Since only a tiny fraction of pairs misbehaves, the summary graph is nearly complete, and Turán's theorem from Chapter 7 finds a complete graph inside it on \(m := R(\Delta+1)\) nodes.

Now paint the edges of that complete summary graph: violet if the pair of chunks is dense in \(G\), gold if it is sparse. A sparse pair in \(G\) is a dense pair in the complement \(\overline{G}\), so the two colours point at the two graphs we are allowed to build in. By the choice of \(m = R(\Delta+1)\), Ramsey's theorem hands us a one-coloured complete graph on \(\Delta+1\) chunk-nodes. Since \(H\) has maximum degree at most \(\Delta\), a greedy proper colouring uses at most \(\Delta+1\) colours, which means \(H\)'s vertices can be split into \(\Delta+1\) groups with no edges inside a group. Send each group into its own chunk. The blow-up lemma from Chapter 7 then says the regular, dense pairs really do contain all the edges you need, so \(H\) lands inside \(G\) if the colour was violet, and inside \(\overline{G}\) if it was gold. Every chunk is a fixed fraction of \(G\), which is why the whole bound stays linear.^[2]

The frontier: Ramsey-minimal graphs

A different question about the same phenomenon: rather than asking how big a forcing graph must be, ask what the smallest forcing graphs look like.

You might hope that for a simple target the frontier is a short list. It is not.

The proof is a two-step trick that repays study. Step one: by Erdős's theorem from Chapter 5 (proved probabilistically in Chapter 11), there are graphs \(G\) with chromatic number greater than \(r^2\) and girth greater than \(n\), where \(r = |T|\) and \(n\) is any size you like. Girth greater than \(n\) means every cycle is longer than \(n\). Paint \(G\)'s edges violet and gold. If both the violet subgraph and the gold subgraph could be properly coloured with \(r\) colours, then labelling each vertex by its pair of colours would properly colour all of \(G\) with \(r^2\) colours, which is impossible. So one colour class needs more than \(r\) colours, hence contains a subgraph of minimum degree at least \(r\), hence contains \(T\). So \(G\) forces \(T\).

Step two: shrink \(G\) down to a Ramsey-minimal subgraph \(G^*\). Could \(G^*\) be a forest, that is, cycle-free? No. A forest can always be painted so that no path of three edges is one-coloured: walk each tree from its root and alternate colours by level. Since \(T\) is a tree that is not a star, it contains a path of three edges, so a forest never forces \(T\). Therefore \(G^*\) contains a cycle, and every cycle of \(G\) has more than \(n\) vertices, so \(G^*\) has more than \(n\) vertices. Since \(n\) was arbitrary, Ramsey-minimal graphs for \(T\) come in unbounded sizes.^[2]

Induced copies change everything

Everything so far allowed sloppy copies. When we said \(G\) contains \(H\), we meant \(H\)'s vertices and edges are present; extra edges among those vertices were nobody's business. Section 9.3 of the book raises the bar and demands exact copies.

An induced copy of \(H\) inside \(G\) is a set of vertices such that the edges of \(G\) among them are exactly the edges of \(H\): every edge of \(H\) present, every non-edge of \(H\) absent. The non-edges are now part of the specification. That one change destroys the trivial strategy.

Three people found this independently within a couple of years, which usually means the statement was in the air and the difficulty was the construction. The proof runs in three moves: standardise bipartite graphs, solve the problem for bipartite graphs, then assemble the general case by stacking bipartite solutions.

Move one: every bipartite graph is a membership graph

For this section a bipartite graph is written as a triple \(P = (V_1, V_2, E)\), recording which side is which so that copies cannot flip the sides. An embedding \(\varphi \colon P \to P'\) is a no-collisions map of vertices that keeps first side inside first side, second inside second, and satisfies a strict rule: \(\varphi(v_1)\varphi(v_2)\) is an edge of \(P'\) exactly when \(v_1v_2\) is an edge of \(P\). The "exactly when" is what makes embeddings induced. Non-edges must go to non-edges.

Why can every bipartite graph be recorded this way? Given \(P\) with first side \(a_1, \dots, a_n\) and second side \(b_1, \dots, b_m\), take \(2n+m\) points. Send \(a_i\) to the point \(x_i\). Send \(b_j\) to the block consisting of exactly the points matching \(b_j\)'s neighbours, plus one private index point \(z_j\) so that two different \(b\)'s with identical neighbourhoods still get different blocks, plus enough unused padding points to reach the common block size \(k = n+1\). Membership then reproduces adjacency exactly, in both directions.^[3] The gain is that the whole problem is now stated in the language of sets and their subsets, which is precisely the language the general finite Ramsey theorem speaks.

Move two: bipartite graphs have bipartite Ramsey graphs

Here is the shape of the argument, with the arithmetic suppressed. Write \(P = (X, [X]^k, E)\) in point-block form. Build \(P' = (X', [X']^{k'}, E')\) with the larger block size \(k' = 2k-1\) and with \(|X'|\) chosen to be a suitable general Ramsey number. Now let an adversary paint \(P'\)'s edges violet and gold.

Each block of \(P'\) has \(2k-1\) edges running up to its member points. Sorting \(2k-1\) things into two colours leaves at least \(k\) of them in one colour, by pigeonhole. So every block \(Y'\) owns a distinguished \(k\)-element subset \(Z' \subseteq Y'\) whose edges all share a colour; call that the colour associated with \(Y'\). Record two facts about each block: which colour it is associated with, and where its distinguished subset sits inside it, read off a fixed ordering of \(X'\). That pair of facts is a colouring of the \(k'\)-subsets of \(X'\) using \(2\binom{k'}{k}\) colours, where \(\binom{k'}{k}\) ("k-prime choose k") counts the ways of choosing \(k\) positions out of \(k'\). Finitely many colours is all that matters. The general finite Ramsey theorem now supplies a large monochromatic set \(W\): inside \(W\), every block has its distinguished subset in the same position pattern and the same colour, say violet.

Finish by placing the points of \(X\) into \(W\) spaced out with exactly \(k-1\) unused elements between consecutive images. Each block \(Y\) of \(P\) is then sent to the block built from the images of \(Y\)'s points topped up with spare elements from the gaps, chosen so the image lands in the standard position pattern. The edges we care about are all violet, membership is preserved in both directions, and no two things collide.^[3]

Move three: the partite construction

The general case is assembled from bipartite pieces by an idea of Nešetřil and Rödl. Let \(n := R(|H|)\), so any violet/gold painting of \(K^n\)'s edges has a one-coloured complete graph on \(|H|\) vertices. Build a scaffold with \(n\) rows and one column for every possible way of choosing \(|H|\) of the \(n\) rows. In each column, place an exact copy of \(H\) on its chosen rows, and leave the remaining cells of that column as isolated dots.

The scaffold by itself forces nothing. The construction then walks through the row-pairs one at a time. For the current pair of rows, the bipartite graph between them is replaced by its bipartite Ramsey graph from move two, and the rest of the scaffold is duplicated once per embedding, so that any monochromatic copy found between those two rows still extends to a full copy of the previous scaffold. After all row-pairs have been processed, the final graph \(G\) has the property we wanted: under any painting of its edges, you can descend through the layers of the construction and find a copy of the original scaffold in which, for each pair of rows, every surviving edge between those two rows carries a single colour.

Finish by squashing each row to a single point. The row-pair colours become an edge colouring of \(K^n\), and by the choice of \(n = R(|H|)\) some \(|H|\) rows form a one-coloured complete graph. The column that placed its copy of \(H\) on exactly those rows now gives an induced, one-coloured copy of \(H\).^[3] One bonus falls out of the construction: the graph \(G\) it produces has the same clique number as \(H\), meaning \(\omega(G) = \omega(H)\), so it contains no larger complete graph than \(H\) already does.

Sparsity can be pushed much further, and doing so took fifty years.

Diestel does not give the proof, describing it as highly complex, and this course will not attempt one either. The statement alone is worth sitting with. It says that forcing an induced copy of \(H\) needs no dense local structure anywhere: the host can look, in any small window, as thin as \(H\) itself. All the forcing power lives in the global pattern of overlaps. For a sense of scale, merely building graphs with large girth and large chromatic number, a far weaker demand, already required the probabilistic method back in Chapter 5.

One boundary case explains why the forest clause reads the way it does. If \(H\) is a tree that is not a star, no forest can be a Ramsey graph for it, by the alternating-colour argument used earlier for Ramsey-minimal graphs. So "infinite girth" is out of reach, and "arbitrarily large girth" is the best available statement.

What connectivity forces

The last section of the chapter changes the question again. Suppose the large graph is not arbitrary but connected, or 2-connected, or more. What must it contain? The answers are short lists of very plain shapes, and the depth is entirely in the proof that the lists are complete.

Two reminders about the notation. The star \(K_{1,r}\) is one hub joined to \(r\) leaves that are pairwise non-adjacent, and \(P^r\) is the path with \(r\) edges, so \(r+1\) vertices; Diestel counts a path's length in edges, which is why Figure 9.9 shows \(P^6\) with seven dots.

The proof splits into a dense case and a sparse case, and this split is the template for the whole section. Set \(d+1 := R(r)\). Case one: some vertex \(v\) has more than \(d\) neighbours. Apply Ramsey's theorem inside the neighbourhood \(N(v)\), the set of vertices joined to \(v\). Either \(r\) of those neighbours are pairwise adjacent, giving \(K^r\), or \(r\) of them are pairwise non-adjacent, and those \(r\) together with \(v\) form an induced star \(K_{1,r}\). Case two: every vertex has at most \(d\) neighbours. A graph with bounded degree in which every vertex is within distance \(r\) of some fixed centre can only hold boundedly many vertices, because each step outward multiplies the count by at most \(d-1\). So a huge graph of bounded degree must have two vertices further apart than \(r\), and a shortest path between two such vertices is automatically induced, since any shortcut would make it shorter.^[4]

Raising the connectivity changes the list, and it also weakens the currency. From here on the guaranteed structures are minors and topological minors rather than induced subgraphs. Recall from Chapter 1 that a topological minor is obtained by replacing some edges by longer paths, and a minor by contracting connected chunks to single vertices. Both are weaker demands than an induced subgraph, and paying that price is what keeps the lists short.

The proof reuses the dense-versus-sparse split. If the graph has large radius, take two far-apart vertices; 2-connectedness plus Menger's theorem from Chapter 3 gives two paths between them that share only their endpoints, and together those two paths close into a long cycle. Otherwise some vertex \(v\) has huge degree. Delete \(v\), which leaves the graph connected, and take a smallest tree that still reaches all of \(v\)'s former neighbours; minimality forces every leaf of that tree to be one of those neighbours. Apply the connected-graph result to the tree. A tree contains no large clique, so it must have a vertex of large degree or a long path. A long path between two leaves closes through \(v\) into a long cycle. A high-degree vertex \(u\) of the tree sends \(r\) disjoint branches to leaves, each of which hops to \(v\), giving \(r\) internally disjoint \(u\)-\(v\) paths: a subdivided \(K_{2,r}\).^[4]

At connectivity 3 and 4 the results are stated without proof in the book, and the shapes get more interesting.

A crown is the skeleton of a triangulated cylindrical band: two cycles of equal length, one inside the other, stitched together by a zigzag of edges so that the ring between them is tiled by triangles. A Möbius crown is the same band glued with a half-twist. All four shapes on the 4-connected list are themselves 4-connected, which is what you would want from an unavoidable structure: the list members belong to the class they describe.

Why these lists are the right lists

Four theorems, four lists. Are the lists arbitrary? The chapter answers no, and to say so precisely it needs a way of comparing whole families of graphs.

The name is borrowed from Kuratowski's planarity theorem, where two graphs form the complete list of obstructions to drawing a graph without crossings. Incomparability is what forces the catalogue to be short; the covering condition is what forces it to be complete. Together they pin the catalogue down: any two Kuratowski sets for the same class and relation match entry for entry up to equivalence.

Notice that complete graphs vanish from the first row even though they appeared in the theorem about connected graphs. The reason is the change of relation. Under plain subgraph containment, \(K^{r+1}\) contains both \(K_{1,r}\) and \(P^r\), so a family with unboundedly large complete graphs already sits above both catalogue entries, and adding a third entry for complete graphs would violate the requirement that entries be pairwise incomparable. Under induced-subgraph containment the absorption fails, which is exactly why the earlier theorem needed all three shapes.

What to carry forward

Three ideas from this chapter reappear elsewhere in the book. First, the either/or shape: no single pattern is forced by size, but one of two opposite patterns always is, and that is enough to build a theory on. Second, the compactness move: an infinite theorem plus König's lemma yields the finite theorem in full generality, a pattern that recurs whenever finite statements resist direct attack. Third, the split between finding a copy and finding an exact copy. Sloppy copies are forced by mere size. Exact copies are forced only by a host built for the purpose, and that construction, stacking bipartite Ramsey graphs row-pair by row-pair, is the technique that modern structural Ramsey theory runs on.

The infinite Ramsey theorem returns in Chapter 12, where it helps prove that certain orderings have no infinite bad sequences, the first step on the road to the graph minor theorem. The probabilistic lower bound for \(R(r)\) promised here is proved in Chapter 11. And the Kuratowski-set viewpoint, a canonical finite list of unavoidable or forbidden shapes, is the exact viewpoint that the graph minors project turns into a general theory.