Mathematics of the Worst-Case Scenario

Optimization is an obvious and major theme of applied mathematics. What may be less obvious to the public is the extent to which mathematics relies on a dual process, which one might call 'pessimization'.

Suppose we want to partially relate two functions, f and g, with a statement of the form

"f(x) >= M implies g(x) >= N". So, f and g are positively correlated, and we want to quantify this relationship.

How do we get the strongest possible relationship? Fixing M, we choose x to minimize g(x) subject to the constraint f(x) >= M. This value of g(x) is the tightest lower-bound N we can get, and the most informative statement.

Why is this 'pessimization'? We look for statements of the above form when we are interested in ensuring that g(x) is high (g is some measure of 'goodness', and f is some simpler measure that we can more easily estimate and which is heuristically related to g); but, to achieve this we have to spend much of the time thinking perversely about how low g could wriggle subject to the constraint that f is high.

This kind of thinking is ubiquitous. The subject is too general (really only a 'theme') to have truly distinctive methods or theoretical constructs (in particular, there is no fundamental difference between optimization and pessimization--the latter is just optimization from the devil's perspective), but where it treats discrete, finite objects and collections it is sometimes called 'extremal combinatorics'; I recommend Jukna's book by that name.

Sometimes the heuristic relationship between our two functions has a clear logical grounding. For instance, let f(G) measure the number of edges in a graph, and let h(G) measure the number of triangles; adding an edge to a graph can never decrease the number of triangles. However, f(G) > f(G') does not imply that h(G) >= h(G'); G' may be more 'pessimally' organized than G with respect to triangles. Turan's Theorem, giving exact conditions on f to guarantee that h > 0, is considered the founding result of extremal combinatorics. Can you prove such a theorem? What do triangle-pessimal graphs on m vertices look like?

The preceding example is really a special case. Having a triangle and having at least a certain number of edges are both 'monotone properties' in the sense that they are monotone functions of the 0/1 adjacency matrix of a graph. A simple result of Kleitman, provable by induction, says that if A and B are two such properties and we uniformly generate a graph on n labeled vertices, Prob[A & B hold] >= Prob[A holds]*Prob[B holds].

So, e.g., being informed that our graph has diameter at least 10 cannot make it less likely to be planar, as should be intuitive ("diam >= 10" and planarity are antimonotone properties, so we apply the result to their negations and then rephrase).

A pleasant feature of investigations in extremal combinatorics is that they can be jump-started with simple questions; the exotic structure emerges naturally in exploring pessimal objects. Or, sometimes, the pessimal structures end up being very simple and familiar, but meeting them in the context of the investigation sheds new light on them. For example, we may heuristically observe that collections of 'many' distinct numbers contain 'many' distinct pairwise differences; even though the pessimal structure that pops out when we pursue this relationship is nothing more than n points in arithmetic progression, it's still a nice problem (which becomes more interesting when raised to 2 or more dimensions).

Some quite simple results of extremal combinatorics have important uses in elementary probability and in complexity theory. For example, take a square 0/1 matrix with 'many' ones; we'd like to conclude that it has many rows with many ones each; if we're willing to settle for either many 1-heavy rows or many 1-heavy columns, we can do much better (since pessimal examples against the 'many-rows' conclusion promote the 'many-columns' conclusion) when we quantify our various 'manys'. If we'd also settle for even a single 1-heavy row or column, we can do still better.

Such results have some immediate interpretations in terms of conditional probabilities. They also fuel a kind of robust reduction from any function f(x) on n bits to the function g(x, y) = (f(x), f(y)) (with the two matrix dimensions in our analysis corresponding to the two inputs to g). This is at the heart of a certain approach to hardness amplification, including a proof of Yao's XOR Lemma, given in this paper (see also my earlier post on the XOR Lemma). In fact, Jukna's book is rife with complexity apps, and was written with computer scientists in mind.

As I've said, no 'deep' unifying theory of extremal combinatorics exists, and I feel more inclined to share problems than to exposit. But this time, instead of belaboring my idiosyncratic preferences, let me point you to a great site with more problems than you'll ever solve: Kalva, a clearing-house of old Olympiads with many solutions. Many sterling combinatorics puzzles lie amidst the usual geometry and number theory. Olympiads are hard, but with this many problems to peruse you WILL find ones you can solve--and that feels good.