What makes extremal problems in graph theory interesting?

Question

I have recently started reading through lecture notes on graph theory, and it seems to me that after some introductory material the focus will often become extremal graph theory. Moreover, there are entire lectures and books devoted to the topic.

Now to me as a newbie in the field, questions like "How many edges can I put into this graph until I can't avoid having X as a subgraph?" do sound interesting, but also feel weirdly specific. However, since it is such a large field, I was wondering whether there is some deeper meaning to such questions or some connections to other fields that would motivate so much attention devoted to them.

Any insight would be appreciated, though if the answer is just "Continue studying and you'll eventually see", I'd be fine with that too.

Answer 1

Questions in extremal graph theory naturally appear when we think about two different graph properties, and ask how they're related.

Suppose we start by comparing the number of edges in an $n$-vertex graph to the number of copies of a subgraph X. (This is not entirely an arbitrary choice, but more on that later.) This is going to be some region in the (edges, copies of X) plane.

Okay, so technically it's just a bunch of discrete points, because it's a finite problem. But if you take different values of $n$, you get different bunches of points which roughly form the same kind of shape at different scales. We eventually realize that (for most X) we need to scale the number of edges down by $\binom n2$, and the number of copies of X down by $\binom nx$ where $x$ is the number of vertices in X, for the shapes to be the same size for different values of $n$. At that point, for each $n$, we get a discrete approximation of some continuous region, and we can ask: what is this region?

At this point, we are already mostly doing extremal graph theory. We are definitely doing extremal graph theory when we ask the natural next question: what are the boundaries of this region? Because at this point, we are minimizing or maximizing the number of copies of X, or the number of edges, as $n \to \infty$. In particular:

• The top of the region will probably be bounded by the same curve everywhere, and this will be the answer to a boring question: what's the most copies of X we can have in an $n$-vertex, $m$-edge graph? The answer is (for all X, I think) $O(m^{x/2})$ by trying to make larger and larger complete graphs with the edges you have.
• The bottom of the region will stay flat for a while (no copies of X) then switch to some very complicated behavior. We have all sorts of questions, but maybe the simplest one to ask is: when does it switch from zero to complicated?

In other words, at which number of edges are we forced to have a copy of X?

---

In principle, we could pick any two properties of graphs, and ask how they're related. Some other questions in extremal graph theory do just this: comparing the number of $K_3$'s and the number of $K_4$'s in graphs, or whatever. There are several considerations, though:

• We wouldn't want to pick two random properties, because then they're probably not very related.
• Even if two complicated properties are related, they are probably connected through a third, simpler property. That's why comparing things to the number of edges is fruitful: the number of edges is often the big underlying factor anyway.
• Also, if you compare complicated things, you might not be able to get anywhere, because the question is too hard.