The Space of Robustness
Posted by David Corfield
At Tim Gowers’ blog, there has been a discussion in the ‘somewhat philosophical’ category of How can one equivalent statement be stronger than another?. Gowers gives the example of Hall’s theorem or Hall’s marriage theorem.
In graph theoretic guise,
Let be a bipartite graph with finite vertex sets and of the same size. A perfect matching in is a bijection such that and are neighbours for every .
So if members of are women and members of are men, then in this heterosexual universe where women are only prepared to marry men, and vice versa, willingness to marry is represented by an edge between such pairs. A perfect matching sees everyone happily married to a partner. So when does this happy event occur?
Given a subset , the neighbourhood of is the set of vertices in that are joined to at least one vertex in . A trivial necessary condition for the existence of a perfect matching is that for every subset the neighbourhood is at least as big as , since it must contain , which has the same size as . This condition is called Hall’s condition.
So, if our people can be happily married off, then for any subset of the women, the totality of men at least one of these women is happy to marry is at least as numerous. This is trivially the case, since this totality includes the men they do actually marry.
Much less obviously, Hall’s theorem states that the condition is also sufficient. So long as for every subset of women the subset of men loved by at least one of them is no less numerous, then everyone can be married off happily.
Gower’s observation is that while the existence of a perfect matching and the satisfaction of Hall’s condition are equivalent, the former seems to be stronger as the implication to the latter is very straightforward, while the reverse implication is quite tricky.
In the comments, Terry Tao observes,
Another reason why the “difficult” implication in Hall’s theorem is non-trivial is that it is non-functorial: there is no canonical way to obtain the perfect matching from a bipartite graph obeying Hall’s condition which respects isomorphisms (i.e. relabeling of the graph). Instead, one must make many arbitrary choices. Thus, it largely falls outside the range of “abstract nonsense”. (The fact that the theorem fails in the infinite case is perhaps a symptom of this non-functoriality; the inability to generalise the result to a more abstract setting indicates that the implication must depend sensitively on all of its hypotheses, and so cannot be replaced by overly “soft” techniques that are insensitive to one or more of these hypotheses.)
[Perhaps one could sum up the two cultures of mathematics succinctly as “mathematics which generalises” and “mathematics which does not generalise”? :-)]
As readers will know, I’m very interested in this ‘two cultures’ idea (I and II). From Gowers’ writings about his side of the divide, Tao’s characterisation could be extended to read “mathematics which does not generalise, but which suggestively helps in a number of different areas”.
This idea crops up in another part of the discussion where Gowers wonders why we don’t say that Fermat’s Last Theorem implies and is implied by the four-colour theorem (in ZFC). On this issue, Tao observes
…most “useful” implications in mathematics tend to have at least some robustness with respect to at least some kinds of perturbations.
So, new developments in the area of one statement ought to have an effect on the area of the other statement. All good mathematics must have some degree of this robustness.
It could be said that we at the Café enjoy robustness under the greatest degree of perturbation. But how to think of the space of robustness? Does the functorial/non-functorial mark a sharp split? Is there more to be said about the functorially robust? How much texture is there to the non-functorially robust? And what stops the non-functorially robust descending into the sludge of brute mathematical fact?
A small side thought: remember our attempts to categorify the Cauchy-Schwarz inequality had us looking at , for , to compare its dimension to . Should we be interested in the fact that it reappears (as ) in David Ben-Zvi’s post?:
One of the great advances in representation theory (due in large part to some of the names listed at the top) was the realization that many of the algebras of greatest interest can be realized as convolution algebras of the form , where , are topological spaces or groupoids (in fact algebraic varieties or stacks) and is a function theory, such as cohomology and K-theory.
But then perhaps the observation that
…the algebra of block diagonal matrices is Morita equivalent to the commutative algebra
suggests we shouldn’t care about dimensions too much.
Tao on “fruitfulness”; Re: The Space of Robustness
There was a somewhat related thread, on “fruitfulness” in Mathematics.
Tao, Fruitful or Truthful; Re: Two Cultures in the Philosophy of Mathematics?
“Fruitfulness is key. If a neologicist doesn’t care about the fruitfulness of their abstraction principles then they’ve rejected an enormously important part of Fregean thinking.”
An extremely interesting statement!
Did not Terry Tao list this as one of the (nonexlusive) markers of “good mathematics”?
[truncated]